1.递推思想在排列组合中的应用-《中学生数理化》高二数学2024年3月刊

递推思想在排列组合中的应用 ■河北南宫中学 韩文娟 霍忠林 利用递推思想求解排列组合问题是一种 解题思路,但对同学们的数学素养要求较高, 是排列组合中的难点。如何借助分类加法计 数原理和分步乘法计数原理找到递推关系这 是解题的关键点,下面通过六种题型来分析 递推思想在排列组合中的应用。 题型一、爬楼梯问题 例 1 一段楼梯,有10个台阶,小明每 次走一个或两个台阶,则他有多少种不同的 走法? 解析:问题一般化:一段楼梯,有n 个台 阶,小明每次走一个或两个台阶,则他有多少 种不同的走法? 设小明走n个台阶有an 种走法,则a1= 1,a2=2。 思路一 按第一步走的台阶数分类 若第一步走一个台阶,则余下的n-1个 台阶共有an-1 种走法。 若第一步走两个台阶,则余下的n-2个 台阶共有an-2 种走法。 所以an=an-1+an-2(n≥3)。 当n=10时,易得a10=89。 思路二 按最后一步走的台阶数分类 若最后一步走一个台阶,则前n-1个台 阶共有an-1 种走法。 若最后一步走两个台阶,则前n-2个台 阶共有an-2 种走法。 所以an=an-1+an-2(n≥3)。 当n=10时,易得a10=89。 评析:“爬楼梯问题”本质上就是“斐波那 契数列”,该数列是普通高中教材人教 A版 《数学选择性必修第二册》第11页、第12页的 内容。采用类似方法还可以处理下面变式。 变式1:一段楼梯,有5个台阶,小明每次 走一个或两个或三个台阶,则他有多少种不 同的走法? 解析:该 问 题 等 价 于:已 知 数 列 an = an-1+an-2+an-3(n≥4),其中a1=1,a2=2, a3=4,求a5 的值。过程略。 题型二、平面划分问题 例 2 3条直线最多能将平面分成几 部分? 4条直线最多能将平面分成几部分呢? 解析:问题一般化:n条直线最多能将平面 分成几部分? 设n条直线最多将平面分成an 部分,则 前n-1条直线最多将平面分成an-1 部分。 要使第n条直线将平面分成的部分最多,则 第n条直线必须与前n-1条直线均相交,此 时共有n-1个交点,增加n 部分,从而有 an=an-1+n(n≥2),其中a1=2。容易得到 a3=7,a4=11,即为本题所求的答案。 评 析:平 面 划 分 问 题 是 典 型 的 an = an-1+f(n)型递推公式的应用,通过累加法 可以得到an= n2+n+2 2 。 题型三、错排问题 例 3 甲、乙、丙、丁、戊5个人排成一 排,重新站队,各人都不站在原来的位置,共 有多少种不同的站队方式? 解析:问题一般化:n 个人排成一排,重 新站队,各人都不站在原来的位置,共有多少 种不同的站队方式? 设n个人排成一排,重新站队,各人都不 站在原来的位置共有an 种方法。 第一步,第一个人不站在原来的位置共 有n-1种方法。 第二步,不妨设第一个人站在第二个人 的原来位置,则第二个人的站法又可以分为 两类: 第一类是第二个人站在第一个人原来的 位置,此时余下的n-2人共有an-2 种站法; 第二类是第二个人不站在第一个人原来 的位置,此时第三个人不站在第三个人原来 的位置,第四个人不站在第四个人原来的位 置,……,第n个人不站在第n个人原来的位 置,所以有an-1 种站法。 由分类加法计数原理和分步乘法计数原 理得an=(n-1)·(an-1+an-2)(n≥3),其 3 知识篇 新高考名师护航 高二数学 2024年3月 中a1=0,a2=1。 容易得到a5=44,即为本题所求的答案。 评析:错排问题的本质是先把n个不同元 素排成一排,再重新排列,所有元素各有一个 指定位置不能站,且不同元素不能站的指定位 置也不同。上述解题过程中第二步的第二类: 从第二个人到第n个人,每个人均有一个指定 位置不能站,且不同的人不能站的指定位置也 不同,因此是n-1个人的错排问题。比如例3 与下面变式本质是一样的。 变式2:甲、乙、丙、丁、戊排成一排,重新 站队时,甲不能站原来乙的位置,乙不能站原 来丙的位置,丙不能站原来丁的位置,丁不能 站原来戊的位置,戊不能站原来甲的位置,则 不同的站队方式有多少种? (答案略。) 题型四、传球问题 例 4 甲、乙、丙三人传球,由甲开始发 球,并作为第一次传球,经过5次传球后,球 仍回到甲手中,则不同的传球方式有多少种? 解析:问题一般化:甲、乙、丙三人传球, 由甲开始发球,并作为第一次传球,经过n次 传球后,球仍回到甲手中,则不同的传球方式 有多少种? 设n次传球后,球仍回到甲手中有an 种 方法,要使第n 次传球后,球在甲手中,则第 n-1次传球后球一定在乙或丙手中,而n-1 次传球一共有2n-1 种方法,所以第n