公式
有时候也表示成:
组合公式的推导是由排列公式去掉重复的部分而来的,排列公式是建立一个模型,从n个不相同元素中取出m个排成一列(有序),第一个位置可以有n个选择,第二个位置可以有n-1个选择(已经有1个放在前一个位置),则同理可知第三个位置可以有n-2个选择,以此类推第m个位置可以有n-m+1个选择,则排列数为,而组合公式对应另一个模型,取出m个成为一组(无序),由于m个元素组成的一组可以有m!种不同的排列(全排列),组合的总数就是。
性质
递推公式
等式左边表示从 m个元素中选取 n 个元素,而等式右边表示这一个过程的另一种实现方法:任意选择m中的某个备选元素为特殊元素,从 m 中选 n 个元素可以由此特殊元素的被包含与否分成两类情况,即 n 个被选择元素包含了特殊元素和 n 个被选择元素不包含该特殊元素。前者相当于从 m-1 个元素中选出 n-1 个元素的组合,即;后者相当于从 m-1 个元素中选出 n 个元素的组合,即 。
相关运用:的二项式定理的系数,即为此数列;任何集合的子集个数也为用为此数列,而得出为 个。
算法举例
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 证明:
方法1、可直接利用组合数的公式证明。
方法2、(更重要的思路)。
从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)
公式5(公式4的同种)
S(K=0,N)K*(K-1)*C(M,K)
=S(K=0,N-2)M*(M-1)*C(M-2,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