普通型生成函数
一、定义
构造这么一个多项式函数 \(F(x)\)，使得 \(x\) 的 \(n\) 次方系数为 \(f(n)\)。
\[F[x] = \sum^\infty_{i = 0}f(i)\ x^i \]二、格式声明
==为逻辑判断符，=为运算符号
[表达式] 表达式值为真返回$\ 1\ \(，否则返回\)\ 0\ $
<>中表示序列、f()、g(x)表示原函数、F()、G()表示生成函数
拿斐波那契数列举个例子：
\[<f_1,f_2,f_3,……> \]\[f(n) = f(n-1) + f(n-2) + [n == 1] \]\[F[x] = \sum^\infty_{i = 0}f(i)\ x^i \]三、常见操作
h()表示操作后的函数，H()表示操作后的生成函数
1.数乘
\[<cf_0,cf_1,cf_2,…> \]\[h(x) = cf(x) \]\[H(x) = cF(x) \]2.加减
\[<f_0+g_0,f_1+g_1,f_2+g_2,…> \]\[h(x) = f(x) + g(x) \]\[H(x) = F(x) + G(x) \]3.右移(k位)
\[<0,0,0,0,f_0,f_1,f_2,f_3,…> \]\[h(x) = f(x - k) \]\[H(x)=x^kF(x) \]4.求导
\[<f_1,2f_2,3f_3,…> \]\[H(x) = F'(x) \]5.卷积
\[<f_0g_0,f_1g_0+f_0f_1,f_0g_2+f_1g_1+f_2g_0,…,\sum_{i+j=n}f_ig_j,…> \]\[h(x) =\sum_{i=0}^nf_ig_{n-i} \]\[H(x)=F(x)\times G(x) \]6.取项
\[<0,0,0,…，0,f(n),0,…,0,0> \]\[g(x) = \begin{cases}h(x) & n = 1\\0 & otherwise\end{cases} \]\[[x^n]F(x) = f(n) \]四、全是例子
建议蒙住右边的生成函数一列，这样食用效果更佳
点击注脚查看证明，*为卷积
| 编号 | 记法 | 函数 | 数列 | 生成函数 |
|---|---|---|---|---|
| \(T_1\) | 无 | \(f(x)\to f(x-1)\) | 无 | \(F(x)\to xF(x)\) |
| \(T_2\) | \(1\) | \(f(x) = 1\) | \(<1,1,1,…,1,1,1>\) | \(F(x)= 1 + x + x^2 + x^3 + …=\frac{1}{1-x}\)[1] |
| \(T_3\) | \([n == 1]\) | \(f(x) = \begin{cases}1&x==1\\0&otherwise\end{cases}\) | \(<0,1,0,…,0,0>\) | \(F(x) = 1\) |
| \(T_4\) | \([n\%3 == 0 ]\) | \(f(x) = \begin{cases}1&x\%3 == 0\\0&otherwise\end{cases}\) | \(<1,0,0,1,0,0,…>\) | \(F(x) = 1 + x^3 + x^6 + x^9 + … = \frac{1}{1-x^3}\)[2] |
| \(T_5\) | \([n\geq 3]\) | \(f(x) = \begin{cases}1&x\geq 3\\0&otherwise\end{cases}\) | \(<0,0,0,1,1,1,…>\) | \(F(x) = x^3 + x^4 + … = \frac{x^3}{1-x}\)[3] |
| \(T_6\) | \([n\leq3]\) | \(f(x) = \begin{cases}1 & x\leq3\\0&otherwise \end{cases}\) | \(<1,1,1,1,0,0,…>\) | \(F(x) = \frac{1}{1-x} - \frac{x^4}{1-x}\)[4] |
| \(T_7\) | \(2^n\) | \(f(x) = 2^x\) | \(<1,2,4,8,…>\) | \(F(x)=1 + 2x + 4x + … = \frac{1}{1-2x}\)[5] |
| \(T_8\) | \(n\) | \(f(x) = x\) | \(<0,1,2,3,…>\) | $F(x) = 1 + 2x + 3x^2+… =1*1 = \frac{1}{(1-x)^2} $（此处\(1*1\)的\(1\)为\(T_2\)的记法） |
五、全是例题
Q1. 有1g、2g、3g、4g的砝码各一个，问对于一些重量，求方案数
\[\begin{cases}1g&<1,1,0,0,0,…>&F(x) = 1 + x\\ 2g&<1,0,1,0,0,…>&G(x) = 1 + x^2\\ 3g&<1,0,0,1,0,…>&H(x) = 1 + x^3\\ 4g&<1,0,0,0,1,0,…>&I(x) = 1 + x^4 \end{cases} \]\[P(x) = F(x)\times G(x)\times H(x)\times I(x)\\=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} \]答案数列为:\(<1,1,1,2,2,2,2,2,1,1,1>\)
Q2. n个盘子的汉诺塔问题
aaaa
\[f(x) = 2\times f(x-1)+1 \]\[F(x) = 2xF(x) + \frac{1}{1-x} \\ \Downarrow\\F(x) = \frac{1}{(x-1)(2x-1)} \]更详细推导过程详见[6]
Q3.无限砝码1g,2g,3g,4g
\[\begin{cases}1g&<1,1,1,1,1,1,…>&F(x)=\frac{1}{1-x}\\2g&<1,0,1,0,1,0,…>&G(x)=\frac{1}{1-x^2}\\3g&<1,0,0,1,0,0,1,…>&H(x)=\frac{1}{1-x^3}\\4g&<1,0,0,0,1,0,0,0,1,…>&I(x) = \frac1{1-x^4}\end{cases} \]\[P(x) = F(x)\times G(x)\times H(x)\times I(x) \]Q4.斐波那契数列
\[f(n) = f(n-1)+f(n-2)+[n==1] \]\[F(x) = xF(x) + x^2F(x)+x \]\[(1-x-x^2)F(x) = x \]\[F(x) = \frac x {1-x-x^2} \]Q5.？？？？
\[e^x = 1 + x + \frac 1 2x^2 + \frac 1 {3!}x^3+… \]证明：\(xF(x) + 1= 1 + x + x^2 + x^3 + … = \frac{1}{1-x} = F(x)\\ \Downarrow \\F(x) = \frac{1}{1-x}\) ↩︎
证明：令\(t = x^3\)、套用\(T_2\)即可 ↩︎
证明：\(\frac{F(x)}{x^3} = 1 + x + x^2 = \frac{x^3}{1-x}\) ↩︎
证明：从\(0\)到\(\infty-\)从\(4\)到\(\infty=\)从\(0\)到\(3\) ↩︎
证明：\(F(x) = 1 + (2x) + (2x)^2 + (2x)^3 + …\)再用 ↩︎
推导：\(f(x-1)\)生成函数为\(G(x) = xF(x)\)(右移)，\(2f(x-1)\)生成函数为\(H(x) = 2G(x) = 2xF(x)\)(数乘)，\(2f(x-1)+1\)生成函数即为\(F(x) = H(x) + \frac{1}{1-x}=2xF(x) + \frac 1 {1-x}···(T_2)\) ↩︎