1、1递推法解排列、组合及概率问题刘东林 （广东省普宁市第二中学数学组 515300）排列组合在高中数学旧教材中是相对独立的内容，而在高中数学新教材中排列组合是概率及统计的基础，因此，排列组合内容在高中数学新教材中的位置也变得相对重要起来了。而概率是新教材中新增加的内容，也是初等概率论中最基本的内容。在历年的高考中，排列组合知识多是选择题或填空题，概率一般是一个解答题，这些题的题型繁多，解法独特，因此得分率普遍较低。本文试图用递推法来解决几类常见的排列组合及概率问题。1 走楼梯问题例 1：欲登上第 10 级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有( )（A）34 种 （B）55 种
2、（C）89 种 （D）144 种解法 1：分类法：第一类：没有一步两级，则只有一种走法；第二类：恰有一步是一步两级，则走完 10 级要走 9 步，9 步中选一步是一步两级的，有 种可能走法；91第三类：恰有两步是一步两级，则走完 10 级要走 8 步，8 步中选两步是一步两级的，有 种可能走法；28C依此类推，共有 =89，故选(C)。546372819解法 2：递推法：设走 级有 种走法，这些走法可按第一步来分类，nna第一类：第一步是一步一级，则余下的 级有 种走法；1n1na第二类：第一步是一步两级，则余下的 级有 种走法，22所以 ，又易得 ，由递推可得 ，故选21nn ,12a891
3、0(C)。显然，递推法的关键是按照某种标准找出递推关系式，并求出 取第一个值n(或前几个值)时的各项，然后代入递推关系式，求出题中要求的值。当然，我们也可以由找出的递推关系，求出通项 ，但对于选择填空题，我们不必大动na干戈的去求通项，因为这样太浪费时间与精力。2 更列问题把 个元素排成一列，所有元素各有一个不能占据的指定位置，且)(Nn不同元素不能占据的指定位置也不同，我们把满足这种条件的一个排列叫做这些元素的一个更列。例 2：五个人排成一列，重新站队时，各人都不站在原来的位置上，那么不同的站队方式共有( )（A）60 种 （B）44 种 （C）36 种 （D）24 种解：首先我们把人数推广
4、到 个人，即 个人排成一列，重新站队时，各人n都不站在原来的位置上。设满足这样的站队方式有 种，现在我们来通过合理na分步，恰当分类找出递推关系：第一步：第一个人不站在原来的第一个位置，有 种站法。1第二步：假设第一个人站在第 2 个位置，则第二个人的站法又可以分为两2类：第一类，第二个人恰好站在第一个位置，则余下的 个人有 种站队2n2na方式；第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，第 个人不站在第 个位置，所以有 种站队方式。n1na由分步计数原理和分类计数原理，我们便得到了数列 的递推关系式：na，显然， ，
5、再由递推关系有 ，)(112nna1,021a9,243a，故应选(B)45a我们再来看一道全国高考题：例 3：同室 4 人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则 4 张贺年卡不同的分配方式共有( ) (1993 年全国高考试题)（A）6 种 （B）9 种 （C）11 种 （D）23 种此题就是更列问题，即为例 2 中的 ，故选（B）94a3 染色问题例 4：用 4 种不同颜色涂四边形的 4 个顶点，要求每点染一种颜色，相邻的顶点染不同的颜色，则不同的染色方法有( )（A）84 种 （B）72 种 （C）48 种 （D）24 种解：我们先把这个题目推广：用 种不同颜
6、色给 边形 的 个顶mnnA21点染色(其中 ，且 为常数)，每点染一种颜色，相邻的顶点染不同3,nm的颜色，不同的染色方法有多少种？设不同的染色方法有 种，现在我们来通过合理分布，恰当分类找出递推na关系：第一步：染 ，有 种染法；1A第二步：染 ，有 种染法；2同理，染 均有 种染法，最后染 ，如果仅考虑 与 不13,n mnAnA1同色，则仍有 种染法，相乘得 种染法，但要去掉 与 同色的1)(n染法数，此时可将 与 合并看成一个点，得出需要排除的染法数为 ，所n1 1na以有 ，显然， 。)(nama3ma又本题中，颜色数 ，所以递推关系为： ，又4 134nna，所以 （种） ，故选
7、（A） 。243A83用这种方法，不难求出下面两道 2003 年的高考题：例 5：如图 1，一个地区分为 5 个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有四种颜色可供选择，则不同的着色方法共有 种。（以数字作答）(2003 年全国高考试题)例 6：某城市在中心广场建造一个花圃，花圃分成 6 个部分(如图 2)，现要栽种 4 种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法共有 种。 （以数字作答）(2003 年天津理科高考试题)21345图 112 3456图 23我们来看例 5，其中 2、3、4、5 四个区域围成一个四边形，因此可以把它们看成是一个
8、四边形的 4 个顶点，而区域 1 就是这个四边形对角线的交点。第一步，先涂区域 1，有 4 种涂法，由于区域 1 跟其余四个区域都相邻，因此涂1 的颜色不能用来涂其余的四个区域，因此第二步相当于用 3 种颜色来涂一个四边形的四个顶点，由例 4 不难得出 ， ，所以，123nnaa6A342a，由分步计数原理，得出共有 种涂法。8 718同理，不难得出例 6 的答案为 120 种。4 传球问题例 7：甲、乙、丙、丁四人相互传球，第一次甲传给乙、丙、丁中的任一人，第二次由拿球者再传给其他人中任一人，这样共传了四次，则第四次球仍传回到甲的方法共有( )（A）21 种 （B）42 （C）24 （D）2
9、7解：先把这个题目进行推广： 个人相互进行 次传球，)(Nm)(Nn由甲先传，第一次甲传给其他 个人中的任一人，第二次由拿球者再传给其1他人中任一人，这样经过 次传球，最后球仍回到甲手中的传球方法有多少种？n(这里 为常数)m设不同的传球方法共有 种，现在我们来通过合理分步，恰当分类找出递a推关系：第一步进行第一次传球：甲传给其他人，有 种传球方法；1m第二步进行第二次传球：拿球者把球传给其他人，仍有 种传球方法；同理，第三次、第四次、第 次传球都有 种传球方法，最后n进行第 次传球，由于只能传给甲，故只有一次传球方法，相乘得 种n 1)(nm传球方法，但要注意第 次传球不能传给甲，否则就不存
10、在第 次传球，因1n此要去掉第 次传球，球恰好传给甲的传球方法数，这就是由甲先传，经过次传球后球又回到甲手中的传球方法，显然，这里有 种传球方法，所1 1na以有递推关系： ，又易得， 。1)(nnama01而在本题中， ，所以 ，所以由递推可得，43n，312a，故本题应选（A）2,63423最后，我们来用递推法求解一个概率问题。5 概率问题例 8：A、B 二人拿两颗骰子做抛掷游戏，规则如下：若掷出的点数之和为3 的倍数时，原掷骰子的人再继续掷；若掷出的点数不是 3 的倍数时就由对方接着掷，第一次由 A 开始掷，求第 次仍由 A 掷的概率 。nnP解：连续掷两次骰子，点数之和为 3 的倍数的
11、概率为 ，不是 3 的倍1624数的概率为 ，又第 次由 A 掷这一事件，包括第 次由 A 掷，第321n1n次继续由 A 掷这一事件以及第 次由 B 掷，第 次由 A 掷这一事件，并且n1这两个事件是互斥的，而第 次由 A 掷的概率为 ，由 B 掷的概率为1nP，所以1nP，又显然 ，),2(,32)1(321 NPnnn 1P由有 ，所以 ，1 113(n即 。),()2NPnn现在我们再来看看下面这组练习：（1）袋子里有 10 个相同的小球，现在把这些球全部摸出来，一次可以摸一个球，也可以摸两个球，则不同的摸法共有多少种？恰好 7 次摸完的概率为多少？（2）五本不同的书分给五个同学，而每
12、个同学都看过其中的一本书，但没有两个同学看过同一本书，则每个同学分到恰好是他没有看过的书概率为多少？恰有一个同学分到他看过的书的概论为多少？（3）有一堆大小相同的小球，里面有红色、黄色、白色，并且每种颜色的球至少都有 3 个，现从中任取 6 个球排成一圈，要求任意相邻的两个小球不得同色，则不同的排法有多少种？（4）从集合1，2，3，4中任取 5 个数（可重复）排成一个五位数，要求首位只能排 1 且任意相邻两个位置不能排同一数，则末位恰好也是 1 的五位数有多少个？末位不是 1 的五位数有多少个？末位是 2 的概率为多少？事实上，我们利用上面几个问题的模型，可以很容易的解决这组练习，因为它们就是那几个模型的实同形异的变式，分别对应于走楼梯问题、更列问题、染色问题与传球问题。
