生成函数

斐波那契生成函数
将数列的项映射到多项式,就构成了最简单的生成函数,对于斐波那契数列 FF

F(x)=F0+F1x+F2x2+=n0Fnxn\displaystyle F(x) = F_0 + F_1x + F_2x^2 + \cdots = \sum_{n \geqslant 0} F_nx^n

F(x)=F0+F1x+F2x2+F3x3+F4x4+F5x5+xF(x)=F0x+F1x2+F2x3+F3x4+F4x5+x2F(x)=F0x2+F1x3+F2x4+F3x5+\begin{aligned} F(x) = F_0 + F_1x + &F_2x^2 + F_3x^3 + F_4x^4 + F_5x^5 + \cdots \\ xF(x) =\quad F_0x + &F_1x^2 + F_2x^3 + F_3x^4 + F_4x^5 + \cdots \\ x^2F(x) = \quad \quad &F_0x^2 + F_1x^3 + F_2x^4 + F_3x^5 + \cdots \end{aligned}

注意到 F0=0F_0 = 0,并且 Fi=Fi1+Fi2F_i = F_{i-1} + F_{i-2}
F(x)xF(x)x2F(x)=(F1F0)x=xF(x) - xF(x) - x^2F(x) = (F_1 - F_0)x = x

生成函数为 F(x)=x1xx2\displaystyle F(x) = \frac{x}{1 - x - x^2}

熟练的话,根据递推 an=an1+an2a_n = a_{n-1} + a_{n-2} 可以推出
[xn]F(x)=x[xn1]F(x)+x2[xn2]F(x),n2\displaystyle [x^n]F(x) = x\cdot [x^{n-1}]F(x) + x^2 \cdot [x^{n-2}]F(x), \quad n \geqslant 2
特别注意,此时序列不包括 <x0,x1>\left<x^0, x^1 \right> 的项,减去对应的项即可
[xn]F(x)F0F1x=(x[xn1]F(x)F0x)+(x2[xn2]F(x))\displaystyle [x^n]F(x) - F_0 - F_1x = \left(x \cdot [x^{n-1}]F(x) - F_0x \right) + \left( x^2 \cdot [x^{n-2}]F(x) \right)

F(x)=xF(x)+x2F(x)+(F1F0)x\displaystyle F(x) = xF(x) + x^2F(x) + (F_1 - F_0)x

问题描述
2×12 \times 1 的多米诺骨牌完全覆盖 2×n2 \times n 的矩形,有多少种不同的方式
n=0n = 0 时候的方案数为 a0a_0n=1n = 1 方案数为 a1a_1,以此类推,那么将方案数 aiaixia_i \to a_ix^{i}
映射成多项式的系数,转为研究 f(x)=i=1naixif(x) = \displaystyle\sum_{i = 1}^{n} a_ix^{i}
f(x)f(x) 称为序列 <a0,a1,a2,an>\left<a_0, a_1, a_2, \cdots a_n \right> 的生成函数

不仅如此,序列 <a0,a1,a2,,an>\left<a_0, a_1, a_2, \cdots, a_n\right> 还可以表示斐波那契数,斯特林数,卡特兰数等等

以二项式举例,<(r0),(r1),(r2),>\displaystyle \left<\binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \cdots \right> 生成函数为

(1+x)r=k0(rk)xk(1+x)^{r} = \displaystyle\sum_{k \geqslant 0} \binom{r}{k} x^{k},同理,(1+x)s=k0(rs)xs(1+x)^{s} = \displaystyle\sum_{k \geqslant 0} \binom{r}{s} x^{s}

nr+sn \leftarrow r+s,可以推出 (1+x)r(1+x)s=(1+x)r+s(1+x)^{r}(1+x)^{s} = (1+x)^{r+s},对应到生成函数,对应到数列第 nnxnx^n 的系数

k0n(rk)(snk)=(r+sn)\sum_{k \geqslant 0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}

这就是范德蒙德卷积

回到一开始的问题
不妨记 nn 所对应的方案数为 dp(n)dp(n),那么根据第一列骨牌的摆放方式,可以竖着也可以横着
如果竖着放 11 个骨牌,剩下的方案数对应 dp(n1)dp(n-1),如果横着放 22 个,方案数为 dp(n2)dp(n-2)
dp(n)=dp(n1)+dp(n2)dp(n) = dp(n-1) + dp(n-2),显然是一个斐波那契数列

斐波那契数对应 a0=1,a1=1,a2=1,an=an2+an1a_0 = 1, a_1 = 1, a_2 = 1, a_{n} = a_{n-2} + a_{n-1},求出生成函数为
f(x)=x1xx2f(x) = \displaystyle\frac{x}{1-x-x^2},原问题对应的方案数 dp(n)=Fn+1dp(n) = F_{n+1}

记生成函数 f(x)f(x)xnx^{n} 的系数为 [xn]f(x)[x^{n}]f(x),那么有 x1xx2=k=0n[xk]f(x)xk\displaystyle\frac{x}{1-x-x^2} = \sum_{k = 0}^{n} [x^{k}]f(x) \cdot x^{k}

原问题对应 xkxk+1x^{k} \leftarrow x^{k+1},那么有 x1xx2=[xk+1]f(x)\displaystyle\frac{x}{1-x-x^2} = \sum [x^{k+1}]f(x),可以得到

11x(x)2=[xk]f(x)\displaystyle\frac{1}{1-x'-(x')^2} = \sum [{x'}^{k}]f(x'),该问题的生成函数为 f(x)=11xx2f(x) = \displaystyle\frac{1}{1-x-x^2}

多米诺骨牌问题

实际上,探讨 3×n3 \times n 的多米诺覆盖问题
gen-func-01
gen-func-02

根据是否允许使用竖着的牌,可以将方案数分为两类,一类是仅允许使用横着的骨牌,另一类是允许使用竖着的骨牌
这两种方案,分别对应到填满 3×n3 \times n 完整的矩形 UnU_n ,和填满 3×n3 \times n 但缺一个角的矩形 VnV_n

如上图所示,有如下递推成立

U0=1,U1=0V0=0,V1=1Un=Un2+2Vn1, Vn=Vn2+Un1, n2\begin{aligned} &U_0 = 1, U_1 = 0 \\ &V_0 = 0, V_1 = 1 \\ &U_n = U_{n-2} + 2V_{n-1}, \ V_n = V_{n-2} + U_{n-1}, \ n \geqslant 2 \end{aligned}

求解生成函数
这一步用的策略也比较简单,假设说序列 <an>\left<a_n\right> 对应的生成函数是 f(x)f(x),如果有 bn=an2b_n = a_{n-2}
那么求解 bnb_n 的生成函数 g(x)g(x) 的时候,有 g(x)=x2f(x)g(x) = x^2 \cdot f(x),形式化表述为
[xn]g(x)=[xn2]f(x)[x^n]g(x) = [x^{n-2}]f(x),即 [xn2]g(x)x2=[xn2]f(x)\displaystyle [x^{n-2}]\frac{g(x)}{x^2} = [x^{n-2}]f(x)
于是有 [xn2]g(x)=[xn2](x2f(x))[x^{n-2}] g(x) = [x^{n-2}] \left(x^2f(x)\right),可以推出 g(x)=x2f(x)g(x) = x^2 f(x)

首先,将多米诺骨牌的递推写成对所有 nn 的形式
Un=2Vn1+Un2+[n=0],Vn=Un1+Vn2U_n = 2V_{n-1} + U_{n-2} + [n = 0], \quad V_n = U_{n-1} + V_{n-2}
对应的生成函数有
U(x)=2xV(x)+x2U(x)+1,V(x)=xU(x)+x2V(x)U(x) = 2xV(x) + x^2U(x) + 1, \quad V(x) = xU(x) + x^2V(x)

根据等式可以推出 U(x)=1x214x2+x4, V(x)=x14x2+x4\displaystyle U(x) = \frac{1-x^2}{1-4x^2 + x^4}, \ V(x) = \frac{x}{1-4x^2 + x^4}

根据 114x2+x4\displaystyle\frac{1}{1-4x^2 + x^4} 展开,是关于 x2x^2 的幂级数

根据生成函数可以发现,U(x)U(x) 是关于 x2x^2 的,也就是说 U2k+1=0U_{2k+1} = 0V(x)V(x) 是关于 x2xx^2 \cdot x 的,也就是说 V2n=0V_{2n} = 0

展开生成函数
这里可以令 W(x2)=114x2+x4\displaystyle W(x^2) = \frac{1}{1-4x^2+x^4},我们有 U(x)=(1x2)W(x2), V(x)=xW(x2)U(x) = (1-x^2)W(x^2), \ V(x) = xW(x^2)

如果令 y=x2y = x^2,那么 (1x2)W(x2)=W(y)yW(y)(1-x^2)W(x^2) = W(y) - yW(y),对于 yny^n,右边有 [yn]W(y)y[yn1]W(y)[y^n]W(y) - y\cdot[y^{n-1}]W(y)
左边呢?因为 yn=x2ny^{n} = x^{2n},所以 [x2n]U(x)=[yn]W(y)y[yn1]W(y)[x^{2n}]U(x) = [y^{n}]W(y) - y\cdot[y^{n-1}]W(y)

所以我们有 U2n=WnWn1U_{2n} = W_{n} - W_{n-1},同理 [x2n+1]V(x)=[yn]W(y)[x^{2n+1}]V(x) = [y^n]W(y),即 V2n+1=WnV_{2n+1} = W_{n}

那么研究 W(x)W(x) 及其展开即可,14x+x2=(1ϕx)(1ϕ^x)1-4x + x^2 = (1-\phi x)(1-\hat{\phi} x),求出 ϕ=2+3, ϕ^=23\phi = 2+\sqrt{3}, \ \hat{\phi} = 2-\sqrt{3}

由此,我们有 V2n+1=Wn=3+236(2+3)n+3236(23)n\displaystyle V_{2n+1} = W_{n} = \frac{3+2\sqrt{3}}{6}(2+\sqrt{3})^n + \frac{3-2\sqrt{3}}{6}(2-\sqrt{3})^n

U2n=WnWn1=3+36(2+3)n+336(23)n=(2+3)n33+(23)n3+3\displaystyle U_{2n} = W_n - W_{n-1} = \frac{3+\sqrt{3}}{6}(2+\sqrt{3})^n + \frac{3-\sqrt{3}}{6}(2-\sqrt{3})^n = \frac{(2+\sqrt{3})^n}{3-\sqrt{3}} + \frac{(2-\sqrt{3})^n}{3+\sqrt{3}}

注意到 (23)n3+3(0,1)\displaystyle\frac{(2-\sqrt{3})^n}{3+\sqrt{3}} \in (0, 1),关于 U2nU_{2n} 的表达式简化为

U2n=(2+3)n33, n0U_{2n} = \displaystyle \left\lceil \frac{(2+\sqrt{3})^n}{3-\sqrt{3}} \right\rceil, \ n \geqslant 0
正确的答案是取离 U2nU_{2n} 最近的整数得到

换零钱问题

5050 美分的方案数,假设必须使用 11 美分,55 美分,11 角(1010 美分),2525 美分以及 5050 美分硬币支付
假设只允许使用 11 美分的硬币,此时的方案数为 PP
P=+<1>+<1><1>+<1><1><1>+<1><1><1><1>+=+<1>+<1>2+<1>3+<1>4+\begin{aligned}\displaystyle P &= \not 1 + \left< 1 \right> + \left< 1 \right>\left< 1 \right> + \left< 1 \right>\left< 1 \right>\left< 1 \right> + \left< 1 \right>\left< 1 \right>\left< 1 \right>\left< 1 \right> + \cdots \\ &= \not 1 + \left< 1 \right> + \left< 1 \right> ^2 + \left< 1 \right> ^3 + \left< 1 \right> ^ 4 + \cdots \end{aligned}

其中每一项表示用几个 11 美分硬币,如果允许使用 55 美分呢?
实际上,对于每一种方案,我们要乘以 (P1)\displaystyle\binom{P}{1},每一种 55 美分的选择方案,都可以对应到 PP11 美分的方案任意选一种

55美分的方案数记为 NN,那么
N=P+<5>P+<5><5>P+<5><5><5>P+<5><5><5><5>P+=(+<5>+<5>2+<5>3+<5>4+)P\displaystyle\begin{aligned} N &= P + \left< 5 \right> P + \left< 5 \right>\left< 5 \right> P + \left< 5 \right>\left< 5 \right>\left< 5 \right> P + \left< 5 \right>\left< 5 \right>\left< 5 \right>\left< 5 \right>P + \cdots \\ &= (\not 5 + \left< 5 \right> + \left< 5 \right> ^2 + \left< 5 \right> ^3 + \left< 5 \right> ^4 + \cdots) P \end{aligned}

以此类推,1010 美分的方案记为 DD2525 美分的方案记为 QQ5050 美分的方案记为 CC,注意这里的方案是向下兼容的
比如你能用 1010 美分的,也能用 11 美分,55 美分的,但不能够用 2525 美分的

D=(1̸0+<10>+<10>2+<10>3+<10>4+)ND = (\not{10} + \left< 10 \right> + \left< 10 \right>^2 + \left< 10 \right>^3 + \left< 10 \right>^4 + \cdots) N
Q=(2̸5+<25>+<25>2+<25>3+<25>4+)DQ = (\not{25} + \left< 25 \right> + \left< 25 \right>^2 + \left< 25 \right>^3 + \left< 25 \right>^4 + \cdots) D
C=(5̸0+<50>+<50>2+<50>3+<50>4+)QC = (\not{50} + \left< 50 \right> + \left< 50 \right>^2 + \left< 50 \right>^3 + \left< 50 \right>^4 + \cdots) Q

问题就转换成为求解 CC 中恰好值 5050 美分的项数
考虑使用生成函数,用 xx 替代 <1>\left< 1 \right>x50x^{50} 替代 <50>\left< 50 \right>,这样购买 1313 美分的方案数为
(<1>13),(<5>1,<1>8),(<5>2,<1>3),(<10>1,<1>3)(\left<1\right>^{13}), (\left<5\right>^1, \left<1\right>^8), (\left<5\right>^2, \left<1\right>^3), (\left<10\right>^1, \left<1\right>^3)
对应的 x13x^{13} 的系数是 44,综上所述
P=1+x+x2+x3+x4+\displaystyle P = 1+x+x^2+x^3+x^4+\cdots
N=(1+x5+x10+x15+x20+)P\displaystyle N = (1+x^5+x^{10}+x^{15}+x^{20}+\cdots)P
D=(1+x10+x20+x30+x40+)N\displaystyle D = (1+x^{10}+x^{20}+x^{30}+x^{40}+\cdots)N
Q=(1+x25+x50+x75+x100+)D\displaystyle Q = (1+x^{25}+x^{50}+x^{75}+x^{100}+\cdots)D
C=(1+x50+x100+x150+x200+)Q\displaystyle C = (1+x^{50}+x^{100}+x^{150}+x^{200}+\cdots)Q

显然 Pn=1P_n = 1,另外可以知道 Nn=n/5+1N_n = \lfloor n/5 \rfloor + 1NnN_n 对应支付 nn 美分的方案数
可以使用的 55 美分有 (0,1,2,,n/5)(0, 1, 2, \cdots, \lfloor n/5 \rfloor) 个,55 美分的方案数对应 n/5+1\lfloor n/5 \rfloor + 1
剩下 11 美分的方案数是唯一的

注意到 1+xm+x2m+=1/(1xm)1+x^m+x^{2m}+\cdots = 1/(1-x^{m}),可以知道
P=1/(1x)P = 1/(1-x)
N=P/(1x5)N = P/(1-x^5)
D=N/(1x10)D = N/(1-x^{10})
Q=D/(1x25)Q = D/(1-x^{25})
C=Q/(1x50)C = Q/(1-x^{50})

可以化为
P=1+xPP = 1+xP
N=P+x5NN = P + x^5N
D=N+x10DD = N + x^{10}D
Q=D+x25QQ = D + x^{25}Q
C=Q+x50CC = Q + x^{50}C

展开生成函数,可以知道 [xn]P(x)=x[xn1]P(x)+[n=0][x^n]P(x) = x \cdot [x^{n-1}]P(x) + [n = 0]
[xn]N(x)=[xn]P(x)+x5[xn5]N(x)[x^n]N(x) = [x^n]P(x) + x^{5}\cdot [x^{n-5}]N(x),以此类推
Pn=Pn1+[n=0]P_n = P_{n-1} + [n=0]
Nn=Nn5+PnN_n = N_{n-5} + P_n
Dn=Dn10+NnD_n = D_{n-10} + N_n
Qn=Qn25+DnQ_n = Q_{n-25} + D_n
Cn=Cn50+QnC_n = C_{n-50} + Q_n

这样可以递归的来求,比如说 Qn=Dn+Dn25+Dn50+Dn75+Q_n = D_{n} + D_{n-25} + D_{n-50} + D_{n-75} + \cdots

其实 CnC_n 的封闭形式也很好求,注意到
(1x)P=1(1-x)P = 1
(1x5)N=P(1-x^5)N = P
(1x10)D=N(1-x^{10})D = N
(1x25)Q=D(1-x^{25})Q = D
(1x50)C=Q(1-x^{50})C = Q

两边全部乘起来,得到 C=11x11x511x1011x2511x50C = \displaystyle\frac{1}{1-x}\frac{1}{1-x^5}\frac{1}{1-x^{10}}\frac{1}{1-x^{25}}\frac{1}{1-x^{50}}

实际上,1(1x)(1x2)(1x3)\displaystyle\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}xnx^{n} 的系数为 p(n)p(n),对应 nn划分的个数

nn 的一个划分,即将 nn 表示成正整数之和,不考虑顺序

生成函数展开策略

基本展开

二项式展开
二项式比较值得注意的恒等式有如下两种

1(1x)n+1=k0(n+kn)xk\frac{1}{(1-x)^{n+1}} = \sum_{k \geqslant 0} \binom{n+k}{n} x^{k}

这个式子的证明也比较容易,可以通过反转上指标得到,反转上指标的公式如下
rk=r(r1)(rk+1)=(1)k(r)(r+1)(k1r)=(1)k(k1r)k\displaystyle \begin{aligned}r^{\underline{k}} &= r(r-1)\cdots (r-k+1) \\ &=(-1)^{k}(-r)(-r+1)\cdots (k-1-r) = (-1)^{k}(k-1-r)^{\underline{k}}\end{aligned}
反转上指标的规则是

(rk)=(1)k(kr1k)\binom{r}{k} = (-1)^{k} \binom{k-r-1}{k}

有了这个规则,实际上 (1x)n1(1-x)^{-n-1} 的展开 xkx^k 系数本来是 (1)k(n1k)\displaystyle(-1)^k\binom{-n-1}{k},反转上指标后 (n+kk)\displaystyle \binom{n+k}{k}
很容易得到上式

另外,如果将上述展开式两边同时 ×xn\times x^{n},就得到以下推广

xn(1x)n+1=k0(kn)xk\frac{x^{n}}{(1-x)^{n+1}} = \sum_{k \geqslant 0} \binom{k}{n} x^{k}

待定系数展开
对于斐波那契生成函数 f(x)=x1xx2f(x) = \displaystyle \frac{x}{1-x-x^2},分母二次式可以写成 (1αx)(1βx)(1-\alpha x)(1-\beta x) 形式

x1xx2=A1αx+B1βx\displaystyle \frac{x}{1-x-x^2} = \frac{A}{1-\alpha x} + \frac{B}{1-\beta x},求解待定系数即可

接下来将 A1αx+B1βx\displaystyle\frac{A}{1-\alpha x} + \frac{B}{1-\beta x} 展开成幂级数,k0akxk\displaystyle \sum_{k \geqslant 0}a_k x^k
对应的第 kk 项即为 ak=[xk]f(x)a_k = [x^{k}]f(x)

展开求解,容易发现 α,β\alpha, \beta 分别是 x2x+1=0x^2-x+1=0 的两个根,α=1+52,β=152\alpha = \displaystyle\frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}
ϕ=1+52,ϕ^=152\phi = \displaystyle\frac{1 + \sqrt{5}}{2}, \hat{\phi} = \displaystyle \frac{1-\sqrt{5}}{2},代入可知, A=BA = -B,且 A=15A = \displaystyle\frac{1}{\sqrt{5}}

综上所述,可以得到生成函数为 f(x)=15(11ϕx11ϕ^x)\displaystyle f(x) = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi x} - \frac{1}{1-\hat{\phi}x}\right)

展开成幂级数,对于第 nn 项斐波那契数,通项为 an=15(ϕnϕ^n)a_n = \displaystyle\frac{1}{\sqrt{5}} \left(\phi ^ n - \hat{\phi} ^ n\right)

基本策略

F(x),G(x)F(x), G(x) 分别为 <fn>,<gn>\left<f_n\right>, \left<g_n\right> 的生成函数,对于取负值的 nn,令 fn,gnf_n, g_n 均为 00

线性和
αF(x)+βG(x)=αnfnxn+βngnxn=n(αfn+βgn)xn\displaystyle\alpha F(x)+\beta G(x) = \alpha \sum_{n} f_nx^n + \beta \sum_n g_n x^n = \sum_{n}(\alpha f_n + \beta g_n) x^n
<αfn+βgn>\left< \alpha f_n + \beta g_n \right> 的生成函数就为 αF(x)+βG(x)\alpha F(x) + \beta G(x)

向右平移 mm
构造 <0,0,,0,g0,g1,>=<gnm>\left<0, 0, \cdots, 0, g_0, g_1, \cdots \right> = \left< g_{n-m} \right>,实际上,

xmG(x)=ngnxn+m=ngnmxn,m0\displaystyle x^m G(x) = \sum_{n} g_n x^{n+m} = \sum_{n} g_{n-m} x^n, \quad m \geqslant 0

向左平移 mm
我们需要减去前 mm 项,<gm,gm+1,gm+2,>=<gn+m>\left< g_m, g_{m+1}, g_{m+2}, \cdots \right> = \left< g_{n+m} \right>

G(x)g0g1xgm1xm1xm=nmgnxnm=n0gn+mxn\displaystyle \frac{G(x)-g_0 - g_1x - \cdots - g_{m-1}x^{m-1}}{x^m} = \sum_{n \geqslant m} g_n x^{n-m} = \sum_{n \geqslant 0} g_{n+m} x^n

这里因为 g0=g1==gm1=0g_0 = g_1 = \cdots = g_{m-1} = 0,所以成立

常数倍
G(cx)=ngn(cx)n=ncngnxn\displaystyle G(cx) = \sum_{n}g_n(cx)^n = \sum_{n} c^n g_n x^n
给出了 <cngn>\left< c^n g_n \right> 的生成函数

微分
G(x)=g1+2g2x+3g3x2+=n(n+1)gn+1xn\displaystyle G'(x) = g_1 + 2g_2x + 3g_3 x^2 + \cdots = \sum_{n}(n+1)g_{n+1}x^{n}
给出更普遍的形式

xG(x)=nngnxn\displaystyle xG'(x) = \sum_{n} n g_n x^n,这是 <ngn>\left< ng_n \right> 的生成函数

积分
0xG(t)dt=g0x+12g1x2+13g2x3+=n11ngn1xn\displaystyle\int_{0}^{x} G(t) {\rm d} t = g_0x + \frac{1}{2}g_1x^2 + \frac{1}{3} g_2x^3 + \cdots = \sum_{n \geqslant 1} \frac{1}{n} g_{n-1}x^n

向左平移,给出 <gn/n>\left< g_n / n \right> 的生成函数 0x(G(t)g0t)dt\displaystyle \int_{0}^{x} \left(\frac{G(t) - g_0}{t} \right) {\rm d} t

卷积
F(x)G(x)=n(kfkgnk)xn\displaystyle F(x)G(x) = \sum_{n} \left(\sum_{k} f_k g_{n-k}\right) x^n
注意到 k<0k < 0fk=0f_k = 0k>nk > ngnk=0g_{n-k} = 0,所以有 <fn>,<gn>\left< f_n \right>, \left< g_n \right> 卷积生成函数

n(k=0nfkgnk)xn=F(x)G(x)\displaystyle \sum_{n}\left(\sum_{k = 0}^{n} f_k g_{n-k}\right)x^n = F(x)G(x)

特殊卷积
F(x)=xmF(x) = x^m,此时求和式只有一项 fm=1f_m = 1,其他的 ff 均为 00,所以 ngnmxn=xmG(x)\displaystyle \sum_{n} g_{n-m} x^n = x^m G(x)

F(x)=11x=1+x+x2+F(x) = \displaystyle \frac{1}{1-x} = 1+x+x^2+\cdots
此时所有的 ff 均为 11,我们有

11xG(x)=n(k=0ngnk)xn=n(kngk)xn\displaystyle \frac{1}{1-x}G(x) = \sum_{n}\left(\sum_{k = 0}^{n}g_{n-k}\right)x^n = \sum_{n} \left(\sum_{k \geqslant n} g_k\right) x^n

1/(1x)1/(1-x) 乘以一个生成函数,得到原序列累加和数列的生成函数

常见的生成函数求解举例

fn=<1,1,1,>nxn=11xf_n = \left<1, 1, 1, \cdots \right> \longrightarrow \displaystyle \sum_{n} x^n = \frac{1}{1-x}

基于此,我们很容易求出其他生成函数

fn=<1,2,3,>=1+2x+3x2+=n(n+1)1xnf_n = \left<1, 2, 3, \cdots \right> = 1 + 2x + 3x^2 + \cdots = \displaystyle\sum_{n}(n+1)\cdot \bm{1}\cdot x^n
我们知道 gn=<1,1,>g_{n} = \left<1, 1, \cdots\right> 的生成函数是 G(x)=11xG(x) = \displaystyle \frac{1}{1-x}

根据前面微分生成函数,可以知道 fnf_n 的生成函数 F(x)=G(x)=1(1x)2\displaystyle F(x) = G'(x) = \frac{1}{(1-x)^2}

fn=<1,0,1,0,>f_n = \left<1, 0, 1, 0, \cdots \right>
注意到该序列只有偶次幂有贡献,令 xx2x \leftarrow x^2F(x)=11x2F(x) = \displaystyle \frac{1}{1-x^2}

取给定数列标号为偶数的项<g0,0,g2,0,g4,0,>\left<g_0, 0, g_2, 0, g_4, 0, \cdots \right> 有一般性的方法

G(x)+G(x)=ngn(1+(1)n)xn=2ngn[nmod2=0]xnG(x) + G(-x) = \displaystyle \sum_{n} g_n \left(1 + (-1)^n \right) x^n = 2 \sum_{n} g_n [n \bmod 2 = 0] x^n

G(x)+G(x)2=ng2nx2n\displaystyle \frac{G(x)+G(-x)}{2} = \sum_{n} g_{2n}x^{2n}

类似的,奇数项为

G(x)G(x)2=ng2n+1x2n+1\displaystyle \frac{G(x)-G(-x)}{2} = \sum_{n} g_{2n+1}x^{2n+1}

比如对斐波那契数列偶数项 <0,1,3,8,>\left<0, 1, 3, 8, \cdots \right> 求生成函数

nF2nx2n=12(x1xx2+x1+xx2)=x213x2+x4\displaystyle\sum_{n}F_{2n}x^{2n} = \frac{1}{2} \left(\frac{x}{1-x-x^2} + \frac{-x}{1+x-x^2} \right) = \frac{x^2}{1-3x^2 + x^4}

递归式求解

多项式除法

形如 R(x)=P(x)Q(x)\displaystyle R(x) = \frac{P(x)}{Q(x)}

研究 [xn]R(x)[x^n]R(x) 的形式,有一类有理函数,a(1ρx)m+1=n0(m+nm)aρnxn\displaystyle \frac{a}{(1-\rho x)^{m+1}} = \sum_{n \geqslant 0} \binom{m+n}{m} a \rho ^n x^n

这样可以构造出一个有限和式 S(x)=a1(1ρ1x)m1+1+a2(1ρ2x)m2+1++ak(1ρkx)mk+1\displaystyle S(x) = \frac{a_1}{(1-\rho_1 x)^{m_1 + 1}} + \frac{a_2}{(1-\rho_2 x)^{m_2 + 1}} +\cdots + \frac{a_k}{(1-\rho_k x)^{m_k + 1}}

展开之后,对于 xnx^n 的系数有 [xn]S(x)=a1(m1+nm1)ρ1n+a2(m2+nm2)ρ2n++ak(mk+nmk)ρkn\displaystyle[x^n]S(x) = a_1 \binom{m_1 + n}{m_1} \rho_1 ^n + a_2 \binom{m_2 + n}{m_2} \rho_2 ^n + \cdots + a_k \binom{m_k + n}{m_k} \rho_k ^n

要证明 R(x)R(x) 为多项式,必须证明每一个 R(0)R(0) \neq \infty 的有理函数 R(x)=S(x)+T(x)R(x) = S(x) + T(x),其中 T(x)T(x) 为多项式

注意到x=1/ρ1,1/ρ2,,1/ρkx = 1/\rho_1, 1/\rho_2, \cdots, 1/\rho_k 的时候有 S(x)=S(x) = \infty,而 R(x)=S(x)+T(x)R(x) = S(x) + T(x) 为多项式
αk=1/ρk\alpha_k = 1/\rho_k,我们有 limxkαkS(x)=S(αk)=\displaystyle\lim_{x_k \to \alpha_k} S(x) = S(\alpha_k) = \infty
所以只要证 limxkαkP(x)/Q(x)=\displaystyle\lim_{x_k \to \alpha_k} P(x)/Q(x) = \infty

另一方面,P,QP, Q 是多项式,仅当 Q(x)=0Q(x) = 0 时有 R(x)=R(x) = \infty
由此考虑 limxkαkQ(x)=Q(αk)=0, αk=1/ρk\displaystyle\lim_{x_k \to \alpha_k} Q(x) = Q(\alpha_k) = 0, \ \alpha_k = 1/\rho_k

对于 Q(x)=q0+q1x+q2x2++qmxm,(q00,qm0)Q(x) = q_0 + q_1x + q_2x^2 + \cdots + q_mx^m, \quad (q_0 \neq 0, q_m \neq 0),其反射多项式
QR(x)=q0xm+q1xm1++qmQ^{R}(x) = q_0x^m + q_1x^{m-1} + \cdots + q_m
二者的关系为 QR(x)=q0(xρ1)(xρm),Q(x)=q0(1ρ1x)(1ρmx)Q^{R}(x) = q_0(x-\rho_1)\cdots (x-\rho_m), \quad Q(x) = q_0(1-\rho_1x)\cdots(1-\rho_mx)
这样我们可以求出 ρ\rho

不同根的有理展开

R(x)=P(x)Q(x)R(x) = \displaystyle\frac{P(x)}{Q(x)},其中 Q(x)=q0(1ρ1x)(1ρkx)Q(x) = q_0(1-\rho_1x)\cdots (1-\rho_k x),并且 <ρ1,ρ2,,ρk>\left<\rho_1, \rho_2, \cdots, \rho_k \right> 不同
如果 P(x)P(x) 是次数小于 kk 的多项式,那么有

[xn]R(x)=a1ρ1n++akρkn,(ak=ρkP(1/ρk)Q(1/ρk))[x^n]R(x) = a_1\rho_1^n + \cdots + a_k \rho_k ^n, \quad \left(a_k = \frac{-\rho_k P(1/\rho_k)}{Q'(1/\rho_k)}\right)

证明,实际上只要证 R(x)=P(x)/Q(x)R(x) = P(x)/Q(x) 等于 S(x)=a11ρ1x++ak1ρkx\displaystyle S(x) = \frac{a_1}{1-\rho_1 x} + \cdots + \frac{a_k}{1-\rho_k x}
这一步是根据幂级数展开的等价式

只要证 x1ρkx \to \displaystyle \frac{1}{\rho_k},即 xαk, (αk=1/ρk)x \to \alpha_k, \ (\alpha_k = 1/\rho_k) 时,有 S(x)=R(x)S(x) = R(x)

我们希望能证明 limxαk(xαk)R(x)=limxαk(xαk)S(x)\displaystyle \lim_{x \to \alpha_k} (x - \alpha_k) R(x) = \lim_{x \to \alpha_k} (x-\alpha_k) S(x)

limxαkS(x)=limxαka(xαk)1ρkx\displaystyle\lim_{x \to \alpha_k} S(x) = \lim_{x \to \alpha_k}\frac{a(x-\alpha_k)}{1- \rho_k x},这是一个 00\displaystyle\frac{0}{0} 极限

应用洛必达法则,可以知道 limxαkS(x)=ak/ρk\displaystyle\lim_{x \to \alpha_k} S(x) = \displaystyle -a_k /\rho_k

另外,limxαk(xαk)P(x)Q(x)=P(αk)limxαkxαkQ(x)=P(αk)Q(αk)\displaystyle\lim_{x \to \alpha_k} (x - \alpha_k) \frac{P(x)}{Q(x)} = P(\alpha_k) \lim_{x \to \alpha_k}\frac{x-\alpha_k}{Q(x)} = \frac{P(\alpha_k)}{Q'(\alpha_k)}

最后一步同样用了洛必达法则,这样就证明了结论

推广
R(x)=P(x)Q(x)R(x) = \displaystyle \frac{P(x)}{Q(x)},其中 Q(x)=q0(1ρ1x)d1(1ρkx)dkQ(x) = q_0 (1- \rho_1 x)^{d_1} \cdots (1- \rho_k x)^{d_k},而 <ρ1,ρ2,,ρk>\left<\rho_1, \rho_2, \cdots, \rho_k \right> 互不相同

P(x)P(x) 是次数小于 d1+d2++dkd_1 + d_2 +\cdots + d_k 的多项式,那么有

[xn]R(x)=f1(n)ρ1n++fk(n)ρkn,n0[x^n]R(x) = f_1(n)\rho_1^n + \cdots + f_k(n)\rho_k^n, \quad n \geqslant 0

其中每一个 fk(n)f_k(n) 是一个次数为 dk1d_k - 1 并且首项系数为

ak=(ρk)dkP(1/ρk)dkQ(dk)(1/ρk)=P(1/ρk)(dk1)!q0jk(1ρj/ρk)dja_k = \frac{(-\rho_k)^{d_k} P(1/\rho_k)d_k}{Q^{(d_k)}(1/\rho_k)} = \frac{P(1/\rho_k)}{(d_k-1)! q_0 \prod_{j \neq k} (1- \rho_j / \rho_k)^{d_j}}

类似地,实际上令 S(x)=a1(d11)!(1ρ1x)d1++ak(dk1)!(1ρkx)dk\displaystyle S(x) = \frac{a_1(d_1 - 1)!}{(1- \rho_1 x)^{d_1}} + \cdots + \frac{a_k(d_k - 1)!}{(1- \rho_k x)^{d_k}}

我们同样地,只要证 limxαk(xαk)dkP(x)Q(x)=limxαk(xαk)dkS(x)\displaystyle \lim_{x \to \alpha_k}(x - \alpha_k)^{d_k} \frac{P(x)}{Q(x)} = \lim_{x \to \alpha_k}(x - \alpha_k)^{d_k}S(x)

其中,dk=max(d1,d2,,dk)d_k = \max(d_1, d_2, \cdots, d_k)

先证右边,根据洛必达法则,limxαk(xαk)dkak(dk1)!(1ρkx)dk=ak(dk1)!(ρk)dk\displaystyle\lim_{x \to \alpha_k}(x - \alpha_k)^{d_k} \cdot \frac{a_k(d_k - 1)!}{(1- \rho_k x)^{d_k}} = \frac{a_k(d_k-1)!}{(-\rho_k)^{d_k}}

对于左边,limxαk(xαk)dkP(x)Q(x)=P(αk)limxαkdk(dk1)!Q(dk)(x)\displaystyle \lim_{x \to \alpha_k} (x-\alpha_k)^{d_k} \frac{P(x)}{Q(x)} = P(\alpha_k) \lim_{x \to \alpha_k} \frac{d_k (d_k-1)!}{Q^{(d_k)}(x)}

从而 ak(dk1)!(ρk)dk=dk(dk1)!P(αk)Q(dk)(αk)\displaystyle \frac{a_k (d_k-1)!}{(-\rho_k)^{d_k}} = \frac{d_k (d_k-1)! P(\alpha_k)}{Q^{(d_k)}(\alpha_k)}

举例,斐波那契数列
P(x)=x,Q(x)=1xx2P(x) = x, Q(x) = 1-x-x^2,那么 ρ=ϕ=1+52\rho = \phi = \displaystyle\frac{1+\sqrt{5}}{2}ϕn\phi^n 的系数是 ρP(1/ρ)Q(1/ρ)=ρρ+2\displaystyle\frac{-\rho P(1/\rho)}{Q'(1/\rho)} = \frac{\rho}{\rho+2}

由此 ϕn\phi^{n} 的系数是 ϕϕ+2=15\displaystyle\frac{\phi}{\phi+2} = \frac{1}{\sqrt{5}}ϕ^n\hat{\phi}^n 的系数是 ϕ^ϕ^+2=15\displaystyle\frac{\hat{\phi}}{\hat{\phi}+2} = \frac{-1}{\sqrt{5}}

Fn=(ϕnϕ^n)/5F_n = \displaystyle (\phi^n - \hat{\phi}^n) / \sqrt{5}

带随机性的递归式

引入修正因子,比如

g0=g1=1gn=gn1+2gn2+(1)nn2\begin{aligned} &g_0 = g_1 = 1 \\ &g_n = g_{n-1} + 2g_{n-2} + (-1)^n \quad n \geqslant 2 \end{aligned}

引入 n<2n < 2 的修正因子,gn=gn1+2gn2+(1)n[n0]+[n=1]g_n = g_{n-1} + 2g_{n-2} + (-1)^n[n \geqslant 0] + [n=1]

技巧,实际上 (1)n[n0]=n(1n)xn=(1+x)1(-1)^n[n\geqslant 0] = \displaystyle \sum_{n} \binom{-1}{n}x^n = (1+x)^{-1}

可以推出 G(x)=xG(x)+2x2G(x)+11+x+x\displaystyle G(x) = xG(x) + 2x^2G(x) + \frac{1}{1+x} + x

G(x)=1+x+x2(12x)(1+x)2\displaystyle G(x) = \frac{1+x+x^2}{(1-2x)(1+x)^2}