1．          圓排列
圓排列個數(shù) =P(n, r)/r= n!/( r*(n-r)! )

例：8人圍著餐桌吃飯，多少種就座方式？

Ans: P(8, 8)/8=7!

2．          重排列
a.       無限重排列：n個不同元素中取r個按次序排列，每個元素可取無限次，總數(shù)為nr。

b.      有限重排列：r個不同色彩球放入n個標號的盒子，第i種彩球有ri個，總數(shù)為P(n, r) / (r1!* r2!*… rt!)

3．          非重組合：每個元素最多出現(xiàn)一次
C(n, r)

4．          重組合
N個不同的元素中取r個元素，允許重復取，不考慮順序?？倲?shù)為C(n+r-1, r)

5．          母函數(shù)
a.       引出：

(x1+ x2+… +xk)n的組合數(shù)學意義是將n個無區(qū)別的球放入k個編號不同的盒子里，每個盒子球數(shù)不限。多項式展開后，x1n1 *x2n2*…* xknk通過冪可以表示一組解。而這個項的系數(shù)為

C(n, n1)* C(n-n1, n2)*…* C(n-n1-n2-…-nk-1, nk)=n!/ (n1!n2!…nk! )

各系數(shù)之和為kn。

b.      普通母函數(shù)

一個序列{an}，稱a0+a1x+ a2x2+…+ anxn+…這個多項式為{an}的普通母函數(shù)。

例1：（天平稱物問題）有質(zhì)量n1，n2…nk整數(shù)克的砝碼，要稱i克物體，物體在左，砝碼在右。共有多少種不同的稱法？

解：設有ai種方法，則

(1+xn1) (1+xn2)…(1+xnk)=∑ ai xi

1表示(1+xnj)中提供1，砝碼nj沒有用上。

ai為所求。

注：多項式展開后，還可以看出能稱出哪些重量

經(jīng)驗：始終記得，一個括號內(nèi)一次僅有一個項被取，用于提供給展開式的某一項

例2：（重復取物）有n種不同的物品，每種物品分別能最多取b1，b2… bn件。從中可重復的取r件物品有多少種不同的取法？

解：設有ar種不同的取法。則

(1+x+x2+…+xb1) (1+x+x2+…+xb2)… (1+x+x2+…+xbn)=a0+a1x+ a2x2+…+ arxr+…

展開式中xr的來源xm1xm2…xmn=xr

于是成了重組合問題，答案為C(n+r-1, r)

例3：整數(shù)拆分：整數(shù)r拆分成k1，k2… km的和，ki允許最多重復ni次。求拆分方案數(shù)。

解：這是求k1b1+ k2b2+…+ kmbm=r的不定方程的非負整數(shù)解的個數(shù)，0<= bi<= ni 。

考慮(1+xk1+xk1*2+xk1*3+…+xk1*n1)( 1+xk2+xk2*2+xk2*3+…+xk2*n2)…( 1+xkn+xkn*2+xkn*3+…++xkm*nm)

則答案是xr的系數(shù)

c.       指數(shù)母函數(shù)

N個元素中，ai重復了ni次，求從中取r個元素的排列數(shù)為br。

設取mi個ai，∑mi=r。則相互不同的排列數(shù)為r! / ∏mi!

則對于所有的mi的拆分方法，br=∑( r! / ∏mi! )

例4：若有8個元素，其中a1重復了3次，a2重復了2次，a3重復了3次。求從中取出4個元素的排列數(shù)。

解：先構造普通母函數(shù)
G(x)=(1+x+ x2+x3) (1+x+ x2) (1+x+ x2+x3)

X4的系數(shù)為10，說明取4個元素的組合數(shù)為10。這相當于上面所說的對于mi的拆分方法。
4 = 1+0+3 = 0+1+3 = 2+0+2 = 1+1+2 = 0+2+2 =  3+0+1 = 2+1+1 = 1+2+1 = 3+1+0 = 2+2+0

代入br=∑( r! / ∏mi! )，得到70種
 

為了便于計算br，引入函數(shù)

g(x)= (1+x+x2/2!+x3/3!+…+xn1/n1!) (1+x+x2/2!+x3/3!+…+xn2/n2!)… (1+x+x2/2!+x3/3!+…+xnk/nk!)=∑ (br*xr/r!)

g(x)稱為{br}的指數(shù)母函數(shù)。br=∑( r! / ∏mi! )