组合数查看源代码讨论查看历史
| 组合数 | |
|---|---|
组合数，从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