組み合わせと母関数 - tkenichi の日記

M.m. さんの日記に触発されて少し調べた。人の日記のコメントで議論を続けるのはやめて、自分の日記にまとめておこう。

普通は関数をべき級数展開してその係数として数列が現れるが、逆に数列が与えられたときにそれをべき級数の係数に持つような関数を考える。それを数列の母関数という。

有名なものをいくつか。

組み合わせ

$\sum_{i=0}^{n} \. {}_n \mathrm{C}_i x^{i} = (1+x)^{n}$

ベルヌイ数

$\sum_{n=0}^{\infty} B_n \frac{x^{n}}{n!} = \frac{x}{e^{x}-1}$
ただし $|B_n|$ や $|B_{2n}|$ をベルヌイ数とする流儀もあるみたい。

分割数

$1 + \sum_{n=1}^{\infty} \rho_n x^{n} = $ \prod_{n=1}^{\infty} (1-x^{n}) $^{-1}$
これは同じものn個を空でない組に分けるわけ方の総数。この公式はオイラーが見つけたらしい。

Bell Number

$\sum_{n=0} B(n) \frac{x^{n}}{n!} = \exp(e^{x}-1)$
これは異なるn個を空でない組に分けるわけ方の総数。たとえば n = 3 なら、{{a,b,c}},{{a},{b,c}},{{b},{c,a}},{{c},{a,b}},{{a},{b},{c}} の5通り。これの満たす微分方程式は $y' = e^{x}y$ だから、これの n 次の項を比較して、
$B(n+1) = \sum_{k=0}^{n} \. {}_n \mathrm{C}_k B(k)$
という漸化式が出る。

M.m. さんが日記で取り上げていた問題は、異なるn個を等号を含めて順序をつけるつけ方の総数。たとえば n = 3 なら、

a=b=c
a<b=c b<c=a c<a=b
a=b<c b=c<a c=a<b
a<b<c b<c<a c<a<b a<c<b c<b<a b<a<c

の合計13通り。この数を A(n) とすると、A(0) = 1 として、
$\sum_{n=0}^{\infty} A(n) \frac{x^{n}}{n!} = \frac{1}{2-e^{x}}$
が成り立つ。
$y-1 = y(e^{x}-1)$ と変形してから両辺の n 次の係数を比較して、
$A(n) = \sum_{i=0}^{n-1} \. {}_n \mathrm{C}_{i} A(i)$
という漸化式を得る。もちろんこの漸化式の方を先に見つけた。