組合數與母函數

　　母函數能用來解決排列組合的關系，很多資料卻隻解釋母函數的知識沒和排列組合結合起來，這篇文章很好的解釋了他們之間的關系，最後本人會在原創的基礎上加上各類杭電ACM的試題和AC代碼，以便更好的了解，本文轉載的是海子大牛的文章　　　　　　　　　　　　　

母函數與排列組合

　　在談論母函數問題之前，我們先看一個簡單的問題描述：假如有兩組資料（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+x2）*（1+x3）=1+2x+2x2+2x3+2x4+2x5+x6

　　這個多項式和上面的有一些差別了，它的幂級數超過1了。如果要從（1+x）、（1+x+x2）和（1+x3）中得到x的2次方的話，有兩種選擇：從（1+x）和（1+x+x2）中分别選擇一個x或者從（1+x+x2）中選擇x2；如果要得到x的6次方的話，隻有1種選擇，就是從（1+x）中選擇x、（1+x+x2）中選擇x2、（1+x3）中選擇x3。也就是說乘積結果的每一項anxn的前面的系數an表示了從（1+x）、（1+x+x2）和（1+x3）中得到xn的組合數。

　　其實上面的例子就利用了母函數的思想，下面來具體讨論一下母函數。

一.什麼是母函數

　　下面這個對于母函數的描述摘自維基百科：

　　​​在數學中，某個序列 的母函數是一種形式幂級數，其每一項的系數可以提供關于這個序列的資訊。​​

　　也就是說母函數是針對某個序列的，它的外在表現形式是一種形式幂級數。比如說有這樣一個序列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)/k!的函數。

二.利用普通型母函數解決組合問題

　利用母函數的思想可以解決很多組合問題，下面舉例說明：

　1.口袋中有白球2個，紅球3個，黃球1個，從袋中摸出3個球有幾種取法？

　   和上面描述的例子類似，我們可以用次數代表球的個數，多項式的每一項前面的系數代表取法的種樹。

　　可以很容易地寫出下面這個式子：

　　（1+x+x2）（1+x+x2+x3）（1+x）

 　　（1+x+x2）表示有白球2個，1表示白球不取，x代表取1個白球，x2代表取2個白球，即用x的次數表示取球的個數，後面的也是類似。那麼這個多項式的乘積就把所有的情況都表示出來了，對于最終乘積的每一項anxn，表示取n個球有an種取法。

    2.有若幹個1克，2克，5克的砝碼，要稱出20克的重量，有多少種稱法？

　　這裡不限制砝碼的個數，無所謂，照樣寫出母函數：

　　（1+x+x2+x3+......xk+....）（1+x2+x4+x6......+x2n+......）（1+x5+x10+......x5m+......）

　　因為要稱出20克，是以隻需要找找到結果中次數為20 的那一項就可以得到結果。

    3.同樣對于正數劃分也可以解決，比如有整數20，劃分成1，2，5，有多少種劃分方法？

　　解法和2的類似。

     還有一類題目和這類似，有n個球放到m個盒子中，有多少種不同的放法？

    （1+x+x2+x3+...xk+...）（1+x+x2+x3+...xk+...）（1+x+x2+x3+...xk+...）總共有m項，然後找出乘積中次數為n的那一項系數。

三.利用指數型母函數解決排列問題

　　1.口袋中有白球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種排列。

　　2.用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)!+......）