組合數檢視原始碼討論檢視歷史
| 組合數 | |
|---|---|
組合數，從n個不同元素中，任取m(m≤n)個元素並成一組，叫做從n個不同元素中取出m個元素的一個組合;從n個不同元素中取出m(m≤n)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數。[1]
定義
從m個不同元素中取出n(n≤m)個元素的所有組合的個數，叫做從m個不同元素中取出n個元素的組合數(Combination)。
公式
在線性寫法中被寫作C(m,n)。
c(m,n)=p(m,n)/n!=m!/((m-n)!*n!)
性質
1.互補性質
組合數性質如右圖所示：
即從m個不同元素中取出n個元素的組合數=從m個不同元素中取出(m-n)個元素的組合數
這個性質很容易理解，例如C(9,2)=C(9,7)，即從9個元素里選擇2個元素的方法與從9個元素里選擇7個元素的方法是相等的。
規定:C(m,0)=1 [2]
2.組合恆等式
若表示在n個物品中選取m個物品，則如存在下述公式: C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)
變換技巧舉例
1、設15000件產品中有1000件次品，從中拿出150件，求得到次品數的期望和方差?
2、設某射手對同一目標射擊，直到射中R次為止，記X為使用的射擊次數，已知命中率為P，求E(X)、D(X)。
這兩題都要用到一些技巧。我先列出幾個重要公式，證明過程中提供變換技巧，然後把這兩個題目作為例題。
先定義一個符號，用S(K=1，N)F(K)表示函數F(K)從K=1到K=N求和。(我不會用求和的符號)
公式1:
C(M-1，N-1)+C(M-1，N)=C(M，N)
證明:方法1、可直接利用組合數的公式證明
方法2、(更重要的思路)
C(M，N)是從M個物品中任選N個的方法。
從M個物品中任意指定一個。則選出N個的方法中，包含這一個的有C(M-1，N-1)種，不包含這一個的有C(M-1，N)種。
因此，C(M-1，N-1)+C(M-1，N)=C(M，N)
公式2:
S(K=N，M)C(K-1，N-1)=C(M，N) (M》=N)
證明:C(M，N)是從M個物品中任選N個的方法。
從M個物品中任意指定M-N個，並按次序編號為第1到第M-N號，而其餘的還有N個。
則選出N個的方法可分類為:
包含1號的有C(M-1，N-1)種;
不包含1號，但包含2號的有C(M-2，N-1)種;
。。。。。。
不包含1到M-K號，但包含M-K+1號的有C(K-1，N-1)種
。。。。。。
不包含1到M-N-1號，但包含M-N號的有C(N，N-1)種不包含1到M-N號的有C(N，N)種，而C(N，N)=C(N-1，N-1)
由於兩種思路都是從M個物品中任選N個的方法，因此
S(K=N，M)C(K-1，N-1)=C(M，N)
公式3:
S(K=0，N)C(P，K)*C(Q，N-K)=C(P+Q，N) (P，Q)=N)
證明:一批產品包含P件正品和Q件次品，則從這批產品中任選N件的選法為C(P+Q，N)。而公式裡面的K表示選法中正品數量，
C(P，K)*C(Q，N-K)表示N件產品中有K件正品，N-K件次品的選法。K從0到N變化時，就包含了所有不同正品、次品數的組合。
因此，S(K=0，N)C(P，K)*C(Q，N-K)=C(P+Q，N)
公式4(一種變換技巧):
S(K=0，N)K*C(M，K)=S(K=0，N-1)M*C(M-1，K)
證明:
S(K=0，N)K*C(M，K)
=S(K=1，N)K*C(M，K)
=S(K=1，N)K*M!/K!/(M-K)!
=S(K=1，N)M*(M-1)!/(K-1)!/(M-K)!
=S(K=1，N)M*C(M-1，K-1)
=S(K=0，N-1)M*C(M-1，K)
證明:(類似上式)
S(K=0，N)K*(K-1)*C(M，K)
=S(K=2，N)K*(K-1)*M!/K!/(M-K)!
=S(K=2，N)M*(M-1)*(M-2)!/(K-2)!/(M-K)!
=S(K=2，N)M*(M-1)*C(M-2，K-2)
=S(K=0，N-2)M*(M-1)*C(M-2，K)
公式4用於求數學期望，公式4、公式5結合起來可用於求方差。
例1、設15000件產品中有1000件次品，從中拿出150件，求得到次品數的期望和方差?
解:(本題利用公式3、4、5)
有K件次品的概率為:
P(K)=C(1000，K)*C(14000，150-K)/C(15000，150)
E(X)
=S(K=0，150)K*C(1000，K)*C(14000，150-K)/C(15000，150)
=S(K=0，149)1000*C(999，K)*(14000，149-K)/C(15000，150)
=1000*C(14999，149)/C(15000，150)
=10
D(X)
=S(K=0，150)(K-10)*(K-10)*C(1000，K)*C(14000，150-K)/C(15000，150)
=S(K=0，150)(K*K-K-19*K+100)*C(1000，K)*C(14000，150-K)/C(15000，150)
=S(K=0，150)K*(K-1)*C(1000，K)*C(14000，150-K)/C(15000，150)
-19*S(K=0，150)K*C(1000，K)*C(14000，150-K)/C(15000，150)
+100*S(K=0，150)C(1000，K)*C(14000，150-K)/C(15000，150)
=S(K=0，148)1000*999*C(998，K)*C(14000，148-K)/C(15000，150)
-19*S(K=0，149)*1000*C(999，K)*C(14000，149-K)/C(15000，150)
+100*S(K=0，150)C(1000，K)*C(14000，150-K)/C(15000，150)
=1000*999*C(14998，148)/C(15000，150)
-19*1000*C(14999，149)/C(15000，150)+100
=138600/14999
=9.240616041
此題推廣形式為:
設M件產品中有P件次品，從中拿出N件(N《=P)，求得到次品數的期望和方差?
E(X)=P*N/M
D(X)=P*(P-1)*C(M-2，N-2)/C(M，N)
+(1-2*P*N/M)*P*C(M-2，N-2)/C(M，N)+(P*N/M)^2
例2、設某射手對同一目標射擊，直到射中R次為止，記X為使用的射擊次數，已知命中率為P，求E(X)、D(X)。
解:射中R次，使用的射擊次數為K次(K>=R)，則前K-1次射中R-1次，第K次射中了，概率為:
P(K)=C(K-1，R-1)*P^R*(1-P)^(K-R)
(以下暫時用W表示無窮大)
射中R次，使用的射擊次數可為R次、R+1次...W次
因此S(K=R，W)P(K)=1 (這是概率的特點)
即:S(K=R，W)C(K-1，R-1)*P^R*(1-P)^(K-R)=1
以上證明的式子是另一個公式，即無論P，R是什麼數都成立，以下將應用這一公式。
E(X)
=S(K=R，W)K*C(K-1，R-1)*P^R*(1-P)^(K-R)
=S(K=R，W)K*(K-1)!/(R-1)!/(K-R)!*P^R*(1-P)^(K-R)
=S(K=R，W)R*K!/R!/(K-R)!*P^R*(1-P)^(K-R)
=S(K=R，W)R*C(K，R)*P^R*(1-P)^(K-R)
=R/P*S(K=R，W)C(K，R)*P^(R+1)*(1-P)^(K-R)
令K1=K+1，R1=R+1，則
E(X)=R/P*S(K1=R1，W)C(K1-1，R1-1)*P^R1*(1-P)^(K1-R1)
利用以上公式得
E(X)=P/R
D(X)
=S(K=R，W)(K-R/P)^2*C(K-1，R-1)*P^R*(1-P)^(K-R)
=S(K=R，W)(K*K-2*K*R/P+R*R/P/P)*C(K-1，R-1)*P^R*(1-P)^(K-R)
=S(K=R，W)[K*(K+1)-(K+2*K*R/P)+R*R/P/P]*C(K-1，R-1)*P^R*(1-P)^(K-R)
=S(K=R，W)[K*(K+1)*C(K-1，R-1)*P^R*(1-P)^(K-R)
-S(K=R，W)(K+2*K*R/P)*C(K-1，R-1)*P^R*(1-P)^(K-R)
+S(K=R，W)R*R/P/P*C(K-1，R-1)*P^R*(1-P)^(K-R)
=(推導過程同求E(X)，略)
=R(R+1)/P/P-(2*R+P)*R/P/P+R*R/P/P
=(1-P)*R/P/P