生成函数
多项式：\(A(x)=\sum_{i=0}^n a_ix^i\)
形式幂级数：\(A(x)=\sum_{i\geq0}a_ix^i\)
其中\(a_i\in K\)，K是一个域，通常我们考虑\(K=\mathbb{R}或K=\mathbb{Z}_p\)
注意这里的x可以理解为独立于域K的一个符号
形式幂级数的运算
设\(A(x)=\sum_{i\geq 0}a_ix^i,B(x)=\sum_{i\geq 0}b_ix^i\)
- 加\减法：\(A(x)\pm B(x)=\sum_{i\geq 0}(a_i\pm b_i)x^i\)
- 乘法：\(A(x)B(x)=\sum_{k\geq 0}(\sum_{i+j=k}a_ib_j)x^k\)
可以验证，形式幂级数在以上定义的+，-，*下形成一个环
环就是加法满足存在0,负元，结合律，交换律，乘法满足结合律，乘法对加法满足左右分配律的代数结构
记号：记形式幂级数(或多项式)A(x)的\(x^n\)项的系数为\([x^n]A(x)\)
形式幂级数的逆元
- 形式幂级数A(x)的逆元：A(x)B(x)=1
- 逆元存在的条件：\([x^0]A(x)\neq 0\)
- 暴力计算的方法：递推\(O(n^2)\)
\(A(x)=a_0+a_1x+···+a_nx^n+···\)
\(B(x)=b_0+b_1x+···+b_nx^n+···\)
\(A(x)B(x)=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+···+(a_0b_n+···+a_nb_0)x^n+···=1\)
则\(a_0b_0=1\rightarrow b_0=a_0^{-1}\)
\(a_0b_1+a_1b_0=0\rightarrow b_1=\frac{-a_1b_0}{a_0}\)
····
\(a_0b_n+···+a_nb_0=0\rightarrow b_n=-\frac{a_1b_{n-1}+···+a_{n}b_0}{a_0}\) - 常见的多项式
\(A(x)=1+x+x^2+···+x^n=\frac{1-x^{n+1}}{1-x}\) - 常见的逆元
- \(A(x)=1+x+x^2+···和B(x)=1-x,即\frac{1}{1-x}=\sum_{i\geq 0}x^i\)
- \(A(x)=1+ax+a^2x^2+···和B(x)=1-ax,即\frac{1}{1-ax}=\sum_{i\geq0}a^ix^i\)
- \(A(x)={k-1 \choose 0}+{k \choose 1}x+{k+1 \choose 2}x^2+···和B(x)=(1-x)^k,即\frac{1}{(1-x)^k}=\sum_{i\geq0}{i+k-1 \choose i}x^i\)
常生成函数
一个数列{\(a_n\)}对应的常生成函数为\(A(x)=\sum_{n\geq 0}a_nx^n\)
问题
不定方程解的数量
- 求不定方程\(x_1+x_2+···+x_k=n\)的解的数量，\(l_i\leq x_i \leq r_i(1\leq i\leq k)\)
设\(F_i(x)=\sum_{j=l_i}^{r_i} x^j\)
\(F(x)=\prod_{i=1}^kF_i(x)=F_1(x)F_2(x)···F_k(x)\)
\(ans=[x^n]F(x)\) - 求\(x_1+2x_2+3x_3=n\)的正整数解的个数
\(F_1(x)=\sum_{i\geq 1}x^i\)
\(F_2(x)=\sum_{i\geq1, 2|i}x^i\)
\(F_3(x)=\sum_{i\geq1,3|i}x^i\)
\(F(x)=F_1(x)F_2(x)F_3(x)\)
\(ans=[x^n]F(x)\)
常生成函数定理
设\(S=\{a_1,a_2,···,a_k\}\)，且\(a_i\)可以取的次数的集合为\(M_i\)，记\(F_i(x)=\sum_{u\in M_i}x^u\)，则从S中取n个元素组成集合的方案数g(n)的常生成函数\(G(x)=\sum_{i\geq 0}g(i)x^i\)，满足
\(G(x)=F_1(x)F_2(x)···F_k(x)\)
递推关系
例斐波那契数列 \(a_0=0,a_1=1,a_2=1,a_n=a_{n-1}+a_{n-2} (n \geq 2)\),求其生成函数
\(A(x)=a_0+a_1x+a_2x^2+····\)
\(\quad\quad=0+x+(a_0+a_1)x^2+(a_1+a_2)x^3+···+(a_{n-1}+a_{n-2})x^n+···\)
\(\quad\quad=x+(a_0x^2+a_1x^3+a_2x^4+···+a_{n-2}x^n)+(a_1x^2+a_2x^3+a_3x^4+···+a_{n-1}x^n)\)
\(\quad\quad=x+x^2A(x)+x(A(x)-a_0)\)
则\(A(x)=\frac{x}{1-x-x^2}=x(\frac{c}{1-ax}-\frac{d}{1-bx})=\sum_{n\geq 1}(c\cdot a^{n-1}-d\cdot b^{n-1})x^n\)
其中a,b,c,d可用待定系数法求得，在这里\(a=\frac{1+\sqrt5}{2},b=\frac{1-\sqrt5}{2},c=\frac{1}{\sqrt5},d=-\frac{1}{\sqrt5}\)