学不会的生成函数

不知道怎么开始

• $a=\langle1,1,1,1,1…\rangle$的生成函数是

  $$f(x)=x+x^2+x^3+x^4+...$$

  限定 $x\in(-1,1)$

  $$f(x)=\lim_{n\to \infty} \frac{1-x^n}{1-x} = \frac{1}{1-x}$$

  同理得,函数

  $$f(x)=1+x^2+x^4+x^6...=\frac{1}{1-x^2}$$ $$f(x)=1+2x+3x^2+4x^3...=\frac{1}{\left(1-x \right)^2}$$ $$f(x)=1+3x+6x^2+10x^3+15x^4...=\frac{1}{\left(1-x\right)^3}$$

  推广有：

  $$\frac{1}{\left(1-x\right)^k} 的生成数列是 \sum_i^\infty C_{i+k-1}^{k-1} x^i$$

设 $F(z) , G(z)$ 是数列 $\langle \ f_n \ \rangle , \langle \ g_i \ \rangle$ 的生成函数

• 相加

  $$\begin{aligned} \alpha F(z)+ \beta G(z) &= \alpha \sum_n f_nz^n + \beta \sum_ng_nz^n \\ &=\sum_n (\alpha f_n + \beta g_n) z^n\\ \end{aligned}$$

  得到数列 $\langle \ \alpha f_n+\beta g_n \ \rangle$ 的生成函数

• 平移生成函数

  • 向右 $m$ 位

    即，构造前面有 $m$ 个 $0$ 的数列 $\langle \ \underbrace{0,\cdots}_{m个},g_0,g_1,\cdots \ \rangle = \langle \ g_{n-m} \ \rangle$ 的生成函数

    直接用 $z_m$ 乘

    $$z_m \cdot G(z) = \sum_n g_nz^{n+m} = \sum_n g_{n-m}z^n$$

  • 向左 $m$ 位

    即，构造前面 $m$ 个元素被删除的数列 $\langle \ g_m,g_{m+1},g_{m+2},\cdots \ \rangle$ 的生成函数

    减去前 $m$ 项，并用 $z_m$ 来除

    $$\frac{G(z)-g_0-g_1z-\cdots -g_{m-1}z^{m-1}}{z^m} = \sum_{n\geq m} g_nz^{n-m} = \sum_{n\geq 0} g_{n+m}g^z$$

• 常数倍的 $z$

  $$G(cz) = \sum_ng_n(cz)^n = \sum_n g_nz^n$$

  即，数列 $\langle \ c^ng_n \ \rangle$ 的生成函数

  当 $c=-1$ 时特别有用

• 相乘

  $$\begin{aligned} F(z)G(z) &=(f_0+f_1z+f_2z^2+\cdots ) \cdot (g_0+g_0z+g_0z^2+\cdots) \\ &=(f_0 \cdot g_0) + (f_0\cdot g_1 + f_1 \cdot g_0)z + (f_0\cdot g_2 + f_1\cdot g_1 + f_2 \cdot g_0) z^2 + \cdots \\ &=\sum_n \left(\sum f_k \cdot g_{n-k} \right) z^n \\ \end{aligned}$$

  求得数列 $\langle \ h_n \ \rangle$ 的生成函数，即数列 $\langle \ f_n \ \rangle , \langle \ g_i \ \rangle$ 的卷积的生成函数

  和式 $\displaystyle{h_n=\sum_{k=0}^n f_k \cdot g_{n-k}}$

具体参见具体数学P280 , 表7-1，7-2