第 15 讲 建立常用模型处理计数问题讲义-2025-2026学年高二下学期数学人教A版选择性必修第三册

第 15 讲 建立常用模型处理计数问题 1. 卡特兰数 (1) 通项公式: . (2) 递推关系式:① ; ② . (3) . 2. 容斥原理 (1) ; (2) card . 热点课堂 【例 1】在一个凸 边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形,则不同划分的方案数为_____. 【分析】本题可通过两种思路进行分析. 解法一: 设方案数为 ,令该凸 边形的顶点分别为 ,其中 , 如图 1,由对角线 和对角线 把凸 边形分成三个部分,分别是由 构成的 边形, 和由 , 构成的 边形, 图 1 根据分步乘法原理, 的问题就等价于凸 边形的划分方案数 乘以凸 边形的划分方案数 ,即 ,而 可以取 , 所以再根据分类加法原理,得 , 根据卡特兰数的递推式可知 ,再结合通项可得结果为 . 解法二: 如图 2,在凸 边形中,把边 设为 ,其中 , 图 2 则得到除了边 以外的其余各边分别为 , 再把相邻两边的字母加上小括号来表示这两边构成的三角形的第三边. 如 表示由边 与 构成的三角形的第三边, 表示由 与 构成的三角形的第三边. 这样 的值与 “给 添加 对小括号的方案数”相等. 再把左括号用数字 1 表示, 右括号用数字 -1 表示, 由于每个右括号前必有一个左括号,所以把问题转化成卡特兰数的另一经典形式: 由 个 1 与 个 -1 构成 项的数列 ,其部分和满足 ,则此序列的个数等于第 个卡特兰数 . 【解答】 评注:本题是卡特兰数产生的背景之一, 也是现今卡特兰数应用的一个典例. 本题的解法一是从卡特兰数的递推式入手，而解法二则通过对应转换后变成经典题型，该经典题型的证明可通过通项公式实现，而这一系列的对应转化过程正好涉及了卡特兰数的常见应用“格子路径问题”、“出入栈问题”、“括号正确匹配问题”. 因此，掌握了这两种思路，基本上就清楚了卡特兰数的应用. 在 2016 年的清华大学自主招生暨领军计划试题和高考全国卷中都有此应用. 【例 2】将 6 个数2,0,1,9,20,19按任意次序排成一行,拼成一个八位数 (首位不为 0)，则产生的不同的八位数的个数为_____. 【分析】本题关键是解决 “ 1,9 ”与 19 ；“ 2,0 ”与 20 的重复问题，故可用容斥原理进行求解. 将2,0,1,9,20,19的首位不为 0 的排列的全体记为 ,可得 (这里及以下， 表示有限集 的元素个数)， 将 中由 1 和 9 组成“19”的排列的全体记为 ; 将 中由 2 和 0 组成“20”的排列的全体记为 , 则 , 因此满足条件的八位数的个数为 . 【解答】 498 【例 3】从正 15 边形的顶点中选出 3 个点构成钝角三角形,则不同的钝角三角形有( ) A.10105 个 B. 225 个 C. 315 个 D. 420 个 【分析】先考虑顶点的位置,可考虑钝角三角形的个数,也可考虑锐角三角形的个数, 解法一: 设正 15 边形的顶点为 (其中 ), 先从 15 个顶点中任选一个点 (以 为例),那么以该点为顶点的三角形共有 个, 接下来考虑这些三角形中锐角三角形的个数, 易知三角形内部包含正 15 边形的中心时为锐角三角形, 因此锐角三角形的另外两个顶点必然分别在 以及 中, 当其中一个顶点为 时,另一顶点的可能位置分别有 个, 共 个, 这样可得所有的钝角三角形有 个. 解法二: 规定以逆时针方向为正方向,若某个三角形在正方向意义下的“起点”为 ,则 “该三角形为钝角三角形”的充要条件是“其余两个顶点选自于 这 7 个点”, 故以 为“起点”的钝角三角形共有 个, 因此所有的钝角三角形有 个. 解法三: 设 是以 为钝角顶点的三角形, 作正 15 边形的外接圆,则 中顶点数小于等于 8 个, 则两侧顶点数之和小于等于 7,共有 种情况, 所以钝角三角形有 个. 【解答】C 评注: 一般地,对于正 边形,钝角三角形有 个. 【例 4】设 ,求满足 的映射 的个数. 【分析】两次映射后对应自身,可以考虑两种情形,一种是 ,一种是 . 【解答】① 当全都满足 时,这样的映射有 1 个; 2 当有一组满足 ，其余 3 个满足 ，这样的映射有 个； 3 当有两组满足 ，另外 1 个满足 ，这样的映射有 个； 综上符合条件的映射个数为 . 【例 5】已知组合数 ,则 ( ) A.10106 B. 2018 ! C. D. 以上选项都不对 【分析】处理 的计算问题常用公式 . 因为 , 所以 又因为 , 所以 , 因此,原式 . 【解答】C 【例 6】设整数数列 满足 ,且 ，则这样的数列的个数为_____. 【分析】由条件 可知 或 ,若由此考虑构造新数列, 则得到解法一, 若由此联系到 “走阶梯” 的模型, 则得到解法二, 而这两种解法本质上是对同一思路的两种不同的表达. 解法一: 设 , 则有 ①, ②. 用 表示 中值为 2 的项数. 由②知, 也是 中值为 2 的项数,其中 . 因此 的取法数为 , 取定 后,任意指定 的值,有 种方式. 最后由①知，应取 使得 为偶数， 这样的 的取法是唯一的,并且确定了整数 的值, 进而数列 唯一对应一个满足条件的数列 , 综上可知,满足条件的数列的个数为 . 解法二:原问题等价于 “用 9 步从第 级阶梯上到第 级阶梯,每步可以上 1 级或 2 级, 且从 到 的级数与从 到 的级数相同,共有几种不同的走法?” 由 ,得 , 1 当 时，从第 5 级到第 15 级，需要 8 步上 1 级，1 步上 2 级，则 到 及 到 每步上 1 级，所以共有 种； 2 当 时，从第 6 级到第 18 级，需要 6 步上 1 级，3 步上 2 级， 若 到 每步上 1 级,则有 种, 若 到 需 2 步上 1 级，1 步上 2 级，则共有 种， 所以此情况下共有 种; 3 当 时，从第 7 级到第 21 级，需要 4 步上 1 级，5 步上 2 级， 若 到 需 1 步上 1 级,2 步上 2 级,则有 种, 若 到 需 2 步上 1 级,1 步上 2 级,则有 种, 所以此情况下共有 种; 4 当 时，从第 8 级到第 24 级，需要 2 步上 1 级，7 步上 2 级， 若 到 需 1 步上 1 级，2 步上 2 级，则有 种， 若 到 每步上 2 级,则有 种, 所以此情况共有 种; 5 当 时，每步上 2 级，共有 1 种； 因此，共有 种. 【解答】80 学科网（北京）股份有限公司 $