第六十八讲 递推方法 讲义-2026年高中数学竞赛

第六十八讲 递推方法 在组合计数问题中, 有时可以将需要计算的对象与较小的情形联系起来, 得到等式(或不等式)，称之为递推关系，由此解决问题。递推方法也是归纳思想的体现。本节中我们介绍利用递推方法解决一些计数问题。 例 1 从集合 中选取一个子集 ,使得 中不存在连续两个整数。问有多少种选取方法。 解 称不含连续两个整数的集合为 “好的”。设集合 的好子集个数为 。易知 。假设 是 的一个好子集。 若 ,则 是 的好子集,不含 的好子集 的个数为 。 若 ,则 ,从而 是 的好子集,并且任意这样形式的 均为 的好子集。因此含有 的好子集 的个数为 。 由此得到递推关系 。这正是斐波那契数列, 用特征方程可解得通项公式, 可知 评注 本题直接计算 中满足要求的子集个数是不容易的。将问题一般化后可以比较方便地得到递推关系, 再通过解线性递推数列得到通项公式。 例 2 16 个人围着圆桌坐成一圈，解散后重新坐下，这时每个人要么坐在原来位置,要么坐在相邻的位置。问:这样的坐法有多少种? 解 每个人有三个可能的位置, 我们分别称之为顺时针移动、逆时针移动和不动。 如果有连续两个人都顺时针(或逆时针)移动，则所有人都顺时针(或逆时针)移动。 除了上述两种旋转坐法，其他坐法一定是选取若干对相邻的人交换座位。对其中一个人 讨论。如果他坐在原位，剩下 15 个人可看成排成直线，选取其中若干对相邻的人交换，设这样的方法是 。一般直线上 个人选取若干对相邻的人交换的方法数记为 ,于是 。对 ,若第一个人不动,则有 种方法,若第一个人与第二个人交换,有 种方法,因此 ,即 是斐波那契数列。 因此 坐在原位坐法有 种。若 与顺时针的邻居互换位置,则有 种坐法,同样地,若 与逆时针的邻居互换位置,也有 种坐法。 因此所有不同的坐法数为 。 例 3 一种密码锁的密码设置是在正 边形 的每个顶点处赋值 0 和 1 两个数中的一个, 同时在每个顶点处涂染红、蓝两种颜色之一, 使得任意相邻的两个顶点的数字或颜色中至少有一个相同。问: 该种密码锁共有多少种不同的密码设置? 解 密码锁的每个顶点上是四种可能的状态之一。作一个正方形 ,四个顶点分别代表这四种状态, 表示 表示 表示 表示 。 这样一个密码锁的设置等价于在每个 上赋值四个字母 ,从 起绕正 边形一周回到 可以看作一只蚂蚁从正方形 中某个顶点 (即 上的赋值) 出发,在正方形顶点上移动,经过 步移动之后回到出发点。题目条件等价于蚂蚁的每一步移动可以移动到相邻顶点, 或者停留在原处。所求密码锁的设置数也等于蚂蚁的移动路径数。 在这样的理解下,从 中任何一个顶点出发经过 步移动后回到起点的移动方法数都相同。不妨考虑从 出发,设 步移动后回到 的路径数为 ,到达 的路径数为 ，到达 的路径数为 ，由对称性，到达 的路径数也是 。显然每一步移动都有 3 种可能, 由乘法原理可知 考虑经过 步移动回到 的移动路径数。对蚂蚁的第一步分类讨论。若第一步停留在 处,则后续 步从 到 ,有 种移动路径。若第一步移动到 ,则后续 步从 到 ,有 种移动路径。若第一步移动到 ,则后续 步从 到 ,也有 种移动路径。因此 类似方法,讨论经过 步移动到达 和到达 的移动路径数,有 由于 ,代入 的递推式得 。结合 ,解出 再代入 的递推式得 ,结合 ,解出 因此，密码锁的不同密码设置方法数为 。 例 4 证明卡塔兰数 具有如下的递推关系: 解 若卡塔兰序列 满足 ,对 成立,则称其为本原卡塔兰序列。显然若 是本原卡塔兰序列,则 -1，且 是 卡塔兰序列。反之，任取一个 卡塔兰序列， 在前后分别添上 1 和 -1 后便得到了 -本原卡塔兰序列,故 -本原卡塔兰序列的个数等于 。 对一个 -卡塔兰序列 ,取最小的正整数 ,满足 。显然 是偶数,设 ,则 是本原卡塔兰序列,并且 也是卡塔兰序列( 时，是空序列，认为是 0 -卡塔兰序列)。 对 分类计数,就有 例 5 给定正整数 ，有一个天平和 个质量分别为 的砝码。 现通过 步操作逐个将所有砝码放上天平,使得在操作过程中天平的右边总不重于天平的左边。每一步操作是从尚未放上天平的砝码中选取一个砝码,将它放到天平的左边或右边, 直到所有砝码都被放上天平。 试求整个操作过程的不同方法个数。 解 设将 个砝码放到天平上的方法数为 。显然 。考虑 个砝码的情形。不妨将每个砝码的质量乘以 个砝码质量分别为 ,不改变放置方法数。 注意到 ,因此任何时刻只需最重的那个砝码在天平的左边。考虑最轻的砝码放置的时刻,假设是第 步放置到天平上。 情形一: 。此时只能放置在左边。而剩下的 个砝码逐个放上去时，仍需保持任何时刻保证最重的那个砝码在左边,此时放置方法数为 。 情形二: 。此时质量为 的砝码可以放在任何一边,并且在整个放置过程中,删去这个砝码,是 这 个砝码符合条件的放置方法。故这一情形对每个 都恰有 种放置方法,因此总共 种放置方法。 综合两种情形可知, 。由 ,不难用归纳法证明 例 6 给定凸二十边形 ,用 的 17 条在内部不相交的对角线将 分割成 18 个三角形,所得图形称为 的一个三角剖分图。对 的任意一个三角剖分图 的 20 条边以及添加的 17 条对角线均称为 的边。 的任意 10 条两两无公共端点的边的集合称为 的一个完美匹配。当 取遍 的所有三角剖分图时,求 的完美匹配个数的最大值。 解 将二十边形换成 边形,考虑一般的问题。记 为 的完美匹配的个数。 设 ,这是斐波那契数列。我们证明,对凸 边形 的最大值等于 。从而原问题的答案为 。 对凸 边形 的一条对角线,若其两侧各有奇数个 的顶点,称其为奇弦,否则称为偶弦。我们注意到下述基本事实:对 的任意三角剖分图 的完美匹配不含奇弦。因为如果选取一条奇弦 ,则必然选取另一条 的边 ,其两个端点分别在 的两侧,由于 是凸多边形, 与 在 内部相交,这与 是三角剖分图矛盾。 下面对 归纳证明,若 是凸 边形的任意一个三角剖分图,则 。 时,凸四边形 的三角剖分图 没有偶弦,因此 的完美匹配只用 的边, 故 。 时,凸六边形 的三角剖分图 至多有一条偶弦。若 没有偶弦,同上可知 。若 含有偶弦,不妨设是 。选用 的完美匹配是唯一的,剩下两条边只能是 和 ,此时 。总之 。 结论在 时均成立。假设 ,且结论在小于 时均成立。考虑凸 边形 的一个三角剖分图 。若 没有偶弦,则同上可知 。 对于偶弦 ,记 两侧中 的顶点个数的较小值为 。若 含有偶弦,取其中一条偶弦 使 达到最小。设 ,不妨设 为 ,则由 的最小性以及三角剖分图的边在内部不相交可知每个 不能引出偶弦。 因为 的完美匹配不含奇弦,所以 只能与其相邻顶点配对。特别地, 只能与 或 配对。下面分两种情形讨论。 情形 1: 选用边 。此时必选用边 。在凸 边形 中 的边给出了一个三角剖分图 ,而 中含有边 , 的完美匹配,其余 条边恰是 的完美匹配,因此在这一情形中 的完美匹配个数为 。 情形 2: 选用边 。此时必选用边 。由于 ,以及 ,可知 。在凸 边形 中构造如下的三角剖分图 : 对 ,若线段 是 的边,则也将其作为 的边。由于这些边在内部互不相交,因此可再适当地添加一些 的对角线,得到一个 的三角剖分图 ,因此每个包含边 , 的 的完美匹配,其余的边必定是 的完美匹配。故此时 的完美匹配的个数不超过 。 由归纳假设, ,结合上面两种情形,有 下面说明等号可以成立。考虑凸 边形 的三角剖分图 : 添加对角线 重复前面的论证过程, 。对 ,考虑偶弦 ,情形 1,选用边 ,则在凸 边形 中 的边恰构成三角剖分图 ,因此此时有 个完美匹配。情形 2,选用边 。在凸 边形 中 的边恰构成三角剖分图 ,故此时有 个 的完美匹配。从而对 有 由数学归纳法即得 。结论得证。 学科网（北京）股份有限公司 $