第二十八讲 递推方法在组合中的应用讲义-2026年高中数学竞赛

第二十八讲 递推方法在组合中的应用 通过建立递归关系解决问题的方法称之为递推方法。递推方法是探索数学规律和解题思路的重要方法之一, 它对几乎所有的数学分支都有着重要作用。随着计算机的广泛应用，这种方法越来越受到重视。递推关系是从很多计数问题中产生的，它也是递推方法的数学描述。利用递推关系计数的一般步骤是: (1) 用 表示与 有关的欲计数的个数； (2) 计算一些初始值 等; (3) 建立 与 之间的递推关系； (4) 求解递推关系。 例 1 在银行的某个窗口前有 12 个人在排队，当该窗口因故关闭时，这 12 个人都要到另一个窗口重新排队。要使得这 12 个人中每个人的位置与原来所排的次序相差都不超过 1 , 问有多少种不同的排队方法? 解 用 表示有 个人排队时,满足条件的排队方法数。 易知 。 当 时,考虑第 个人重新排队后的位置,共有两种可能: 若第 个人仍排在第 个位置,则前 人的排队方式数恰好为 ; 若第 个人排在第 个位置,则第 人必排在第 个位置,而前 人的排队方式数恰好为 。因此 。 于是, 依次可得 故共有 233 种不同的排队方法。 例 2 设 。求 的满足下列性质的排列 , 的个数: 仅存在一个 ,使得 。 解 用 表示具有题设性质的排列的个数。易知, 。 对于 ,若 ,则这样的排列个数有 个; 若 ,考虑所有这样的排列,可以从 个数 中选 个数按从小到大的顺序排列成 ,其余的按从小到大的顺序排列在剩下的位置,于是有 种排法,所以 。即 .......................... 把上面这些式子相加,得 。 注 在解决一些计数问题时, 往往题目并不给出明显表达式, 需通过观察、分析、 归纳、猜想、论证等来确定递推关系。本题中,将 分类计数,一类与 个数的情形相联系，另一类可直接计数，从而得到了递推关系。 例 3 对一个边长互不相等的凸 边形的边染色,每条边可以染红、黄、 蓝三种颜色中的一种，但是不允许相邻的边有相同的颜色。问:共有多少种不同的染色方法? 例 3 图 解 设不同的染色法有 种。易知 。 当 时,首先,对于边 ,有 3 种不同的染法,由于边 的颜色与边 的颜色不同，所以，对边 有 2 种不同的染法,类似地,对边 边 均有 2 种染法。对于边 ，用与边 不同的 2 种颜色染色，但是，这样也包括了它与边 颜色相同的情况，而边 与边 颜色相同的不同染色方法数就是凸 边形的不同染色方法数的种数 ,于是可得 。 于是 综上所述，不同的染色方法数为 。 例 4 若 是有理数,证明: 对一切正整数 也是有理数。 证明 令 ,则 是有理数, 是有理数,且 是有理数。 由上面的递推关系及 是有理数知,对所有的正整数 都是有理数,从而命题得证。 例 5 设 为方程 的三个根。 证明: 对任意正整数 为整数。 证明 我们证明对任意非负整数 是整数。 由条件知 。 因为 为方程 的三个根,所以 于是 因为 ,比较二次项系数知 ,故 而 ,所以根据 的递推公式可知,对任意正整数 为整数。 注 递推方法除了应用于组合计数, 亦可用于一些别的场合。在本题中, 从 的通项结构容易发现, 应是一个常系数三阶线性递推数列,因此只要初值 、 为整数，便可通过建立递推关系，归纳地推出各项均为整数。 例 6 在 的一个排列 中，如果 , ,则称这种排列为一个错位排列 (也称更列)。求错位排列的个数 。 解 易知 。 对于 及 的任意一个错位排列 中, 可取除 1 以外的任一其他 个数,设 ,于是: 如果 ,这种错位排列数等于 个元素的错位排列数 ; 如果 ,则这种错位排列就是元素 在第 2 到第 这 个位置上的一个排列,其中 1 不在第 个位置,其他元素都不在它自身所标记的位置上，这种排列相当于 这 个元素的一个错位排列，所以共有 个。 考虑到 共 种这样的情况,我们得到 ① 令 ,则 ① 可变形为 ,所以 ② 反复利用②，并注意到 ， ，对 ，有 由此可得 ,所以 注 这是著名的“错位排列”计数问题的一种递推解法。在建立递推关系时,对应原理是必不可少的,但有时候需要变通地找出对应关系,例如在上述解法讨论 , 的情况时,把元素 1 暂时视作 ,即对应到 这 个元素的一个错位排列。 例 7 在 方格表的 个方格中,每格用黑、白两色之一染色。若要求任何两个有公共边的方格不都染黑色，求不同的染色方案的数目。 解 用递推方法。设满足条件的染色方案共有 种,其中在第 列中均染白色的染色方案共 种,因而第 列染不同色的染色方案数为 。 当 时,方格表的前 列一定是 方格表的一种满足要求的染色方案。 当第 列均染白色时,第 列(从上到下，下同)对应有“白白”“黑白”“白黑”3 种染色方法; 当第 列染不同色时,不妨设为 “黑白”,则第 列对应有 “白白” “白黑”2 种染色方法。因此可建立递推关系: 另一方面, 方格表的每一种染色方案与 方格表每一种第 列染 “白白” 的染色方案一一对应,故 。 因此 时,有 ,又验证知 ,故解得 注 1 递推关系具有形式多样性。比较多的问题中所利用的是单递推关系, 但也有一些是利用多元递推关系。本题中 的递推关系并不明显,因而将染色方案分为 “第 列中均染白色”与“第 列染不同色”两种类型,引入辅助量 参与递推关系的建立,最后消去 ,即得到 的递推关系。 注 2 与之等价的问题有: 设数列 每项均为 0 或 1,且满足 。 对给定正整数 ，求 个数 的不同的取值方法总数。 例 8 一种密码锁的密码设置是在正 边形 的每个顶点处赋值 0 和 1 两个数中的一个, 同时在每个顶点处涂染红、蓝两种颜色之一, 使得任意相邻的两个顶点的数字或颜色中至少有一个相同。问:该种密码锁共有多少种不同的密码设置? 解 设满足条件的密码设置方案共 种,其中点 赋值与染色全同的方案有 种,其全体构成集合 ; 点 赋值与染色恰有一项相同的方案有 种,其全体构成集合 ,则 此外,若不考虑相邻两点 间的赋值与染色是否兼容,首先设置 位置, 有 4 种方式,再依次设置 ,各有 3 种方式,根据乘法原理,共 种方式,因此,若将点 赋值与染色完全不同,但其余任意两个相邻顶点赋值与染色至少有一项相同的设置方式数记为 ,则 对每种密码设置方案,考虑顶点 的赋值与染色情况。 (I)若赋值与染色情况全同，这样的情况数为 ，每种情况恰可对应 中的一个元素及 中的两个元素(例如，若 、 均为“0 红”，则 可为“0 红”“0 蓝”或 “1 红”，前者对应 中的方案，后两者对应 中的方案)。 (II)若赋值与染色恰有一项相同,这样的情况数为 ,每种情况恰可对应 中的一个元素及 中的一个元素 (例如,若 为“ 0 红”, 为“ 1 红”,则 可为“ 0 红”“1 红”，前者对应 中的方案，后者对应 中的方案)。 (III) 若赋值与染色均不同,这样的情况数为 ,每种情况恰可对应 中两个元素(例如，若 为“ 0 红”， 为“ 1 蓝”，则 可为“ 0 蓝”“ 1 红”)。 由此, 可建立递推关系 由(1)和(3)知 ，结合(2)与(4)可整理得 ,又枚举得 ,所以 注 本题为 2010 年全国高中数学联赛加试最后一题, 标准解法是直接计数, 其中涉及到组合式的化简。上述解法为递推法, 虽不算很简洁, 但体现了递推法的思维特点: 为了计算 ,可根据解题的实际需要引入一系列辅助量 ,通过计数原理清楚地列出它们之间的等量关系 (如果是 个辅助量,等量关系通常应列出 个), 最后消去辅助量便可得到 的递推关系。 学科网（北京）股份有限公司 $