种？

22解：按要求放6个，其余4个按隔板站位法有C4?C?26?15种方法．

另解：（隔板法）设1，2，3号盒子所放的球数分别为a，b，c.则有a?b?c?10. 设x?a，y?b?1，z?c?2，则方程x?y?z?7的正整数解的组数，就是放球的

22方法数.所以共有C4?2?C6?15种方法.

注意：这种利用“先换元，再用隔板技巧”的方法对于求有限制条件的不定方程的非负整数解的问题很有效！

【总结提炼】

均匀分组（不计组的顺序）问题不是简单的组合问题，如：将3个人分成3 组，每组

111一个人，显然只有1种分法，而不是C3?C2?C1?6种 一般地，将m?n个不同元素均匀分成n组，有【课后作业】 【板书设计】（略） 【教学后记】

mmCmnC(mn?1)m?CmAmm种分法；

第四课时排列组合问题的解题方法（四）

教学目标：

掌握几类特殊的排列问题的解决技巧. 教学重点：掌握“递推法”等问题的解题技巧. 教学难点：如何应用“技巧”解题． 教学过程： 十.穷举法：

对于一些不能直接用两个原理，且类别不多的问题，通常采用穷举法.即列举所有情况. 例19 将五个市级三好学生名额和八个区级优秀学生干部名额全部分配到辖区的两所中学，每所学校至少有一个名额，有多少种不同的分配方案？

解：分配情况用有序数组(x,y)表示：（1,12），（2,11），（3,10），（4,9），（5,8），（6,7）.

然后两校交换.所以共有分配方案数为2?(2?3?4?5?6?6)?52种.

例20 . 十一.递推法：

对于一些较复杂的排列问题，可以建立排法之间的一个递推关系，通过递推关系求出排法种数.

例19 一个楼梯共10个台阶，如果规定一步登一个台阶或登两个台阶，一共有多少种不同的走法？

解：设上n级台阶的走法为an种，易知a1?1，a2?2，当n?2时，上n级台阶的走法可分两类：第一类是最后一步跨一级，有an?1种走法，第二类是最后一步跨二级，有an?2种走法.由加法原理可知an?an?1?an?2，据此可得a10?89种不同的走法.

例20 有五个人排成一列，现在要重新排列，要求都不能站在原来的位置，有几种不同排法？

解：我们考虑人数为n的情况，即n个人排成一列，重新站队时，各人都不站在原来的位置上.设满足这样的站队方式有an种，现在我们来通过合理分步，恰当分类找出递推关系：

第一步：第一个人不站在原来的第一个位置，有n?1种站法.

第二步：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类： 第一类，第二个人恰好站在第一个位置，则余下的n?2个人有an?2种站队方式； 第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，??，第n个人不站在第n个位置，所以有

an?1种站队方式.

由分步计数原理和分类计数原理，我们便得到了数列an的递推关系式：

an?(n?1)(an?1?an?2)，显然，a1?0，a2?1，?，a5?44.故有44种不同排法.

注意：n个人排成一排后，解散后重新排队，自己不站原来的位置的排法种数可由以下公式推导得到：

（1）a1?0，a2?1，an?(n?1)(an?1?an?2)（n?3）； （2）an?n![1?1111???????(?1)n]. 1!2!3!n!n1n?12n?23n?3n0（3）an?An?CnAn?1?CnAn?2?CnAn?3?????(?1)nCnA0.

例21 在n?m的网格中，从(0,0)点到(n,m)点，只能沿网格的边向x轴正方向或y轴正方向前进，问共有多少种不同的前进路线？

解：对任意一个非x轴、y轴上的点(x,y)，可以从点(x,y?1)走来，也可以从点

(x?1,y)走来.因此，设(x,y)处的路线条数为f(x,y)，则有递推公式：

f(x,y)?f(x,y?1)?f(x?1,y).

x下面的推理很重要：根据上述递推公式，可得f(x,y)?Cx?y，即从x?y件物品中选

出无顺序的x件（或y件）的总方案数.即f(x,y)?(x?y)!. x!y!?小结：上述问题中把每个f(x,y)指标在对应的坐标点处，再将坐标系顺时针旋转135，你发现了什么？这是杨辉三角，f(x,y)?Cx?y.而我们知道，Cxy?Cxy?1?Cxy?1.这就是通项公式的来源.

另解：记网格横向的x条线段从左至右依次为a1、a2、?、ax，网格纵向的y条线段从下至上依次为b1、b2、?、by.从(0,0)到(x,y)的走法种数，就是a1、a2、?、ax及b1、

xb2、?、by这x?y个元素的一个定序排列.于是有

?yAxx?yAxxAyy（或

(x?y)!）种不同走法. x!y!例22 某地决定在一个大型广场建一个同心圆形花坛，花坛分为两部分，中间小圆部分种植草坪，周围的圆环分为n（n?3,n?N）等份种植红、黄、蓝三色不同的花. 要求相邻两部分种植不同颜色的花. 如图①，圆环分成的3等份分别为a1，a2，a3，有6种不同的种植方法.如图②，圆环分成的4等份分别为 a1，a2，a3，a4，有18种不同的种植

方法；则在图③中，圆环分成的n(n?3,n?N)等份分别为a1，a2，a3，?,an, 有 种不同的种植方法.

a1 a1 a2 a4 ②

a2 ??

a1 a2 a3 a3 ①

a3 an ? ③

第18题图

解：对于n的情形，总的涂法数为3?2n?1，但是最后一块与第一块有两种情况：不同色

（满足题意）与同色，同色时就是n?1的情形，于是得出递推公式：an?3?2n?1?an?1anan1an?131an?1?????1??(?1) ，即

22n?1222n?12n2naF(n)6111n?3?1??1???1???(?)，即F(n)?2n?2?(?1)n?1. 因为3，所以3n844222（n?4），变形得

例23 有甲乙两队，各有7名队员，分别编号1～7，首先两队编号为1的队员对抗比赛，负者淘汰，胜者与负方的2号队员比赛，?，依次类推.直到某队全部淘汰为止.问最后有多少种不同比赛方式？

解：设f(x,y)表示甲乙两队分别由x，y名队员组成时的方式数.由于上次可能是甲、乙两队中某个被淘汰，故递推公式为：f(x,y)?f(x,y?1)?f(x?1,y).故转化为与上题

相同的数学模型.即f(x,y)?(x?y)! x!y!另解：记甲队7人分别为a1、a2、?、a7，乙队7人分别为b1、b2、?、b7.比赛结束时的方案数就是a1、a2、?、a7及b1、b2、?、b7这14个元素的一个定序排列.于是有

1414!A14（或）种不同方案数. 777!7!A7A7小结：求排列组合递推问题时，一定要注意以下几个方面： ①初始条件；②递推关系中?1，?1的问题；③递推终止条件.

例24 有甲、乙、丙三人踢毽子，互相传递，每人每次只能踢一下，由甲开始踢，经过5次传递后，毽子又被踢回给甲，问有多少种不同的传递方式？

解：设k（k?2）个人传递n（n?2）次后回到甲处的不同传递方法数为an. 则a2?k?1.下面考查an?1与an的关系.（如图）

甲?①?②?③?④???????甲

则甲?①有k?1种不同方法，①?②有k?1种不同方法，②?③有k?1种不同方法，??，?????k?1种不同方法.

而第n次接毽子的人?可能不是甲，也可能是甲，所以an?an?1?(k?1)n?1 对于本题，令k?3，则a2?2，由递推公式得a3?2，a4?6，a5?10. 注意：由an?an?1?(k?1)n?1得

anan?111 ???(k?1)nk?1(k?1)n?1k?1即

anan?1111???[?]， nn?1(k?1)kk?1(k?1)kan11n?2a21??(?)[?]，

(k?1)nkk?1(k?1)2k由等比数列的通项公式知

即

an11n?211??(?)(?)， n(k?1)kk?1k?1kk?1[(?1)n?(k?1)n?1].显然，当k?3时，a5?10. k化简an?