高考数学培优指南：计数原理与关灯方法

Ⅰ.根本方法

1.分类法：完成任务按照某个标准分成几类，则总共的方法数等于按各个标准完成任务的方法数之和.

例 用0，1，2，3，4五个数字共能排成多少个无重复数字的五位偶数？

【解析】按照末位数字是否为0分两类：

2.分步法：完成任务需要几个步骤，则总共完成任务的方法数等于完成每个步骤的方法数之积.

例 用0，1，2，3，4五个数字共能排成多少个无重复数字的五位数？

【解析】第一步，排万位，有4种方法，第二步至第五步分别排千位、百位、十位、个位，分别有4，3，2，1种方法，故n=4×4×3×2×1=96（个）.

Ⅱ.常见方法

1.捆绑法：排列任务需要某些元素相邻，可以先把这些元素看成和其他元素不同的一个元素，并和其他元素一起排列，再对这些相邻元素排列，有多组元素相邻则类似处理.

例 有不同编号的红球4个，黄球3个，白球4个，求这10个球的排列中，红球互相相邻，黄球也互相相邻的不同排列方法数.

2.插空法：排列任务需要某些元素不相邻，可以先对其他元素排列，再把不相邻的元素插入排列好的其他元素形成的空档，注意一个空档只能插一个.

例1 有不同编号的红球4个，黄球3个，求黄球不相邻的排列方法数.

例2 路上有编号为1—9的九盏路灯，为节约用电，要关掉其中的三盏，但不能关掉相邻的两盏或三盏，也不能关掉两端的路灯，问有多少种不同的关灯方法？

3.除法：如果有相同的元素，可以先看成不同的元素进行排列，再除以这些相同元素的全排列数.

例 有相同的红球4个，相同的黄球3个，相同的白球4个，问共有多少种不同排列方法？

4.间接法1——减法：对排列组合任务，如果可以知道总的方法数和所有不满足条件的方法数，则完成任务的方法数为两者之差.

例 6个人排成一排，甲不站最左端，共有多少种不同站法？

5.间接法2——容斥原理：排列组合任务如果有两个条件，则满足条件的方法数等于全部的方法数减去不满足条件A的方法数，减去不满足条件B的方法数，加上同时不满足两个条件的方法数.如果条件更多，则类似容斥原理.注意：在计算不满足条件A的方法数时，不考虑别的条件是否满足，直接当作不存在其他条件.

例 6个人排成一排，甲不站最左端，乙不站在最右端，共有多少种不同站法？

6.枚举法1——全枚举法：列出全部满足要求的排列组合，数一数总数即可.

例 从A，B，C，D，E五人中选派三人去参加竞赛，要求不能同时有A和C，不能同时有D和E，若D去则B也去，则共有多少种不同的选派方案？

【解析】ABD，ABE，BCD，BCE共4种情况，其解题过程为：五人中选派三人，一共有10种情况：ABC，ABD，ABE，ACD，ACE，ADE，BCD，BCE，BDE，CDE，但要划去ABC，ACD，ACE，ADE，BDE，CDE，∵若D去则B也去，等价于B不在，则D也不在，故CDE这一种情况也应划去，故剩下上面4种情况.事实上，若D去则B也去⇔若B不去则D也不去.

7.枚举法2——半枚举法：同分类法.

例 有一个10级楼梯，每次只能上一级或两级，有多少种不同走法？

8.隔板法：将一些相同的元素分成几个组，看成向一排这些元素之间的空档插板（两端不能插板），需要注意的是每个组的要求是至少有一个元素，且n个组只需（n-1）块隔板.

【解析】设甲、乙、丙分别拿到x，y，z本书，变形为：x+（y-1）+（z-2）=7.

练习3 把10本完全相同的新书分给甲、乙、丙三个人，甲至少一本，乙至少两本，丙至少三本，则共有多少种不同的分法？

练习2 有一个10级楼梯，分七步跨完，每步可跨一级或两级或三级，则共有多少种不同跨法？

练习1 （a+b+c）12的展开式中共有多少项？

例1 把6本完全相同的新书分给甲、乙、丙三个人，每个人至少一本，有多少种不同的分法？

例2 方程x+y+z=12有________组正整数解；有________组非负整数解.

9.等可能法：先求出总数，根据同一性求出满足条件的概率，相乘得到满足条件的方法数.

例 把6名教师分配给三所学校，每所学校至少能分配到一名教师，其中王老师不去甲校，问共有多少种不同的分配方案？

（图1-1）

10.动态规划法：假设到第n步和第（n-1）步等各步方法数已知，由所给关系得到第（n+1）步的方法数最后得到递推公式.

例1 有一个10级楼梯，每次只能上一级或两级，有多少种不同走法？

【解析】假设上到第n级有an种方法，由题意可知，第n级是由第（n-1）级或第（n-2）级到达.

∴an=an+1+an-2，又a1=1，a2=2，∴a3=3，a4=5，a5=8，a6=13，a7=21，a8=34，a9=55，a10=89.

评注：此数列为斐波那契数列，可用特征根法求解.

例2 地板上有10个格子排成一排，现要铺红蓝瓷砖，要求蓝瓷砖不得相邻，共有多少种不同铺法？

∴a10+b10=144故共有144种不同铺法.

Ⅲ.常见模型

1.多面手问题

例 有赛艇运动员10人，3人只会划右舷，2人只会划左舷，其余5人左右舷都会划，现选6人上艇，平均分配在两舷上，问共有多少种不同的安排方法？

2.数图形个数问题

例 图1-2有多少个平行四边形？图1-3有多少个矩形？多少个正方形？图1-4有多少个三角形？

（图1-2）

（图1-3）

（图1-4）

3.最短路程问题

（图1-5）

例1 如图1-5所示的路线图中，只能沿各小矩形的边行走，从A到B共有几条最短路径？

例2 如图1-6所示的路线图中，只能沿各小矩形的边行走，从A到B共有几条最短路径？

【解析】从A到B的最短路径为：从A→C→B行走或从A→D→B行走.

（图1-6）

例3 如图1-7所示的路线图中，只能沿各小矩形的边行走，从A到B共有几条最短路径？

【解析】虽然可同上两例类似求解，但分类复杂！这里介绍一种更简便方法，如图1-8，给A标上1，之后每个节点标上数字，这个数字是该节点上方和左方节点数字之和，这里的上方和左方是由A→B往下或往右决定的，但都指向始点方向，当然有些地方没有路，那对应节点就不加上去，这样做到底，终点标出的数字就是路径数，所以，本题共有19条最短路径。

（图1-7）

（图1-8）

例4 如图1-9所示，从点A出发沿方格线走9步（一横格或一竖边记为一步）到达点B，共有多少种不同的走法？

（图1-9）

4.凸n边形的两个量

理解方法：共有n个顶点，任意选两点就有一条线，作出的所有线中除了对角线还有n条边，故要减去n.

理解方法：任意四点可形成一个四边形，一个四边形对应一对对角线交点.

例 圆上8个点的所有连线中，在圆内最多有________个交点.

（图1-10）

5.环排列：环排列与排列的主要区别是环排列没有首尾，所以第一个坐下的人坐任何一个位置都是一样的.

（1）n个元素的环排列共有（n-1）！种方法.

理解1：n个元素排列共有n！种方法，首尾相连以后类似12345和23451是同一种环状排列方法，因此最后再除以n.

理解2：先选一个元素任意坐下，以这个元素为起点将环展开为直线，剩下的（n-1）个元素全排列.

注：上面的讨论把逆时针和顺时针看成了两种不同的环排列，如12345和54321看成了两种不同的环排列，如果把逆时针和顺时针看成一种，最后除以2即可.

6.错位排列：1个元素的错位排列数为0；2个元素的错位排列数为1；3个元素的错位排列数为2；4个元素的错位排列数为9；5个元素的错位排列数为44；6个元素的错位排列数为265，…，且有递推公式：Tn+1=（n+1）Tn+（-1）n+1.

例 用3种颜色给如图1-11所示的三棱柱的6个顶点涂色，要求每条棱两端点的颜色不同，则共有多少种不同的涂色方案？

变式 用4种颜色涂呢？用n种颜色涂呢？

7.传球问题：有n个人，从甲开始传球，每次可以传给另一个人，求传球m次后回到甲有多少种可能性问题称为传球问题.简单的传球问题通过画树形图即可，对于一般情况，要构造递推公式解决.

（图1-11）

例 甲、乙、丙、丁四人做传球练习，从甲开始，求传球4次后仍回到甲手中有几种不同的传球方式？

【解析】依题意知，第三次传球后球一定不在甲手中，而第四次传球只能传给甲，由此根据分步计数原理求出所有传球方法.

①若第二次传球后，球在甲手中，传球方法有

②若第二次传球后，球不在甲手中，传球方法有

8.分配问题：要注意是有序还是无序，是平均还是不平均.

例 6本不同的书，按下列条件，各有多少种不同的分法？

（1）分成三份，每份两本；

（2）分给甲、乙、丙三人，每人两本；

（3）分成三份，一份1本，一份2本，一份3本；(www.xing528.com)

（4）分给甲、乙、丙3人，一人1本，一人2本，一人3本；

（5）分给甲、乙、丙3人，每人至少一本；

（6）分成5份，每份至少一本；

（7）分给5个人，每人至少一本.

9.涂色问题：涂色问题有四种基本类型：直线型、扇环形、星型、全连通型.每种类型用m种不同颜色给n个区域涂色，相连区域不能用相同的颜色涂色，颜色可不用完.

（1）直线型：如图1-12，用m（m≥2）种颜色涂n（n≥2）个区域，则不同的涂色方法数有：

理解：按照分步法涂色即可.

（2）扇环型：如图1-13，用m（m≥2）种颜色涂n（n≥2）个区域，则不同的涂色方法数有：

（图1-12）

（图1-13）

设涂色方法数为an，则a2=m（m-1），且an+an-1=m（m-1）n-1，

即an=-an-1+m（m-1）n-1，

设an+λ（m-1）n=-an-1+m（m-1）n-1+λ（m-1）n，

即an+λ（m-1）n=-an-1+［m+λ（m-1）］（m-1）n-1=-［an-1-（λm-λ+m）（m-1）n-1］，

令λ=-m-λ（m-1），∴λ=-1，即an-（m-1）n=-［an-1-（m-1）n-1］.

∴数列｛an-（m-1）n｝是以［a2-（m-1）2］为首项，以-1为公比的等比数列，

∴an-（m-1）n=（m-1）（-1）n-2，即an=（m-1）n+（-1）n-2（m-1），即an=（m-1）n+（-1）n（m-1）.

理解：按照分步法涂色即可.

理解：按照分步法涂色即可.

（图1-14）

（图1-15）

（图1-16）

例 用4种颜色给如图1-16所示的区域涂色，相连的区域不能涂相同的颜色，共有多少种不同的涂色方案？

∴n=4×18=72（种），故共有72种不同的涂色方案.