101分类计数原理与分步计数原理

1、10.1 分类计数原理与分步计数原理分类计数原理：完成一件事，有n类办法，在第1类办法中有m,种不同的方法，在第 2类办法中有m2种不同的方法，在第 n类办法中有mn种不同的方法，那么完成这件事共有N m1 m2 Lmn 种不同的方法 .分步计数原理：完成一件事，需要分成 n个步骤，做第1步有mi种不同的方法，做第 2步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有N m, m2 L mn种不同的方法.例 1.书架的第一层放有 4 本不同的计算机书，第二层放有 3本不同的文艺书，第 3 层放有 2 本不同的体育书 .( 1 )从书架上任取 1 本书，有多少种不同的取法？(

2、2)从书架的第 1、2、 3 层各取 1 本书，有多少种不同的取法？例2.一种号码锁有 4个拨号盘，每个拨号盘上有从 0到9共10个数字，这 4个拨号盘可以组 成多少个四位数字号码？例 3 .要从甲、乙、丙 3 名工人中选出 2 名分别上日班和晚班，有多少种不同的选法？总结分类计数原理与分步计数原理，回答的都是有关做一件事的不同方法种数的问题.区别在于：分类计数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方 法都可以做完这件事；分步计数原理针对的是“分步”问题，各个步骤中的方法相互依存， 只有各个步骤都完成才算做完这件事 .精选练习：1. 从数集 M 1,2,3 到数集 N

3、1,2,3,4 的不同的映射个数是多少？2. 4 名运动员争夺三项冠军(无并列) ，不同的结果有多少种？34 名运动员参加三项比赛，每人限报一项，不同的报名方式有多少种？4.1200 的自然数中，有多少个各位数上都不含数字 5的个数？5.(aibi)(a2 b2)L (anbn)的展开式中所有不同项的项数是多少个?10.2排列引入一一问题1:从甲、乙、丙3名同学中选出2名参加某天的一项活动，其中1名同学参加上午的活动，1名同学参加下午的活动，有多少种不同的方法？( 元素)问题2：从a,b,c,d这4个字母中，每次取出3个按顺序排成一列，共有多少种不同排法？一般地，从n个不同元素中取出 m(m

4、n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出 m个元素的一个 排列(两个排列相同，当且仅当两个排列的元素完全相同， 且元素的排列顺序也相同)从n个不同元素中取出 m(m n)个元素的所有排列的个数， 叫做从n个不同元素中取出 m个元素的排列数，用符号Am表示对问题1，是求从3个不同元素中取出2个不同的元素的排列数，它记为A；，A 3 2对问题2，是求从4个不同元素中取出 3个不同的元素的排列数，它记为A：，A 4 3 2问：从n个不同元素中取出2个元素的排列数 A是多少？ A呢？ Am(m n)呢？(按依次 填空位的方法来考虑)Ann(n 1)(n 2)L (n m 1)| (

5、n,m N , m n)此公式称为 排列数公式.(计算 Af,A；5, A8 2A2，A(6,An1)n个不同元素全部取出的一个排列，叫做n个不同元素的一个 全排列这时排列数就记做AH,其中|a：n (n 1) (n 2) L 3 2 1 .表示所以AHn !n (n 1) L 3 2 1 n!(n m) L 2 1 (n m)!正整数1到n的连乘积，叫做n的阶乘，用n!一般地，Am n(n 1)(n 2)L (n m 1)n !即有排列数公式Am! (n m)!时继续适用，我们规定 0!1当n m时aIn !，为使上面公式在 n m例1.简单排列问题某年全国足球甲级 (A组)联赛共有14对参

6、加，每队都要与其余各队在主、客场分别比赛1次，共进行多少场比赛?例2.（1）有5本不同的书，从中选 3本送给3名同学，每人各1本，共有多少种不同的送法？（2）有5种不同的书，要送 3本给3名同学，每人各1本，共有多少种不同的送法？例3某信号兵用红、黄、蓝 3面旗从上到下挂在竖直的旗杆上表示信号，每次可以任挂1面、2面或3面，并且不同的顺序表示不同的信号，一共可以表示多少种不同的信号？例4用0到9这10个数字，可以组成多少个没有重复数字的三位数？精选练习：1.某元素必（不）居某位7人排成一排，根据下列条件，分别求各有多少种不同的排法?（1）甲只能排中间（2）甲、乙两人必须排两头（3）甲不在两头2

7、.某些元素（不）相邻四男三女排成一排，接下列要求各有多少种不同排法?（1）男女生各排在一起（2）女生一定不相邻（插空法）（3）甲、乙两人相邻，其它条件不限3. 数字排列问题用0到6七个数字组成没有重复数字的五位数，按下述要求，分别求出其个数：（1）大于25000; （2）能被5整除；（3）偶数4 两类元素互不相邻三男三女相间排列，求排列种数?5.某些元素次序一定 a,b,c,d,e规定a,b,c次序一定，求有多少种不同排法?6.卡片问题现有 0 3,6,17六张卡片，由这六张卡片可以组成多少个不同的3位数?（允许卡片6可当9用）（首位数非零）10.3组合引入一一问题1:从甲、乙、丙3名同学中选

8、出2名去参加一项活动，有多少种不同的方法?一般地，从n个不同元素中取出 m(m n)个元素并成一组，叫做从n个不同元素中取出 m个元素的一个 组合.(组合与元素的顺序无关)从n个不同元素中取出 m(m n)个元素的所有组合的个数， 叫做从n个不同元素中取出 m个元素的组合数，用符号cm表示.对于“从4个不同元素中取出3个元素的排列数 A： ”，可以这样理解：先考虑从4个不同 元素中取出3个元素的组合，共有C：个；再对每一个组合中的 3个不同元素作全排列，各有 A个根据分步记数原理，得 A C： A，因此，c3cmn!m!(n m)!n(n 1)(n2)L(n 口得组合数公式：m(m 1)L 2

9、 1(其中 n, m N , m n )(计算：C；，do ；证明：C：1 C： 1;写出从 a, b, c, d, e 5n m个元素中任取2个元素的所有组合) 组合数性质一：c： c；m，规定c0 1 ；性质二：c：1 c： cn°1例1.平面内有10个点，以其中每 2个点为端点的线段共有多少条？有向线段呢?例2个口袋内装有大小相同的7个白球和一个黑球，从口袋内取出3个球，共有多少种取法？若须含一个黑球呢？若不含有黑球呢？某元例3在100件产品中，有98件合格品，2件次品，从中任意抽取 3件，问：共有多少种不同的抽法？若恰有一件次品呢？若要求至少有一件次品呢？至少有某些元素练1已

10、知C2o3c2on 7求n；已知G? C：56求x ；已知c：,c；,cn成等差数列，求C；.练2解不等式cmcm.练 3.;计算 C；8 nC； n练4计算c： c； C53 C3 C73 C；况 C；1 L C；n（答案用组合数表示）练5.分堆问题六本不同的书, 按下列条件，各有多少种不同的分法？ （1）分给甲、乙、丙三人, 每人两本（2）分成三堆，每堆两本（3）分成三堆，一堆一本，一堆两本，一堆三本（4）分给甲、乙、丙三人，一人一本，一人两本，一人三本（5）分给甲、乙、丙三人，每人至少得一本 .练6.七个不同颜色的小球（1）放入两颜色不同的布袋（2）放入两颜色相同的布袋， 各有多少种不

11、同的放法？练7.平面上有8个点，其中有4个点在一个圆上，其余任意四点不共圆，那么这8个点最多可确定的圆的个数是 （用数字作答）练8.5男4女共9人，他（她）们的身高各不相同，现排成一排，要求男、女生各从高到矮排列（左高右低或左低右高均可）.则共有种不同的排法？练9.某幢楼从二楼到三楼的楼梯台阶共有10级，上楼可以一步上一级，也可以一步上两级，若规定从二楼到三楼用 8步走完，则上楼梯的方法有 种.练10.9人组成篮球对，其中 7人善打锋，3人善打卫，现选出5人（三锋两卫，且锋分左、中、 右，卫分左、右）组对出场，有多少种不同的组队方法？10.4二项式定理二项式定理：(a b)nC°an

12、 C：an怙 LC：an rbr LC：bn(猜想加数学归纳法证明)其中右边的多项式叫做(a b)n的二项展开式；Cnan rbr叫做二项展开式的 通项，为第r 1项，记作Tr i，即|icnanrbr ； C：叫第r1项的二项式系数；展开式共有n 1项；前面的字母a次数由高到低逐渐降低，b次数由低到高逐渐升高.特别地，令 a 1, b x，则有：|(1 x)nC： C：x L Qxr LC：xn1例1. 展开(1)4.x例2.展开(2、,x 1 )6.Jx12例3. 求(x a)的展开式中的倒数第四项.例4.(1)求(1 2x)7的展开式的第4项的系数；(2)求(x -)9的展开式中x3的系

13、数.x补充习题：求特殊项等10235234(1)求(2 a 3b c)展开式中含a b c的系数.2)求(1 x 2x )展开式中含x的系数.(3)求(3 aL)15展开式中的常数项.(4)若(疗-)n展开式中第三项含有a2，求n.aa(5)求 (Vx 仍0 展开式中的有理项 二项式系数的性质：(1) 对称性：与首末两端“等距离”的两个二项式系数相等；(2) 增减性与最大值：二项式系数是先增后减，在中间位置取到最大值.当n是偶数时，中nn 1 n 1间的一项C?取到最大值；当n是奇数时，中间的两项cF'Cy相等且同时取最大值(3) 各二项式系数的和：2n (11)n C0 cn L c

14、n L C(4) 在(a b)n的展开式中，奇数项的二项式系数的和等于偶数项的二项式系数的和.补充习题：1求和：C02cnL2rcnL2nc； ；C：2C：22C：2C；L (1)n2nC小结：组合数系数成等比，则必为某一个二项式的展开式问：组合数系数成等差呢？2.求和：C° 2cn 3CnL (n 1)C103求(1 2x)的展开式中的二项式系数之和，奇数项(偶数项)二项式系数之和，系数之和 .21023104求(x2x 3)展开后的系数和；求(1 x) (1 x) L (1 x)的展开系数和55求(2a3b)展开式的系数和，奇数项系数之和，偶数项系数之和48126设(x1) (x

15、 4)ao(x3)11a1(x 3) Lan(x 3) a12，求 a0a2a4 La12复习课课堂练习：1.已知(1 x)n展开式中，第5, 6，7三项系数成等差数列，求展开式中系数最大项2.(24 3)100的展开式有 个有理项.3求(12x)10的展开式中的系数最大项4.计算1.009 5 (精确到0.001)5.证明32n 2 8n 9能被64整除.解排列问题的常用技巧一一解排列问题，首先必须认真审题，明确问题是否是排列问题，其次是抓住问题的本质特征， 灵活运用基本原理和公式进行解答，同时，还要注意讲究基本策略和方法技巧，使一些看似 复杂的问题迎刃而解（一）特殊元素的“优先安排法”对于

16、特殊元素的排列组合问题，一般应先考虑特殊元素，再考虑其他元素例1用0,1,2,3,4这五个数字，组成没有重复数字的二位数，其中偶数共有 个（二）总体淘汰法对于含有否定词语的问题，还可以从总体中把不符合要求的除去，此时应注意既不能多减也 不能少减例2七人排成一列，规定甲不能站排头，问有多少种排法？（三）合理分类与准确分步解含有约束条件的排列组合问题，应按元素的性质进行分类，事情的发生的连续过程分步， 做到分类标准明确，分步层次清楚，不重不漏例3五人从左到右站成一排，其中甲不站排头，乙不站第二个位置，则不同的站法有 种.（四）相邻问题：捆绑法对于某几个元素要求相邻的排列问题，可先将相邻的元素“捆绑

17、”起来，看作一个“大”的 元素与其他元素排列，然后再对相邻元素内部进行排列例4.7人站成一排照相，要求甲、乙、丙三人相邻，分别有多少种不同的排法？（五）不相邻问题：插空法对于某几个元素不相邻的排列问题，可先将其他元素排好，然后再将不相邻的元素在已排好 的元素之间及两端的空隙之间插入即可例5.7人站成一排照相，要求甲、乙、丙三人不相邻，分别有多少种不同的排法？（六）顺序固定问题用“除法”对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一同进行排列，然后用 总的排列数除以这几个元素的全排列数例6.（1）五人排队甲在乙前面的排法有几种？六人排队，甲乙丙顺序固定 （可以不相邻），问不同排法

18、有几种？（七）分排问题用“直排法”把n个元素排成若干排的问题，若没有其他的特殊要求，可采取统一排成一排的方法来处理例7.7人坐两排座位，第一排坐 3人，第二排坐4人，则有 种排法？（八）实验题中附加条件增多，直接解决困难时，用试验逐步寻找规律有时也是行之有效的方法例8.将数字1,2,3,4填入标号为1,2,3,4的四个方格内，每个方格填1个，则每个方格的标号与所填的数字均不相同的填法种数有 种.（九）探索对情况复杂，不易发现其规律的问题需要仔细分析，探索出其中规律，再予以解决例9.从1到100的自然数中，每次取出不同的两个数，使它们的和大于100，则不同的取法种数有（十）消序例10.有4个男生

19、，3个女生，高矮互不相等，现将他们排成一行，要求从左到右，女生从矮到高排列（可以不相邻），有多少种排法？（十一）住店法解决“允许重复排列问题”要注意区分两类元素：一类元素可以重复另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解的方法称为“住 店法”.例11七名学生争夺五项冠军，获得冠军的可能的种数有 .（十二）对应例12.在100名选手之间进行单循环淘汰赛（即一场比赛失败要退出比赛 ），最后产生一名冠军，问要举行几场？（一场比赛对应淘汰一名）（十三）特征分析研究有约束条件的排数问题，须紧扣题目所提供的数字特征、结构特征，进行推理、分析求解例13.由1,

20、2,3,4,5,6六个数可组成多少个无重复且是6的倍数的五位数.例14.按下列要求，求排法总数：1）6人排成一排，甲乙丙三人都不在两端；2）五男两女站成一排，要求女生不能站在两端，且又要相邻；3）5人排成一行，要求甲乙两人之间至少有一人；4）6人排成一排，要求甲乙两人之间必有2人；5）一排6张椅子上坐3人，每两人之间有一张空椅子；6）8张椅子排成一排，有 4人就坐，每人一个座位，其中恰有3个连续空位；7）8名学生站成前后两排，每排4人，其中要求甲乙两人在后排，丙在前排；8）8人站成一列纵队，要求甲乙丙三人不在排头且互相隔开；9）8位同学，其中有3位是三好学生，他们和班主任合影，要求班主任坐中间

21、，而且左右两边 都要有三好学生；10）六人并排拍照，要求甲不坐最左边，乙不坐最右边练习题：1（1）.求满足方程x y z 10且x, y, z N *的解的个数.（2）某校高二年级有六个班，现需从中选出10名学生参加运动队，规定每班至少要入选1人,问有多少种不同的分配方案？（名额分配问题）推广：求满足方程 x y z 10且x,y,z Z且x 2, y 0, z2的解的个数.2 （1）.从一楼到二楼的楼梯 17级，上楼时可一步一级，也可一步两级, 若要求11步走完这楼梯，则有多少种不同的走法？（2）.如图从5 6方格中的顶点A到顶点B的最短路线有多少条？，但1,2,3，,10的十盏灯，为节约用

22、电又不影响照明，可以把其中的三盏关掉不能关掉相邻的两盏或三盏，也不能关掉两端的路灯问不同关灯方法有多少种?4从1,2,3，,14中，按数从小到大的顺序取出a1,a2,a3,使同时满足a?a13忌 a?3 ,则符合要求的不同取法有多少种?5求四个杯子，四个杯盖均不对号入座的方法种数6有五件不同奖品发给 4位先进工作者，每人至少一件，有多少种不同的发放方法?7从4台甲型和5台乙型电视机中任意取出3台，其中至少要有甲型与乙型电视机各一台，则不同的取法种数共有几种？8.从5个学生中选三人参加代表会，其中甲、乙两人至少一人在内，共有多少不同选法？9将5列车停在5条不同的轨道上，其中 a列车不停在第一道上，b列车不停在第二轨道上，那么不同的停放方法有几种？10. 平面上有11个相异的点，过其中任意两点相异的直线有48条.这11点中，含3个或3个以上的点的直线有几条？（2）这11点构成几个三角形？11. 一直线和圆相离，这条直线上有6个点，圆周上有4个点，通过任意两点作直线，最少可作直线的条数是（）A . 37B . 19C. 13D. 7