普通生成函数
序列ai的普通生成函数(Ordinary generating function,OGF):
F(x)=i≥0∑aixi
举个例子,等比数列的生成函数为
i≥0∑xi=1−x1i≥0∑aixi=1−ax1
这也是 OGF 的常用封闭形式。
牛顿二项式定理
首先我们定义组合数的计算:
(kr)=k!rk(r∈C,k∈N)
其中rk=r(r−1)(r−2)⋯(r−k+1),r0=1。k!是阶乘。
这样就可以扩展二项式定义为
(1+x)α=k≥0∑(kα)xk
卡特兰数的生成函数
考虑卡特兰数的递推式
h(i)=j=0∑i−1h(j)h(i−j−1)
第一部分
其生成函数定义为
C(x)=i≥0∑h(i)xi=1+i≥1∑j=0∑i−1h(j)xjh(i−j−1)xi−j−1x=1+xj≥0∑h(j)xji≥0∑h(i)xi=1+xC2(x)
那么解方程得到
C(x)=2x1±1−4x=1∓1−4x2
因为limx→01+1−4x2=1+12=1=h(0),所以
C(x)=2x1−1−4x
第二部分
接下来我们将它展开为无穷级数。
(1−4x)21=i≥0∑(i21)(−4x)i=1+i≥1∑i!(21)i(−4x)i(1)
化简下降幂的分式:
i!(21)i=(−1)i−12i1i!(2i−3)!!(2)
化简双阶乘:
(2i−3)!!=(2i−2)(2i−4)⋯2(2i−2)!=2i−1(i−1)!(2i−2)!
于是(2)就变为
i!(21)i=(−1)i−122i−11(i−1)!i!(2i−2)!(3)
把(3)带回(1)得到
(1−4x)21=1+i≥1∑i!(21)i(−4x)i=1−i≥1∑2(i−1)!i!(2i−2)!xi(4)
把(4)带回原式得到
C(x)=i≥1∑(i−1)!i!(2i−2)!xi−1=i≥0∑i!(i+1)!(2i)!xi=i≥0∑i+11(i2i)xi
例题
生成函数依次写成
1−x21(1+x)1−x1−x31−x2x1−x411−x1−x4(1+x)1−x31
化简得到
(1−x)4x
根据牛顿二项式定理得到
(1−x)−4=i≥0∑(i−4)(−x)i=i≥0∑(i4+i−1)xi
那么带回原式得到
(1−x)4x=i≥0∑(i3+i)xi+1=i≥0∑(33+i)xi+1=i≥1∑(32+i)xi
生成函数为
i=1∏n(j=0∑mixj)=i=1∏n1−x1−xmi+1=(1−x)−ni=1∏n(1−xmi+1)
根据牛顿二项式定理得到
(1−x)−n=i≥0∑(in+i−1)xi
我们暴力展开后面的多项式,最多只有2n项。考虑每一项对答案的贡献,发现cixi的贡献是
cij=a−i∑b−i(n−1n+j−1)
这样就做完了。