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

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

2、什么？2 、如何完成这件事？（配一个荤菜、配一个素菜、配一汤）3 、它们属于分类还是分步？（是否独立完成）4 、运用哪个计数原理？5 、进行计算.解：属于分步：第一步 配一个荤菜 有3种选择第二步配一个素菜 有5种选择第三步 配一个汤 有2种选择共有 N=3X 5X 2=30 （种）2 、如何完成这件事？3 、它们属于分类还是分步？（是否独立完成）4 、运用哪个计数原理？5 、进行计算。解：属于分类：第一类从上层取一本书有5种选择第二类 从下层取一本书 有4种选择共有N=5+4=9 （种）（2）分析：1、完成的这件事是什么？6 、如何完成这件事？7 、它们属于分类还是分步？（是否独立完成）8

3、、运用哪个计数原理？9 、进行计算.解：属于分步：第一步从上层取一本书有5种选择第二步从下层取一本书 有4种选择共有 N=5X4=20 （种）例3、有1、2、3、4、5五个数字.（1）可以组成多少个不同的三位数？（2）可以组成多少个无重复数字的三位数？（3）可以组成多少个无重复数字的偶数的三位数？（1）分析：1、完成的这件事是什么？2 、如何完成这件事？（配百位数、配十位数、配个位数）3 、它们属于分类还是分步？（是否独立完成）4 、运用哪个计数原理？5 、进行计算.略解：N=5 X 5 X 5 = 125 （个）【例题解析】1、某人有4条不同颜色的领带和6件不同款式的衬衣，问可以有多少种不同

4、的搭配方法?例2 有一个书架共有2层，上层放有5本不同的数学书，下层放有 4本不同的语文书。（1）从书架上任取一本书，有多少种不同的取法？（2）从书架上任取一本数学书和一本语文书，有多少种不同的取法?（1）分析：1、完成的这件事是什么？2、有一个班级共有46名学生，其中男生有21名.(1)现要选派一名学生代表班级参加学校的学代会，有多少种不同的选派方法？(2)若要选派男、女各一名学生代表班级参加学校的学代会，有多少种不同的选派方法?3、有0、1、2、3、4、5六个数字.(1)可以组成多少个不同的三位数？(2)可以组成多少个无重复数字的三位数？(3)可以组成多少个无重复数字的偶数的三位数?排列与

5、组合1 ,排列的概念：从n个不同元素中，任取m ( m n )个元素(这里的被取元素各不相 同)按照一定的顺序排成一列，叫做从n个不同元素中取出 m个元素的一个排列 2 .排列数的定义：从n个不同元素中，任取m ( mn )个元素的所有排列的个数叫做从 n个元素中取出m元素的排列数，用符号表示3 .排列数公式：Anm n(n l)(n 2)L(n m 1) ( m, n N,m n )4 .阶乘：n!表示正整数1到n的连乘积，叫做n的阶乘规定0! 1.5 .排列数的另一个计算公式：A/j (n m)!6 .组合概念：从n个不同元素中取出m m n个元素并成一组，叫做从n个不同元素中 取出m个元

6、素的一个组合7 .组合数的概念：从n个不同元素中取出m m n个元素的所有组合的个数，叫做从n 个不同元素中取出m个元素的组合数.用符号cm表示.Anm n(n l)(n 2)L (n m 1) mn!n8组合数公式:Cnf 或c n (n, m N ,且 m n)Amm!m!( n m)!9 .组合数的性质1： Cnm C/m.规定：Cn°10 .组合数的性质 2: C nm 1 = c nm +c nm 1 C ”+C+ +Cn n=2题型讲解例1 分别求出符合下列要求的不同排法的种数（1）6名学生排3排，前排1人，中排2人，后排3人；（2） 6名学生排成一排，甲不在排头也不在排

7、尾；（3）从6名运动员中选出4人参加4 X 10。米接力赛，甲不跑第一棒，乙不跑第四棒；（4） 6人排成一排，甲、乙必须相邻；（5） 6人排成一排，甲、乙不相邻；（6） 6人排成一排，限定甲要排在乙的左边，乙要排在丙的左边（甲、乙、丙可以不相邻）解：（1）分排坐法与直排坐法一一对应，故排法种数为A66 720（2）甲不能排头尾，让受特殊限制的甲先选位置，有 “种选法，然后其他5人选，有A5§种选法，故排法种数为A41 A55480（3）有两棒受限制，以第一棒的人选来分类：乙跑第一棒，其余棒次则不受限制，排法数为As?；乙不跑第一棒，则跑第一棒的人有A9种选法，第四棒除了乙和第一棒选定

8、的人外，也有 a*4种选法，其余两棒次不受限制，故有 A41 A41 A22种排法，由分类计数原理，共有 A3 A1 A1 A2 252种排法 54 44（4）将甲乙“捆绑”成“一个元”与其他4人一起作全排列共有 A22 As5 240种排法（5）甲乙不相邻，第一步除甲乙外的其余4人先排好；第二步，甲、乙选择已排好的4人的左、右及之间的空挡插位，共有 A44 A§2 （或用6人的排列数减去问题（2）后排列数为A66240 480 ）（6）三人的顺序定，实质是从 6个位置中选出三个位置，然后排按规定的顺序放置这三人，其余人在3个位置上全排列，故有排法C63 A33 120种点评：排队问

9、题是一类典型的排列问题，常见的附加条件是定位与限位、相邻与不相邻例2假设在10。件产品中有 3件是次品，从中任意抽取 5件，求下列抽取方法各多少种？ （1）没有次品；（2）恰有两件是次品；（3）至少有两件是次品解：（1）没有次品的抽法就是从97件正品中抽取5件的抽法，共有 C 975 64446024种（2）恰有2件是次品的抽法就是从97件正品中抽取3件，并从3件次品中抽2件的抽法，共有 C973c32 442320 种（3）至少有2件次品的抽法，按次品件数来分有二类：第一类，从97件正品中抽取3件，并从3件次品中抽取2件，有C973 c32种第二类从97件正品中抽取2件，并将3件次品全部抽取

10、，有C972c3?种按分类计数原理有C973 C32 C972C 33 4 4 6 9 7 6种点评：此题是只选“元”而不排“序”的典型的组合问题，附加的条件是从不同种类的元素中抽取，应当注意：如果第（3）题采用先从3件次品抽取2件（以保证至少有 2件是次品），再从余 下的98件产品中任意抽取3件的抽法，那么所得结果是C32C 983 4 6 6 2 8 8种，其结论是错误的，错在“重复”：假设3件次品是A、B、C,第一步先抽 A、B第二步再抽C和其余2件正品，与第一步先 抽A、C （或B、C）,第二步再抽B （或A）和其余2件正品是同一种抽法，但在算式C32 c983中算作3种不同抽法 mm

11、 1 mm 1 m 1m m 1c例 3 求证： An 1 mAn 1 An ; C n C n 2Cn n - 证明：利用排列数公式左 n 1 !-m n 1 !n m n 1 ! m n 1 ! -rH Anm 右n m 1 ! n m !n m !n m !另一种证法：（利用排列的定义理解）从 n个元素中取m个元素排列可以分成两类:An，1种，然后将a插入,第一类不含某特殊元素 a的排列有和川1第二类含元素a的排列则先从n 1个元素中取出 m 1个元素排列有共有m个空档，故有m A-J种，因此Anmi m Anm i1 Anm利用组合数公式2n !inn 2另法:点评:mmc利用公式Cn

12、 Cn】ni推得左 Cn CnCnCn证明排列、组合恒等式通常利用排列数、组合数公式及组合数基本性质已知f是集合A a, b, c, d到集合B 0,1,2的映射1)不同的映射f有多少个?(2)若要求fa fb f c f d 4则不同的映射f有多少个?分析：(1)确定一个映射 3需要确定a,b, c,d的像(2) a, b, c, d的象元之和为4,则加数可能出现多种情况，即 4有多种分析方案，各方案独立且 并列需要分类计算解：(1) A中每个元都可选。,1,2三者之一为像，由分步计数原理，共有 3 3 3 334个不同映射(2)根据a, b, c, d对应的像为2的个数来分类，可分为三类：

13、第一类：没有元素的像为2,其和又为4,必然其像均为1,这样的映射只有一个；a 4 P 一012 个:第二类：一个元素的像是2,其余三个元素的像必为0,1,1，这样的映射有第三类：二个元素的像是2,另两个元素的像必为 0,这样的映射有C 42 6个由分类计数原理共有1 + 12+6=19 （个）点评：问题（1）可套用投信模型：n封不同的信投入m个不同的信箱，有 mn种方法；问题（2）的关键结合映射概念恰当确定分类标准，做到不重、不漏例5四面体的顶点和各棱的中点共10个点（1）设一个顶点为A,从其他9点中取3个点，使它们和点A在同一平面上，不同的取法有多 少种？（2）在这10点中取4个不共面的点，

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

15、理4点共面取法共有4C 646369故取4个点不共面的不同取法有Cio4 4C646 3141 （种）点评：由点构成直线、平面、几何体等图形是一类典型的组合问题，附加的条件是点共线与不共线，点共面与不共面，线共面与不共面等小结：m个不同的元素必须相邻，有Pmm种“捆绑”方法m个不同元素互不相邻，分别“插入”到n个“间隙”中的m个位置有种不同的“插入”方法m个相同的元素互不相邻，分别“插入”到n个“间隙”中的m个位置，有种不同的“插入”方 法若干个不同的元素“等分”为 m个组，要将选取出每一个组的组合数的乘积除以P/【例题解析】例1完成下列选择题与填空题（1）有三个不同的信箱，今有四封不同的信欲

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

17、投法；四封信投入两个信箱中，“C3 212. 2 .,2）种投法；四封信投入三个信箱，有两封信在同一信箱中，有2 3种投3424243、12 I 22223址.MIIK C<C人4c -） 4c二 A-81.故道 A-33424243直（2）因学生可同时夺得 n项冠军，故学生可重复排列，将 4名学生看作4个“店”，3项冠军看作“客”，每个“客”都可住进 4家“店”中的任意一家，即每个“客”有4种住宿法。由分步计数原理得：N=4X 4X 4=640 故答案选Bo（3）学生可以选择项目，而竞赛项目对学生无条件限制，所以类似（1）可得N=3，=81 （种）；竞赛项目可以挑学生，而学生无选择项目

18、的机会，每一项可以挑4种不同学生，共有 N=43=64 （种）； 等价于从4个学生中挑选 3个学生去参加三个项目的竞赛，每人参加一项， 故共有C3 3 43注：本题有许多形式，一般地都可以看作下列命题：n设集合A=a i,a 2,a 集合B=b i,b 2, ,b m,则f ： Af B的不同映射是m,f ： B- A 的不同映 射是nmo若n< m,则f： A- B的单值映射是：A：。例2 同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四 张贺年卡不同的分配方式有（）种种种种解法一由于共四人（用 1, 2, 3, 4代表甲、乙、丙、丁四人），这个数目不大，化

19、为填数问题之后，可用穷举法进行具体的填写:24 1 32 14 33 14 2再按照题后要求检验最终易知书34 129种分M方法。解法二记甲能冲、乙、丙、丁，邓啊琴出的卡片可以耳¥至扣由其他三人之一收到，故有1种分配方式;3种分配方式;以乙收到为例,其他人收到卡片的情况可分为两充 第一类：甲收到乙送出的卡片，这时丙、丁只有互送卡片第二类：甲收到的不是乙送出的卡片，这时，甲收到卡片的方式有 2种（分别是丙和丁送出的）。对每一种情况，丙、丁收到卡片的方式只有一种。因此，根据乘法原理，不同的分配方式数为3 X （ 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<i（4）时，则填写第i 种方格的数字，有3种填法；最后，将剩

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

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

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

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

25、两条直线互相平行。求：（1 ）这些直线所交成的点的个数（除原10点外）。（2）这些直线交成多少个三角形。解法一 （1）由题设这10点所确定的直线是C.o =45条。,这45条直线除原10点外无三条直线交于同一点，由任意两条直线交一个点，共有 Cn 2个交点。而在原来10点上有9条直线共点于此。所以，在原来点上有IOC?9所以这些直线交成新的点是：C45 2-10C92=630o（2）这些直线所交成的三角形个数可如下求：因为每个三角形对应着三个顶点，这三个点来自 上述630个点或原来的10个点。所以三角形的个数相当于从这64。个点中任取三个点的组合，即C64o3=43 486080 （个）。解法

26、二 （1）如图对给定的10点中任取 4个点，四点连成6条直线，这6条直线交3个新的 点。故原题对应于在10个点中任取 4点的不同取法的3倍，即这些直线新交成的点的个数是：3 c .10（2）同解法一。注 用排列、组合解决有关几何计算问题，除了应用排列、组合的各种方法与对策之外，还要 考虑实际几何意义。例6 （1）如果（x+1）2n展开式中，第四项与第六项的系数相等。求 n,并求展开式中的常数X项；（2）求（X1） 8展开式中的所有的有理项。24x解 （1）由 C2n3=C2n5,可得 3+5=2ll n=4 o设第k+l项为常数项 k 8-k -k k 8-2k则 T k+i=Cs x x =

27、Cs x 8-2k=0 ,即k=4 常数项为T5=Cs4=70o（2）设第k+l项有理项，则8 kITk 1 C8k 转（ -X4）k 2 16 3kC8k （ _1 ）k 丁丁216 3k因为0<k<8,要使 e Z,只有使k分别取0, 4, 84 所以所求的有理项应为： ,351 ,Ti=x4,T 5= x,T 9=x 8256注 （1）二项式展开中，要注意“系数”与“二项式系数”的区别;（2）在二项展开式中求得 k后，对应的项应该是k+l项。例7( 1 )求4X 6n+5n+,被20除后的余数；nl n-12n-2n-I(2) 7 +Cn 7 +Cn 7 + +Cn X 7除

28、以9,得余数是多少？(3)根据下列要求的精确度，求的近似值。精确到；精确至上解 (I )首先考虑4 6n+5向被4整除的余数。 n+1n+1n+11 n 2 n-1n5 =(4+1)=4 +Cn+14 +Cn+1 4 + +Cn+1 4+1其被4整除的余数为1被20整除的余数可以为1, 5, 9, 13, 17然后考虑4 6n+1+5n+1被5整除的余数。n，、 1 5n4+C2 "-2 + +C n- 5 + 1)nnn 被5整除的余数为4 其被20整除的余数可以为4, 9, 14, 19o综上所述，被20整除后的余数为9o(n 1n-12n-2n-1 7nnn=(7+1)n-l=

29、8 n-l=(9-l) n-lnln-12n-2n-I n-1n n=9 -Cn 9 +Cn 9+ +(-l) Cn * 9+(-1) Cn-1(i)当n为奇数时原式=9n-Cn1 911-1 +Cn2 9n 2 + ( -1 ) nJ c 9-2 除以9所得余数为7o(ii)当n为偶数时 nln-12n-2n-I n-19-9 4 (.1) C9nnn除以9所得余数为 0,即被9整除。（3）5a： （ 1 + ）5= 1+01 二 335555523-5C5 X = c 5 X =8X 10当精确到时，只要展开式的前三项和，1+=,近似值为。当精确到时，只要取展开式的前四项和，1+=,近似值

30、为。注（1）用二项式定理来处理余数问题或整除问题时，通常把底数适当地拆成两项之和或之差 再按二项式定理展开推得所求结论。（2）用二项式定理来求近似值，可以根据不同精确度来确定应该取到展开式的第几项。例8证明下列不等式：n n h n卜（1）_ （ _：）n （a. be xl x 是正实数）,n e N）;22（2）已知a、b为正数，且+_ =1，则对于n£N有（a+b） %11222n.2用。a b证明 （1）令 a=x+ 6 , b=x- 62an+bn=(x+ 6 ) n+(x- 6 )n n I n-1n n n 1 n-1n nn=X +Cn X 6 + 4-Cn 6 +X

31、 -Cn X 6 + (-1) Cn 6=2(x n+Cn2xn-2 5 2+Cn4xn-4 6 4+ )2xn即e (二)n22(2 ) (a+b) nnJ a n-1, _ n nnn(a+b)n=bn+Cn1bn-1 a+ +Cnnan上述两式相加得：2(a+b) nn n 1 n-ln-1k(a n-k kn-k knn +=1,且a、b为正数a bab=a+b2 2vab -.ab4又 an-k bk+bn-k ak 2Va n b n =2( ab )n(k=l,2, ,n-l) 2(a+b) n 2 2a 呷 (i jab ) n 2 r n+ +c n-i 2g ab ) 1&

32、#187;A (a+b)n-a n-b n2 (C 1=+ +c n-i) (/ab ) nn nn,2 （2 n-2） 2n22n-2n+,注 利用二项式定理的展开式，可以证明一些与自然数有关的不等式问题。题（1）中的换元法称之为均值换元（对称换元）。这样消去6奇数次项，从而使每一项均大于或等于零。题（2）中，由由称位置二项式系数相等，将展开式倒过来写再与原来的展开式相加，这样充分利用对称性来解 题的方法是利用二项式展开式解题的常用方法。例9已知（lax） 11展开式的第p,p+l,p+2三项的二项式系数构成等差数列，第n+1-p与第n+2-p项的系数之和为0,而（lax ）向展开式的第p+i与p+2项的二项式系数之比为 1 ：2。（1 ）求（1-ax ） n+,展开式的中间项；（2）求（1-ax ） 11的展开式中系数最大的项。解由题设得：2CnP C nP 1 CnP 1Cn11 P（ a）11 P Cm 】p（ a）n 1 p 0 p p 12Cn 1 C n in p由得，2CV=p_ CR+ Cn Pn 1 p p