Skip to content →

指数型母関数入門

形式的冪級数を \(\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}\) と書いて良い。

例題

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

【問題1】\(N\) 個のラベル付きボールを \(a\) の倍数サイズの集合、\(b\) の倍数サイズの集合、\(c\) の倍数サイズの集合の \(3\) つに分ける。ただし \(a,b,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\) と書くことにする。

【問題2】\(N\) 個のラベル付きボールを \(K\) 個の非空なラベルなしグループに分け、そのグループをリストに並べる方法は何通りか。例えば \((\{a,b\},\{c\})\) と \((\{c\}, \{a,b\})\) を区別する数え方である。

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

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

【問題3】\(N\) 個のラベル付きボールを非空なラベルなしグループに分け、そのグループをリストに並べる方法は何通りか。例えば \((\{a,b\},\{c\})\) と \((\{c\}, \{a,b\})\) を区別する数え方である。(出典:ordered Bell number)

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

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

演習

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

【問題4】\(\{1,2,\ldots,N\}\) の順列 \(\{p_1,\ldots,p_N\}\) のうち任意の \(i\) について \(i \neq p_i\) が成り立つ場合の数を求めよ。(出典:攪乱順列)

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

(求めたい級数)×(分かっている級数その1)=(分かっている級数その2)の形は指数型母関数を求める際によく出現する。

【問題5】\(\{1,2,\ldots,N\}\) の順列 \(\{p_1,\ldots,p_N\}\) のうちちょうど \(N-K\) 個の \(i\) について \(i \neq p_i\) が成り立つ場合の数を求めよ。(出典:ARC009 問題C

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

【問題6】\(K\) 個のラベル付きボールを \(N\) 個のラベル付き箱に入れる。全ての箱にボールが入っている入れ方は何通りあるか。

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

【問題7】\(K\) 個のラベル付きボールを \(N\) 個のラベル付き箱に入れる。ボールの入っていない箱を奇数個にする入れ方は何通りあるか。(出典:yukicoder No.1100

【解答】\(f\) を問題7で求めた級数、\(g=\)\(E_{odd}(x)\) とすると \(N![x^N] 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)$$ のサイズが \(|X|![x^{|X|}]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} となる。

例題

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

【問題8】\(N\) 個のラベル付きボールをいくつかの \(a,b,c\) 元集合に分ける方法は何通りか(\(a,b,c\) は互いに異なる)。

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

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

【問題9】\(N\) 個のラベル付きボールを非空なラベルなしグループに分ける方法は何通りか。(出典:Bell number)

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

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

【問題10】単純グラフにおけるラベル付き \(N\) 頂点サイクルの個数を求めよ。

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

【問題11】ラベル付き \(N\) 頂点をすべて使って複数のサイクル(単純グラフ)を生成する個数を求めよ。\(N\) 頂点ラベル付き2-正則グラフの個数を求めよと言い換えてもよい。

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

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

【問題12】\(N\) 頂点ラベル付き木の個数を求めよ。(出典:Cayley の定理)

【解答】\(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}\) が答え。

演習

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

【問題13】\(N\) 頂点ラベル付き森の個数を求めよ。

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

【問題14】\(N\) 頂点ラベル付き unicyclic graph(閉路をちょうど一つ持つ無向連結グラフ)の個数を求めよ。

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

【問題15】次の条件を満たすラベル付き多重グラフはいくつあるか:
  • 自己ループがない。
  • 頂点数 \(N\) 、辺数 \(M\) である。
  • 各頂点の次数が \(2\) 以下。
  • 各連結成分のサイズが \(L\) 以下。
(出典:ABC180 問題F

【解答】頂点数 \(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\) 個あれば良いから、\(N![x^N]\)\(E(A)E_{N-M}(B)\) が答え。

【問題16】\(N\) 頂点ラベル付き連結二部グラフの個数を求めよ。

【解答】\(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)\) より \(N![x^N] g(x) = N![x^N]\frac{1}{2}\log(f(x))\) が答え。

【問題17】自己辺・多重辺を許し、ラベル付き \(N\) 頂点全てを使って有向サイクルを複数作る。各有向サイクルの長さの \(M\) 乗 について積を取った値を全ての場合について和を取るといくつになるか。(出典:夏合宿2019 問題H

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

【問題18】 全ての \(N\) 頂点ラベル付き木について、各頂点の次数の総積の和を求めよ(出典:yukicoder No.1302 テスター解

【解答】Prüfer コード(問題1)を使った解法が明快だが、指数型母関数でもなんとか求めることができる。求める値を \(N![x^N]A^●(x)\) とする。問題12と同じように、木を「根 r 」と「根の子を新たに根とする部分木 T’」に分解する。この部分木 T’ を根 r に繋ぎなおすと T’ の根の次数が 1 増加する。そこで、根の次数のみ 1 加算して、次数の総積の和を数えた値を \(N![x^N]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)\neq\mathcal{A}(Y_1,\ldots,Y_m)\) 。

各 \(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!}$$と定める。

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

例題

【問題19】 余りが出ないように、男女をいくつかの組に分けたい。整数のペアいくつかからなる集合 \(S\) が与えられる。各組の男女の人数 \(a,b\) は \((a,b) \in S\) である。男女が与えられた時のあり得る組み分けの指数型母関数を求めよ。

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

【問題20】 青、青、黄のラベル付き頂点がある。赤、青、黄の頂点をそれぞれ部集合とする3部グラフのうち、連結なものを数えたい。赤、青、黄の頂点が与えられたときの指数型母関数を求めよ。

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

【問題21】 グラフ \(G\) が与えられる。すべての誘導部分グラフ \(G[S]\) に対して、\(G[S]\) の全域部分グラフの個数を求めよ。(出典:熨斗袋さん

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

参考文献

代入が強力で面白かったです。母関数(wikipedia)を見ると他にも色々な母関数の形式があるようです。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA