一、定义

对于数列:$a_0,a_1,a_2,…,a_n$,设$G(x)=a_0+a_1x+a_2x^2+…+a_nx^n$,则称$G(x)$是该数列的生成函数,也叫母函数。

  • 普通型:$G(a_n;x)=\sum_{n=0}^{\infty }a_nx^n$
  • 指数型:$EG(a_n;x)=\sum_{n=0}^{\infty }a_n\frac {x^n}{n!}$

二、计算

  • 加减:
  • 乘常数:
  • 乘幂:$x^k\times G(x)\leftrightarrow <0,0,...,0,g_0,g_1,...>$ (前面有$k$个0)
  • 两母函数相乘:$F(x)\times G(x)$跑FFT搞多项式乘法
  • 求导:

    三、应用

    1、已知数列递推式,求通项公式
    和特征方程类似,此处不再赘述。
    2、解决组合问题
    3、一些奇思妙想

    四、例子

    1、有一些水果,只能拿3的倍数个苹果,只能拿质数个草莓。问对于每个$0<i<=n$,有多少种方案使得恰好拿$i$个水果。
    不妨先构造两个布尔数组(第i个数为0表示不能拿i个,反之能拿):
1
2
苹果-[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1...] 
草莓-[0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0...]

用上面两个数组构造母函数:
苹果-$Apple(x)=x^3+x^6+x^9+…$
草莓-$Straw(x)=x^2+x^3+x^5+x^7+…$
将两个式子相乘,发现$x^k$的系数正好表示取$k$个苹果或草莓的方案数(强烈建议自己动手推,当然前提是得会极限思想等)。
以$x^4$为例,显然$x^4=x^{0} \times x^4=x^1\times x^3=x^2\times x^2=x^{3} \times x^1=x^4\times x^0$,且没有其他拆分方案。这显然可以表示0个苹果+4个草莓,1个苹果+3个草莓……这些选取方案。
根据FFT,可以在$O(n log n)$的时间里求出答案,直接输出卷积即可。

2、从只有4个女装大佬的队伍中选出$n$个女装大佬的方案数。

有点组合基础的就能发现,显然是$\binom{n}{4}$。
从n=0开始枚举,显然答案为:1,4,6,4,1。求其生成函数,易得$G(x)=1+4x+6x^2+4x^3+x^4$。有没有发现序列$1,4,6,4,1$非常熟悉?这不就是二项式展开嘛!于是$G(x)=(1+x)^4$。

3、求$n=x_1+x_2+x_3+…+x_k$有多少非负整数解。

将每个$x_i$都增加1,则有$n+k=x_1+x_2+x_3+…+x_k$。考虑隔板法:把$n+k$个数排成一排,在$n+k-1$个空格中插入$k-1$个隔板,方案数为$\binom{k-1}{n+k-1}=\binom{n}{n+k-1}$,关于$n$的生成函数是$G(x)=\frac {1}{(1-x)^k}=(1-x)^{-k}$。简单证明下:用牛顿二项式定理可得$x^n$的系数是$\binom{n}{n+k-1}$。
换用生成函数来解释:由$1+x+x^2+x^3+x^4+…=\frac {1}{1-x}$可得$(1+x+x^2+x^3+x^4+…)^k=\frac {1}{(1-x)^k}$,显然展开之后$n$次项的系数就是答案。

最后更新: 2018年11月24日 07:03

原始链接: https://ruixiangjiang.github.io/2018/11/10/Generating-function/

× 请我吃糖~
打赏二维码