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

1、两个计数原理与排列组合知识点及例题两个计数原理内容1、分类计数原理：完成一件事，有n类办法，在第1类办法中有m种不同的方法，在第2类办法中有m2种不同的方法在第n类办法中有m种不同的方法，那么完成这件事共有N=m+m2 + +mn种不同的方法.2、分步计数原理：完成一件事，需要分n个步骤，做第1步骤有m种不同的方法，做第2步骤有m2种不同的方法做第n步骤有mn种不同的方法，那么完成这件事共有N=mx m xx m种不同的方法.例题分析例1某学校食堂备有5种素菜、3种荤菜、2种汤。现要配成一荤一素一汤的套餐。问可以配制出多少种不同的品种？分析：1、完成的这件事是什么？2 、如何完成这件事？（配一

2、个荤菜、配一个素菜、配一汤）3 、它们属于分类还是分步？（是否独立完成）4 、运用哪个计数原理？5 、进行计算(2)从书架上任取一本数学书和一本语文书，有多少种不冋的取法?(1)分析:1、完成的这件事是什么？2、如何完成这件事？3、它们属于分类还是分步？（是否独立完成）4、运用哪个计数原理？5、进行计算。解:属于分类：第一类从上层取一本书 有5种选择第二类从下层取一本书有4种选择共有N=5+4=9 （种）(2)分析:1、完成的这件事是什么？2、如何完成这件事？3、它们属于分类还是分步？（是否独立完成）4、运用哪个计数原理？5、进行计算解：属于分步：第一步从上层取一本书有5种选择第二步 从下层取

3、一本书有4种选择共有 N=5X 4=20 （种）例3、 有1、2、3、4、5五个数字（1）可以组成多少个不同的三位数？（2）可以组成多少个无重复数字的三位数？（3）可以组成多少个无重复数字的偶数的三位数？（1）分析：1、完成的这件事是什么？2 、如何完成这件事？（配百位数、配十位数、配个位数）3 、它们属于分类还是分步？（是否独立完成）4 、运用哪个计数原理？5 、进行计算略解：N=5X 5X 5=125 （个）解：属于分步：第一步配一个荤菜有3种选择第二步配一个素菜有5种选择第三步配一个汤有2种选择共有 N=3X 5 X 2=30 (种)【例题解析】例2有一个书架共有2层，上层放有5本不同的

4、数学书，下层放有 4本不同的语文书。（1）从书架上任取一本书，有多少种不同的取法？1、某人有4条不同颜色的领带和 6件不同款式的衬衣，问可以有多少种不同的搭配方法?学习必备熨迎下载取出m个元素的一个组合*7.组合数的概念：从n个不同元素中取出m m乞n个元素的所有组合的个数，叫做从n 个不同元素中取出m个元素的组合数.用符号cnm表示.2、有一个班级共有 46名学生，其中男生有 21名.(1) 现要选派一名学生代表班级参加学校的学代会，有多少种不同的选派方法？(2) 若要选派男、女各一名学生代表班级参加学校的学代会，有多少种不同的选派方法?8. 组合数公式：cj Amn-1)(n-2)(nm

5、1)或cm卫(n,m N ,且m")“Am!m!(n- m)!9. 组合数的性质1: cm = C；-m .规定：Cn =1 ；10. 组合数的性质 2: cn；二 Cnm+cn * Cn0+cn1+- +Cn=2na4种选法，然后其他 5人选，有 A种选法,3、有0、1、2、3、4、5六个数字.(1) 可以组成多少个不同的三位数？(2) 可以组成多少个无重复数字的三位数？(3) 可以组成多少个无重复数字的偶数的三位数？排列与组合1. 排列的概念：从n个不同元素中，任取m ( mn )个元素(这里的被取元素各不相同) 按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列

6、*2. 排列数的定义：从n个不同元素中，任取m ( mn)个元素的所有排列的个数叫做从n个元素中取出m元素的排列数，用符号A；表示3. 排列数公式：A?二 n(n -1)(n - 2川1(n- m 1) ( m, n N ,m n )4. 阶乘：n!表示正整数1到n的连乘积，叫做n的阶乘+规定0! =1.5. 排列数的另一个计算公式：Am= 匚 ”(n -m)!6. 组合概念：从n个不同元素中取出m mn个元素并成一组，叫做从n个不同元素中题型讲解例1分别求出符合下列要求的不同排法的种数(1) 6名学生排3排，前排1人，中排2人，后排3人；(2) 6名学生排成一排，甲不在排头也不在排尾；(3)

7、 从6名运动员中选出4人参加4 X 100米接力赛，甲不跑第一棒，乙不跑第四棒；(4) 6人排成一排，甲、乙必须相邻；(5) 6人排成一排，甲、乙不相邻；(6) 6人排成一排，限定甲要排在乙的左边，乙要排在丙的左边(甲、乙、丙可以不相邻)解：(1)分排坐法与直排坐法一一对应，故排法种数为A；二720(2) 甲不能排头尾，让受特殊限制的甲先选位置，有故排法种数为 A4A? = 480(3) 有两棒受限制，以第一棒的人选来分类： 乙跑第一棒，其余棒次则不受限制，排法数为 乙不跑第一棒，则跑第一棒的人有A：种选法，第四棒除了乙和第一棒选定的人外，也有A：种选法，其余两棒次不受限制，故有a：a4a；种

8、排法，由分类计数原理，共有 A； A：a4a2二252种排法（4） 将甲乙“捆绑”成“一个元”与其他4人一起作全排列共有 A；A? =240种排法（5） 甲乙不相邻，第一步除甲乙外的其余4人先排好；第二步，甲、乙选择已排好的4人的左、右及之间的空挡插位，共有 A4A （或用6人的排列数减去问题（2）后排列数为 A； -240=480）（6） 三人的顺序定，实质是从 6个位置中选出三个位置，然后排按规定的顺序放置这三人，其余3 人在3个位置上全排列，故有排法 cX -120种点评：排队问题是一类典型的排列问题，常见的附加条件是定位与限位、相邻与不相邻例3求证：Amj mA； = Am证明：利用排

9、列数公式左 Cnm1 - cm 2c；mm亠1n-2n-m n-1 ! m n-1 !(n_ m)!八m=An另一种证法：（利用排列的定义理解）从 n个元素中取m个元素排列可以分成两类:第一类不含某特殊元素a的排列有第二类含元素a的排列则先从 n-1个元素中取出 m-1个元素排列有 An1种，然后将a插入,共有m个空档，故有m 人匕种，因此人二1 + m，AnL = A：利用组合数公式2n !(n +2)!m 1 ! n - m 1 !m 1Cn2二石例2 假设在100件产品中有3件是次品，从中任意抽取 5件，求下列抽取方法各多少种？（1） 没有次品；（2）恰有两件是次品；（3）至少有两件是次

10、品解：（1）没有次品的抽法就是从 97件正品中抽取5件的抽法，共有C；7 =64446024种（2） 恰有2件是次品的抽法就是从 97件正品中抽取3件，并从3件次品中抽2件的抽法，共有 c；7c； = 442320 种（3）至少有2件次品的抽法，按次品件数来分有二类：第一类，从97件正品中抽取3件，并从3件次品中抽取2件，有C；7C；种第二类从97件正品中抽取2件，并将3件次品全部抽取，有 c97C；种按分类计数原理有 C；7CC&C： =446976种点评：此题是只选“元”而不排“序”的典型的组合问题，附加的条件是从不同种类的元素中抽取，应当注意：如果第（3）题采用先从3件次品抽取2

11、件（以保证至少有 2件是次品），再从余 下的98件产品中任意抽取 3件的抽法，那么所得结果是 C；C；8 = 466288种，其结论是错误的，错 在“重复”：假设3件次品是A B、C,第一步先抽 A B第二步再抽C和其余2件正品，与第一步先 抽A C （或 B、C），第二步再抽B （或 A）和其余2件正品是同一种抽法，但在算式C；C；8中算作3种不同抽法左=(m+1)!( n - m1)(m 1)( n m + 1)! m(n m)!nm n - m 1 mm1 2m1 n - m 1 1另法：利用公式叫 cncn1推得左二 c：1 c；： c： cm'二 cnvccn%1二右点评：证

12、明排列、组合恒等式通常利用排列数、组合数公式及组合数基本性质例4 已知f是集合Aa,b,c,d到集合B0,1,2?的映射（1）不同的映射f有多少个?（2）若要求fafbfcfd二4则不同的映射f有多少个?分析：（1）确定一个映射f，需要确定a, b, c, d的像（2）a, b, c, d的象元之和为4，则加数可能出现多种情况，即4有多种分析方案，各方案独立且并列需要分类计算解：（1） A中每个元都可选 0,1,2三者之一为像，由分步计数原理，共有3 3 334个不同映射(2) 根据a, b, c, d对应的像为2的个数来分类，可分为三类：第一类：没有元素的像为 2，其和又为4,必然其像均为1

13、,这样的映射只有一个；第二类：一个元素的像是 2，其余三个元素的像必为0,1,1，这样的映射有 C；P31 =12个;第三类：二个元素的像是2，另两个元素的像必为0,这样的映射有 C： =6个由分类计数原理共有 1+12+6=19 (个)点评：问题(1)可套用投信模型：n封不同的信投入 m个不同的信箱，有 mn种方法；问题(2)的关键结合映射概念恰当确定分类标准，做到不重、不漏故取4个点不共面的不同取法有 C：0 - 4C： 6 3 = 141 (种)点评：由点构成直线、平面、几何体等图形是一类典型的组合问题，附加的条件是点共线与不 共线，点共面与不共面，线共面与不共面等小结：m个不同的元素必

14、须相邻，有P；种“捆绑”方法+m个不同元素互不相邻，分别“插入”到n个“间隙”中的m个位置有种不同的“插入”方法+m个相同的元素互不相邻，分别“插入”到n个“间隙”中的m个位置，有C,；种不同的“插入”方法.若干个不同的元素“等分”为m个组，要将选取出每一个组的组合数的乘积除以P,.【例题解析】例5四面体的顶点和各棱的中点共10个点A在同一平面上，不同的取法有多(1) 设一个顶点为 A,从其他9点中取3个点，使它们和点 少种？(2) 在这10点中取4个不共面的点，不同的取法有多少种？解：(1)如图，含顶点 A的四面体的三个面上，除点 A外都有5个点，从中取出3点必与点A共面，共有3C；种取法含

15、顶点A的棱有三条，每条棱上有3个点，它们与所对棱的中点共面，共有3种取法根据分类计数原理和点 A共面三点取法共有 3C；，3=33种(2)取出的4点不共面比取出的 4点共面的情形要复杂，故采用间接法：先不加限制任取4点4(C10种取法)减去4点共面的取法取出的4点共面有三类：第一类：从四面体的同一个面上的6点取出4点共面，有4C；种取法第二类：每条棱上的 3个点与所对棱的中点共面，有 6种取法 第三类：从6条棱的中点取4个点共面，有3种取法根据分类计数原理4点共面取法共有4C： 6 69例1完成下列选择题与填空题(1) 有三个不同的信箱，今有四封不同的信欲投其中，则不同的投法有种。A.81B.

16、64C.24D.4(2) 四名学生争夺三项冠军，获得冠军的可能的种数是()A.81B.64C.24D.4(3) 有四位学生参加三项不同的竞赛， 每位学生必须参加一项竞赛，则有不同的参赛方法有 ; 每项竞赛只许有一位学生参加，则有不同的参赛方法有 ; 每位学生最多参加一项竞赛，每项竞赛只许有一位学生参加，则不同的参赛方法有。解析 (1)完成一件事是“分步”进行还是“分类”进行，是选用基本原理的关键。将“投四封信”这件事分四步完成，每投一封信作为一步，每步都有投入三个不同信箱的三种方法，因此：4N=3X 3 X 3 X 3=3=81,故答案选 A。本题也可以这样分类完成， 四封信投入一个信箱中，有

17、C31种投法；四封信投入两个信箱中，有C32 (C4 Ae2+C42 C22)种投法；四圭寸信投入三个信箱，有两圭寸信在同一信箱中，有C? . As3种投法、，故共有 G1+G2 (G1 A22+C42Cb2) +C42 A33=81 (种)。故选 A。(2) 因学生可同时夺得 n项冠军，故学生可重复排列，将4名学生看作4个“店”，3项冠军看作“客”，每个“客”都可住进 4家“店”中的任意一家，即每个“客”有4种住宿法。由分步计数原理得：N=4X 4X 4=64。故答案选B。(3) 学生可以选择项目，而竞赛项目对学生无条件限制，所以类似(1)可得N=34=81 (种)； 竞赛项目可以挑学生，而

18、学生无选择项目的机会，每一项可以挑4种不同学生，共有N=4=64 (种)； 等价于从4个学生中挑选3个学生去参加三个项目的竞赛，每人参加一项，故共有 C3 A3=24 (种)。注：本题有许多形式，一般地都可以看作下列命题：设集合 A=ai,a2,an,集合B=bi,b2,b m，贝U f: 2 B的不同映射是 m,f :A的不同映射是nmo若nw m,则f ： AtB的单值映射是：血。例2同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四 张贺年卡不同的分配方式有（A.6种B.9种解法一由于共四人（用1, 2, 3, 题之后，可用穷举法进行具体的填写：C.11 种4D

19、.23 种代表甲、乙、丙、丁四人），这个数目不大，化为填数问解法二 记四人为甲、乙、丙、丁，则甲送出的卡片可以且只可以由其他三人之一收到，故有3种分配方式；以乙收到为例，其他人收到卡片的情况可分为两类：第一类：甲收到乙送出的卡片，这时丙、丁只有互送卡片1种分配方式；第二类：甲收到的不是乙送出的卡片，这时，甲收到卡片的方式有 2种（分别是丙和丁送出的）对每一种情况，丙、丁收到卡片的方式只有一种。因此，根据乘法原理，不同的分配方式数为3X（ 1+2） =9o解法三 给四个人编号：1 , 2, 3, 4,每个号码代表1个人，人与号码之间的关系为一对一的关系；每个人送出的贺年卡赋给与其编号相同的数字作

20、为代表，这样，贺年卡的分配问题可抽象为如下“数学问题”：将数字1, 2, 3, 4,填入标号为1, 2, 3, 4的4个方格里，每格填写一个数字， 且每个方格的编号与所填数字都不同的填法共有多少种（也可以说成：用数字1, 2, 3, 4组成没有重复数字的4位数，而且每位数字都不等于位数的4位数共有多少个）？这时，可用乘法原理求解答案：首先，在第1号方格里填写数字，可填上 2、3、4中的任一个数，有 3种填法；其次，当第1号方格填写的数字为i （2 w i w 4）时，则填写第i种方格的数字，有 3种填法； 最后，将剩下的两个数填写到空着的两个空格里，只有1种填法（因为剩下的两个数中，至少有1个

21、与空着的格子的序号相同）。因此，根据乘法原理，得不同填法：3X 3X 1=9注：本题是“乱坐问题”，也称“错排问题”，当元素较大时，必须用容斥原理求解，但元素较小时，应用分步计数原理和分类计数原理便可以求解，或可以穷举。例3宿舍楼走廊上有有编号的照明灯一排8盏，为节约用电又不影响照明，要求同时熄掉其中3盏，但不能同时熄掉相邻的灯，问熄灯的方法有多少种？解法一 我们将8盏灯依次编号为1 , 2, 3, 4, 5, 6, 7, &在所熄的三盏灯中，若第一盏熄1号灯，第二盏熄3号灯，则第3盏可以熄5, 6, 7, 8号灯中的任意一盏，共有4种熄法。若第一盏熄1号灯，第2盏熄4号灯，则第3盏可

22、以熄6,乙8号灯中的任意一盏。依次类推，得若1号灯熄了，则共有 4+3+2+仁10种熄法。若1号灯不熄，第一盏熄的是 2号灯，第二盏熄的是 4号灯，则第三盏可以熄 6, 7, 8号灯中 的任意一盏，共有 3种熄法。依次类推得，若第一盏灯熄的是2号灯，则共有3+2+1=6种熄法。同理，若第一盏熄的是 3号灯，则共有2+1=3种熄法。同理，若第一盏熄的是 4号灯，则有1种熄法。综上所述共有：10+6+3+仁20种熄法。解法二 我们可以假定8盏灯还未安装，其中 5盏灯是亮着的，3盏灯不亮。这样原问题就等 价于：将5盏亮着的灯与3盏不亮的灯排成一排，使 3盏不亮的灯不相邻（灯是相同的）。5盏亮着 的灯

23、之间产生6个间隔（包括两边），从中插入3个作为熄灭的灯一一就是我们经常解决的“相邻不 相邻”问题，采用“插入法”，得其答案为C63=20种。注 解法一是穷举法，将所有可能的情况依次逐一排出。这种方法思路清晰，但有时较繁。方 法二从另外一个角度审题，认清其数学本质，抽象成数学模型，解题时有一种豁然开朗的感觉。例4 已知直线ax+by+c=0中的a,b,c 是取自集合-3,-2,-1,0,1,2,3 中的3个不同的元素， 并且该直线的倾斜角为锐角，求符合这些条件的直线的条数。解 设倾斜角为B,由B为锐角，得 tan 0 =- - >0,即a、b异号。b（1）若 c=0, a、b 各有 3 种

24、取法，排除 2 个重复（3x-3y=0,2x-2y=0,x-y=0）,故有 3X 3-2=7（条）。（2）若c丰0, a有3种取法，b有3种取法，而同时c还有4种取法，且其中任两条直线均不相同，故这样的直线有 3 X 3X 4=36条，从而符合要求的直线共有7+36=43条。注：本题是1999年全国高中数学联赛中的一填空题，据抽样分析正确率只有 0.37。错误原因没有对c=0与cm0正确分类；没有考虑 c=0中出现重复的直线。例5平面上给定10个点，任意三点不共线，由这10个点确定的直线中，无三条直线交于同一点（除原10点外），无两条直线互相平行。求：（1）这些直线所交成的点的个数（除原 10

25、点外）。（2）这些直线交成多少个三角形。解法一 （1 ）由题设这10点所确定的直线是 C10 =45条。这45条直线除原10点外无三条直线交于同一点，由任意两条直线交一个点，共有C452个交点。而在原来10点上有9条直线共点于此。所以，在原来点上有10C92点被重复计数。所以这些直线交成新的点是：C452-10C92=630。（2）这些直线所交成的三角形个数可如下求：因为每个三角形对应着三个顶点，这三个点来自 上述630个点或原来的10个点。所以三角形的个数相当于从这640个点中任取三个点的组合，即C640 =43 486080 （个）。解法二 （1）如图对给定的10点中任取4个点，四点连成6

26、条直线，这6条直线交3个新的点。故原题对应于在10个点中任取 4点的不同取法的3Cio =630。3倍，即这些直线新交成的点的个数是:例7(1 )求4 X 6n+5n+1被20除后的余数;(2) 7n+C?7n-1+G2 严+Gn-1X 7除以9,得余数是多少？(3) 根据下列要求的精确度，求1.02 5的近似值。精确到 解 (1 )首先考虑4 6n+5n+1被4整除的余数。n+1n+1 n+1_1 n _2 n-1_ n5 =(4+1) =4 +G+1 4 +G+1 4 + +G+1 4+1其被4整除的余数为10.01 :精确到 0.001。被20整除的余数可以为1 , 5, 9, 13 ,

27、 17然后考虑4 6n+1+5n+1被5整除的余数。/ 4 6n=4 (5+1) n=4(5 n+Cn1 5n-1+G2 5n-2 +Gn-1 5+1) 被5整除的余数为4(2)同解法一。注 用排列、组合解决有关几何计算问题，除了应用排列、组合的各种方法与对策之外，还要 考虑实际几何意义。其被20整除的余数可以为 4, 9, 14, 19。综上所述，被20整除后的余数为9。2)7 n+Cn1 7n-1+G2 7n-2+Gn-1 7项;(1)如果(X+1) 2n展开式中，第四项与第六项的系数相等。求n,并求展开式中的常数x 1 8求(.、x-1)展开式中的所有的有理项。2如=(7+1) n-1=

28、8 n-1=(9-1) n-1n _ 1n-1 _ 2n-2n-1 _ n-1n _ n=9 -Cn 9 +G 9 + +(-1) G 9+(-1) C-1 (i)当n为奇数时原式=9n-Cn1 9n-1+G2 9n-2+ (-1 ) n-1Gn-1 9-2除以9所得余数为7。35(1)由 C2n =C2n,可得 3+5=2n解/ n=4。设第k+1项为常数项k则 T k+i=C8 x 8-2k=0 ,常数项为(2)设第(ii)当n为偶数时原式=9n-Cn1 9n-1+G2 9n-2+(-1) n-1Gn-1 98-k-k k&2k x =C8 x即k=44T5=G =70。k+1项有

29、理项，则除以9所得余数为5(3) (1.02)疋=1+c0,即被9整除。5(1+0.02 )51 0.02+C52 0.02 2+G3 0.02 3+C540.02 4+G5 0.02 5/ C2X 0.02 2=0.004,C 53x 0.02 3=8X 10-5当精确到0.01时，只要展开式的前三项和，1+0.10+0.004=1.104，近似值为1.10。当精确到 0.001时，只要取展开式的前四项和，1+0.10+0.004+0.0008=1.10408 ，近似值为8 -kX亍(弓kxi14 x k(-尹 4)1641.104。注 (1 )用二项式定理来处理余数问题或整除问题时，通常把

30、底数适当地拆成两项之和或之差 再按二项式定理展开推得所求结论。(2)用二项式定理来求近似值，可以根据不同精确度来确定应该取到展开式的第几项。16 3k Z,只有使k分别取0, 4, 84所以所求的有理项应为：4351-2T1=x ,T 5= x,T 9=x8256注 (1) 二项式展开中，要注意“系数”与“二项式系数”的区别;(2)在二项展开式中求得 k后，对应的项应该是 k+1项。例8 证明下列不等式:因为0< k w 8,要使(1)a + b)n, (a、b x|x 是正实数,n N)21 1(2)已知 a、b 为正数，且一+ =1,则对于 n N有(a+b) n-an-bn>

31、22n-2n+1。a b证明 (1 )令 a=x+ S, b=x- S则x=n n ,、n ,、na +b =(x+ S ) +(x- S )n 1n-1n 从 n n 1n-1n n=x +Cn x S + +Cn S +x -Cn x S + (-1) G S由得，2Gp=Gp+Gpn + 1- p p + 1两边约去Gp,可得：n 2 n-2 、 24 n-4 、 4、=2(x +Cn x S +G x S + )n> 2x由得,2G+1pCn+1n n 1 n-1n. n(2) (a+b) =a +Cn a b+ +G b1. n-1(a+b) =b+Gb a+C a上述两式相加

32、得：n n n _ 1n-1n-1_ k n-k k n-k k_ n n n2(a+b) =(a+b)+Cn(a b+b a)+G (a b +b a)+Cn (a +b) (*)1 1_ +_=1，且a、b为正数a b/ ab=a+b> 2 ab / ab>4约去G+/可得，n=3p+1n = 3p 1又an-kbk+bn-kak> 2 .an bn=2( . ab )"(k=1,2,n-1)得：n=7,p=2.将p=2 ,n=7代入得：C57(-a) 5+C76 - (-a) 6=0解之得：a=0或3。若a=0，则(1-0 x) 8的中间项T5=0, (1-0

33、 x) 7展开式中系数最大的项是T1=1。若a=3,则(1-3x ) 8的中间项T5=C84 (-3x ) 4=5670x4, ( 1-3x ) 7的展开式中，奇数项系数为正,k个元素的不同组合有Cn+1。 2(a+b) n >2an+2bn+cn12( ab) n+Cn22 ( . ab ) n+- +Gn-12( . ab )n (a+b) n-a n-bn> (c'+G2+Gn-1) ( i ab ) nnn> (2 -2) 2=22n-2 n+1注 利用二项式定理的展开式，可以证明一些与自然数有关的不等式问题。题(1)中的换元法称之为均值换元(对称换元)。这样消去S奇数次项，从而使每一项均大于或等于零。题(2)中，由由称