Skip to content →

ゼータ・メビウス変換

各点積・各点和のゼータ・メビウス変換

\(k\) 変数多項式 \(P\) の写像を各点積・各点和で定義する。
\(x\) の down-set の各点積を逆元を掛けて戻すと、
\begin{align}(P(f_1\zeta, \ldots, f_k\zeta))(x)
&= \sum_{\bigvee x_i\leq x} P(f_1(x_1), \ldots,f_k(x_k)) \\
(P( f_1\zeta, \ldots, f_k\zeta)\zeta^{-1})(x)
&= \sum_{\bigvee x_i = x} P(f_1(x_1), \ldots,f_k(x_k)) \\
\end{align}となる。同様に \(x\) のup-set の各点積を逆元を掛けて戻すと
\begin{align}
(P(\zeta f_1 , \ldots,\zeta f_k ))(x)
&= \sum_{\bigwedge x_i\geq x} P(f_1(x_1), \ldots,f_k(x_k)) \\
(\zeta^{-1}P( \zeta f_1, \ldots,\zeta f_k))(x)
&= \sum_{\bigwedge x_i = x} P(f_1(x_1), \ldots,f_k(x_k)) \\
\end{align}となる。

メビウス代数

基底を束 \(L\) の元、掛け算を交わり \(x \cdot y = x \land y\) によって体 \(K\)上の双線形形式 \(A\) を定める。
\(\delta_{i}’\stackrel{\text{def}}{=}\zeta^{-1} \delta_{x, i}\) とする。 \(\zeta\delta_{i}’ = \delta_{x, i}\) より \(\delta_{i}’\) は \(A\) を張る。積は

\begin{align}
\delta_{i}’ \cdot \delta_{j}’
&= \zeta^{-1}(\zeta \delta_{i}’ \odot \zeta \delta_{j}’) \\
&= \zeta^{-1}(\delta_{x, i} \odot \delta_{x, j}) \\
&= \zeta^{-1} \delta_{x, i}\delta_{x, j} \\
&= \begin{cases}
\delta_i’ & ( i = j ) \\
0 & ( i \neq j )
\end{cases}
\end{align}
となる。従って、\(A\) は \(\delta_i’\) を基底として、\(\bigoplus_{t \in L} K_t\) 同型
(\(K_t \cong K\)) である。

Weisnerの定理

\(a \neq \hat 1\) とする。
\begin{align}
&\sum_{i: i \land a = x} \mu(i, \hat 1) \\
=&\delta_a \cdot \zeta^{-1} \delta_{\hat 1} \\
=&\zeta^{-1} (\zeta \delta_a \cdot \zeta \zeta^{-1} \delta_{\hat 1}) \\
=&\zeta^{-1} (\zeta \delta_a \cdot \delta_{\hat 1}) \\
=&\hat 0
\end{align}特に \(x = \hat 0\) とした場合をよく用いる。順序イデアル \(J(P)\) の場合、\(\{i : i \land a = \emptyset\}\) からなる部分posetを考えれば成立は明らか。\(\Pi_n\)の場合、\(a = \{\{1, 2, \ldots, n-1\}, \{n\}\}\) とすると、\(i \land a=\emptyset\) となる \(i\) は \(\hat 0\) か \(\{i, n\}\) の形のブロックを持つ原子しかない。そのような原子は \(n-1\) 個あるので \(\mu_{n}+(n-1)\mu_{n-1}=0\)。従って \(\mu_n = (-1)^{n-1}(n-1)!\) となる。\(B_n(q)\) の場合、\(a\) をある \(n-1\)次元部分空間とすると、\(i \land a=\emptyset\) となる \(i\) は \(\hat 0\) か \(a\) と交わらない \(1\) 次元部分空間である。そのような部分空間は \(q^{n-1}\) 通りあるので、\(\mu_n + q^{n-1}\mu_{n-1} = 0\)。従って、\(\mu_n = (-1)^n q^{\binom{n}{2}}\)。もし、\(\hat 0\)が補原子たちの交わりでないならば、\(\mu(\hat 0, \hat 1) = 0\) である。

cross-cut定理

束\(L\)の元の集合\(X\)が

  • \(\hat 1 \not \in X\)
  • \( s \neq \hat 1 \Rightarrow \exists t, s \leq t \in X
    \)

を満たすとする。\(N_k\) を \(X\) の \(k\) 元集合のうち結びが \(\hat 0\) となるようなものの個数とする。\(\mu(\hat 0, \hat 1) = \sum_k N_k (-1)^k\) が成り立つ。

\begin{align}
&\sum_k N_k (-1)^k \\
= & \left(\prod_t (\delta_{\hat 1} – \delta_t) \right)(\hat 0) \\
= & \left(\zeta^{-1} \prod_t(\zeta\delta_{\hat 1} – \zeta\delta_t) \right)(\hat 0) \\
= & \mu(\hat 0, \hat 1)
\end{align}

Twisted and/or convolution

\(f, g : P \to K\) に対して、各点積を \(f \odot g\)、内積を \(fg\) と書く。

  • \(f(g \odot h)=(g \odot f)h = \sum_x (f \odot g \odot h)(x)\)
  • \(\xi \in I(P, K)\) に対して \((f \xi) g = f (\xi g)\)

の二つが成り立つ。従って、\(f\zeta^{-1}(\zeta g \odot \zeta h) = (\zeta g \odot f\zeta^{-1})\zeta h\) となる。特に、\(h(x)=\delta_{k,x}\) とすると、\(\sum g(i) f(i \land k)\) が得られるので、\((\zeta g \odot f\zeta^{-1})\zeta\) は各 \(k\) に対するこのような変換を表している(yuki1503)。

各点積・各点和のメビウス変換前後の関係式

upset の各点和・各点積は変形すると\begin{align}
&\sum_{y \leq x} \sum_{\bigvee x_i \leq y} P(f_1(x_1), \ldots,f_k(x_k))\\
=& P( f_1\zeta, \ldots,f_k\zeta)\zeta(x)\\
=& P( f_1\zeta, \ldots,f_k\zeta)\zeta^{-1}\zeta^2(x)\\
=& \sum_{y \in L} \#[y, x] \sum_{\bigvee x_i = y} P(f_1(x_1), \ldots,f_k(x_k))
\end{align}となる。

\(\sigma_0(n)\) を \(n\) の約数の個数とする。\(\sum_{a=1}^M \sum_{x\in \mathbb{N}^m \\ a=\mathrm{lcm}(x)} \lfloor M/a \rfloor = \sum_{d=1}^M \sigma_0^m(d)\) を示せ。(yukicoder1781)

\begin{align}
&\sum_{a=1}^M \sum_{x\in \mathbb{N}^m,\\ a=\bigvee x_i} \lfloor M/a \rfloor \\
=&\sum_{a=1}^M \sum_{x\in \mathbb{N}^m ,\\ a=\bigvee x_i} \zeta(\zeta-1)(a, \hat 1) \\
=&\sum_{a=1}^M \sum_{x\in \mathbb{N}^m ,\\ a=\bigvee x_i} \left(\prod_i \zeta(\hat 0, x_i)\right)\zeta(\zeta-1)(a, \hat 1) \\
=& (\zeta^2 \odot \zeta^2 \odot \cdots \odot \zeta^2)\zeta^{-1}\zeta(\zeta-1)(\hat 0, \hat 1) \\
=&(\zeta^2 \odot \zeta^2 \odot \cdots \odot \zeta^2)(\zeta-1)(\hat 0, \hat 1) \\
=&\sum_{d=1}^M \sigma_0^m(d) \\
\end{align}

ランク付きゼータ・メビウス変換

モジュラー束では、$$ \sum \rho(x_i) = \rho\left(\bigvee x_i \right) \Leftrightarrow x_i \land x_j = \hat 0$$である。従って、不定元 \(t\) を用いて、$$\hat f(x)=f(x)t^{\rho(x)}$$ とすると、$$(\zeta^{-1}P(\zeta \hat f))(x)$$ の係数には、\(x_i \land x_j = \hat 0\) を満たす交わり \(\bigvee x_i= x\) が分離されている。例えば \(B_n\) では、\(x\) の分割に対応する。

特定のランク全体のゼータ・メビウス変換

あるランクの要素全体についてのゼータ・メビウス変換は次の様に変形すると、高速に計算できる場合がある。
\begin{align}
\sum_{\rho(x) = k} f(x)\zeta^{-1} &= \sum_{\rho(x) = k} \sum_{y \leq x} f(y)\mu(y, x) \\
&= \sum_{y} f(y) \sum_{y \leq x, \rho(x) = k} \mu(y, x)
\end{align}例えば、\(B_n\) では \(\sum_{y \leq x, \rho(x) = k} \mu(y, x) = {n-\#y \choose k-\#y}(-1)^{k-\#y}\) である。別の導出方法として次のようなものもある。\(g(S) = \sum_{S \subseteq T} f(T)\) とすると
$$\sum_S f(S)x^{\#S} = \sum_S g(S)(x-1)^{\#S}$$
が成り立つ。左辺は各元を \([x]\) でラベル付けする方法、右辺は \(S\) を \([x-1]\) でラベル付けしてから、いくつかの元を \(x\) でラベル付けする方法の数を数えている。また、\(h(S) = \sum_{T \subseteq S} f(T)\) とすると、同様の理由により、
$$\sum_S f(S)x^{n-\#S} = \sum_S g(S)(x-1)^{n-\#S}$$ である。

ブール束

高速ゼータ・メビウス変換

\(B_n \cong J(n\boldsymbol1) \cong J(\boldsymbol1)^n \cong \boldsymbol{2}^n\)より\(\mu_{B_n} = \mu_{\boldsymbol{2}} \otimes \mu_{\boldsymbol{2}}\otimes \cdots \otimes \mu_{\boldsymbol{2}}\)となる。\(\delta \times \cdots\times \delta \times \mu_{\boldsymbol{2}} \times \delta \times \cdots \delta\) の形の行列積に直して、順番に掛けると、高速メビウス変換になる。

1乗和・2乗和

1乗和・2乗和は和の順序を入れ替えることで次のように計算できる(AGC60D)。
\begin{align}\sum_Sf(S) &= \sum_S \sum_{T \subseteq S} g(T)(-1)^{\#S-\#T} \\
&= \sum_{T}2^{n-\#T}g(T)(-1)^{\#S-\#T} \\
\sum_Sf(S)^2 &= \sum_S \left(\sum_{T \subseteq S} g(T)(-1)^{\#S-\#T}\right)^2 \\
&= \sum_S \sum_{T_1 \cup T_2 \subseteq S} g(T_1)(-1)^{\#T_1} g(T_2)(-1)^{\#T_2} \\
&= \sum_{T_1, T_2 } 2^{n-\#(T_1 \cup T_2)}g(T_1)(-1)^{\#T_1} g(T_2)(-1)^{\#T_2}\\
&=\sum_{T_1, T_2 } 2^{n-\#T_1-\#T_2+\#(T_1\cap T_2)}g(T_1)(-1)^{\#T_1} g(T_2)(-1)^{\#T_2} \\
&= 2^n \sum_{S}\left(\sum_{S \subseteq T}g(T)(-1)^{\#T}2^{-\#T}\right)^2 \end{align}

区間の分割:長さの乗法的関数

\(S = \{x_1, x_2, \ldots, x_k\}_{<} \subset [n-1] \)に対して、ある関数 \(h\) を用いて \(g\) が$$g(S) = \prod_{i = 1}^{k+1} h(x_{i}-x_{i-1})$$と書けるとする。ただし、\(x_0 = 0, x_{k+1} = n\) とする。このような関数を区間長に関して乗法的と呼ぶことにする。降下集合が \([n – 1] \setminus S\) に含まれるような長さ \(n\) の順列の個数は区間長に関して乗法的関数になる。\(H(x) = \sum_{i \geq 1} h(i)x^i\) と置くと、このような関数は$$\sum_{n = 0}^\infty x^{n}\sum_{\emptyset \neq S \subseteq [n]} g(S)(-1)^{\#S} = \frac{-H}{1+H}$$が成り立つ。二乗和 \(\sum f(S)^2\) の計算に役立つ。\(n\) を固定して、\(\#S\) について、集計したいときは、次の式で高速化できる。\begin{align}
[x^n] \frac{1}{1-txf(x)} &= \frac{1}{n}\frac{1}{2\pi i} \oint \frac{1}{x^n}\frac{d}{dx}\frac{1}{1-txf(x)} dx\\
&= \frac{1}{n} \frac{1}{2\pi i}\oint \frac{1}{x^n}\frac{t}{(1-txf(x))^2} \frac{d(xf(x))}{dx}dx\\
&= \frac{1}{n}\frac{1}{2\pi i} \oint \frac{f(x)^n}{{z}^n}\frac{t}{(1-tz)^2} dz\\
&= \frac{1}{n}[z^{n-1}] f(g(z))^n\frac{t}{(1-tz)^2} \\
\end{align}ただし、\(z = xf(x)\) を \(x\) について解いて \(z\) の式 \(x = g(z)\) と置いた。これにより、\((xf)^1, (xf)^2, (xf)^3, \ldots\) の \(x^n\) の係数が求まる。

円環の分割:長さの乗法的関数

\(S = \{x_0, x_1, \ldots, x_k\}_{<}\)に対して、ある関数 \(h\) を用いて \(g\) が$$g(S) = \prod_{i = 0}^{k} h(|x_{i+1}-x_{i}|)$$と書けるとする。ただし、\(x_{k+1} = x_{0}\) とする。このとき、
$$\sum_{n = 0}^\infty x^{n}\sum_{S \subseteq \mathbb{Z}/n\mathbb{Z}} g(S)(-1)^{\#S} = \frac{-x\frac{d}{dx}H}{1+H}$$が成り立つ。

円環の部分集合

\(S \subset \mathbb{Z}/n\mathbb{Z}, S \neq \mathbb{Z}/n\mathbb{Z}\) を極大な連続整数列の和 \(S = x_1 \cup x_2 \cup \cdots \cup x_k\) として表した時、\(g(S) = \prod_i h(\#x_i)\) であるとする。
\(H(x) = \sum_{i\geq 1} h(i)x^i\) として、\(\sum_{n \geq 1}x^n\sum_{\emptyset \neq S \subset \mathbb{Z}/n\mathbb{Z}, S \neq \mathbb{Z}/n\mathbb{Z}} (-1)^{\#S}g(S) = \frac{x+x\frac{d}{dx}\left(xH(-x)\right) }{1-(x+xH(-x))}\) となる。

根付き木の分割

根付き木 \(T\) に対する関数 \(g\) が次の条件を満たすとする。

  • 根付き木 \(T_1, T_2\) と \(f(T_1), f(T_2)\) が与えられたとする。\(T_1\) の根に子として\(T_2\) を加えた木を \(T_3\) とする。\(f(T_3)\) が \(O(\#V(T_1)\#V(T_2))\) で求まる。
  • 根付き木 \(T_1, T_2, \ldots, T_k\) からなるグラフ \(G\) について、\(f(G)=f(T_1)f(T_2)\cdots f(T_k)\) である。

\(S \subseteq E(G)\) に対して、\(G-T\) を根付き木 \(G\) から \(S\) に属する辺を削除してできる根付き森とする。\(\sum_{S \subseteq E(G)} f(G-S)(-1)^{\#S}\) は二乗の木DPにより \(O((\#V(G))^2)\) で求まる。例えば、木の交代順列の数え上げに表れる(ARC130D)。

長さk以上の区間の直積からなる束

\(s_i := \{i, i + 1, \ldots, i+k-1\}\) \((1 \leq i \leq n – k + 1)\) を原子とする \(B_n\) の部分束を \(L\) とする。\(L\) のメビウス関数を求めたい。\([n] \setminus \{i\}\) \((2 \leq i \leq k \ \lor \ n-k+2 \leq i \leq n – 1)\) を \(L\) に加えてもそれらは既約なので、\(\mu(\hat 0, \hat 1)\) は不変である。従って、任意の補原子はある \(i\) \((2 \leq i \leq n – 1)\) を用いて \([n] \setminus \{i\}\) と書けるとしてもよい。補原子全体を \(X\) と置く。cross-cut 定理より、 \(N_m\) を \(X\) の \(m\) 元集合であって交わりが \(\hat 0\) であるものの個数とすると \(\mu(\hat 0, \hat 1) = \sum_m N_m(-1)^m\) である。交わりが \(\hat 0\) となるための必要十分条件は、\(m\) 元集合として選ばれなかった補原子の添え字を昇順に並べたときに、連続する整数の長さが \(k\) 未満であることである。このような選び方は \([x^{n-m}]\left(1+x+\cdots+x^{k-1}\right)^{m+1}\) 通りある。以下、機械的に計算すると、
\begin{align}
\mu(\hat 0, \hat 1)=&\sum_m N_m (-1)^m \\
={}& \sum_m \sum_m [x^{n-m}]\left(1+x+\cdots+x^{k-1}\right)^{m+1}(-1)^m \\
={}& [x^{n}]\frac{1+x+\cdots+x^{k-1}}{1+x(1+x+\cdots+x^{k-1})} \\
={}& [x^{n}]\frac{1 – x^{k}}{1 – x^{k+1}} \\
={}& [x^{n}](1 – x^{k})\sum_{i \geq 0} x^{i(k+1)} \\
={}& \begin{cases}
1 & ( n = 0 \pmod {(k + 1)}) \\
-1 & (n = k \pmod {(k + 1)} ) \\
0 & (\text{otherwise})
\end{cases}
\end{align}
を得る。

長さ \(k\) \((\geq 2)\) 以上の任意の連続部分列が条件 \(P\) を満たさない場合を数えたい。条件 \(P\) を無視したときの長さ \(n\) の列の個数が \(a_1^n\)、\(P\) を満たす長さ \(i\) の列の個数が \(b_i\) だとする。メビウス変換により、求める場合の数のOGFは $$\frac{1}{1-\left(a_1x-\sum_{i \geq 1} b_{ki}x^{ki}+\sum_{i \geq 1} b_{ki+1}x^{ki+1}\right)}$$ となる。AGC058Dは \(k=3\) で3変数の場合。yuki1962は \(a_1 = \sum_j c_j, b_{i}=\sum_j c_j^i\) で $$\frac{1}{1-\sum_i \frac{\sum_{j = 1}^{k – 1} (c_ix)^j}{1+\sum_{j = 1}^{k – 1} (c_ix)^j}}$$とした場合。\(f_i = \frac{\sum_{j = 1}^{k – 1} (c_ix)^j}{1+\sum_{j = 1}^{k – 1} (c_ix)^j}\) と置くと $$\sum_{j=1}^{k-1} (c_ix)^j = \frac{f_i}{1-f_i}$$
となり、1個以上並べることで長さ \(k-1\) 以下の列を生成する形式的なオブジェクトのOGFが \(f_i\) になっている(かならいさんの解説)。

一方の条件がもう一方の条件の否定

各 \(i \in [n]\) について

  • \(p_i \geq a_i\)
  • \(p_i \leq b_i\)

のどちらかの条件が与えられたとき、これを満たす \(p \in \mathfrak{S}_n\) の個数を求めよ。

各 \(i \in [n-1]\) について

  • \( p_i < p_{i+1} \)
  • \( p_i > p_{i+1} \)

のどちらかの条件が与えられたとき、これを満たす \(p \in \mathfrak{S}_n\) の個数を求めよ。

k値への拡張

\begin{align}
& g(S_1, \ldots, S_k) = \sum_{S_i \subseteq T_i \\ T_i \cap T_j = \emptyset} f(T_1, T_2, \ldots, T_k) \\
\Leftrightarrow &f(S_1, \ldots, S_k) = \sum_{S_i \subseteq T_i \\ T_i \cap T_j = \emptyset} g(T_1, T_2, \ldots, T_k) \prod (-1)^{\#T_i – \#S_i}
\end{align}

整除束のメビウス変換

\(\prod_{i=1}^M D_{N}\) 上のスパースな関数(非零が \(K\) 個)に対する downset の和を取りたいとする。\(i\) の約数が \(O(i^\epsilon)\) 個しかないので、約数を列挙しておくことで \(O(N^\varepsilon K)\) で計算できる。メビウス変換も同様(ABC230G)。

\(n=\prod p_i^{e_i}\) と因数分解できるとすると、整除関係の束は各素因数の冪の束の直積に分けられて

\begin{align}
&\mu_{D_n} \\
={}& \prod \mu_{D_{p_e^{e_i}}} \\
={}& \prod \mu_{\pmb{e_i+1}}
\end{align}

とできる。各素数のメビウス変換を独立にすることで、\(O(n \log n \log n)\) で \(f\mu\) が列挙できる。

各 \(x\) の downset \(I_x\) が事前に列挙でき、更に事前にトポロジカルソートができるような場合には、大きい元から計算することで、\(\sum |I_x|\) で \(f \mu \) が列挙できる。例えば、\(D_n\) では \(O(n \log n)\) になる。

円環の個数の数え上げ

\(f(a, b) = F(b/a), g(a, b) = G(b/a)\) と書けるとき、\((fg)(a, b) = (gf)(a, b) = (fg)(1, b/a)\) である。

\(\varphi(n)\) を \(n\) 以下の \(n\) と互いに素な数の個数とする。\(q(x, y) = y/x\) とすると、\(\varphi(y/x) = (q\zeta^{-1})(x, y) = (\zeta^{-1}q)(x, y)\) が成り立つ。\((q\zeta^{-1}) \zeta\) は \(n \prod(1/p_i + (1-1/p_i))\) の二項展開、\(q\zeta^{-1}\)は \(n\prod (1-1/p_i)\) の二項展開に対応している。\(g(x)=m^x\) と置くと、\(m\) 種類の文字から長さ \(n\) の円環を作る方法の \(n\) 倍は
\begin{align}
(g q\zeta^{-1})(1, n)
\end{align}
と書ける。\((q\zeta^{-1})\) を \(\varphi\) に置き換えると、$$\sum_{ e\mid d \mid n} \frac{\mu(d/e)m^e}{d} =\sum_{e \mid n} \frac{1}{n} \varphi(n/e)m^e
$$が得られる(ポリアの定理でも同じ式が得られる)。

無平方数

任意の正整数は、正の無平方数と正の平方数の積に一意に書けるので、無平方数と平方数の指示関数を\(f, \zeta_2\)と置くと、$$\sum_{d \preceq n} \zeta_2(\hat 0, d)f(d, n) = 1$$が任意の正整数 \(n\) について成り立つ。\begin{align}
&\zeta_2f = \zeta \\
&f= \zeta_2^{-1}\zeta \\
&f = \sum_{d^2 \preceq n} \mu(d)
\end{align}求める値は \(\sum_{i=1}^n f(\hat 0, i) = \sum_{d=1}^N\mu(d)\lfloor N / d^2\rfloor\)
である。

Dirichlet積

整除束の upset の畳み込みは $$(\xi f)(\hat 0, n)=\sum_{d \preceq n} \xi(n/d) g(d)$$ だが、これはディリクレ積の畳み込み$$\sum_{i} \xi(i) i^{-s}\sum_{j} f(j) j^{-s} = \sum_{n}\sum_{d \preceq n} \xi(n/d)f(d) n^{-s}$$として書ける。

分割束のメビウス変換

\([n]\) を \(k\) 個に分割する方法の個数を \(s(n, k)\) とすると、$$x^n = \sum s(n, k)x(x-1)\cdots(x-k+1)$$
が成り立つ。なぜならLHS = x 色で n 人を塗る方法の数, RHS = n 人を k 個のグループに分けた後、各グループ毎に人を塗る方法の数だから。 \(x\) で割って \(0\) を代入すると、$$\mu(\hat 0, \Pi_n) = (n – 1)!(-1)^{n-1}$$ を得る。分割束の区間は分割束の直積に同型なので、これで全て計算できる。

\(f\) が分割の成分の直積で書けるとき(ABC236H)、\begin{align}
&\mu f(\hat 0, \Pi_n) \\
={}&\sum_{\pi=\{B_1,\ldots,B_k\}\in \Pi_n}\mu(\hat 0,\pi)f(\pi) \\
={}&\sum_{k}\frac{1}{k!}\prod_{B_i \neq \emptyset, \bigsqcup_{i=1}^k B_i=[n]}\mu(\hat 0,\{B_i\})f(\{B_i\})
\end{align}となる。これは、subset convolution で処理できる形である。

任意の分割 \(\pi = \{B_1, \ldots, B_k\}\) に対して $$f(\pi) = \prod f(\#B_i)$$
が成り立つとする。

\begin{align}
&\sum_{\hat 0 \leq \pi \leq \Pi_n} \mu(\hat 0, \pi) f(\pi) \\
=& \sum_{\{B_1,\ldots,B_k\}=\pi \leq \Pi_n} \prod \mu(\#B_i)f(\#B_i)\\
=& n!\sum_{\sum i a_i = n} \left(\frac{\mu(\hat 0, \Pi_i)f(i)}{i!}\right)^{a_i}\\
=& n!\sum_{\sum i a_i = n} \left((-1)^{i-1}\frac{f(i)}{i}\right)^{a_i}\\
\end{align}
畳み込みで \(O(n \log n)\) で計算できる。

$$f(\pi)=f(\{\!\!\{\#B_i : i \in \mathbb{N}\}\!\!\})$$のとき、
\begin{align}
&\sum_{\hat 0 \leq \pi} \mu(\hat 0, \pi)f(\pi) \\
=&\sum_{k=1}^N \sum_{\lambda \vdash k} {N \choose \lambda_1, \ldots, \lambda_l} f(\lambda) \prod \mu(\hat 0, \pi_{\lambda_i})\end{align}

となる。next-permutation と同様のアイディアにより \(\lambda \vdash n\) は \(O(np(n))\) で求まるので、上の計算は \(O(\sum i p(i)) = O(\sqrt N 14^{\sqrt{N}})\) でできる。

  • 1000!を30個の相異なる正整数の積で表す方法が何通りあるか求めよ。(PE495)

部分束のメビウス変換

\(M \subseteq L\) が \(L\) の部分束だとする。定義域を自然に拡張して\begin{eqnarray}
f_L(x)
=
\begin{cases}
f_M(x) & ( x \in M ) \\
0 & ( x \not \in M )
\end{cases}
\end{eqnarray}
とすると、\(\zeta_M f_M = \zeta {f|}_M\) だから \(\zeta_M^{-1}f_M = \zeta^{-1}{f|}_M\) となる。つまり、元の束でメビウス反転してから定義域を制限すればよい。

縮約束のメビウス変換

\(V(G)\) の分割 \(\pi\) のうち、任意の \(S \in \pi\) が誘導する部分グラフ \(G[S]\) が連結なものからなる集合は束をなす。この束は、分割束 \(\Pi_{|V(G)|}\) の部分束であるから、メビウス変換ができる。彩色多項式の計算などに用いる。

非空な downset/upset のゼータ変換

\(\hat 0\) を除いた downset の和は \(\zeta-1\) で取れる。直積の束 \(\prod L_i\) では \(\prod (\zeta_i-1)\) となる。\(g=\prod \zeta_i f \) が容易に求まるならば、\(g\) に \(\prod (1-\zeta_i^{-1})\) を掛けるだけでよい(ABC230G)。

参考文献

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA