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

第二十八讲 递推方法在组合中的应用

通过建立递归关系解决问题的方法称之为递推方法。递推方法是探索数学规律和解题思路的重要方法之一, 它对几乎所有的数学分支都有着重要作用。随着计算机的广泛应用，这种方法越来越受到重视。递推关系是从很多计数问题中产生的，它也是递推方法的数学描述。利用递推关系计数的一般步骤是:

(1)  用 表示与 有关的欲计数的个数；

(2)  计算一些初始值 等;

(3)  建立 与 之间的递推关系；

(4)  求解递推关系。

例 1 在银行的某个窗口前有 12 个人在排队，当该窗口因故关闭时，这 12 个人都要到另一个窗口重新排队。要使得这 12 个人中每个人的位置与原来所排的次序相差都不超过 1 , 问有多少种不同的排队方法?

解 用 表示有 个人排队时,满足条件的排队方法数。

易知 。

当 时,考虑第 个人重新排队后的位置,共有两种可能:

若第 个人仍排在第 个位置,则前 人的排队方式数恰好为 ;

若第 个人排在第 个位置,则第 人必排在第 个位置,而前 人的排队方式数恰好为 。因此 。

于是, 依次可得

故共有 233 种不同的排队方法。

例 2 设 。求 的满足下列性质的排列 , 的个数: 仅存在一个 ,使得 。

解 用 表示具有题设性质的排列的个数。易知, 。

对于 ,若 ,则这样的排列个数有 个;

若 ,考虑所有这样的排列,可以从 个数 中选 个数按从小到大的顺序排列成 ,其余的按从小到大的顺序排列在剩下的位置,于是有 种排法,所以 。即

..........................

把上面这些式子相加,得 。

注 在解决一些计数问题时, 往往题目并不给出明显表达式, 需通过观察、分析、 归纳、猜想、论证等来确定递推关系。本题中,将 分类计数,一类与 个数的情形相联系，另一类可直接计数，从而得到了递推关系。

例 3 对一个边长互不相等的凸 边形的边染色,每条边可以染红、黄、 蓝三种颜色中的一种，但是不允许相邻的边有相同的颜色。问:共有多少种不同的染色方法?

                      

例 3 图

解 设不同的染色法有 种。易知 。

当 时,首先,对于边 ,有 3 种不同的染法,由于边 的颜色与边 的颜色不同，所以，对边 有 2 种不同的染法,类似地,对边 边 均有 2 种染法。对于边 ，用与边 不同的 2 种颜色染色，但是，这样也包括了它与边 颜色相同的情况，而边 与边 颜色相同的不同染色方法数就是凸 边形的不同染色方法数的种数 ,于是可得 。

于是

综上所述，不同的染色方法数为 。

例 4 若 是有理数,证明: 对一切正整数 也是有理数。

证明 令 ,则 是有理数, 是有理数,且 是有理数。

由上面的递推关系及 是有理数知,对所有的正整数 都是有理数,从而命题得证。

例 5 设 为方程 的三个根。

证明: 对任意正整数 为整数。

证明 我们证明对任意非负整数 是整数。

由条件知 。