引入
你一定学过二项式定理,即
(a+b)n=i=0∑n(in)aibn−i
你也大概率做过一道题:求值:
(0n)+(1n)+(2n)+⋯(1)
事实上,只需要展开 (1+1)n 就可以得到这个序列(注意这是一个无限序列,第 n+1 项以后都是 0)。那么读者不难想到是不是也可以用像 (1+1)n 一样的一个函数来表示一个序列呢?于是我们引入了生成函数。
从二项式系数开始
对于一个无限序列 ⟨a0,a1,a2⋯⟩,我们用一个幂级数来表示它:
G(x)=a0+a1x+a2x2+⋯=k≥0∑akxk(2)
即,如果把该幂级数 G(x)=k≥0∑akxk 的 n 次项的系数为 G(x)n(这是自己发明的完全不正式的记法) 即 G(x)n=an,那么 G(x)n 就是该无限序列的第 n 项。称 G(x) 为序列 a 的生成函数。
举例来说,式 (1) 的生成函数即为 G(x)=k≥0∑(kn)xk。它的封闭形式为 (1+x)n
现在,我们考虑两个生成函数 G(x) 与 F(x) 的乘积 H(x)。大家都学过多项式的乘法,于是很显然,两个生成函数的乘积的某一项的系数是一个卷积的形式,容易写出 H(x)n 的式子:
H(x)n=k=0∑nG(x)k⋅F(x)n−k
节标题叫“从二项式系数开始”,所以我们现在开始讨论二项式系数(组合数)。
类似于 (1),令
G(x)=(1+x)n=k≥0∑(kn)xkF(x)=(1+x)m=k≥0∑(km)xkH(x)=G(x)⋅F(x)=(1+x)n+m=k≥0∑(kn+m)xk
考虑 F(x)⋅G(x) 的展开式(卷积)与 H(x) 的第 n 项相等,我们得到
k=0∑n(kn)(n−km)=(nn+m)(3)
即范德蒙德卷积公式。这个公式曾经在另一篇学习笔记 【学习笔记】组合数学 中出现过,并附有组合推理的证明。
练习:仿照该过程,证明:
k=0∑n(km)(n−km)(−1)k=(−1)n/2(n/2m)[ n is even ]
提示:设 G(x)=(1−x)m,F(x)=(1+x)m
鸽了,暑假再学