计数原理与简单排列组合问题知识点及题型归纳

计数原理与简单排列组合问题知识点及题型归纳知识点精讲基本概念.分类加法计数原理Q）有n类方法完成一件事,②任两类无公共方法（互斥）3每类中每法可单独做好这件事共有N共有N=m1 m2mn种不同方法.如图12-1所示.2.分步乘法计数原理m1事、mn2.分步乘法计数原理m1事、mn事事事事A事事m1+m2+m3+…+mn事事事事事事图12-1①必须走完n步，才能完成任务；完成一件事2）前一步怎么走对后一步怎么完成一件事2）前一步怎么走对后一步怎么共有N走无影响（独立）mn种不同方法.如图12-2所示.m〔事 m2事 mi事 mn事肇事事事B事事m1Xm"m3X->mn事事事事事事图12-2n类办法，这nn类办法，这n类办法之间是互斥的，那么分类加法计数原理和“分类”有关，如果完成某件事情有求完成这件事情的方法总数时，就用分类加法计数原理 ^.如果完成某件事情有n.如果完成某件事情有n个步骤，而n个步骤后，这件事情才算完成，那当然，在解决实际问题时，并不一定是单一应用分类计数原理或分步计数原理，有时可能同时用到两个计数原理.即分类时，每类的方法可能运用分步完成；而分步后，每步的方法数可能会采取分类的思想求方法数.对于同一问题，我们可以从不同的角度去处理，从而得到不同的解法（但方法数相同） ，这也是检验排列组合问题的很好方法..排列与排列数从n个不同元素中取出MmfCn）个（不同）元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列.从n个不同元素中选取m个元素（n>m）的排列个数共有A：.Amngn1gn2ggnm1(m个连续正整数之积，n为最大数).A；ngn1gn2gg3gZgln!Amn!Am(nm)!规定0!1.(nm)!注L Amnn1nm1常用Amnn1nm1常用于具体数字计算；而在进行含字母算式化简或证明时，多用Amn!(nm)!可重排列与无重排列的区别.例如：用1,2,3,4,5这五个自然数，可排成有重复数字的四位数—— 5X5X5X5=54四—重复数字的四位数—— 5X4X3X2=A54区别：不可重复排列：用过的数字不可再用，用一个少一个可重复排列：用过的数字还可再用，每次可用数字不减少。再例如：4封不同的信，全部投入5个信箱.0任意投（投过的信箱可再投入）一一 5X5X5X5=54.⑵每箱至多一封信（投过的信箱不可再投入）一一 5X4X3X2=A54..组合与组合数从n个不同元素中取出mm1cn）个（不同）元素，并成一组，叫做从n个不同元素中取出m个元素的一个组合.从n个不同元素中取出m个元素的组合数共有C：.cmAcmAmn(n1)(n2)(nm1)

m!n!m!(nm)!注同样，公式cmn（n1）（n2）—（nm”常用于具体数字计算,cm-n一常用于含字m! m!（nm）!母算式的化简或证明

(1)排列和组合的区别.组合：取出的元素地位平等，没有不同去向和分工 ^排列：取出的元素地位不同，去向、分工或职位不同 ^注排列、组合都是研究事物在某种给定的模式下所有可能的配置数目问题，它们之间的主要区别在于是否要考虑选出元素的先后顺序，不需要考虑顺序的是组合问题，需要考虑顺序的是排列问题 .排列是在组合的基础上对入选的元素进行排队， 因此，分析解决排列组合综合问题的基本思维是 “先组合，后排列”.例如：从10个人中抽出4人参加某项活动有(1)排列和组合的区别.组合：取出的元素地位平等，没有不同去向和分工 ^排列：取出的元素地位不同，去向、分工或职位不同 ^注排列、组合都是研究事物在某种给定的模式下所有可能的配置数目问题，它们之间的主要区别在于是否要考虑选出元素的先后顺序，不需要考虑顺序的是组合问题，需要考虑顺序的是排列问题 .排列是在组合的基础上对入选的元素进行排队， 因此，分析解决排列组合综合问题的基本思维是 “先组合，后排列”.例如：从10个人中抽出4人参加某项活动有C40种方案；从10个人中抽出4人分别参加4项活动有A：。种方案.(2)一切排列数、组合数、阶乘及它们展开式的因数都是正整数 ^3!=6,4!=24,5!=120,6!=720.C2cn2n(n1),A；n,A2n(n1).22)!.10099.21c9C40(口诀：相邻组合数相加，加一元( n—n+1)取大(m+1叫取0!=1!=1,2!=2Cnc； 1,Cnc；(3)公式(性质)n(nc；mCn1)!n(n，如C980Cm;,如C1003C9n+1).mCm2mCnmCm4)CmCm2mCnmCm4)Cm题型归纳及思路提示题型1分类计数原理与分步计数原理思路提示要明确完成一件事所包含的内容是如何进行的，若需分类按加法数原理，若需分步按乘法计数原理 .分类时要做到“不重不漏”，分步时要做到“步骤完整” .有些计数问题既需要分类，又需要分步，此时要综合运用两个原理.例12.1现有3名老师，8名男生和5名女生共16人，有一项活动需派人参加.(1)若只需1人参加，有多少种不同选法？(2)若需老师，男生，女生各1人参加，有多少种不同选法？(3)若需1名老师和1名学生参加，有多少种不同选法？解析(1)有3类选人的方法：3名老师中选1人，有3种方法；8名男生中选1人，有8种方法；5名女生中选1人，有5种方法；由分类计数原理，共有3+8+5=16(种)选法.(2)分3步选人：第一步选老师，有3中方法；第二步选男生，有8种方法；第三步选女生，有5种方法；由分步计数原理，共有 3X8X5=120(种)选法.(3)可分两类：每一类又分两步.第1类：选1名教师和1名男生，因有两步，故3X8=24(种)选法；第2类：选1名教师和1名女生，因有两步，故有3X5=15(种)选法.再由分类计数原理，共有15+24=39(种)选法.评注在解决实际问题时，并不一定是单一地应用分类计数原理或分步计数原理，有时可能同时用到两个计数原理.即分类时，每类的方法可能运用分步完成，而分步后，每步的方法数可能会采取分类的思想求取.变式1有5张卡片，正反面分别写有数字 0与1,2与3,4与5,6与7,8与9,现从中任取三张，排成一列，问共可摆出个不同的三位数.

变式2晚会原有节目单由7个节目排成，现要新添3个不同的节目，且不改变原有节目的相对顺序，则这3个节目有多少种不同的安排方法？例12.2（1）若8名学生争夺3项体育比赛的冠军（每名学生参数项目不限） ，则冠军获得者有种不同情况（每个项目没有并列冠军） ^（2）8名学生从3项体育项目中选择参数，若每一名学生只能参加一项， 则有种不同的参赛方法.分析正确理解任务完成的标志，（1）即把3个冠军名额全部分给8个学生（可以一名学生夺得多个冠军）；（2）即为8名学生都报完比赛项目（可以多名学生报一个项目） ^解析（1）第1个冠军名额的去向有8种，第2个冠军名额和第三个冠军名额同样各有 8个可能去向，故冠军获得者共有8X8X8=83（种）不同的情况.（2）第一位学生报项目的方法有 3种，同样，其他每一位学生都有 3种报取项目的选择方法，根据分步计数原理，故应有3X3X3X3X3X3X3X3=38（种）不同的参赛方法.变式1将3个信封投到4个邮箱，最多的投法有种.变式2现有6名同学听取同时进行的5个课外知识讲座，每个同学可自由选择其中一个讲座，不同的选法有（）种.A.56 B.6 5C.D.6C.D.6X5X4X3X2变式3已知集合A={1,2,3},B={1,2,3,4}.（1）映射f:ZB共有多少个？（2）映射g:4A共有多少个？4张贺卡的不例12.3同室44张贺卡的不同的分配方式有（ ）.A.6种B.9种C.11种D.23种分析将同室4人分别记为a,b,c,d,然后利用4个取卡的情况分步来确定.解析解法一：第一步，4个人中的任意一人（例如a）取一张，则由题意知共有3种取法；第二步：由第一人取走的贺卡的供卡人取，也有 3种取法；第三步：由剩余的两人中的任一人取，只有 1种取法；第四步：最后一人取，只有 1种取法，由分步计数原理，共有3X3X1X1=9（种）.解法二：设4张贺卡分别记为A,B,QD由题意，某人（不妨设A卡的供卡人）取卡的情况有3种，据此将卡的不同分配方式分为 3类，对于每一类，其他人依次取卡分步进行， 为了避免重负或遗漏现象，我们用“树图”表示如下：设a,b,c,d代表4个人，ABC,D分别代表这4个人写的贺卡，则有如图12-3所示的树状图.abcd.A--D--CB——C--D——-A~D-A——-C・A-"D--BC——'D--B--A、D-=A--B•A--B--CD"C A B图12-3所以共有9种不同的分配方式.故选B.评注本例提供的第一种解法用了分步计数原理， 关键是要弄清楚分步时每步的顺序， 例如a先取走C卡,则下一步应由c取，否则由b,c,d中一人取，就很难断定是有3种还是2种取法了.TOC\o"1-5"\h\z第二种解法可以看作两个原理的交替应用，用树图表示一目了然，便于分析计数，避免了重复或遗漏 .在以后的学习中，用树图来直观地分析问题是常用的，请同学们重视 ^变式1（2012全国大纲理11）将字母a,a,b,b,c,c排成三行两列，要求每行的字母互不相同，每列的字母也互不相同，则不同的排列方法共有 （）.A.12种B.18种C.24种D.36种变式23个人踢键子，互相传递，每人每次只能踢一下，由甲开始踢，经过5次传递后，键子又被踢回给甲，则不同的传递方式共有（ ）.A.6种B.8种C.10种D.16种例12.4某外语组有10人，每人至少会英语、法语中的一门 .其中7人会英语，5人会法语.从中选择会英语和法语的各一人派往两地参加会议，有多少种不同的方法？分析对于较为复杂的分类与分步问题，应做到不重不漏，本题应抓住公共元素的处理方法 ^解析由集合知识可知，既会英语又会法语的有 7+5-10=2（人），仅会英语的有7-2=5（人），仅会法语的有5-2=3（人）.易知此题的任务是派遣适合条件的两人 .解法一：按仅会英语的5人的派遣情况分成两类.第1类：仅会英语的5人中有1人选中，则有5种方法，而会法语的则有 5种方法，从而由分步计数原理，有5X5种方法.第2类：仅会英语的5人中没有人被选中，则会英语的必须从既会英语又会法语的 2人中选，从而有2种选法.而会法语的只能从两种语言均会的剩余1人或仅会法语的3人中选，共有1+3=4（种），由分步计数原理得，此时共有2X4种方法.由分类计数原理，共有5X5+2X4=33（种）方法.解法二：按仅会法语的3人的选派情况分成以下两类.第1类：仅会法语的3人恰被选中1,则由分步计数原理，共有 3X7种方法.第2类：仅会法语的3人均未被选中，则由分步计数原理得，共有 2X6种方法.从而由分类计数原理，共有 3X7+2X6=33（种）方法.解法三：按既会英语又会法语的2人的选派情况分成3类.第1类：2人均未被选派，则有3X5种方法.第2类：2人均被选派，则有2种方法.第3类：2人中恰有1人被选派，则又分为两类.若另一人只会英语，则有2X5种方法.若另一人只会法语，则有2X3种方法.由分类计数原理得，共有3X5+2+2X5+2X3=33（种）方法.评注在应用分类和分步计数原理解决较复杂的问题时应注意：（1）认真审题，分析题目的条件、结论，特别要理解题目中所讲的“事情” ，即任务是什么，完成这件事情的含义和标准是什么.（2）明确完成这件事情是分类还是分步，还是既要分类又要分步，并搞清分类或分步的具体标准是什么 .（3）注意两个原理的实质：分类用分类计数原理（即加法） ，分步用分步计数原理（即乘法）^变式1用三种颜色染如图12-4所示的矩形块，要求每块染一种颜色且相邻不同色 ^（1）共有多少方法？（2）每种颜色染两块有多少种方法？图12-4变式2如图12-5所示，马从点A按“马走日”到B,至少走步，如此步数有种不同的走法

图12-5题型2排列数与组合数的推导、化简和计算思路提示尽量用性质计算；推导、证明和化简约分用阶乘形式，计算用乘积形式例12.5⑴证明：Am ngn1图12-5题型2排列数与组合数的推导、化简和计算思路提示尽量用性质计算；推导、证明和化简约分用阶乘形式，计算用乘积形式例12.5⑴证明：Am ngn1ggnm1=n!(nm)!(n,m-•* 、N,mn). —.，… *(2)已知m,nN,且mn.证明：①Ca：Amn!m!(nm)!②c：③cmcmC：1c：m1Cmn1定顺序排成解析（1）An为从n个（nCN）不同兀素中取出m（m^n,mCN）个（不同）兀素，按照定顺序排成一列的不同排列的个数（即排列数） .如表12-1所示，需要m步完成排列任务表12-112Mmn种方法n-1种方法n-n+1种方法第一步（为位置1选择一个元素）有n种选法.第二步（为位置2选择一个元素）有n-1种选法.第m步（为位置m选择一个元素）有n-n+1种选法.依分步计数原理，得A：nn1nm1=n!（2）①C：为从n个不同元素中任取m个（不同）元素并成一组的不同组合的个数 （即组合数），当meN,men时，从n个不同元素中取m个（不同）元素按照一定的顺序排成一列，可以分成两步完成，第一步从n个不同元素中任取m个元素并成一组，第二步把取出的 m个元素按照一定的顺序排成一列，依分步乘法原理得AmcmgAm.即cm，又A即cm，又Amn!(nm)!Amm!,故cm—n—.当m=o,cn1.m!(nm)!TOC\o"1-5"\h\z\o"CurrentDocument"n! 0n! 1,Cn 1也成立.0!gn! 0!gi!@cnm n -n—(nm)![n(nm)]!m!(nm)!故cm cnm.@cmcm1n n m!(nm)!(m1)!(nm1)!(m1)n!(m1)!(nm)!(m1)n!(m1)!(nm)!(nm)n!(m1)!(nm)!(n1)!(m1)!(nm)!(n1)!(m1)!(nm)!m1cn1④由cm cmm1 ④由cm cmm1 cm1 cm 1cm2 ,则cm Cm 1cm2 cm2 cm2cm3,依此类推,m m1m m1C；01cmncmncmncmn1C；01评注题目⑷中的求和应用，如⑴c2c3c20o3 3(ii)C10C113 3 3C20 C3 C3 3(ii)C10C113 3 3C20 C3 C4C20(C3c4C9)=C21 C10.变式1组合数C；(nr1,n,rZ)恒等于().A.」C；1B.(n1)(r1)Cn11 C.n13 2 *变式2解万程A2n100A2(nN).nrC：；D.』Cr1Cn1r例12.6(1)乘积m(m1)(m2)（m20）可表示为（）.A.A20mmB.21 _Am C.20Am20D.21Am20(2)式子m(m1)(m2)(m20)20!可表不为（).A.Am020B. Cm0A.A20mmB.21 _Am C.20Am20D.21Am20(2)式子m(m1)(m2)(m20)20!可表不为（).A.Am020B. Cm020 C.2优匕0D.21cm120解析原式二(m20)(m19)[(m20)211]Am12021,也可以观察，一共有21个连续正整数的积，可以直接表本为 Am20.故选D.A21(2)原式=AR20!A2121-^21cmi20.故选D.21!评注公式Amn1nm1的构成特点是：公式右边第一个因数是n,其后每个因数都比它前面一个因数少1,最后一个因数是n-n+1,共有m个因数相乘，组合数C：公式也有相似特点.使用时要注意三个问题：第一个因数是什么、最后一个因数是什么、一共有多少个连续相乘的正整数,防止我们在“n”，"m'比较复杂时用错公式.应用公式时，要注意正用、逆用和活用等 .变式1一排9个座位坐了3个三口之家，若每家人坐在一起，则不同的坐法种数为().A.3X3!

_ _ 4C.(3!)B.3D.9!3X(3!)题型3计数原理与排列组合问题的结合思路提示要注意可重排列与不可重排列的区别；选择适当的解题策略，即加法与减法；应注意不重不漏 .例12.7如图12-6所示，电路中共有13个开关（电阻略），每个开关可任选“开”或“关”一种状态，且相互独立.图12-6图12-6⑴(2)⑴(2)分析解析（1）灯亮，第一步A通到C,再相乘得整体通（即灯亮）方法数.第一步：先算A到C不通方法数,—（22—1）=5,中路不通的方法数灯亮，有多少种整体状况；灯灭，有多少种整体状况.每个开关有“开”或“关”两种状况，逐个确定这 13个开关的“开”、“关”状态共有213=8192（个）整体状态，只要求出（1）与（2）中一值，用减法即可求出另一值第二步C通到D,第三步D通到E,第四步E通到B,算出每步方法数,即上、中、下三路都不通，上路不通的方法数=23—（上路通的方法数）二23=1,下路不通的方法数=22—1=3.故A到C不通的方法数为5X1X3=15.A到C通的方法数=28—15=256—15=241,

C到D通的方法数=22—1=3,D到E通的方法数=1,E到B的方法数=22-1=3.故灯亮即四步都通，整体状况有 241X3X1X3=2169（种）.（2）灯不亮有213—2169=8192—2169=6023（种）.评注 串联求通：把各段通数相乘，得总通数.串联求不通：先求通，再用减法，得串联不通数.并联求通：先求不通数，再用减法，得并联通数 .并联不通：把各支路不通数相乘 .变式1直线方程Ax+By=0,从1,2,3,4,5这五个数中每次取两个不同的数作 A和B共可确定（ ）条直线.A.20B.19C.18D.16变式2一个n棱锥的所有顶点共可确定条直线，这些直线可确定对异面直线.例12.8如图12-7所示，有4种不同颜色供选，要求ABCDE每块一种颜色，相邻两块不同色，共有多少种染色方法？解析如图12-8所示，记4种颜色为1,2,3,4,可以从E开始染，有4种染法，A与E相邻，A,E不同色，所以A有3种方法，B与AE均相邻，B有2种染法，最后剩CD,此时要注意分类讨论，如图12-8所示，C与A同色时，D有2种染法；C与A不同色时，D有1种染法，即CD共有3种方法.综上共有4X3X2X3=72种染色方法.评注利用计数原理求解染色问题，一般有“区域”染色和“线段端点”染色两类，其中区域染色问题，常用的原则有“最多相邻优先”，但要注意最后2〜3个区域的分类讨论.变式1如图12-9所示，用4种不同颜色给图中A,B,C,D,E,F共6个点染色，要求每个点染一种颜色，且图中每条线段的两个端点不同色，则不同的染色方法共有 （） 种.A.288B.264C.240D.168变式2用4种不同颜色为正方体的六个面着色， 要求有公共棱的两个面不同色， 则共有（）种不同的着色方法.A.24B.48C.72D.96变式3用红、黄、蓝三色之一去涂如图12-10所示的标号1〜9的9个小正方形，使任意有公共边的小正方形不同色，且3,5,7的方块同色，则共有种不同涂色方法.图12-9 图12-10变式4在五边形ABCDE中，五个顶点各染红、黄、绿三色之一，相邻顶点不同色，共有种不同染法.例12.9某市汽车牌照前面两个英文字母 （不可重复）后面四个数字（可重复）组成，最多有多少个牌照?解析任务：第一步，确定前面两个英文字母2625A26；第二步：确定后面四个数字4 4 6 .1010101010.所以最多可有262510 6.510（个）牌照

TOC\o"1-5"\h\z变式1某通信公司推出一组手机号码，号码的前 7位数固定，从 0000到 9999共10000个号码。公司规定：凡卡号的后4位带有数字4或7的一律作为优惠卡，则这组号码中优惠卡有（）个.A.2000 B.4096 C.5904 D.8320变式2用数字0,1,2,3,4这4个数字组成的四位数中有重复数字的四位数有（ ）个.A.192 B.182 C.174 D.274变式3用数字2,3组成四位数，且数字2,3至少都出现一次，这样的四位数共有个（用数字作答）.例12.10设集合I1,2,3,4,5,选择I的两个非空子集A与B,要使B中最小的元素大于A中的最大元素，则A与B的不同的选择方法共有（ ）种.A.50 B.49 C.48 D.47分析关键在于选择分类的依据.选才iAB的元素个数x为分类依据是最佳选择，显然，依题意x2,3,4,5.或选择B中的最小元素为分类依据.解析 解法一：令AB中有x个元素，则x2有C；种选法.x3有2C；种选法.x4有3C54种选法.x4有4C；种选法，则不同的选择方法共有 C2+2C53+3C54+4C5=49.故选B.解法二：当B中的最小元素为2时，则A中的最大元素只能为 1,2318种；当B中的最小元2 2素为3时，则A中的最大兀素只能为1或2,有2 2 1 12种；当B中的最小元素为4时，则A中的最大元素小于或等于3,有2231 14种；当B中的最大元素为小于或等于 4时，有1241 15种；，共有812141549.故选B.评注解法一中可以理解组合问题隔板法，应为 A,B集合中元素大小顺序一定.解法二中应注意排除可能出现空集的问题.变式1I1,2,3,4,5,A,B是I的两个子集，A中有3个元素，B中至少有两个元素，且 B中所有的元素不大于A中的最小元素，这样的A,B有组.变式2I1,2,3,4,从I中取出4个不同的子集，满足条件：①其中必有和I;②4个子集中的任意两个子集A与B,必有AB或B A.则4个子集共有种选法.例12.11用1~9填如图12-11所示的