MathLabs

組合せ論と離散数学

母関数

数列を係数として符号化するべき級数で、組合せ論の問題を代数の問題に変える。

直観母関数とは何か

無限に多くのペグが 0,1,2,3,…0, 1, 2, 3, \dots と番号付けされた物干しロープを想像してほしい。数列 a0,a1,a2,…a_0, a_1, a_2, \dots を表すには、nn 番目のペグに数 ana_n を吊るす。母関数とは、この物干しロープをひとつの代数的対象として書き直したものであり、数 ana_n はべき級数における xxn^n の係数になる。変数 xx に数値を代入することはなく、各項を自分の場所に保持するだけであり、そのおかげで数列の足し算・掛け算・シフトが多項式の普通の代数演算になる。

生成関数 $\frac{1}{1-x}$ を近似する三次式 $1+x+x^2+x^3$ のグラフ。
この曲線は三次式 1+x+x2+x31+x+x^2+x^3 であり、11−x=∑n=0∞xn\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n の最初の4項、つまり定数列 an=1a_n=1 の母関数である。各係数(a,b,c,da,b,c,d をドラッグ)は数列の1つのペグが曲線に詰め込まれたものである。

中高数列をべき級数に詰め込む

定義: 通常型母関数

数列 a0,a1,a2,…a_0, a_1, a_2, \dots の通常型母関数(OGF)とは、形式的べき級数 G(x)=∑n=0∞anxnG(x)=\sum_{n=0}^{\infty}a_nx^n のことである。「形式的」とは、この和を数値的に評価する関数としてではなく、代数的な式として扱うという意味であり、xx の特定の値における収束の問題は組合せ論には関係しない。

G(x)=∑n=0∞anxnG(x)=\sum_{n=0}^{\infty}a_nx^n

最も単純な構成要素は、すべての n≥0n \ge 0 に対する数列 an=1a_n=1 であり、その母関数は等比級数 11−x=∑n=0∞xn\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n である。この等式は母関数を用いるほとんどの議論の原動力であり、11−x\frac{1}{1-x} が「無制限に供給される中から nn 個を順序を問わず1通りずつ選ぶ」ことを符号化していることを意味する。

1(1−x)2=∑n=0∞(n+1)xn\frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}(n+1)x^n
よく使われる数列とその母関数
数列母関数
定数、an=1a_n=111−x\frac{1}{1-x}
線形、an=n+1a_n=n+11(1−x)2\frac{1}{(1-x)^2}
フィボナッチ、an=Fna_n=F_nx1−x−x2\frac{x}{1-x-x^2}
二項係数の行、an=(kn)a_n=\binom{k}{n}(1+x)k(1+x)^k

大学漸化式から閉じた形へ

定理: フィボナッチ母関数の閉じた形

F0=0, F1=1F_0=0,\ F_1=1 とし、n≥2n\ge2 に対して Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} とする。このとき通常型母関数 F(x)=∑n=0∞FnxnF(x)=\sum_{n=0}^{\infty}F_nx^n は F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2} に等しい。

なぜ正しいのか?

係数が定数の線形漸化式は、xxn^n を掛けてすべての nn について和を取れば、常に単純な代数(実際には有理)方程式になる — 漸化式は xx の多項式を掛ける操作になる。

証明

漸化式 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}(n≥2n\ge2 で成立)に xnx^n を掛けて n≥2n\ge2 について和を取る: ∑n≥2Fnxn=∑n≥2Fn−1xn+∑n≥2Fn−2xn\sum_{n\ge2}F_nx^n=\sum_{n\ge2}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n。

左辺は F(x)−F0−F1x=F(x)−xF(x)-F_0-F_1x=F(x)-x である。右辺の最初の和は x∑n≥2Fn−1xn−1=x∑m≥1Fmxm=x(F(x)−F0)=xF(x)x\sum_{n\ge2}F_{n-1}x^{n-1}=x\sum_{m\ge1}F_mx^m=x(F(x)-F_0)=xF(x) となる。2番目の和は x2∑n≥2Fn−2xn−2=x2∑k≥0Fkxk=x2F(x)x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2\sum_{k\ge0}F_kx^k=x^2F(x) となる。

よって F(x)−x=xF(x)+x2F(x)F(x)-x=xF(x)+x^2F(x)、すなわち (1−x−x2)F(x)=x(1-x-x^2)F(x)=x が成り立つ。

F(x)F(x) について解くと F(x)(1−x−x2)=xF(x)(1-x-x^2)=x となり、したがって F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2} が得られる。これは無限に続くフィボナッチ数列全体を詰め込んだ、ただ1つの有理関数である。

定理: 部分分数分解によるビネの公式

φ=1+52\varphi=\frac{1+\sqrt{5}}{2} および ψ=1−52\psi=\frac{1-\sqrt{5}}{2} とすると、1−x−x21-x-x^2 の根から、すべての n≥0n\ge0 に対する閉じた式 Fn=15(φn−ψn)F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right) が得られる。

なぜ正しいのか?

分母が相異なる一次因子を持つ有理型母関数はすべて、単純な等比級数の和に分解でき、各等比級数から係数の明示的な公式が直接読み取れる。

証明

分母を因数分解する:1−x−x2=01-x-x^2=0 の根は x=1/φx=1/\varphi と x=1/ψx=1/\psi であるから、1−x−x2=(1−φx)(1−ψx)1-x-x^2=(1-\varphi x)(1-\psi x) が成り立つ。

x1−x−x2=A1−φx+B1−ψx\frac{x}{1-x-x^2}=\frac{A}{1-\varphi x}+\frac{B}{1-\psi x} と定数 A,BA,B で書く。分母を払い、定数項と xx の係数を比較すると、A=15A=\frac{1}{\sqrt5}、B=−15B=-\frac{1}{\sqrt5} を解とする連立方程式が得られ、x1−x−x2=15(11−φx−11−ψx)\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x}-\frac{1}{1-\psi x}\right) となる。

各項を等比級数として展開する:11−φx=∑n≥0φnxn\frac{1}{1-\varphi x}=\sum_{n\ge0}\varphi^nx^n、11−ψx=∑n≥0ψnxn\frac{1}{1-\psi x}=\sum_{n\ge0}\psi^nx^n。

両辺の xnx^n の係数を読み取ると、ビネの公式として知られる Fn=15(φn−ψn)F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right) が得られる。

大学実世界での応用と具体例

母関数は理論的な興味の対象であるだけでなく、実用的な道具でもある。計算機科学者は再帰的アルゴリズムの正確な、また漸近的な実行時間を求めるために母関数を使い、物理学者は統計力学において密接に関連する分配関数を使い、確率論者は確率分布全体を母関数として符号化し、和を取る代わりに微分することでモーメントを計算する。

例: 2種類の硬貨での両替

11単位硬貨と22単位硬貨を無制限に使って、硬貨の順序を問わず金額 44 を作る方法は何通りあるか。

解答

金額を作るそれぞれの方法は、11単位硬貨と22単位硬貨をそれぞれ何枚使うかの選択であるから、母関数は 11単位硬貨の母関数 11−x\frac{1}{1-x} と 22単位硬貨の母関数 11−x2\frac{1}{1-x^2} の積であり、組み合わせた母関数は 1(1−x)(1−x2)\frac{1}{(1-x)(1-x^2)} となる。

2つの因子を等比級数として展開し、掛け合わせる:(∑i≥0xi)(∑j≥0x2j)\left(\sum_{i\ge0}x^i\right)\left(\sum_{j\ge0}x^{2j}\right)。x4x^4 の係数は i+2j=4i+2j=4、i,j≥0i,j\ge0 を満たす組 (i,j)(i,j) の個数を数える。

有効な組は (4,0)(4,0)、(2,1)(2,1)、(0,2)(0,2) であり、したがって 33 通りある:11単位硬貨4枚、11単位硬貨2枚と22単位硬貨1枚、22単位硬貨2枚。

例: 母関数からビネの公式へ

閉じた式 F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2} とビネの公式 Fn=15(φn−ψn)F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right) を使って、F0,…,F4F_0,\dots,F_4 を順に列挙せずに F5F_5 を直接計算せよ。

解答

上の定理により、φ=1+52\varphi=\frac{1+\sqrt{5}}{2} と ψ=1−52\psi=\frac{1-\sqrt{5}}{2} はビネの公式 Fn=15(φn−ψn)F_n=\frac{1}{\sqrt{5}}\left(\varphi^n-\psi^n\right) に用いる根である。

数値的には φ≈1.618\varphi\approx1.618、ψ≈−0.618\psi\approx-0.618 であるから、φ5≈11.09\varphi^5\approx11.09、ψ5≈−0.09\psi^5\approx-0.09 となる。

よって F5=15(φ5−ψ5)≈15(11.09−(−0.09))=11.185≈5F_5=\frac{1}{\sqrt5}(\varphi^5-\psi^5)\approx\frac{1}{\sqrt5}(11.09-(-0.09))=\frac{11.18}{\sqrt5}\approx5 となる。

実際に F5=5F_5=5 であり、漸化式 0,1,1,2,3,50,1,1,2,3,5 を反復して得られる値と一致する — しかしビネの公式を使えば、それ以前の項を計算せずに任意の FnF_n に直接到達できる。

すべての n≥0n\ge0 に対する定数列 an=1a_n=1 の通常型母関数は何か。

1(1−x)2\frac{1}{(1-x)^2} における x3x^3 の係数はいくつか。

次のうち、母関数を使うのが最も自然な問題はどれか。

フィボナッチ数列の母関数 F(x)=∑FnxnF(x)=\sum F_nx^n はどの閉じた式を満たすか。

参考文献

  1. Herbert S. Wilf (1994). generatingfunctionology
  2. Philippe Flajolet, Robert Sedgewick (2009). Analytic Combinatorics