生成函数

标签：... 函数 2x 生成 cfrac 数列

《组合数学》 2.2

定义

生成函数，也就是母函数，是为了求数列的通项公式。

对于数列 \(C_0,C_1,C_2,...\)，构造函数

\[G(x) = C_0 x^0 + C_1 x^1 + ... \]

生成函数和原数列一一对应。
其中数列的长度可以有限，也可以无限。

具体怎么用呢？

河内塔问题

递推式我们求出来了是 \(H_i = 2H_{i-1} + 1\)。
特别地 \(H_0 = 0\)。
考虑 \(H\) 的生成函数 \(G(x) = H_0 x^0 + H_1 x^1 + ...\)
考虑

\[H_1 x = (2H_0 + 1) x \\ H_2 x^2 = (2H_1 + 1) x^2 \\ ... \]

左右两边分别求和，得到
\(G(x) = 2xG(x) + (x + x^2 + ...)\)
我们有 \(\cfrac{1}{1-x} = (1 + x + x^2 + ...)\)，这个式子对生成函数的转化有极大用处。

继续转化， \((1-2x)G(x) = x \times \cfrac{1}{1-x}\)，\(G(x) = \cfrac{x}{(1-x)(1-2x)}\)。

现在母函数求出来了，考虑怎么求出原数列。目标是还原成接近 \(\cfrac{1}{1-x}\) 的形式，从而能够回去。

考虑 \(G(x) = \cfrac{A}{1-x} + \cfrac{B}{1-2x}\)，待定系数法得 \(A = -1,B= 1\)。于是 \(G(x) = \cfrac{1}{1-2x} - \cfrac{1}{1-x} = (1+2x+2^2x^2+...) - (1+x+x^2+...)\)

因此 \(H_i = 2^i - 1\)。

标签：...,函数,2x,生成,cfrac,数列
From： https://www.cnblogs.com/Zeardoe/p/16935953.html