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個標(biāo)號的盒子，第i種彩球有ri個，總數(shù)為P(n, r) / (r1!* r2!*… rt!)

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

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

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

(x1+ x2+… +xk)n的組合數(shù)學(xué)意義是將n個無區(qū)別的球放入k個編號不同的盒子里，每個盒子球數(shù)不限。多項(xiàng)式展開后，x1n1 *x2n2*…* xknk通過冪可以表示一組解。而這個項(xiàng)的系數(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+…這個多項(xiàng)式為{an}的普通母函數(shù)。

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

解：設(shè)有ai種方法，則

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

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

ai為所求。

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

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

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

解：設(shè)有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允許最多重復(fù)ni次。求拆分方案數(shù)。

解：這是求k1b1+ k2b2+…+ kmbm=r的不定方程的非負(fù)整數(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重復(fù)了ni次，求從中取r個元素的排列數(shù)為br。

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

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

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

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

X4的系數(shù)為10，說明取4個元素的組合數(shù)為10。這相當(dāng)于上面所說的對于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種
 

為了便于計(jì)算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! )