论文部分内容阅读
在高中数学计数原理这一章学习中，常常碰到一些诸如圆环区域染色，三人互相传球，爬楼梯等有着递推背景的计数问题。这是计数知识与数列知识的交汇点，如果从递推的视角看待探究这类问题，解题思路给人豁然开朗的感觉。笔者将教学中常遇到此类问题及递推视角的解题思路举例如下，供大家教学和学习参考。
一、一阶递推关系的计数问题
例1：（圆环染色问题）如下图1，2所示，圆环形花坛区域等分，种植红、黄、蓝、白四色不同的花，要求相邻区域种植不同颜色的花，问共有多少中不同的种植方法？
解析：记对于n等分的圆形花坛，共有种种植方法，任意指定一块区域作为第一块开始染色，按顺时针顺序，则有n=2时，a2=4×3=12;n=3时，a3=4×3×2=24;n=4时情况要复杂，这时要区分第三块区域颜色和第一块区域颜色相同还是不同，根据分类加分计数原理，共有;当n≥5时，按照上述思路，分类将会变得无比复杂。如果按照顺时针染色，先只考虑和前方区域颜色不同，则有4×3n-1，但此时，第n块区域的染色有两种可能性：①与第一块区域颜色相同;②与第一块区域颜色不同。②恰是我们需要的an，而①时，我们将第n块区域与第一块区域看成同一块区域，则此时的染色恰为an-1，因此，得到递推公式。
由此递推公式求通项公式，可采用正负号调节后的累加法：
累加
得
整理得。
例2：（三人传球问题）三人相互传球，由甲开始发球，并作为第一次传球，经过n次传球后，球仍回到甲手中，则不同的传球方式有多少种？
解析：如图所示，列举前3次所有的传球方式：
记n次传球后，球仍回到甲的传球方式有an种，则有上述列举图可知：，且可以发现，n次传球后，共有2n中传球方式，第n次传球后，球传到甲手中的次数等于上一次中球不在甲手中的次数，由此，我们得到递推公式，类似例1的方法，求得通项公式。
例3：（汉诺塔问题）如图，有三根杆子A，B，C。A杆上有个穿孔圆盘，盘的尺寸由上到下依次变大。要求按如下规则将所有圆盘移至C杆：①可以借助B杆;②每次只移动一个圆盘;③在移动的过程中始终保持每个杆上的圆盘自上而下都是由小变大顺利排列。问最少需要移动多少次圆盘？
解析：记按要求将A杆上的盘子移至C杆上最少需要移动an次盘子。显然，当n=1时，直接移过去，有a1=1;当n=2时，先将上面盘子移至B杆，再将第二个盘子移至C杆，第三步将B杆上的盘子移至C杆，因此a2=3;当n时，先将上面n-1个盘子移至B杆，需移动an-1次，再将最下一个盘子移至C杆，需移动1次，第三步将B杆上的n-1个盘子移至C杆，需移动an-1次，因此得到递推公式：。解得。（关于此问题更有意思的描述请参看科普名著《从一到无穷大》）
以上三个背景各不相同的计数问题从数学上看都是一阶递推关系的递推问题，相似的还有如下参考题：
练习1：如图，将n-棱锥S-A1A2…An（n≥3）的每一个顶点涂上一种颜色，并使同一条棱的两端点异色，如果只有5中颜色可供使用，那么有多少种不同的涂色方法？
练习2：某情报站有A，B，C，D四種互不相同的密码，每周使用其中的一种密码，且每周都是从上周未使用的三种密码中等可能地随机选用一种。设第一周使用A种密码，那么第n周也使用A种密码的概率是______。
二、二阶递推关系的计数问题
例4：（爬楼梯问题）一楼楼梯共n（n≥1）级，每步可以向上跨1级或2级，问共有多少种上楼梯的方式？
解析：记跨完n级楼梯共有an种走法，如下我们分两类来考虑此问题：①第一步跨了1级，则剩下的还有an-1种走法;②第一步跨了2级，则剩下的还有an-2种走法。由此我们得到二阶递推公式an=an-2+an-1。这是著名的斐波那契数列的递推公式，这里a1=2，a2=2。由特征根法我们知道通项公式。
练习3：（贴瓷砖问题）定义一个瓷砖为一个1×2的矩形，如下图。有多少种将瓷砖平铺在一起得到n×2的矩形的方法？
例6：（错位排列问题）现将n个编号分别为的小球放入编号为的n个盒子中，要求每个盒子只放1个小球，则球号与盒号都不相同的放法共有多少种？
解析：记球号与盒号都不相同的放法共有an种。显然，当n=1时，a1=0;当n=2时，a2=1;当n≥3时，如下我们分两类来考虑此问题：①1号球放入k（2≤k≤n）号盒子且k号球放入1号盒子时，由于k有n-1种变化，故共有（n-1）an-2种放法;②1号球放入k（2≤k≤n）号盒子且k号球不放入1号盒子时，此时问题归结为将2，3，...，n号球放入号盒子，且k号球不放入1号盒子，由于k有n-1种变化，故共有（n-1）an-1种放法。因此，我们得到二阶递推公式。利用递归迭代方法求出an，推导如下：
令，则有，整理得，对于n≥2，我们有
再累加得，所以。
上述给大家列举的几个递推问题，是高中数学教学中经常遇到的经典问题，集趣味性和思想性于一体，如果用计算机编程语言实现，则这些问题也就是计算机数据结构算法中的典型案例。如能合理的渗透到高中数学教学中，相信必能促进学生的数学学习的热情和思维的发展，提升学生的数学核心素养。
参考文献
[1]单墫、熊斌.多功能题典·高中数学竞赛华.东师范大学出版社，2008年
[2]PaulZeitz.怎样解题·数学竞赛攻关宝典.人民邮电出版社，2010年
[3]伽莫夫.从一到无穷大·科学中的事实和臆测.科学出版社，2013年
一、一阶递推关系的计数问题
例1：（圆环染色问题）如下图1，2所示，圆环形花坛区域等分，种植红、黄、蓝、白四色不同的花，要求相邻区域种植不同颜色的花，问共有多少中不同的种植方法？
解析：记对于n等分的圆形花坛，共有种种植方法，任意指定一块区域作为第一块开始染色，按顺时针顺序，则有n=2时，a2=4×3=12;n=3时，a3=4×3×2=24;n=4时情况要复杂，这时要区分第三块区域颜色和第一块区域颜色相同还是不同，根据分类加分计数原理，共有;当n≥5时，按照上述思路，分类将会变得无比复杂。如果按照顺时针染色，先只考虑和前方区域颜色不同，则有4×3n-1，但此时，第n块区域的染色有两种可能性：①与第一块区域颜色相同;②与第一块区域颜色不同。②恰是我们需要的an，而①时，我们将第n块区域与第一块区域看成同一块区域，则此时的染色恰为an-1，因此，得到递推公式。
由此递推公式求通项公式，可采用正负号调节后的累加法：
累加
得
整理得。
例2：（三人传球问题）三人相互传球，由甲开始发球，并作为第一次传球，经过n次传球后，球仍回到甲手中，则不同的传球方式有多少种？
解析：如图所示，列举前3次所有的传球方式：
记n次传球后，球仍回到甲的传球方式有an种，则有上述列举图可知：，且可以发现，n次传球后，共有2n中传球方式，第n次传球后，球传到甲手中的次数等于上一次中球不在甲手中的次数，由此，我们得到递推公式，类似例1的方法，求得通项公式。
例3：（汉诺塔问题）如图，有三根杆子A，B，C。A杆上有个穿孔圆盘，盘的尺寸由上到下依次变大。要求按如下规则将所有圆盘移至C杆：①可以借助B杆;②每次只移动一个圆盘;③在移动的过程中始终保持每个杆上的圆盘自上而下都是由小变大顺利排列。问最少需要移动多少次圆盘？
解析：记按要求将A杆上的盘子移至C杆上最少需要移动an次盘子。显然，当n=1时，直接移过去，有a1=1;当n=2时，先将上面盘子移至B杆，再将第二个盘子移至C杆，第三步将B杆上的盘子移至C杆，因此a2=3;当n时，先将上面n-1个盘子移至B杆，需移动an-1次，再将最下一个盘子移至C杆，需移动1次，第三步将B杆上的n-1个盘子移至C杆，需移动an-1次，因此得到递推公式：。解得。（关于此问题更有意思的描述请参看科普名著《从一到无穷大》）
以上三个背景各不相同的计数问题从数学上看都是一阶递推关系的递推问题，相似的还有如下参考题：
练习1：如图，将n-棱锥S-A1A2…An（n≥3）的每一个顶点涂上一种颜色，并使同一条棱的两端点异色，如果只有5中颜色可供使用，那么有多少种不同的涂色方法？
练习2：某情报站有A，B，C，D四種互不相同的密码，每周使用其中的一种密码，且每周都是从上周未使用的三种密码中等可能地随机选用一种。设第一周使用A种密码，那么第n周也使用A种密码的概率是______。
二、二阶递推关系的计数问题
例4：（爬楼梯问题）一楼楼梯共n（n≥1）级，每步可以向上跨1级或2级，问共有多少种上楼梯的方式？
解析：记跨完n级楼梯共有an种走法，如下我们分两类来考虑此问题：①第一步跨了1级，则剩下的还有an-1种走法;②第一步跨了2级，则剩下的还有an-2种走法。由此我们得到二阶递推公式an=an-2+an-1。这是著名的斐波那契数列的递推公式，这里a1=2，a2=2。由特征根法我们知道通项公式。
练习3：（贴瓷砖问题）定义一个瓷砖为一个1×2的矩形，如下图。有多少种将瓷砖平铺在一起得到n×2的矩形的方法？
例6：（错位排列问题）现将n个编号分别为的小球放入编号为的n个盒子中，要求每个盒子只放1个小球，则球号与盒号都不相同的放法共有多少种？
解析：记球号与盒号都不相同的放法共有an种。显然，当n=1时，a1=0;当n=2时，a2=1;当n≥3时，如下我们分两类来考虑此问题：①1号球放入k（2≤k≤n）号盒子且k号球放入1号盒子时，由于k有n-1种变化，故共有（n-1）an-2种放法;②1号球放入k（2≤k≤n）号盒子且k号球不放入1号盒子时，此时问题归结为将2，3，...，n号球放入号盒子，且k号球不放入1号盒子，由于k有n-1种变化，故共有（n-1）an-1种放法。因此，我们得到二阶递推公式。利用递归迭代方法求出an，推导如下：
令，则有，整理得，对于n≥2，我们有
再累加得，所以。
上述给大家列举的几个递推问题，是高中数学教学中经常遇到的经典问题，集趣味性和思想性于一体，如果用计算机编程语言实现，则这些问题也就是计算机数据结构算法中的典型案例。如能合理的渗透到高中数学教学中，相信必能促进学生的数学学习的热情和思维的发展，提升学生的数学核心素养。
参考文献
[1]单墫、熊斌.多功能题典·高中数学竞赛华.东师范大学出版社，2008年
[2]PaulZeitz.怎样解题·数学竞赛攻关宝典.人民邮电出版社，2010年
[3]伽莫夫.从一到无穷大·科学中的事实和臆测.科学出版社，2013年