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

\(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_x\zeta^{-1} (\zeta \delta_a \odot \zeta \zeta^{-1} \delta_{\hat 1}) \\
=&\delta_x\zeta^{-1} (\zeta \delta_a \odot \delta_{\hat 1}) \\
=& 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:=\delta_{k}\) とすると、\(\sum g(i) f(i \land k)\) が得られるので、\((\zeta g \odot f\zeta^{-1})\zeta\delta_k\) は各 \(k\) に対するこのような変換を表している（yuki1503)。

\(\sum_{a \leq i \leq b} \sum_{j \land b = i} f(j)=\sum_{a \leq i} f(i)\) を区間 \([a,b]\) で反転して \(\sum_{j \land b = i} f(j) = \sum_{i \leq i’ \leq b}\mu(i, i’)\sum_{i’ \leq i”}f(i”)\) としても同じ式が得られる。Weisnerの定理も同様の方法で得られる。

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

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}となる。特に整除束の\(\sum_{i=1}^n f(i) \lfloor n/i\rfloor = \sum_{b=1}^n\sum_{a|b}f(a)= \sum_{ab \leq n}f(a)\)が良く出てくる。

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

ディリクレ型母関数を使うのも有力。
整除束を \(p_1, p_2, \ldots, p_k\) の \(k\mathbb{B}\) に対応する部分 \(A\) とそれ以外 \(B\) の直積 \(A \times B\) として取る。
\(\sum \mu_A(i) \lfloor n/i \rfloor = \sum_{ab \leq n} \mu_A(a) = \sum_{b=1}^n \zeta_{A\times B} \mu_{A}=\sum_{b=1}^n (1_A \times \zeta_{B})(b)=\sum_{b=1}^n(bがp_1,\ldots,p_kと互いに素か)\)
\(\sum \mu(i) \lfloor n/i^2 \rfloor = \sum_{b=1}^n \sum_{a^2|b} \mu(a)=\sum_{b=1}^n \sum_{a’ | b’} \mu(a’)=\sum_{b=1}^n\delta(b’)\)
ただし、\(b’^2\) は \(b\) の平方数部分とする。

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

モジュラー束では、$$ \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}$$ である。
ランクが偶数の要素全体についての和も考えられる。\(\boldsymbol{n}\) だと \(\sum_{\text{$i$ is even}} f(i) = \sum_{i \ \text{is even}} (f(i)-f(i-1)) = -f(1)+f(2)-f(3)+\cdots\) となる。\(B_n\) だと \(\sum_{\#S \ \text{is even}} f(S) = \sum_{\#S \ \text{is even}} \sum_{T \subseteq S}(-1)^{\#(S-T)}g(T) = \sum_{T \neq [n]}(-1)^{\#T}2^{n-\#T-1}+[\text{$n$ is even}]f([n])\) となる。
例えば、[0,1]上の n 個の一様乱数の列 \((x_1,x_2, \ldots, x_n)\) について、初項からの ascending run の長さが偶数となる確率は \(\int_{0}^1 (x-\frac{1}{2}x^2+\frac{1}{3}x^3-\cdots)dx\) となる(wtf19 e)。

ブール束

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

\(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\) の形の行列積に直して、順番に掛けると、高速メビウス変換になる。

2乗和

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_{S \subseteq [n]} g(S)(-1)^{\#S} = \frac{H}{1+H}$$が成り立つ。\(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(z^{\langle -1\rangle}(z))^n\frac{t}{(1-tz)^2} \\
&= \frac{1}{n}[z^{n}] \left(\frac{z}{z^{\langle -1\rangle}(z)}\right)^n\frac{tz}{(1-tz)^2} \\\end{align}ただし、\(z(x) = xf(x)\) と置いた。\([x^n]\left(xf(x)\right)^k=[z^{n-k}]\frac{k}{n}\left(\frac{z}{z^{\langle -1\rangle}(z)}\right)^{n-k}\) からも最後の式を得ることができる。ただし、\(f(x)=1/(1-x)^C\) のような簡単な形の時には直接計算した方が良いと思う（ABC225H）。\(t^m\) の係数は \([x^n] \left(\frac{x}{(1-x)^C}\right)^m = [x^{n-m}]\frac{1}{(1-x)^{Cm}} = (\!\!{Cm \choose n-m}\!\!)\) となる。

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

\(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}
を得る。

次の様に示すこともできる。
\(A_n\) を \(k\) 個の連続する整数が現れない \([n]\) の部分集合全体とする。\(B_{n,d} = \{S \cup \{n-(d-1),\ldots,n\}: S \in A_{n-d}\}\) と置く。\(B_{n,d}\) では \({n-(k-1)-i,\ldots, n}\)
\((0 \leq i \leq d-1)\) のみが \(k\) 個以上連続する極大整数列として現れ得る。従って、\(\#B_{n,0}-\#A_n = \#B_{n,k}-\#B_{n,k+1}+\#B_{n-(k+1), 0}-\#A_{n-(k+1)}\)より
$$\begin{align}
&\#B_{n,0}-\#A_n = \sum_{i=0}^\infty \left(\#B_{n-(k+1)i,k}-\#B_{n-(k+1)i,k+1}\right) \\
\iff& \#A_n=\#B_{n,0} -\sum_{i=0}^\infty \left(\#B_{n-(k+1)i,k}-\#B_{n-(k+1)i,k+1}\right)
\end{align}
$$

長さ \(k+1\) \((\geq 2)\) 以上の任意の連続部分列が条件 \(P\) を満たさない場合を数えたい。条件 \(P\) を無視したときの長さ \(n\) の列の個数が \(a_1^n\)、\(P\) を満たす長さ \(i\) の列の個数が \(b_i\) だとする。メビウス変換により、求める場合の数のOGFは $$\frac{1}{1-\left(a_1x-\sum_{i \geq 1} b_{(k+1)i}x^{(k+1)i}+\sum_{i \geq 1} b_{(k+1)i+1}x^{(k+1)i+1}\right)}$$ となる。AGC058Dは \(k=2\) で3変数の場合である。母関数は\(f=a+b+c+\sum_{i > 0} \left((abc)^ia+(bca)^ib+(cab)^ic \right)-\sum_{i > 0}\left((abc)^i+(bca)^i+(cab)^i)\right)\) とすると \(1 / (1-f)\) となる。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\) になっている(かならいさん)。また、このことから、メビウス関数を逆算することもできる。一般に、\(n\) 種類の形式的べき級数 \(f_1, f_2, \ldots, f_n\) の（順序を区別した）積であって、同じ形式的べき級数が連続しないものの和は \(1 / (1-\sum f_i / (1+f_i))\) と表せる。\(f, g\) のうち、\(f\) だけ連続してはいけない場合は \(\frac{1}{1-(f/(1+f)+g)} = (1+f) / (1-g(f+1))\) となるが、これは \((1+f)(g^af)(g^bf)(g^cf)\cdots\)という一意な分解を行っていると解釈できる。\(1+g=1/(1+\sum f_i/(1+f_i)) \iff g/(1+g) = \sum f_i / (1+f_i)\) だが、これは右辺が not equal の包除になっている。

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

整除束のメビウス変換

\(\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)\) と書けるような隣接代数の関数の畳み込みはディリクレ型母関数の畳み込みと同型である。

\(\zeta\) のディリクレ型母関数を \(\zeta(s)\) と置く。\(\varphi(n)\) を \(n\) 以下の \(n\) と互いに素な数の個数とする。このとき、\(\varphi\) のディリクレ型母関数 \(\Phi\) は \begin{align}
\Phi=&\sum_n \frac{n}{n^s} \prod_i \left(1-\frac{1}{p_i^s}\right)\\
=&\zeta(s-1) / \zeta(s)
\end{align} で表される。\(q(x, y) = y/x\) とすると、\(\varphi(y/x) = (q\zeta^{-1})(x, y) = (\zeta^{-1}q)(x, y)\) が成り立つ。\(\zeta(s-1) = \Phi \zeta(s)\) は \(n \prod(1/p_i + (1-1/p_i))\) の二項展開に対応している。\(g(s)=\sum m^x/n^s\) と置くと、\(m\) 種類の文字から長さ \(n\) の円環を作る方法の \(n\) 倍は
\begin{align}
&g \zeta(s-1) /\zeta(s)^{-1}\\ =& g \Phi
\end{align}
と書ける。具体的に書くと、\begin{align}&\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 \\
\iff & \sum_{abc = n} \mu(b)m^ac =\sum_{ab = n} \varphi(a)m^b
\end{align}
となる(ポリアの定理でも同じ式が得られる）。また、\(\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/m\mathbb{Z}\) で同じことをすると$$\sum_{d’|d|n}\sum_{e’|e|m}\frac{1}{de}\mu(d/d)\mu(e/e)x^{\frac{nm}{\mathrm{lcm}(n/d,n/e)}} = \frac{1}{nm}\sum_{d|n}\sum_{e|n} \varphi(n/d)\varphi(m/e)x^{\frac{nm}{\mathrm{lcm}(n/d,n/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\)
である。

？

\(g = \zeta f\) とする。\(f= \zeta^{-1}\zeta f = \sum_{i=0}^\infty (-1)^i(\zeta-1)^ig=g-(\zeta-1)f\) である。\(g(i)=G(\left\lfloor n/i\right\rfloor) \) と書けるとする。\(g\) は定数時間で計算できるとする。\(f(n), f(n-1), \ldots, f(1)\) の順に計算すると \(O(n^{3/4})\) で \(f(1)\) が計算できる。メビウス関数の累積和を Meissel Lehmer algorithm で列挙すると \(f(1)\) は \(O(n^{2/3} \log(n))\) で求まる(TUPC2022I)。

円分多項式

\(f(n)=\prod_{\gcd(k,n)=1}(1-x^k)\)と置くと、\(1-x^n = \prod_{d|n}f(d)\)より\(f(n) = \prod(1-x^{n/d})^{\mu(d)}\)となる。

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}$$として書ける。
\(1+1/p^s=\frac{1-1/p^{2s}}{1-1/p^s}\)なので、\(|\mu(n)|\)のディリクレ型母関数は\(\zeta(s)/\zeta(2s)\)である。\(1+p/p^s+p^2/p^{2s} = (1-1/p^{3(s-1)}) / (1-1/p^{(s-1)})\) ので cubic free part のディリクレ型母関数は \(\zeta(s-1)\zeta(3s)/\zeta(3(s-1))\) となる。

分割束のメビウス変換

\([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_{n = \sum \lambda_i} \frac{1}{k!}\prod_i \frac{\mu(\hat 0, \Pi_{\lambda_i})f(\lambda_i)}{\lambda_i!}\\
=& n!\sum_{n = \sum \lambda_i} \frac{1}{k!}\prod_i (-1)^{\lambda_i-1}\frac{f(\lambda_i)}{\lambda_i}\\
\end{align}
expで計算できる形になった。
下位集合に対する包除原理は次の様になる。
\begin{align}
&\sum_{\hat 0 \leq \pi \leq \Pi_n} f(\pi) \mu(\pi, \Pi_n)\\
=& \sum_{\{B_1,\ldots,B_k\}=\pi \leq \Pi_n} (-1)^{k-1}(k-1)!\prod_i f(\#B_i)\\
=& n!\sum_{n = \sum \lambda_i} (-1)^{k-1}\frac{1}{k}\prod_i\frac{f(\lambda_i)}{\lambda_i!}
\end{align}
これはEGFのlogの形である。
$$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)

縮約束のメビウス変換

\(V(G)\) の分割 \(\pi\) のうち、各ブロック \(S \in \pi\) が誘導する部分グラフ \(G[S]\) が連結なものからなる半順序集合は束をなす。例えば、\(f(\pi)\) を \(\pi\) の各ブロックを縮約したグラフを \(K\) 色で頂点彩色する場合の数とすると \(f(\pi)=\sum_{\pi \leq \sigma} g(\sigma) = K^{|\pi|}\) となるので、\(g\) はメビウス反転により求まる。ただし、メビウス関数が高速に得られないので、実際に計算するのには向かないと思う。しかし、分割束に持ち上げると、高速に計算できる。また次のような導出も知られている。頂点彩色の各色の頂点集合は独立集合をなす。従って、\(h\) を独立集合の set FPS とすると、\(K\) 色で頂点彩色する場合の数は \((1+h)^K\) により求まる。

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

\begin{align}
&\sum_{\hat 0 < x \leq \hat 1} f(x) \\
=&\delta_{\hat 0}\zeta f-\delta_{\hat 0}f\\
=&\delta_{\hat 0} (\zeta-1)f \\
=&\delta_{\hat 0} (1-\zeta^{-1})g \\
=&\sum_{\hat 0 < x \leq \hat 1} -\mu(\hat 0, x)g(x)
\end{align}
ABC230G, ABC302F。ABC230Gでは束の直積について、それぞれで \(\hat 0\) を含まない場合が出題された。

n 種類のアイテムがそれぞれ \(p_1, p_2, \ldots, p_n\) の確率で出るガチャがある。それぞれ \(a_1, a_2, \ldots, a_n\) 個以上集めるまでガチャを回すとき、回す回数の期待値を求めよ(AGC38E)。
整除束の1以上N以下の要素からなる長さ \(k\) の鎖
\(t_1 \leq t_2 \leq \cdots \leq t_k\) は \(O\left(N \log \left((N \right)^k\right)\) 個ある。これは \(1 \leq xyz \leq N\) （通常の大小）となる \((x, y)\) が \(O((N/z) \log(N/z))\) 個あることから示せる。

\begin{align}
g(\emptyset)&=\sum_{V = V_1′ \sqcup V_2′}\sum_{V_1 \subseteq V_1′}g(V_1′)(-1)^{\#V_1′} \\
&=\frac{1}{2^{\#V}}\sum_{V = V_1 \sqcup V_2} \sum_{V_1\subseteq V_1′}\sum_{V_2\subseteq V_2′}g(V_1′)(-1)^{\#V_1′}(+1)^{\#V_2}
\end{align}
\(g(U)\) を奇点の集合が \(U\) となる \(V\) 上のグラフの個数とすると、\((-1)^{\#V_1}(+1)^{\#V_2} = (-1)^{\sum_{v \in V}d(v)}\) となって都合が良い。\(a_{i,j}\) を \(n\) 頂点偶グラフであって、辺数 \(i\) 、頂点 \(1\) の次数 \(j\) のグラフの個数とすると \(\sum a_{i,j} x^iy^j\) がこの手法で求まる。

\(g(n) = \sum_{d | n} f(d)\) とすると、\(f, g\) のOGF \(F, G\) は \(G(x) = \sum_{i \geq 1} F(x^i)\) の関係にある。多重集合のOGF \(g(x) = \exp \sum_{i \geq 1} \frac{f(x^i)}{i}\) は \( xg'(x)/g(x) = \sum_{i \geq 1}x^{i}f'(x^{i})\)、\(F(x) = xf'(x)\) とすることで上記のメビウス反転の形になる。
\(\mathbb{F}_q\)上のmonic多項式の数\(f(n)\)は \(\frac{1}{1-qx}=\exp(\sum_{i \geq 1} f(x^i)/i)\) より

\begin{align}
& -\log(1-qx) = \sum_{i \geq 1}f(x^{i})/i\\
\Longrightarrow & \frac{qx}{1-qx} = \sum_{i \geq 1}x^if'(x^{i})\\
\iff &q^{n} = \sum_{i | n} if_i \\
\iff & f_n = \frac{1}{n} \sum_{i | n}q^i\mu(i, n)
\end{align}
となる。既約多項式の根をすべて集めると、\(\mathbb{F}_{q^n}\) になるという数え方もある。

\(\sum_{i \geq 1} f_{\geq i}x^i = \sum_{i \geq 1}g_ix(x-1)^{i-1}\)

左辺を \(\sum_{i \geq 1}f_i (x+\cdots+x^i) = \sum f(S)\#\{(\phi, a) :a
\in S, \phi \in [x]^{[i]}, \phi(j) = 0\text{ for }j > a\}\) と見る。\(g(S)x(x-1)^{\#S-1}\) は \(a = \max(S)\) と 0 に移らない集合 \(S \setminus \{a\}\) 毎に数えている。

参考文献

• 隣接代数入門（maspyさん）
• 組合せ論（van Lint, R. M. Wilson）
• [数学] 畳み込み入門：Dirichlet積とゼータ変換・メビウス変換