形式的冪級数を \(\sum a_nx^n\) ではなく、 \(\sum a_n\frac{x^n}{n!}\) の形で取ると意味のある畳込みが計算できてなぜか上手くいくことがある。僕は何度も経験があり不思議に思っていた。後者の指数型母関数（母級数）の形で上手くいくのはどんな場合か、またその性質を積極的に利用して考察に生かせないのか。この疑問について答えよう。形式的な解説を付けたが、先に問題を解き、何を計算しているか見失いそうになってから真面目に解説を読むのが良いと思う。

追記：sugarknri さんがこの記事の解説を書いてくれたのでそちらも併せて読むと良いかも。

種と指数型母関数の定義

種 \(\mathcal{A}\) を次の条件に従う構造物だとする。

1. 有限集合 \(X\) に対して別の有限集合 \(\mathcal{A}(X)\) を定める。
2. 有限集合 \(X, Y\) について \(|X|=|Y|\) ならば \(|\mathcal{A}(X)|=|\mathcal{A}(Y)|\) 。
3. 有限集合 \(X, Y\) について \(X \neq Y\) ならば \(\mathcal{A}(X) \cap \mathcal{A}(Y) = \emptyset \) 。

この規則のうち、(ii), (iii) は意味のある畳み込みや合成が計算できるための条件である（がこの記事の目的は指数型母関数で何ができるかを伝えることなのでこの条件は気にせず進める）。

\(\mathcal{A}_n:=\mathcal{A}( \{1,2,\ldots ,n \})\) と置く。種 \(\mathcal{A}\) を用いて指数型母関数を$$A(x) := \sum_{n=0}^\infty \left|\mathcal{A}_n\right| \frac{x^n}{n!}$$で定義する。\(\mathcal{A}\) の引数の要素 \(1,2,\ldots,n\) の型は (ii) より何でも良く、その都度「ボール」「n元集合」「根付き木」「森」「サイクル」のように使用者が解釈を入れる。

種の例

基本的な種をいくつか見ておく。

置換の種 \(\mathcal{S}\) を、\(\mathcal{S}(X)\) が集合 \(X\) の全ての置換の集合である種と定める。\(n\) 元集合の置換は \(n!\) 個あるので \(S(x) = \sum_{n=0}^\infty n! \frac{x^n}{n!} = \frac{1}{1-x}\) を得る。

また有限集合の種 \(\mathcal{E}\) を、\(\mathcal{E}(X) = \{ X \} \) で定める。指数型母関数は \( E(x) = \sum_{n=0}^\infty \frac{x^n}{n!} = e^x \) となる。自明な例だが、後々非常に役立つ。

他にも簡単な種を列挙しておく。
\(n\) 元集合の種 \(\mathcal{E_{n}}(X)\begin{eqnarray} = \begin{cases} X & (|X|=n) \\ \emptyset & (\text{otherwise}) \end{cases} \end{eqnarray}\): \(E_n(x) = \frac{1}{n!}x^n\)
奇サイズの集合の種 \(\mathcal{E_{odd}}\)：\(E_{odd}(x) = (e^x-e^{-x})/2=\sinh(x)\)
非空集合の種 \(\mathcal{E_{nonempty}}\)：\(E_{nonempty}(x) = E(x)-E_0(x)=e^x-1\)
巡回置換の種 \(\mathcal{C}\)： \(C(x) =\sum_{n=1}^\infty (n-1)!\frac{x^n}{n!}=\log\left(\frac{1}{1-x}\right) \)

畳み込み

種 \(\mathcal{A}, \mathcal{B}\) の畳み込みを$$(\mathcal{A}*\mathcal{B})(X):= \coprod_{S \subseteq X} A(S) \times B(X \setminus S) $$で定義する。\((\mathcal{A}*\mathcal{B})(X)\) もまた種となる（証明略）。右辺は種の定義 (iii) から disjoint な要素の和集合である。また、(ii) より種の像のサイズは引数のサイズのみで決まるから \(n=|X|\) とすると　\(|(\mathcal{A}*\mathcal{B})(X)|=\sum_{k=0}^n {n \choose k}|\mathcal{A}_{n-k}| |\mathcal{B}_{k}|\) となる。すると通常の冪級数の畳込みが種の指数型母関数の畳込みと等しくなる： $$\begin{align}A(x) B(x) = &\sum_{n=0}^\infty \sum_{k=0}^n \frac{\mathcal{A}_{n-k}}{(n-k)!} \frac{\mathcal{B}_k}{k!} x^n\\ = &\sum_{n=0}^\infty |(\mathcal{A}*\mathcal{B})(X)| \frac{x^n}{n!} \end{align}$$ \(X\) は集合であるから、区別のつかないものは数えられないことに注意せよ。例えば、「区別のつかないボール \(N\) 個をいくつかの箱に分ける方法はいくつあるか？」という問題は集合 \(X\) が潰れてしまうので指数型母関数では扱えない。一方「それぞれ番号が \(1\) から \(N\) まで割り振られたボールをいくつかの箱に分ける方法はいくつあるか？」という問題は \(X=\{1,\ldots,N\}\) とすると指数型母関数で扱える。サイズについて交換法則 $$|((\mathcal{A}*\mathcal{B})*\mathcal{C}))(X)|=|(\mathcal{A}*(\mathcal{B}*\mathcal{C}))(X)|$$ が成り立つので、掛ける順序は気にせず \(\mathcal{A}*\mathcal{B}*\mathcal{C}\) と書いて良い。

例題

何を計算しているか分からなくなってから初めて戻るつもりで、問題を色々見て慣れるのが良いと思う。※「種の例」で扱った種は断りなく使う。

\(X=\{\)ボール1, ボール2, \(\ldots\), ボールN\(\}\)、\begin{eqnarray} |\mathcal{F_i}(X)| = \begin{cases} 1 & (\text{if}\ |X| \equiv 0 \pmod i \ ∧ |X|>0) \\ 0 & (\text{otherwise}) \end{cases} \end{eqnarray} として $$(\mathcal{F}_a*\mathcal{F}_b*\mathcal{F}_c)(X)$$ $$=\coprod_{S \subseteq X, T \subseteq X \setminus S} F_a(S) \times F_b(T) \times F_c(X \setminus (S \cup T))$$ のサイズを数え上げればよい。そこで解答は次のようになる。

【解答】\(F_a=\sum_{m=1}^\infty E_{ma}\), \(F_b=\sum_{m=1}^\infty E_{mb}\), \(F_c=\sum_{m=1}^\infty E_{mc}\) とすると \(N!F_aF_bF_c\) の \(x^N\) の係数が答え（\(E_i(x)\) は「種の例」で定義した）。

頻繁に登場するのでこれから、\(f\) の \(x^N\) の係数を \([x^N]f\) と書くことにする。同様に、\(x^N/N!\) の係数を \([x^N/N!]f\) と書く。

【解答】 \(f(x)=E_{nonempty}(x)\) とするとき、 \(\left[\frac{x^N}{N!}\right]f^K\) が答え。

直積の定義から掛けられた順序を区別して数え上げることに注意せよ。

【解答】 \(f(x)=E_{nonempty}(x)\) とするとき、 \(\left[\frac{x^N}{N!}\right]\sum_{i=0}^\infty f^i = \left[\frac{x^N}{N!}\right] \frac{1}{1-f}\) が答え。

形式的冪級数で成り立つ操作（例えば\(\sum_{i=0}^\infty f=\frac{1}{1-f}\)) は指数型母関数でも成り立つ。

演習

ネタバレに配慮して一部黒塗りにしている。※「種の例」で扱った種は断りなく使う。

【解答】求める値を \(\left[\frac{x^N}{N!}\right]f(x), g=\) \(E(x)\) とすると \(fg=S\) だから \(\left[\frac{x^N}{N!}\right]Sg^{-1}\) が答え。

（求めたい級数）×（分かっている級数その１）＝（分かっている級数その２）の形は指数型母関数を求める際によく出現する。

【解答】\(f\) を問題4で求めた母級数, \(h(x)=\)\(E_K(x)\) とすると \(\left[\frac{x^N}{N!}\right]fh\) が答え。

【解答】問題2と同じであるが、ここでは問題4の解答の方針でいこう。求める値を \(\left[\frac{x^N}{N!}\right]f(x), g(x)=\) \(E(x)\) \(,h(x)=\) \(\sum_{i=0}^\infty (i^K/i!) x^i\) とする。\(fg=h\) だから \(\left[\frac{x^N}{N!}\right]g^{-1}h\) が答え。

【解答】\(f\) を問題7で求めた級数、\(g=\)\(E_{odd}(x)\) とすると \(\left[\frac{x^N}{N!}\right] fg\) が答え。

代入

指数型母関数の代入は定義に従えば、 $$B(A(x))=\sum_{k=0}^\infty B_k\frac{A(x)^k}{k!}$$ である。問題2と問題3から \(\mathcal{A}^k(X)\) は「\(X\) の \(k\) 個の集合への順序付き分割」の種 \(\mathcal{A}\) の像の直積（つまり順序付き）全てだったから、\(\frac{\mathcal{A}^k(X)}{k!}\) は「\(X\) の \(k\) 個の集合への順序なし分割」の種 \(\mathcal{A}\) の像の集合（つまり順序なし）とみなせる（なぜなら個数のみが重要だから）。従って、\(X\) の順序なし分割の種 \(\mathcal{A}\) の像の集合を \(\mathcal{E}[\mathcal{A}](X)\) として種 \(\mathcal{E[A]}\) を定義すると、 $$\coprod_{\zeta\in\mathcal{E}[\mathcal{A}](X)} \left(\{\zeta\} \times \mathcal{B}(\zeta)\right)$$ のサイズが \(\left[\frac{x^{|X|}}{|X|!}\right]B(A(x))\) と等しくなる。従ってこの式を \(\mathcal{A}\) を \(\mathcal{B}\) に代入したものとして定義し、\(\mathcal{B[A]}\) と書く。

集合 \(\{\zeta\}\times\mathcal{B}(\zeta)\) の要素が何を表しているかは使用者が解釈を入れる必要がある。例えば、\(\mathcal{A}\) を根付き木の種、\(\mathcal{B}\) をサイクルの種とする。すると、下図のように \(\{\zeta\}\times\mathcal{B}(\zeta)\) はサイクルの各要素を根付き木で置き換えた unicyclic graph だとみなすことができる。従って、\(B(A(x))\) を計算することでその個数を数え上げることができる。

注意として \(\mathcal{A}(\emptyset)\neq\emptyset\) だと空集合への分割が可能になり、集合の分割方法が無限にできてしまうので、\(\mathcal{A}(\emptyset)=\emptyset\) とする。これは \(A_0=0\) と同値である。

“根付き” 種

種 \(\mathcal{A^●}\) を \(\mathcal{A^●}(X)=X\times\mathcal{A}(X)\) で定義する。 これは各要素 \(a \in \mathcal{A}(X)\) に対して、\(X\) の要素を選ぶという自由度を加えたものと捉えられる。 根付き木の根をどれにするか全通り試したい場合などに役立つ（問題13）。 あるいは重みを \(|X|\) 倍したものと考えても良い（問題14）。どちらが考えやすいかは問題によると思う。 指数型母関数は \begin{align} A^●(x)=&\sum_{n=0}^\infty nA_nx^n\\ =&x\frac{d}{dx}A(x)\\ \end{align} となる。

例題

何を計算しているか分からなくなったら定義に戻って確認してほしい。※「種の例」で扱った種は断りなく使う。

【解答】\(\left[\frac{x^N}{N!}\right]E(E_a)E(E_b)E(E_c)\) が答え。

\(E(E_a)\) は \(\mathcal{E}\) による分割の各要素を \(\mathcal{E}_a\) の各要素で置き換えるというイメージである。

【解答】\(\left[\frac{x^N}{N!}\right]E(E_{nonempty}(x))\) が答え。

代入する \(E_{nonempty}\) は \([x^0] E_{nonempty}=0\) を満たすことに注意。一般に指数型母関数の代入において定数項が \(0\) でなければ、意味のある計算にはならない。

【解答】 反転を同一視することと \(N=1, 2\) のときサイクルが存在しないことから \(\left[\frac{x^N}{N!}\right](1/2)(C(x)-x-x^2/2)\) が答え。

【解答】 \(f\) を問題10で求めた級数とする。\(\left[\frac{x^N}{N!}\right]E(f(x))\) が答え。

一般に \(E(x)\) に（連結XXXグラフ）を代入すると連結性が失われ、（XXXグラフの集まり）を数えることができる。

【解答】\(n+1\) 頂点のラベル付き根付き木から根 \(v\) を取り除くと \(n\) 頂点のラベル付き根付き森になる。 ただし、根付き森の各根は \(v\) と接続していた頂点とする。 逆に \(n\) 頂点のラベル付き根付き森に頂点 \(v\) を追加して全ての根と辺を張ると \(v\) を根とする \(n+1\) 頂点ラベル付き根付き木になる。 以上から \(\mathcal{T}^●\) を根付き木（根は全通り試す）の種とすると次が成り立つ： $$T^●(x) = x\exp(T^●(x)).$$ ラグランジュの反転公式を使うと \(T^●(x)=\sum_{n=1}^\infty \frac{n^{n-1}}{n!}x^n\) が得られる。ラグランジュの反転公式の部分は解説しないが、「Lambert’s W function Taylor Series」で検索すると類似の計算が見つかる。以上から \(T_N=N^{N-2}\) が答え。

演習

ネタバレに配慮して一部黒塗りにしている。

【解答】問題12より \(f:=\)\(\sum_{n=1}^\infty \frac{n^{n-2}}{n!}x^n\) とすると \(\left[\frac{x^N}{N!}\right] E_{nonempty}(f(x))\) が答え。

【解答】\(f\) を問題10で求めた母級数、\(g\) を問題12の \(T^●(x)\) だとする。\(\left[\frac{x^N}{N!}\right]f(g(x))\) が答え。

【解答】頂点数 \(L\) 以下のサイクルおよびパスの種 \(\mathcal{A, B}\) の指数型母関数はそれぞれ \(A(x)=\)\(\frac{x^2}{2}+\sum_{n=3}^L \frac{(n-1)!}{2}\frac{x^n}{n!}\)、\(B(x)=\)\(x+\sum_{n=2}^L \frac{n!}{2}\frac{x^n}{n!}\) である。パスが \(N-M\) 個あれば良いから、\(\left[\frac{x^N}{N!}\right]\)\(E(A)E_{N-M}(B)\) が答え。

【解答】\(f(x)=\sum_{n=0}^\infty \frac{x^n}{n!}\sum_{k=0}^n {n \choose k}2^{k(n-k)}\), \(\exp(2g(x))=f(x)\) より \(\left[\frac{x^N}{N!}\right] g(x) = \left[\frac{x^N}{N!}\right]\frac{1}{2}\log(f(x))\) が答え。

【解答】 \(f(x)=\)\(E(x)\), \(g(x)=\)\(C(x)\) とするとき、 \(\left[\frac{x^N}{N!}\right]f(\)\((x d/dx)^M\) \(g(x))\) が答え。

【解答】Prüfer コード（問題1）を使った解法が明快だが、指数型母関数でもなんとか求めることができる。求める値を \(\left[\frac{x^N}{N!}\right]A^●(x)\) とする。問題12と同じように、木を「根 r 」と「根の子を新たに根とする部分木 T’」に分解する。この部分木 T’ を根 r に繋ぎなおすと T’ の根の次数が 1 増加する。そこで、根の次数のみ 1 加算して、次数の総積の和を数えた値を \(\left[\frac{x^N}{N!}\right]B^●(x)\) とする。\(A^●(x)=\)\(x \sum_{k=1}^\infty kE_k(B^●(x))\), \(B^●(x)=\)\(x \sum_{k=1}^\infty (k+1) E_k(B^●(x))\) が成り立つ。ここからLagrange の反転公式を2度使うことで \(A^●, B^●\) が求まる。続きは本家の解説を参照せよ。

多変数の指数型母関数

以上の理論は合成に関して、多変数にそのまま拡張できる。 多変数の種 \(\mathcal{A}(X_1,X_2,\ldots,X_m)\) を次の条件に従う構造物とする。

1. 有限集合 \(X_1, \ldots, X_m\) に対して、別の有限集合 \(\mathcal{A}(X_1,\ldots,X_m)\) を定める。
2. 全ての \(i=1,2,\ldots,m\) について \(|X_i|=|Y_i|\) ならば \(\mathcal{A}(X_1,\ldots,X_m)=\mathcal{A}(Y_1,\ldots,Y_m)\) 。
3. ある \(i=1,2,\ldots,m\) について \(X_i \neq Y_i\) ならば \(\mathcal{A}(X_1,\ldots,X_m)\cap\mathcal{A}(Y_1,\ldots,Y_m) = \emptyset\) 。

各 \(i\) について \(n_i=|X_i|\) の種を \(\mathcal{A}_{n_1,n_2,\ldots,n_m}:=\mathcal{A}(X_1,X_2,\ldots,X_m)\) と略記する。種 \(\mathcal{A}\) の指数型母関数を $$A(x_1,x_2,\ldots,x_m)=\sum |\mathcal{A}_{n_1,\ldots,n_m}| \frac{x_1^{n_1!}x_2^{n_2!}\cdots x_m^{n_m!}}{n_1!n_2!\cdots n_m!}$$と定める。

※指数型母関数の積と合成が、１変数の時と同様に意味づけできることを確かめよ。

例題

【解答】 男を \(x\)、女を \(y\) に割りてて、\( \exp(\sum_{(a,b) \in S} \frac{x^{a}y^b}{a!b!})\) が答え。

【解答】赤、青、黄の頂点を \(x,y,z\) に割り当てて、\(\log(\sum_{i,j,k} 2^{ij+jk+ki}\frac{x^iy^jz^k}{i!j!k!})\) が答え。

【解答】頂点 \(i\) を \(x_i\) に割り当てて、\(\log(\sum_{S \subset V} 2^{||G[S]||} \prod_{i \in S} x_i)\) が答え。subset convolution により、\(O(2^nn^2)\) で求まる。

分割がなす半順序集合と \(\exp, \log\) の関係

集合 \([n]\) の分割の集合を \(\Pi_n\) と置きます。分割 \(\pi, \sigma \in \Pi_n\) に対して、「\(\pi \leq \sigma \Leftrightarrow\) \(\pi\) の各元（ブロック）が \(\sigma\) のある元（ブロック）の部分集合である」として、半順序集合にします。例えば、$$\{\{1\}, \{2, 5\}, \{3, 4\}\} \leq \{\{1\}, \{2, 3, 4, 5\}\}$$ です。有限な半順序集合にはメビウスの反転公式が定義できて、\begin{align} f(\pi) &= \sum_{\sigma \leq \pi} g(\sigma) \\ g(\pi) &= \sum_{\sigma \leq \pi} f(\sigma)\mu(\sigma, \pi) \end{align}と書けます。特に、\(\Pi_n\) の最小元と最大元を \(\hat 0, \hat 1\) と置くと、\(\mu(\hat 0, \hat 1) = (-1)^{n-1}(n-1)!\) であることが知られています。\(\pi = \hat 1\) ならば、\([\sigma, \pi] \cong \Pi_{|\sigma|}\) なので、\(\mu(\sigma , \hat 1) = (-1)^{|\sigma|-1}(|\sigma|-1)!\) です。 ここで分割 \(\pi = \{B_1, B_2, \ldots, B_k\}\) に対して、ある関数 \(G\) を用いて \begin{align} g(\pi) =\prod_{i} G(|B_i|) \end{align} と書けるならば、\begin{align} F(n) :=& \sum_{|\pi| = n} f(\pi) \\ =& \sum \frac{1}{k!}{n \choose i_1, i_2, \ldots, i_k}G(i_1)G(i_2) \ldots G(i_k) \\ =& n!\sum \frac{1}{k!} \frac{G(i_1)}{i_1!}\frac{G(i_2)}{i_2!} \ldots \frac{G(i_k)}{i_k!} \\ \end{align} となり、ゼータ変換して特定のランクの和を取った値が指数型母関数の \(\exp\) と同じ式になります。同様に、\begin{align} G(n) =& \sum_{\sigma \leq \hat 1} f(\sigma)\mu(\sigma, \hat 1)\\ =& \sum \frac{(-1)^{k-1}(k-1)!}{k!}{n \choose i_1, i_2, \ldots, i_k}F(i_1)F(i_2) \ldots F(i_k) \\ =& n!\sum \frac{(-1)^{k-1}}{k} \frac{F(i_1)}{i_1!}\frac{F(i_2)}{i_2!} \ldots \frac{F(i_k)}{i_k!} \\ \end{align} となり、メビウス変換した値が指数型母関数の \(\log\) と同じ式になります。 set型の多変数の指数型母関数は \(\pi = \{B_1, B_2, \ldots, B_k\}\) に対して、ある関数 \(G\) を用いて \begin{align} g(\pi) =\prod_{i} G(B_i) \end{align} と書ける場合です。\(f, g\) が特定の良い性質を持つとき、メビウス・ゼータ変換が、指数型母関数の \(\exp,\log\) として現れていることが分かりました。ながたかなさんのブログでも同じ話がされています。\(\Pi_n\) の要素数の増大は早く、例えば \(|\Pi_{15}|=1382958545\) です。指数型母関数で定式化できない良い性質で計算量を削減できる場合があるので、どちらも使えるのが良いと思います。\(\pi\) のブロックサイズの多重集合が等しいこと、つまり、 \(g=G(\{\!\!\{\#B_i : i \in \mathbb{N}\}\!\!\})\) を満たす \(G\) が存在することを利用して、計算量を \(n\) の分割数で抑える問題を見たことありますが、それは指数型母関数での定式化が難しいのではと思います。

サイクル分解の標準形

サイクル分解の標準形とサイクルの集合は$$\frac{1}{1-x} = \exp(\log(1-x))$$ の左辺と右辺の関係にある。 もう少し複雑な例として、\(f(x) = \sum_i A_i x^i\) と置いて、 \begin{align} \frac{1}{(1-x^i)^{A_i}} &= \exp\left(\sum _iA_i\log(1-x^i)\right) \\ &= \exp\left(\sum_k \frac{1}{k}\sum_iA_i(x^k)^i\right) \\&= \exp\left(\sum_k \frac{1}{k} f(x^k)\right) \end{align}がある。

ベクトル空間への一般化

簡約隣接数

\([n]:=\{1, 2, \ldots, n\}\) の順序付き分割 \([n] = S \sqcup T\) と、 \([n]\) の包含関係にある2つの部分集合 \(A \subseteq B\) は \(S \sqcup T \mapsto S \subseteq (S \cup T)\) という全単射があります。EGF を包含関係が載るような母関数として一般化すると、簡約隣接代数と呼ばれるものになります。OGF や EGF はその一例ですが、ここでは \(\mathbb{F}_q\) 係数 \(n\) 次元ベクトル空間 \(V_n\) を考えてみましょう。\(V_n\) の部分空間の列 \(W_1 \subseteq W_2 \subseteq \cdots \subseteq W_k\) であって、各 \(i\) について \(a_i = \dim W_i\) が成り立つものは、\(\frac{[n!]_q}{[a_1!]_q[a_2!]_q \cdots [a_k!]_q}\) 個あります。ただし、\([i]_q := 1 + q + \cdots + q^{i-1}, [i!]_q := [1]_q[2]_q\cdots[i]_q\) です。従って、\(\sum_{n \geq 0} f(n) x^n/ n!\) の代わりに \(\sum_{n \geq 0} f(n)x^n/[n!]_q\) とすると、積に関しては、EGFと同じように定式化できます。

非交和

非交和に着目して、\(V_n\) に対して拡張することもできます。\(\mathbb{F}_q\) 係数 \(n\) 次元ベクトル空間の線形同型写像は \(\gamma_n = (q^n-1)(q^n-q)\cdots (q^n-q^{n-1})=[n!]_q(q-1)^nq^{n \choose 2}\) 個あります。直和 \(V_n = W_1 \oplus W_2 \oplus \cdots \oplus W_k\) であって、各 \(i\) に対して、\(a_i = \dim W_i\) が成り立つものは \(\frac{\gamma_n}{\gamma_{a_1}\gamma_{a_2} \cdots \gamma_{a_k}}\) 通りあります。従って、\(\sum_{n \geq 0}f(n)x^n/\gamma_n\) とすると、積・合成に関して、EGFと同じような定式化ができます。

参考文献

• ヴァン・リント&ウィルソン 組合せ論 上 第4章
  • 最初に指数型母関数に触れた印象深い本。
• David G. Wagner 氏の授業資料
  • 何を計算しているか迷子だったのを救ってもらった。
• Foundations of Combinatorics with Applications by Edward A. Bender & S. Gill Williamson
• Enumerative Combinatorics 2(Richard Stanley)