组合数公式558.pdf
.；.组合数公式 编辑 锁定 组合数公式是指从 m 个不同元素中，任取 n(nm)个元素并成一组，叫做从 m 个不同元素中取出n 个元素的一个组合；从m 个不同元素中取出 n(nm)个元素的所有组合的个数，叫做从 m 个不同元素中取出 n 个元素的组合数。用符号 c(m,n)表示。中文名 组合数公式 公式写法 c(m,n)=p(m,n)/n!递推公式 c(m,n)=c(m-1,n-1)+c(m-1,n)应用领域 数学等 目录 1.1 公式 2.2 性质 3.3 递推公式 4.4 算法举例 组合数公式公式 编辑 有时候也表示成：（在旧版本里，排列数的字母写作 P）组合公式的推导是由排列公式去掉重复的部分而来的，排列公式是建立一个模型，从 n个不相同元素中取出 m 个排成一列（有序），第一个位置可以有 n 个选择，第二个位置可以有 n-1 个选择（已经有 1 个放在前一个位置），则同理可知第三个位置可以有 n-2 个选择，以此类推第 m 个位置可以有 n-m+1 个选择，则排列数为 ，而组合公式对应另一个模型,取出 m 个成为一组（无序）,由于 m 个元素组成的一组可以有 m!种不同的排列（全排列 ）,组合的总数就是 .；.组合数公式性质 编辑 组合数公式递推公式 编辑 c(m,n)=c(m-1,n-1)+c(m-1,n)等式左边表示从 m 个元素中选取 n 个元素，而等式右边表示这一个过程的另一种实现方法：任意选择 m 中的某个备选元素为特殊元素，从 m 中选 n 个元素可以由此特殊元素的被包含与否分成两类情况，即 n 个被选择元素包含了特殊元素和 n 个被选择元素不包含该特殊元素。前者相当于从 m-1 个元素中选出 n-1 个元素的组合，即 c(m-1,n-1)；后者相当于从 m-1 个元素中选出 n 个元素的组合，即 c(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）*PR*(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）*PR*(1-P)(K-R)=1 以上证明的式子是另一个公式，即无论 P，R 是什么数都成立，以下将应用这一公式。E（X）.；.=S（K=R，W）K*C（K-1，R-1）*PR*(1-P)(K-R)=S（K=R，W）K*（K-1）！/（R-1）！/（K-R）！*PR*(1-P)(K-R)=S（K=R，W）R*K！/R！/（K-R）！*PR*(1-P)(K-R)=S（K=R，W）R*C（K，R）*PR*(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）*PR1*(1-P)(K1-R1)利用以上公式得 E（X）=P/R D（X）=S（K=R，W）（K-R/P）2*C（K-1，R-1）*PR*(1-P)(K-R)=S（K=R，W）（K*K-2*K*R/P+R*R/P/P）*C（K-1，R-1）*PR*(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）*PR*(1-P)(K-R)=S（K=R，W）K*（K+1）*C（K-1，R-1）*PR*(1-P)(K-R)-S（K=R，W）（K+2*K*R/P）*C（K-1，R-1）*PR*(1-P)(K-R)+S（K=R，W）R*R/P/P*C（K-1，R-1）*PR*(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
