母函数与排列组合 - 海 子 - 博客园

母函数与排列组合 - 海 子 - 博客园

　　在谈论母函数问题之前，我们先看一个简单的问题描述：假如有两组数据（A,B）和（C,D），每组中选出一个构成一个组合，总共有几种选法？很显然总共有4种选法：AC,AD,BC,BD。而且很容易联想到这个式子（A+B）*（C+D）=A*C+A*D+B*C+B*D。式子中的几个乘积项就是上面的4种选法。假如把问题换一下：每组中选出一个或0个数据构成组合，总共有几种组合？那么结果就变成：{空},A,B,C,D,AC,AD,BC,BD，而式子（1+A+B）*（1+C+D）=1+C+D+A+A*C+A*D+B+B*C+B*D，正好和上面组合的结果又一致（1代表什么都没选）。从这2个例子我们可以发现多项式乘积和组合存在着某种关系。事实上我们可以这么理解：（1+A+B）可以理解为从第一组数据中取0个数据，取A或者取B，同样（1+C+D）可以理解为从第二组数据取0个数据，取C或者取D。两者相乘的结果就表示了所有的组合。再看一下这个多项式：

　　（1+x）*（1+x+x²）*（1+x³）=1+2x+2x²+2x³+2x⁴+2x⁵+x⁶

　　这个多项式和上面的有一些区别了，它的幂级数超过1了。如果要从（1+x）、（1+x+x²）和（1+x³）中得到x的2次方的话，有两种选择：从（1+x）和（1+x+x²）中分别选择一个x或者从（1+x+x²）中选择x²；如果要得到x的6次方的话，只有1种选择，就是从（1+x）中选择x、（1+x+x²）中选择x²、（1+x³）中选择x³。也就是说乘积结果的每一项a_nxⁿ的前面的系数a_n表示了从（1+x）、（1+x+x²）和（1+x³）中得到xⁿ的组合数。

Read full article from 母函数与排列组合 - 海 子 - 博客园