在進(jìn)行排列組合計(jì)算以及概率計(jì)算時(shí)我們經(jīng)常會(huì)遇到一些具有相同性質(zhì)的問(wèn)題。假設(shè)問(wèn)題的樣本空間Ω中一共有k種類(lèi)型的元素α, β,γ... κ。每種類(lèi)型的元素個(gè)數(shù)分別為Nα, Nβ,Nγ... Nκ。那么這些元素組成的重復(fù)元素的集合Ω為：
Ω= { Nα * α, Nβ * β, Nγ * γ, ... Nκ * κ}
總的元素?cái)?shù)量 N = Nα + Nβ + Nγ + ... Nκ
在實(shí)踐中我們會(huì)遇到從集合Ω中取子集Ε的問(wèn)題，取子集的問(wèn)題從概率論的角度來(lái)說(shuō)就是某種事件出現(xiàn)的概率。 如果是同時(shí)取的話(huà)就不會(huì)考慮排列的順序因此這就會(huì)歸類(lèi)為一個(gè)求組合的問(wèn)題。而如果是依次取的話(huà)就需要考慮排列的順序了因此這個(gè)就可以歸類(lèi)為一個(gè)排列的問(wèn)題，而對(duì)于排列的問(wèn)題我們又可以細(xì)分為放回排列和不放回排列兩種場(chǎng)景。因此我們可以將從集合Ω中取元素分類(lèi)為三種大類(lèi)型的問(wèn)題：組合、放回排列、不放回排列。
組合
對(duì)于組合類(lèi)型的問(wèn)題來(lái)說(shuō)總是描述為從N個(gè)元素的集合Ω中同時(shí)取出M個(gè)元素組成的子集Ε， 然后再問(wèn)其中的某種類(lèi)型元素或者某幾種類(lèi)型元素出現(xiàn)的個(gè)數(shù)的問(wèn)題。 這里之所以用組合的原因是強(qiáng)調(diào)同時(shí)以及不需要排列的概念，因此不需要考慮每次取的順序，就不存在排列的問(wèn)題。因此我們從N個(gè)元素里面取M個(gè)元素的總共的取法有 C(N,M) 種方法。
子問(wèn)題1: 某種類(lèi)型元素γ剛好出現(xiàn)R次。
這里的γ 是k種類(lèi)型的元素中的任意一種，數(shù)量為Nγ。 因?yàn)樗蠱個(gè)元素中γ的數(shù)量固定為R，因此其他剩下的元素的組合數(shù)量是C(N-Nγ, M-R)， 而在Nγ個(gè)中取R個(gè)元素γ的組合數(shù)量是 C(Nγ, R)。因此一共有：
C(Nγ,R) * C(N-Nγ, M-R)
舉例1：一個(gè)袋中有5個(gè)白球，3個(gè)紅球。一次取2個(gè)問(wèn)取到的是2個(gè)紅球的概率？
_ 答 _ ：C(5,0) * C(3,2) / C(8,2) = 3 / 28
舉例2：一個(gè)袋中有5個(gè)白球，3個(gè)紅球。一次取2個(gè)問(wèn)取到的是2個(gè)相同的球的取法？
_ 答 _： C(5,0) * C(3,2) + C(3,0) * C(5,2) = 13
子問(wèn)題2： 某種類(lèi)型元素γ最多出現(xiàn)R次。
這個(gè)問(wèn)題可以理解為分別計(jì)算出現(xiàn)0次到R次的和：
R
ΣC(Nγ, i) * C(N-Nγ, M-i)
i=0
舉例1：一個(gè)袋中有5個(gè)白球，3個(gè)紅球。一次取2個(gè)，取到的不是紅球的概率？
C(5,2) * C(3,0) / C(8,2) = 10 / 28 //紅球0次
子問(wèn)題3： 某種類(lèi)型元素γ最少出現(xiàn)R次。
M
Σ C(Nγ, i) * C(N-Nγ, M-i)
i=R
子問(wèn)題4： 元素α出現(xiàn)A次，元素β出現(xiàn)B次... 元素γ出現(xiàn)R次。A + B + .. R <= M
C(Nα, A) * C(Nβ, B) * ... C(Nγ, R) * C(Nα-Nβ - ... Nγ , M - A - B -... R)
舉例1：一個(gè)袋中有5個(gè)白球，3個(gè)紅球。一次取2個(gè)，取到的是一個(gè)白球和一個(gè)紅球的概率
_ 答 _: C(5,1) * C(3,1) * C(8-8, 2-1-1) / C(2,8) = 15 / 28
舉例2：一個(gè)袋中有5個(gè)白球，3個(gè)紅球。一次取3個(gè)，取到的是一個(gè)白球和一個(gè)紅球的概率
_ 答 _: C(5,1) * C(3,1) * C(8-8, 3-1-1) / C(2,8) = 0 / 28 // 因?yàn)镃(0,1) == 0, 這是因?yàn)榘咨图t色取3個(gè)，不可能只有一個(gè)白球和一個(gè)紅球的情況。
舉例3： 口袋中有10個(gè)球，分別標(biāo)號(hào)為1到10，現(xiàn)在從中任選3只，問(wèn)最小號(hào)為5的取法？
_ 答 _: 這個(gè)問(wèn)題可以簡(jiǎn)化為 5個(gè)大于5的元素為一類(lèi)，5為一類(lèi)，4個(gè)小于5的元素為一類(lèi)，這樣就轉(zhuǎn)化為了大于5的元素出現(xiàn)2次，等于5的元素出現(xiàn)1次的數(shù)量了： C(5,2) * C(1,1) * C(10 - 5 - 1, 3 -2 -1) = 10
子問(wèn)題5：元素α至少出現(xiàn)A次，元素β出現(xiàn)B次。
這個(gè)問(wèn)題可以先選擇β 再來(lái)選擇α。
M - B
C(Nβ, B) * Σ C(Nα, i ) * C(N-Nα-Nβ, M - i - B)
i = A
子問(wèn)題6： 元素α至少出現(xiàn)A次，元素β至少出現(xiàn)B次... 元素γ至少出現(xiàn)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：一個(gè)袋中有10個(gè)白球，20個(gè)紅球，30個(gè)黑球。 一次取18個(gè)，問(wèn)取到的結(jié)果中白球至少有3個(gè)，紅球至少有2個(gè)，黑球至少有4個(gè)的取法
_ 答：_ 按上述公式套入即可
子問(wèn)題7： 元素α至多出現(xiàn)A次，元素β至多出現(xiàn)B次... 元素γ至多出現(xiàn)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個(gè)元素中取出一個(gè)元素，然后再放回，然后再繼續(xù)取，依次取M次。這樣一次就有N種取法，M次就一共有N^M種取法，因?yàn)槭且来稳∷孕枰紤]排列的順序。 可放回排列也稱(chēng)為n重伯努利實(shí)驗(yàn)。每次取的元素都是獨(dú)立的。
子問(wèn)題1： 第i次取到是元素γ的方法。
第i次有Nγ種取法，其他M-1次都有N種。因此結(jié)果是：
Nγ * N^(M-1)
上面公式中無(wú)論哪次取的概率都是： Nγ / N。這個(gè)就像可重復(fù)抽獎(jiǎng)一樣，對(duì)于獎(jiǎng)品每次的概率都是一樣的。
子問(wèn)題2： 只有第i次取到的是元素γ的方法。（1 <= i <= M)
因?yàn)橹挥械趇次取到元素γ，因此前面和后面都不能再出現(xiàn)γ了，這樣的數(shù)量為：
(N-Nγ)^(i-1) * Nγ * (N - Nγ)^(M-i) == Nγ * (N-Nγ)^(M-1)
子問(wèn)題3： 取到γ元素R次的取法。
某元素一次可能出現(xiàn)在任何一個(gè)位置，某次出現(xiàn)的次數(shù)是: Nγ * (N-Nγ)^(M-1) 。而因?yàn)槌霈F(xiàn)R次所以有：Nγ^R * (N - Nγ)^(M - R), 而這R次一共有 C(M, R)種位置擺放。因此最終的數(shù)量是：
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種類(lèi)型的元素，這個(gè)結(jié)果正是二項(xiàng)分布的公式。因此二項(xiàng)里面的概率p其實(shí)就是這種元素的個(gè)數(shù)Nγ/N。
舉例1 骰子連續(xù)擲2次，求最小點(diǎn)數(shù)是2的方法？
_ 答：_ 每次有6種結(jié)果，可重復(fù)排列，因?yàn)檫@里要求最小為2，因此我們可以劃分為 {3，4，5，6} {2} 2個(gè)集合,這樣可以用 { 4 * a, 1*b} 這種形式，因此問(wèn)題變?yōu)榱饲骲出現(xiàn)1次或者出現(xiàn)2次的問(wèn)題：
11*(5-1)(2-1) * C(2,1) + 12*(5-1)(2-2)*C(2,2) = 8 + 1 = 9
子問(wèn)題3 ： 第i次取到α, 第j次取到β, .. 第w次取到γ ( i <>j <>...<>w)。取的種類(lèi)數(shù)為R
Nα * Nβ * ... Nγ * N^(M - R)
子問(wèn)題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個(gè)白球，4個(gè)黑球，6個(gè)紅球，可放回取，取7次。問(wèn)取到3顆白球和2顆黑球的方法？
_ 答: _ 10^3 * 4^2 * 6 ^ 2 * C(7,3) * C(4,2)
不放回排列
不放回排列是從N個(gè)元素里面依次取，每次取1個(gè)，然后一共取M次。這樣第一次有N種取法，第二次有N-1種取法，第M次有N-M+1種取法，因此總的可取的數(shù)量是：A(N,M) 。這里的排列是要考慮順序的。
子問(wèn)題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)
子問(wèn)題2： 取到γ元素R次。 (R < Nγ)
某一個(gè)位置上一共有 A(Nγ, R) * A(N-Nγ, M-R)，一共有 C(M,R)種放置方法。因此結(jié)果是：
C(M,R) * A(Nγ, R) * A(N-Nγ,M-R)
子問(wèn)題3 ： 第i次取到α, 第j次取到β, ... 第w次取到γ ( i <>j <>... w) 類(lèi)型數(shù)量為R
這個(gè)問(wèn)題因?yàn)槊看稳〉降闹岛推渌恢萌〉降闹禑o(wú)關(guān)，每種類(lèi)型的方法都是其元素的數(shù)量，因此可以用乘法，剩余的再用排列來(lái)計(jì)算。
Nα * Nβ * ...*Nγ * A(N-R, M-R)
子問(wèn)題4： 取到α元素A次，β元素B次,... γ元素R次
這個(gè)問(wèn)題中每種類(lèi)型出現(xiàn)的次數(shù)固定，因此這種類(lèi)型用排列，每種元素之間用乘法來(lái)實(shí)現(xiàn)，同時(shí)每種元素的位置則是用組合。
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個(gè)白球，4個(gè)黑球，6個(gè)紅球，不放回取，取7次。問(wèn)取到3顆白球和2顆黑球的方法？
_ 答: _ C(7,3) * C(4,2) * A(10, 3) * A(4,2) * A(6 , 2)
總結(jié)
通過(guò)上面的公式，我們可以發(fā)現(xiàn)這些公式之間的一些相似的特征:
- 某種元素γ出現(xiàn)的次數(shù)R的公式可以分解為三部分：位置部分 * 自身的排列組合部分 * 剩余元素的排列組合部分 。位置部分總是C(M,Nγ); 自身的排列組合部分則組合總是1，可放回排列則是Nγ^R，不可放回排列則是A(Nγ,R); 剩余元素的排列組合部分則組合是C(N-Nγ, M-R), 可放回排列則是(N-Nγ)^(M-R), 不可放回排列則是A(N-Nγ, M-R)。
- 多種元素出現(xiàn)次數(shù)的公式則是單種元素出現(xiàn)次數(shù)的乘積，而且和出現(xiàn)的順序是無(wú)關(guān)的，正因?yàn)槿绱瞬趴梢允褂贸朔ü健?/li>
- 某個(gè)元素至多至少出現(xiàn)的R的公式則可以分解為從0到R次(至多)或者R到M次(至少)的和來(lái)計(jì)算。
- 某些問(wèn)題看似和上面描述的各種子問(wèn)題無(wú)關(guān)，但是我們可以通過(guò)一定的方式來(lái)轉(zhuǎn)化為上述各種子問(wèn)題來(lái)求解。例如我們要把N個(gè)元素放入M個(gè)位置(N <=M)時(shí)則可以反過(guò)來(lái)看成一個(gè)可放回的排列問(wèn)題把位置M當(dāng)做元素而把元素N當(dāng)做位置來(lái)求解。
