常見排列組合問題的計算公式

在進行排列組合計算以及概率計算時我們經常會遇到一些具有相同性質的問題。假設問題的樣本空間Ω中一共有k種類型的元素α, β,γ... κ。每種類型的元素個數分別為Nα, Nβ,Nγ... Nκ。那麼這些元素組成的重複元素的集合Ω為：
Ω= { Nα * α,  Nβ * β,  Nγ * γ, ... Nκ * κ} 

總的元素數量 N = Nα + Nβ + Nγ + ...  Nκ

在實踐中我們會遇到從集合Ω中取子集Ε的問題，取子集的問題從概率論的角度來說就是某種事件出現的概率。 如果是同時取的話就不會考慮排列的順序因此這就會歸類為一個求組合的問題。而如果是依次取的話就需要考慮排列的順序了因此這個就可以歸類為一個排列的問題，而對於排列的問題我們又可以細分為放回排列和不放回排列兩種場景。因此我們可以將從集合Ω中取元素分類為三種大類型的問題：組合、放回排列、不放回排列。

組合

對於組合類型的問題來說總是描述為從N個元素的集合Ω中同時取出M個元素組成的子集Ε， 然後再問其中的某種類型元素或者某幾種類型元素出現的個數的問題。 這裡之所以用組合的原因是強調同時以及不需要排列的概念，因此不需要考慮每次取的順序，就不存在排列的問題。因此我們從N個元素裡面取M個元素的總共的取法有 **  C(N,M)  ** 種方法。

子問題1: 某種類型元素γ剛好出現R次。

這裡的γ 是k種類型的元素中的任意一種，數量為Nγ。 因為所有M個元素中γ的數量固定為R，因此其他剩下的元素的組合數量是C(N-Nγ, M-R)， 而在Nγ個中取R個元素γ的組合數量是 C(Nγ, R)。因此一共有：

**  C(Nγ,R) * C(N-Nγ, M-R)  **

舉例1：一個袋中有5個白球，3個紅球。一次取2個問取到的是2個紅球的概率？

_ 答 _ ：C(5,0) * C(3,2) / C(8,2) = 3 / 28

舉例2：一個袋中有5個白球，3個紅球。一次取2個問取到的是2個相同的球的取法？

_ 答 _： C(5,0) * C(3,2) + C(3,0) * C(5,2) = 13

子問題2： 某種類型元素γ最多出現R次。

這個問題可以理解為分別計算出現0次到R次的和：

** R **
**  ΣC(Nγ, i) * C(N-Nγ, M-i)   **
** i=0 **

舉例1：一個袋中有5個白球，3個紅球。一次取2個，取到的不是紅球的概率？

C(5,2) * C(3,0) / C(8,2) = 10 / 28    //紅球0次

子問題3： 某種類型元素γ最少出現R次。

** M **
**  Σ  C(Nγ, i) * C(N-Nγ, M-i) **
** i=R **

子問題4： 元素α出現A次，元素β出現B次... 元素γ出現R次。
A + B + .. R  <= M

** C(Nα, A) * C(Nβ, B)  * ... C(Nγ, R) * C(Nα-Nβ -  ... Nγ , M - A - B -... R)  **

舉例1：一個袋中有5個白球，3個紅球。一次取2個，取到的是一個白球和一個紅球的概率

_ 答 _:  C(5,1) * C(3,1) * C(8-8, 2-1-1) / C(2,8) = 15 / 28

舉例2：一個袋中有5個白球，3個紅球。一次取3個，取到的是一個白球和一個紅球的概率

_ 答 _:  C(5,1) * C(3,1) * C(8-8, 3-1-1) / C(2,8) = 0 / 28    // 因為C(0,1) == 0,  這是因為白色和紅色取3個，不可能只有一個白球和一個紅球的情況。

舉例3： 口袋中有10個球，分別標號為1到10，現在從中任選3隻，問最小號為5的取法？

_ 答 _: 這個問題可以簡化為 5個大於5的元素為一類，5為一類，4個小於5的元素為一類，這樣就轉化為了大於5的元素出現2次，等於5的元素出現1次的數量了： C(5,2) * C(1,1) * C(10 - 5 - 1, 3 -2 -1)  = 10

子問題5：元素α至少出現A次，元素β出現B次。

這個問題可以先選擇β 再來選擇α。

**　　　　M - B **
** C(Nβ, B)  * Σ C(Nα, i )  * C(N-Nα-Nβ, M -  i - B) **
** 　　　　i = A  **

子問題6： 元素α至少出現A次，元素β至少出現B次... 元素γ至少出現R次。
A + B + .. R  <= M

**  M-B-..R      　M-i-.. R　　　M - i - j -.. .  **
**  Σ C(Nα, i)  *      Σ C(Nβ, j) *   ...   Σ C(Nγ, w)  * C(N-Nα-Nβ - ... Nγ, M - i - j - ..w )     **
**  i=A　　　 j = B　　　　　w = R  **

舉例1：一個袋中有10個白球，20個紅球，30個黑球。    一次取18個，問取到的結果中白球至少有3個，紅球至少有2個，黑球至少有4個的取法

_ 答：_ 按上述公式套入即可

子問題7： 元素α至多出現A次，元素β至多出現B次... 元素γ至多出現R次。

**  A 　　　　min(B, M-i)　min(R,  M - i - j -.. .)  **
** ΣC(Nα, i)  *      Σ C(Nβ, j) *   ...   ΣC(Nγ,w)  * C(N-Nα - Nβ -... Nγ, M - i - j - ..w)     **
**  i=0　　　 j = 0　　　　w = 0  **

可放回排列

可放回排列每次從N個元素中取出一個元素，然後再放回，然後再繼續取，依次取M次。這樣一次就有N種取法，M次就一共有N^M種取法，因為是依次取所以需要考慮排列的順序。 可放回排列也稱為n重伯努利實驗。每次取的元素都是獨立的。

子問題1：  第i次取到是元素γ的方法。

第i次有Nγ種取法，其他M-1次都有N種。因此結果是：

** Nγ *  N^(M-1)  **

上面公式中無論哪次取的概率都是： Nγ / N。這個就像可重複抽獎一樣，對於獎品每次的概率都是一樣的。

子問題2： 只有第i次取到的是元素γ的方法。（1 <= i <= M)

因為只有第i次取到元素γ，因此前面和後面都不能再出現γ了，這樣的數量為：

** (N-Nγ)^(i-1)  *  Nγ  * (N - Nγ)^(M-i) ==  Nγ  * (N-Nγ)^(M-1) **

子問題3： 取到γ元素R次的取法。

某元素一次可能出現在任何一個位置，某次出現的次數是:  Nγ * (N-Nγ)^(M-1) 。而因為出現R次所以有：Nγ^R * (N - Nγ)^(M - R), 而這R次一共有 C(M, R)種位置擺放。因此最終的數量是：

** C(M, R) * Nγ^R * (N - Nγ)^(M - R)   **

概率為C(M, R) * Nγ^R * (N - Nγ)^(M - R) /  N^M = C(M,R) *(Nγ / N)^R * ((N-Nγ)/N)^(M-R)   。

如果只有2種類型的元素，這個結果正是二項分布的公式。因此二項裡面的概率p其實就是這種元素的個數Nγ/N。

舉例1   骰子連續擲2次，求最小點數是2的方法？

_ 答：_  每次有6種結果，可重複排列，因為這裡要求最小為2，因此我們可以劃分為 {3，4，5，6} {2} 2個集合,這樣可以用 { 4 * a, 1*b} 這種形式，因此問題變為了求b出現1次或者出現2次的問題：

11*(5-1)(2-1) * C(2,1) + 12*(5-1)(2-2)*C(2,2) = 8 + 1 = 9

子問題3  ： 第i次取到α, 第j次取到β, .. 第w次取到γ ( i <>j <>...<>w)。取的種類數為R

** Nα * Nβ * ... Nγ  *  N^(M - R) **

子問題4： 取到α元素A次，β元素B次,...  γ元素R次。

** C(M, A) * C(M-A, B) *... C(M-A-B-..., R) * Nα^A * Nβ^B *... Nγ^R  * (N - Nα -Nβ  - ...Nγ) ^ (M - A - B - ... R)   **

舉例1  10個白球，4個黑球，6個紅球，可放回取，取7次。問取到3顆白球和2顆黑球的方法？

_ 答: _   10^3 * 4^2 * 6 ^ 2 * C(7,3) * C(4,2)

不放回排列

不放回排列是從N個元素裡面依次取，每次取1個，然後一共取M次。這樣第一次有N種取法，第二次有N-1種取法，第M次有N-M+1種取法，因此總的可取的數量是：** A(N,M) ** 。這裡的排列是要考慮順序的。

子問題1：  第i次取到的元素是γ。(1 <= i <= M)

前i-1次不能取到γ，i+1次以後也不能取到，而第i次有Nγ種取法，因此得到：

**   A(N-1, i-1) * Nγ * A(N-i, M-i) = Nγ * A(N-1, M-1) **

子問題2： 取到γ元素R次。  (R  < Nγ)

某一個位置上一共有  A(Nγ, R) * A(N-Nγ, M-R)，一共有 C(M,R)种放置方法。因此結果是：

**   C(M,R) * A(Nγ, R) * A(N-Nγ,M-R) **

子問題3  ： 第i次取到α, 第j次取到β, ... 第w次取到γ ( i <>j <>... w)  類型數量為R

這個問題因為每次取到的值和其他位置取到的值無關，每種類型的方法都是其元素的數量，因此可以用乘法，剩餘的再用排列來計算。

** Nα * Nβ * ...*Nγ * A(N-R, M-R）**

子問題4： 取到α元素A次，β元素B次,...  γ元素R次

這個問題中每種類型出現的次數固定，因此這種類型用排列，每種元素之間用乘法來實現，同時每種元素的位置則是用組合。

** C(M, A)*C(M-A, B) *...C(M-A-B..., R) * A(Nα, A) *A(Nβ, B) * ..A(Nγ, R) * A(N-Nα-Nβ-...Nγ, M-A-B-...R) **

舉例1  10個白球，4個黑球，6個紅球，不放回取，取7次。問取到3顆白球和2顆黑球的方法？

_ 答: _   C(7,3) * C(4,2) * A(10, 3) * A(4,2) * A(6 , 2)

總結

通過上面的公式，我們可以發現這些公式之間的一些相似的特徵:

某種元素γ出現的次數R的公式可以分解為三部分：** 位置部分 * 自身的排列組合部分 * 剩餘元素的排列組合部分** 。位置部分總是C(M,Nγ); 自身的排列組合部分則組合總是1，可放回排列則是Nγ^R，不可放回排列則是A(Nγ,R);  剩餘元素的排列組合部分則組合是C(N-Nγ, M-R), 可放回排列則是(N-Nγ)^(M-R), 不可放回排列則是A(N-Nγ, M-R)。

多種元素出現次數的公式則是單種元素出現次數的乘積，而且和出現的順序是無關的，正因為如此才可以使用乘法公式。

某個元素至多至少出現的R的公式則可以分解為從0到R次(至多)或者R到M次(至少)的和來計算。

某些問題看似和上面描述的各種子問題無關，但是我們可以通過一定的方式來轉化為上述各種子問題來求解。例如我們要把N個元素放入M個位置(N <=M)時則可以反過來看成一個可放回的排列問題把位置M當做元素而把元素N當做位置來求解。

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。