生成函数在证明许多组合恒等式的过程中都十分有用哦 ~不过，我不是专门做组合的，所以这里我就抛砖迎玉讲个简单的吧 ~

我们以 Chu-Vandermonde 恒等式为例。二项式展开（Binomial theorem, Binomial expansion）告诉我们

上面等式的左边就相当于右边 或 前面序列的生成函数（generating function）。把他俩乘在一起，就得到了

然后，利用对 使用二项式定理进行展开，便得到了

左边的二重级数可以进行重排，从而得到

比较系数以后，我们便得到了：

用组合数来表示的话就有

或者，利用 将其写作

这里主要的关键步骤是

也就是说，等式的两端可以通过两种不同的方式进行计算（这是常用的技巧）。其他非常多组合数的等式都是用这种方法得到的。除此之外，许多有关多项式序列的等式也是通过这种方法得到的，例如 Bernoulli 多项式，Euler 多项式等等。

来源：知乎 www.zhihu.com

作者：罗旻杰

【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载

此问题还有 2 个回答，查看全部。