从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

• 中文名 组合数
• 外文名 combinatorial number
• 所属学科 数学
• 公式 C(m,n)=n!/((n-m)!*m!)(m≤n)
• 性质1 C(m,n)= C(n-m,n)

定义

　　从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.组合恒等式

　　若表示在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