数列の母関数の意味とその応用例

カタラン数の母関数を $f(x)=\displaystyle\sum_{k=0}^{\infty} c_k x^k$ とおく。

$f(x)^2$ の $x^n$ の係数は $\displaystyle\sum_{i=0}^nc_{i}c_{n-i}$ となるので漸化式が使える：

$$\begin{aligned} f(x)^2 &= \sum_{n=0}^{\infty} \left( \sum_{i=0}^nc_{i}c_{n-i} \right) x^n\\ &= \sum_{n=0}^{\infty}c_{n+1}x^n\\ &= \dfrac{\displaystyle\sum_{n=0}^{\infty}c_{n+1}x^{n+1}}{x}\\ &= \dfrac{f(x)-1}{x} \end{aligned}$$

よって，$f(x)$ についての2次方程式

$$f(x)^2x-f(x)+1=0$$

を得る。これを $x \neq 0$ の範囲で解いて，

$$f(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}$$

ただし，初期条件 $f(0)=c_0=1$ であり，$x=0$ で関数が連続になる必要があるため符号がマイナスの方が採用される。

よって，カタラン数の母函数は $$\dfrac{1 - \sqrt{1-4x}}{2x}$$ である。

$\sqrt{1-4x}$ の $n+1$ 回微分係数 $f^{(n+1)}(0)$ を求める：

$$\begin{aligned} &f^{(n+1)} (0)\\ &=(-4)^{n+1} \dfrac{1}{2} \left(-\dfrac{1}{2}\right) \left(-\dfrac{3}{2} \right) \cdots \left( -\dfrac{2n-1}{2} \right)\\ &= -2^{n+1} (2n-1)(2n-3) \cdots 3 \cdot 1\\ &= -2\dfrac{(2n)!}{n!} \end{aligned}$$

よって，$\sqrt{1-4x}$ をマクローリン展開した時の $n+1$ 乗の係数は $-2\dfrac{(2n)!}{(n+1)!n!}$ となり，

$f(x)$ を展開したときの $x^n$ の係数は，

$$\dfrac{(2n)!}{(n+1)!n!} = \dfrac{1}{n+1}{}_{2n}\mathrm{C}_n$$

となりカタラン数の一般項となる。