两个计数原理与排列组合知识点及例题

1、两个计数原理与排列组合知识点及例题两个计数原理内容1分类计数原理：完成一件事，有 n n 类办法，在第 1 1 类办法中有 m m 种不同的方法，在第2 2 类办法中有 m m 种不同的方法在第 n n 类办法中有 m m 种不同的方法，那么完成这件事共有 N N 二 m+mm+m + +.+m+m 种不同的方法2、分步计数原理：完成一件事，需要分 n n 个步骤，做第 1 1 步骤有 m m 种不同的方法，做第2 2 步骤有 m m 种不同的方法. 做第 n n 步骤有 m m 种不同的方法，那么完成这件事共有 N N 二 mXmmXm x x.x x m m 种不同的方法.例题分析例 1

2、某学校食堂备有 5 种素菜、3 种荤菜、2 种汤。现要配成一荤一素一汤的套餐。问可以配制出多少种不同的品种？分析：1完成的这件事是什么？2、如何完成这件事？(配一个荤菜、配一个素菜、配一汤)3、它们属于分类还是分步？(是否独立完成)4、运用哪个计数原理？5、进行计算.解：属于分步：第一步 配一个荤菜 有 3 种选择第二步配一个素菜 有 5 种选择第三步配一个汤有 2 种选择共有 N=3X 5X2=30 (种)例 2 有一个书架共有 2 层，上层放有 5 本不同的数学书，下层放有 4 本不同的语文书。(1)从书架上任取一本书，有多少种不同的取法？(2)从书架上任取一本数学书和一本语文书，有多少种

3、不同的取法？(1)分析：完成的这件事是什么？2、如何完成这件事？3、它们属于分类还是分步？（是否独立完成）4、运用哪个计数原理？5、进行计算。解：属于分类：第一类从上层取一本书有 5 种选择第二类 从下层取一本书有 4 种选择共有 N=5+4=9 （种）（2）分析：1完成的这件事是什么？2、如何完成这件事？3、它们属于分类还是分步？（是否独立完成）4、运用哪个计数原理？5、进行计算.解：属于分步：第一步从上层取一本书有 5 种选择第二步 从下层取一本书有 4 种选择共有 N=5X 4=20 （种）例 3、 有 1、2、3、4、5 五个数字.（1）可以组成多少个不同的三位数？（2）可以组成多少个

4、无重复数字的三位数？（3）可以组成多少个无重复数字的偶数的三位数？（1）分析：1、完成的这件事是什么？2、如何完成这件事？（配百位数、配十位数、配个位数）3、它们属于分类还是分步？（是否独立完成）4、运用哪个计数原理？5、进行计算.略解：N=5X 5X5=125 （个）【例题解析】某人有 4 条不同颜色的领带和 6 件不同款式的衬衣，问可以有多少种不同的搭配方法?2、有一个班级共有 46 名学生，其中男生有 21 名.(1) 现要选派一名学生代表班级参加学校的学代会，有多少种不同的选派方法？(2) 若要选派男、女各一名学生代表班级参加学校的学代会，有多少种不同的选派方法?8. 组合数公式：c：

5、Amn(n 1)(n 2)L(nm 1)或c：(n,m N ,且m n)Amm!m!(n m)!9. 组合数的性质 1：c；mcnnm.规定：co1；10. 组合数的性质 2：cnn1=g+cnrcno+cn1+-+cn=2n3、有 0、1、2、3、4、5 六个数字.(1)可以组成多少个不同的三位数？(2)可以组成多少个无重复数字的三位数？(3)可以组成多少个无重复数字的偶数的三位数?排列与组合1. 排列的概念：从n个不同元素中，任取m( m n )个元素(这里的被取元素各不相 同)按照一定的顺序 排成一列，叫做从n个不同元素中取出m个元素的一个排列2. 排列数的定义：从n个不同元素中，任取m

6、( m n )个元素的所有排列的个数叫做从n个元素中取出m元素的排列数，用符号A：表示3. 排列数公式：Anmn(n 1)(n 2)L (n m 1)(m,n N , m n)4. 阶乘：n!表示正整数 1 到n的连乘积，叫做n的阶乘规定 0! 1.5. 排列数的另一个计算公式：阳=(n m)!6. 组合概念：从n个不同元素中取出mm n 个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合7. 组合数的概念：从n个不同元素中取出mm n 个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号cm表示.题型讲解例 1 分别求出符合下列要求的不同排法的种数(1) 6 名学

7、生排 3 排，前排 1 人，中排 2 人，后排 3 人；(2) 6 名学生排成一排，甲不在排头也不在排尾；(3)从 6 名运动员中选出 4 人参加 4X100 米接力赛，甲不跑第一棒，乙不跑第四棒；(4) 6 人排成一排，甲、乙必须相邻；(5) 6 人排成一排，甲、乙不相邻；(6) 6 人排成一排，限定甲要排在乙的左边，乙要排在丙的左边(甲、乙、丙可以不相邻)解：(1)分排坐法与直排坐法一一对应，故排法种数为A 720(2)甲不能排头尾，让受特殊限制的甲先选位置，有A1种选法，然后其他 5 人选，有A种选法，故排法种数为A4A5480(3) 有两棒受限制，以第一棒的人选来分类：1乙跑第一棒，其

8、余棒次则不受限制，排法数为A3；2乙不跑第一棒，则跑第一棒的人有A：种选法，第四棒除了乙和第一棒选定的人外，也有A：种选法，其余两棒次不受限制，故有A：A4A；种排法，由分类计数原理，共有AA：A：A2252种排法(4)将甲乙“捆绑”成“一个元”与其他4 人一起作全排列共有(6)三人的顺序定，实质是从6 个位置中选出三个位置，然后排按规定的顺序放置这三人，其余A；A；5240种排法(5)甲乙不相邻，第一步除甲乙外的其余4 人先排好；第二步，甲、乙选择已排好的4 人的左、右及之间的空挡插位，共有A：A；(或用 6 人的排列数减去问题(2)后排列数为A 240 480)按分类计数原理有C；7c；c

9、&c；446976种点评：此题是只选“元”而不排“序”的典型的组合问题，附加的条件是从不同种类的元素中抽取，应当注意：如果第（3）题采用先从 3 件次品抽取 2 件（以保证至少有 2 件是次品），再从余 下的 98 件产品中任意抽取 3 件的抽法，那么所得结果是C；C；8466288种，其结论是错误的，错在“重复”：假设 3 件次品是AB、C,第一步先抽AB 第二步再抽 C 和其余 2 件正品，与第一步先抽AC （或 B C）,第二步再抽 B （或 A）和其余 2 件正品是同一种抽法，但在算式C；C；8中算作 3种不同抽法 例 3 求证：Anm1mAnm11A：:cm1证明：利用排列数

10、公式n m n 1! m n 1 !n !A：右n m !n m !另一种证法：（利用排列的定义理解）从 n 个元素中取 m 个元素排列可以分成两类:（1）不同的映射f有多少个？（2） 若要求fa f b f c f d4则不同的映射f有多少个？分析：（1）确定一个映射f，需要确定a, b, c, d的像（2）a, b, c, d的象元之和为 4，则加数可能出现多种情况，即4 有多种分析方案，各方案独立且并列需要分类计算解：（1） A 中每个元都可选 0,1,2 三者之一为像，由分步计数原理，共有3 3 3 3 34个不同映射（2）根据a,b,c, d对应的像为 2 的个数来分类，可分为三类：

11、第一类：没有元素的像为2，其和又为 4,必然其像均为 1,这样的映射只有一个；第二类：一个元素的像是2，其余三个元素的像必为 0,1,1 ,这样的映射有12个；人在 3 个位置上全排列，故有排法C；A；120种点评：排队问题是一类典型的排列问题，常见的附加条件是定位与限位、相邻与不相邻第一类不含某特殊元素a的排列有Am1第二类含元素a的排列则先从n 1个元素中取出m 1个元素排列有A：,种，然后将a插入,共有 m 个空档，故有m Anm11种，因此m 1mAn 1An利用组合数公式2n !例 2 假设在 100 件产品中有 3 件是次品，从中任意抽取5 件，求下列抽取方法各多少种？（1）没有次

12、品；（2）恰有两件是次品；（3）至少有两件是次品解：（1）没有次品的抽法就是从 97 件正品中抽取 5 件的抽法，共有C9764446024种（2） 恰有 2 件是次品的抽法就是从 97 件正品中抽取 3 件，并从 3 件次品中抽 2 件的抽法，共 有C；7c；442320种（3）至少有 2 件次品的抽法，按次品件数来分有二类：第一类，从 97 件正品中抽取 3 件，并从 3 件次品中抽取 2 件，有C97C；种第二类从 97 件正品中抽取 2 件，并将 3 件次品全部抽取，有C&C；种另法：利用公式cmCnn1cm11推得左Cm 1mnCnCmm 1nCn点评：证明排列、组合恒等式通

13、常利用排列数、组合数公式及组合数基本性质例 4 已知f是集合A a,b,c,d至傑合B 0,1,2的映射Cm 1nm 1n1Cn1Cn 2右Cmn12叫Cm 1 n2第三类：二个元素的像是 2，另两个元素的像必为 0,这样的映射有C426个由分类计数原理共有 1+12+6=19 （个）点评：问题（1）可套用投信模型：n 封不同的信投入 m 个不同的信箱，有mn种方法；问题（2）的关键结合映射概念恰当确定分类标准，做到不重、不漏例 5 四面体的顶点和各棱的中点共10 个点（1） 设一个顶点为 A,从其他 9 点中取 3 个点，使它们和点 A 在同一平面上，不同的取法有多 少种？（2）在这 10

14、点中取 4 个不共面的点，不同的取法有多少种？解：（1）如图，含顶点 A 的四面体的三个面上，除点 A 外都有 5 个点，从中取出 3 点必与点 A 共面，共有3C；种取法含顶点 A 的棱有三条，每条棱上有 3 个点，它们与所对棱的中点共面，共有3 种取法根据分类计数原理和点 A 共面三点取法共有3C；333种（2）取出的 4 点不共面比取出的 4 点共面的情形要复杂，故采用间接法：先不加限制任取4 点4（C10种取法）减去 4 点共面的取法取出的 4 点共面有三类：第一类：从四面体的同一个面上的6 点取出 4 点共面，有4C；种取法第二类：每条棱上的 3 个点与所对棱的中点共面，有 6 种取

15、法第三类：从 6 条棱的中点取 4 个点共面，有 3 种取法根据分类计数原理 4 点共面取法共有4C；6369故取 4 个点不共面的不同取法有C104C；6 3141（种）点评：由点构成直线、平面、几何体等图形是一类典型的组合问题，附加的条件是点共线与不共线，点共面与不共面，线共面与不共面等小结：m个不同的元素必须相邻，有pmm种“捆绑”方法m个不同元素互不相邻，分别“插入”到n个“间隙”中的m个位置有Pnm种不同的“插 入”方法m个相同的元素互不相邻，分别“插入”到n个“间隙”中的m个位置，有Cn种不同的“插入”方法若干个不同的元素“等分”为m个组，要将选取出每一个组的组合数的乘积除以P,【

16、例题解析】例 1 完成下列选择题与填空题（1） 有三个不同的信箱，今有四封不同的信欲投其中，则不同的投法有_种。B.64（2）四名学生争夺三项冠军， 获得冠军的可能的种数是（）B.64（3）有四位学生参加三项不同的竞赛，1每位学生必须参加一项竞赛，则有不同的参赛方法有 _ ;2每项竞赛只许有一位学生参加，则有不同的参赛方法有 _;3每位学生最多参加一项竞赛，每项竞赛只许有一位学生参加，则不同的参赛方法有_ 。解析 （1）完成一件事是“分步”进行还是“分类”进行，是选用基本原理的关键。将“投四 封信”这件事分四步完成，每投一封信作为一步，每步都有投入三个不同信箱的三种方法，因此： N=3X3X3

17、X3=34=81，故答案选 A。本题也可以这样分类完成， 四封信投入一个信箱中，有 C31种投法；四封信投入两个信箱中，有G2（C41 A2+C2 G2）种投法；四封信投入三个信箱，有两封信在同一信箱中，有C2 A33种投法，故共有 G+G （ C4 A2+C4C2） +C4 A3=81 （种）。故选 A。（2）因学生可同时夺得 n 项冠军， 故学生可重复排列， 将 4 名学生看作 4 个“店”， 3 项冠军看 作“客”，每个“客”都可住进 4 家“店”中的任意一家，即每个“客”有4 种住宿法。 由分步计数 原理得：N=4X4X4=64。故答案选 B。（3）学生可以选择项目， 而竞赛项目对学生

18、无条件限制，所以类似（1）可得 N=34=81 （种）;2竞赛项目可以挑学生，而学生无选择项目的机会，每一项可以挑4 种不同学生，共有 N=4=64 （种）；3等价于从 4 个学生中挑选 3 个学生去参加三个项目的竞赛，每人参加一项， 故共有 C3A3=24 （种）。注： 本题有许多形式，一般地都可以看作下列命题：设集合 A=a1,a2,an,集合 B=b1,b2,b ，贝Uf : 2 B 的不同映射是 m,f ：A 的不同映射是 nm。若 nwm 则 f : ATB 的单值映射是：血。例 2 同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四 张贺年卡不同的分配方式

19、有（）种种种种解法一 由于共四人（用 1, 2, 3, 4 代表甲、乙、丙、丁四人），这个数目不大，化为填数问题之后，可用穷举法进行具体的填写:2 14 32 34 124 1 33 14 234 134 2 14 12 34 3 1243 2 1再按照题目要求检验，最终易知有9 种分配方法。解法二 记四人为甲、乙、丙、丁，则甲送出的卡片可以且只可以由其他三人之一收到，故有3 种分配方式；以乙收到为例，其他人收到卡片的情况可分为两类：第一类：甲收到乙送出的卡片，这时丙、丁只有互送卡片1 种分配方式；第二类：甲收到的不是乙送出的卡片，这时，甲收到卡片的方式有 2 种（分别是丙和丁送出的）对每一种

20、情况，丙、丁收到卡片的方式只有一种。因此，根据乘法原理，不同的分配方式数为3X（1+2） =9。解法三 给四个人编号：1 , 2, 3, 4,每个号码代表 1 个人，人与号码之间的关系为一对一的 关系；每个人送出的贺年卡赋给与其编号相同的数字作为代表，这样，贺年卡的分配问题可抽象为 如下“数学问题”：将数字1, 2, 3, 4,填入标号为 1, 2, 3, 4 的 4 个方格里，每格填写一个数字， 且每个方格的编号与所填数字都不同的填法共有多少种（也可以说成：用数字1, 2, 3, 4 组成没有重复数字的 4 位数，而且每位数字都不等于位数的4 位数共有多少个）？这时，可用乘法原理求解答案：首

21、先，在第 1 号方格里填写数字，可填上2、3、4 中的任一个数，有 3 种填法；其次，当第 1 号方格填写的数字为 i（20,即 a、b 异号。b（1）若 c=0, a、b 各有 3种取法，排除 2 个重复（3x-3y=0,2x-2y=0,x-y=0）,故有 3X3-2=7（条）。（2） 若 c丰0, a 有 3 种取法，b 有 3 种取法，而同时 c 还有 4 种取法，且其中任两条直线均不 相同，故这样的直线有3X3X4=36 条，从而符合要求的直线共有7+36=43 条。注：本题是 1999 年全国高中数学联赛中的一填空题，据抽样分析正确率只有。错误原因没有对 c=0 与 c丰0 正确分类

22、；没有考虑 c=0 中出现重复的直线。例 5 平面上给定 10 个点，任意三点不共线，由这10 个点确定的直线中，无三条直线交于同一点（除原 10 点外），无两条直线互相平行。求：（1）这些直线所交成的点的个数（除原 10 点外）。（2）这些直线交成多少个三角形。解法一（1 ）由题设这 10 点所确定的直线是 GQ2=45 条。这 45 条直线除原 10 点外无三条直线交于同一点，由任意两条直线交一个点，共有C452个交点。而在原来 10 点上有 9 条直线共点于此。所以，在原来点上有10C9点被重复计数。所以这些直线交成新的点是：C452-10C92=630O（2）这些直线所交成的三角形个数

23、可如下求：因为每个三角形对应着三个顶点，这三个点来自 上述 630个点或原来的 10 个点。所以三角形的个数相当于从这640 个点中任取三个点的组合，即C6403=43 486080 （个）。解法二 （1）如图对给定的 10 点中任取 4 个点，四点连成 6 条直线，这 6 条直线交 3 个新的 点。故原题对应于在10 个点中任取 4 点的不同取法的 3 倍，即这些直线新交成的点的个数是：43C10=630。（2）同解法一。注 用排列、组合解决有关几何计算问题，除了应用排列、组合的各种方法与对策之外，还要 考虑实际几何意义。例 6 （1）如果（x+）2n展开式中，第四项与第六项的系数相等。求n

24、,并求展开式中的常数x项；（2）求（iX-1）8展开式中的所有的有理项。35解 (1)由 C2n=C2n,可得 3+5=2n/ n=4 。设第 k+1 项为常数项则 Tk+i=C8k x8-k x-k=C8k x8-2k 8-2k=0，即卩 k=4常数项为 T5=G4=70。(2)设第 k+1 项有理项，则Tk1C8k1!x4)k2C8k16 3k除以 9 所得余数为 0,即被 9 整除。(3)5-( 1+)5=1+c51 +G2 +C53 +C523-5GX=,C5X=8X10当精确到时，只要展开式的前三项和，1+=,近似值为。当精确到时，只要取展开式的前四项和，1+=,近似值为。注 (1

25、)用二项式定理来处理余数问题或整除问题时，通常把底数适当地拆成两项之和或之差 再按二项式定理展开推得所求结论。(2)用二项式定理来求近似值，可以根据不同精确度来确定应该取到展开式的第几项。例 8 证明下列不等式：(1)因为 0wkw8,要使16 3k Z,只有使 k 分别取 0, 4, 84所以所求的有理项应为：4351-2T1=x ,T5=X,T9=x8256注 (1) 二项式展开中，要注意“系数”与“二项式系数”的区别;(2)在二项展开式中求得 k 后，对应的项应该是 k+1 项。(2)已知 a、b 为正数,(a、b x|x 是正实数,n N);例 7(1 )求 4X6n+5n+1被 20

26、 除后的余数；(2) 7n+cn17n-1+cn2严+Cn-1X7 除以 9,得余数是多少?(3) 根据下列要求的精确度，求的近似值。精确到；精确到。解(1)首先考虑 4 6n+5n+1被 4 整除的余数。/ 5n+1=(4+1)n+1=4n+1+G+114n+G+124n-1+C+1n 4+1其被 4 整除的余数为 1被 20 整除的余数可以为 1, 5, 9, 13 , 17然后考虑 4 6n+1+5n+1被 5 整除的余数。/ 4 6n=4 (5+1)n=4(5n+Cn1 5n-1+G2 5n-2+Gn-1 5+1)被 5 整除的余数为 4其被 20 整除的余数可以为 4, 9, 14,

27、 19。综上所述，被 20 整除后的余数为 9。“、n _ 1n-1_ 2n-2_ n-1(2) 7 +Cn 7 +Cn 7 + +G 7=(7+1)n-仁 8n-1=(9-1)n-1=9n-Cn1 9n-1+G2 9n-2+(-1)n-1Cnn-1 9+(-1)nGn-1(i)当 n 为奇数时原式=9n-Cn1 9n-1+Cn2 9n-2+ (-1 )n-1Cnn-1 9-2除以 9 所得余数为 7。(ii)当 n 为偶数时n _ 1n-1 _ 2n-2n-1 _ n-1原式=9-Cn 9 +G 9 + +(-1) G 9且丄ab=x-+-=1，则对于 n N 有(a+b)n-an-bn 2

28、2n-2n+1。b(1)令 a=x+S,a b则 x=2a +b =(x+S) +(x-S)1n-1n从n n 1 n-1.=x +CnxS+GS+x -CnxS+(-1) GS=2(xn+C2xn-2S2+C4xn-4S亠)2xn证明bn(2) (a+b)n=an+Cn1an-1b+ +Gnbn(a+b)n=bn+C；bn-1a+Cnnan上述两式相加得：n , n . n1 , n-1n-1k, n-k. k . n-k kn, n . n、2(a+b) =(a +b )+Cn(a b+b a)+ +G (a b +b a )+ +G(a +b) (*)1 1T +=1,且 a、b 为正数

29、a b ab=a+b2 .ab ab 4又an-kbk+bn-kak 2 .anbn=2( .ab)n(k=1,2,n-1)2(a+b)n2an+2bn+Cn12.ab)n+C22 (、ab)n+ +Gn-12(、ab)nn n n(a+b) -a -b (CnJC2*+Gn-1) ( .ab)n 1 (2n-2)注 利用二项式定理的展开式，可以证明一些与自然数有关的不等式问题。题(1)中的换元法称之为均值换元(对称换元)。这样消去3奇数次项，从而使每一项均大于或等于零。题(2)中，由由称位置二项式系数相等，将展开式倒过来写再与原来的展开式相加，这样充分利用对称性来解 题的方法是利用二项式展开

30、式解题的常用方法。例 9 已知(1-ax)n展开式的第 p,p+1,p+2 三项的二项式系数构成等差数列，第 n +1-p 与第 n+2-p项的系数之和为 0,而(1-ax )n+1展开式的第 p+1 与 p+2 项的二项式系数之比为1 : 2。(1 )求(1-ax )n+1展开式的中间项；(2)求(1-ax )n的展开式中系数最大的项。解由题设得：故(1-3x )7展开式中系数最大的项为T7=G6 (-3 )6X6=5103X6。注 一般地，求(a+bx)n展开式中系数绝对值最大的项的方法是: 设第 k+1 项为系数绝对值最大的项，则由knk kk1nk1 k 1Cna-bCna -bknkkk1nk1 k 1CnabCna -b求出 k 的取值范围，从而确定第几项最大。