首页 > 代码库 > 母函数与排列组合
母函数与排列组合
【本文链接】
http://www.cnblogs.com/hellogiser/p/generating-function-and-permutation-combination.html
0. 公式
排列A(n,k) = n*(n-1)...*(n-k+1) = (n!)/(n-k)!
组合C(n,k) = A(n,k)/k! = (n!)/((n-k)!*k!)
1. 什么是母函数
下面这个对于母函数的描述摘自维基百科：
在数学中，某个序列 的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。
也就是说母函数是针对某个序列的，它的外在表现形式是一种形式幂级数。比如说有这样一个序列a0，a1，......an，构造一个函数
f(x)=a0+a1x+a2x2+......+anxn
则f(x)是序列a0，a1，......an的母函数。比如说最常见的(1+x)n，它是序列C(n,0)，C(n,1)，C(n,2)...C(n,n)的母函数。
母函数包括几种，其中最常见的是普通型母函数和指数型母函数。普通型母函数是形如 f(x)=a0+a1x+a2x2+......+anxn的函数，而指数型母函数是形如G(x) = a0 + a1*(x)/1! + a2*(x2)/ 2! + a3*(x3)/3! + …… an*(xn)/n!的函数。
2. 利用普通型母函数解决组合问题
口袋中有白球2个，红球3个，黄球1个，从袋中摸出3个球有几种取法？
和上面描述的例子类似，我们可以用次数代表球的个数，多项式的每一项前面的系数代表取法的数量。
设白球a个，红球b个，黄球c个。则a=0,1,2； b=0,1,2,3; c = 0,1
可以很容易地写出下面这个式子：
（1+x+x2）（1+x+x2+x3）（1+x）
（1+x+x2）表示有白球2个，1表示白球不取，x代表取1个白球，x2代表取2个白球，即用x的次数表示取球的个数，后面的也是类似。那么这个多项式的乘积就把所有的情况都表示出来了，对于最终乘积的每一项anxn，表示取n个球有an种取法。
3个球的取法： 021=BBC,030=BBB,120=ABB,111=ABC,210=AAB,201=AAC共有6种，刚好是X3的系数
其它问题：
有若干个1克，2克，5克的砝码，要称出20克的重量，有多少种称法？ （1+x+x2+x3+......xk+....）（1+x2+x4+x6......+x2n+......）（1+x5+x10+......x5m+......）
同样对于正数划分也可以解决，比如有整数20，划分成1，2，5，有多少种划分方法？
求用1分、2分、3分的邮票贴出不同数值的方案数？ (注意，每种邮票的出现次数可以是无限制的即count=0,1,2,3...)
3. 利用指数型母函数解决排列问题
口袋中有白球2个，红球3个，黄球1个，任取3个作为一个排列，总共有多少种排列？
类似地用指数型母函数解决
用（1+x/1!+x2/2!）表示取白球0个，1个或者2个
那么（1+x/1!+x2/2!）（1+x/1!+x2/2!+x3/3!）（1+x/1!）来表示所有的排列结果。
=1+3x+4x2+19x3/6+19x4/12+6x5/12+x6/12
=1+3*(x/1!)+8*(x2/2!)+19*(x3/3!)+38*(x4/4!)+60*(x5/5!)+60*(x6/6!)
找到次数为3的那一项，系数为19，那么总共有19种排列。
来看一下排列和组合的区别：
3个球的组合取法：
021=BBC, 对应的排列有BBC,BCB,CBB共3种，刚好是1*(X2/2!)*(X/1!) = 3*(X3/3!)的系数
030=BBB, 对应的排列有BBB共1种，刚好是1*(X3/3!)*1 = 1*(X3/3!)的系数
111=ABC,对应的排列有ABC,ACB,BAC,BCA,CAB,CBA共6种，刚好是X*X*X = 6*(X3/3!)的系数
依次类推，总计19种排列。
其它问题
用1，2，3，4能够组成多少个5位数，要求1出现2次或者3次，2出现0次或者1次，3没有限制，4只出现偶数次。（x2/2!+x3/3!）（1+x）（1+x/1!+x2/2!+x3/3!+.....xk/k!+....）（1+x2/2!+x4/4!+......+x2n/(2n)!+......）
【参考】
http://www.cnblogs.com/dolphin0520/archive/2012/11/07/2755080.html
http://www.wutianqi.com/?p=596
母函数与排列组合