第 15 讲 建立常用模型处理计数问题
1. 卡特兰数
(1) 通项公式: Cn= C2n
n
n+1
(n∈N ) .
(2) 递推关系式:
①
Cn=C0Cn−1+C2Cn−2+⋯+Cn−1C0(n≥2)
; ②
Cn= 4 n−2
n+1 Cn−1(n≥1) .
(3) C0=1,C1=1,C2=2,C3=5,C4=14 ,C5= 42,⋯ .
2. 容斥原理
(1) card ( A ∪B)=card ( A)+card (B)−card ( A ∩B) ;
(2) card
( A ∪B∪C)=card ( A)+card (B)+card (C)−card ( A ∩B)−card ( A ∩C)−card (B∩C)+card ( A ∩B∩C
.
热点课堂
【例 1】在一个凸 n+2(n≥1) 边形中,通过若干条互不相交的对角线,把这
个多边形划分成了若干个三角形,则不同划分的方案数为_____.
【分析】本题可通过两种思路进行分析.
解法一: 设方案数为 f (n+2) , 令该凸 n+2 边形的顶点分别为
P1, P2,⋯, Pk ,⋯, Pn+2 ,其中 2≤k ≤n+1 ,
如图 1,由对角线 P1 Pk 和对角线 Pn+2 Pk 把凸 n+2 边形分成三个部分,分
别是由 P1, P2,⋯, Pk 构成的 k 边形, △P1 Pk Pn+2 和由 Pk , Pk +1,⋯ , Pn+2 构
成的 n−k +3 边形,
图 1
根据分步乘法原理, f (n+2) 的问题就等价于凸 k 边形的划分方案数 f (k )
乘以凸 n−k +3 边形的划分方案数 f (n−k +3) ,即 f (k )×f (n−k +3) ,而 k 可
以取 2,3,4 ,⋯,n+1 ,
所
以
再
根
据
分
类
加
法
原
理
,
得
f (n+2)= f (2)f (n+1)+ f (3)f (n)+⋯+ f (n+1)f (2) ,
根据卡特兰数的递推式可知 f (n+2)=Cn ,再结合通项可得结果为 C2n
n
n+1
.
解法二: 如图 2,在凸 n+2 边形中,把边 Pi−1 Pi 设为 ai−1 ,其中 2≤i≤n+2 ,
图 2
则得到除了边 P1 Pn+2 以外的其余各边分别为 a1,a2,a3,⋯,an+1 ,
再把相邻两边的字母加上小括号来表示这两边构成的三角形的第三边. 如
(a1a2) 表示由边 a1 与 a2 构成的三角形的第三边, ((a1a2)a3) 表示由 (a1a2) 与
a3 构成的三角形的第三边.
这样 f (n+2) 的值与 “给 a1a2a3⋯an+1 添加 n 对小括号的方案数”相
等. 再把左括号用数字 1 表示, 右括号用数字 -1 表示,
由于每个右括号前必有一个左括号,所以把问题转化成卡特兰数的另一经典
形式:
由 n 个 1 与 n 个 -1 构成 2n 项的数列 a1,a2,a3,⋯,an+1 ,其部分和满
足 a1+a2+a3+⋯+ak ≥0(k =1,2,3,⋯,2n) ,则此序列的个数等于第 n 个卡特兰
数 Cn= C2n
n
n+1
.
【解答】 C2n
n
n+1
(n≥1)
评注:本题是卡特兰数产生的背景之一, 也是现今卡特兰数应用的一个典例.
本题的解法一是从卡特兰数的递推式入手，而解法二则通过对应转换后变成经
典题型，该经典题型的证明可通过通项公式实现，而这一系列的对应转化过程
正好涉及了卡特兰数的常见应用“格子路径问题”、“出入栈问题”、“括号
正确匹配问题”. 因此，掌握了这两种思路，基本上就清楚了卡特兰数的应用.
在 2016 年的清华大学自主招生暨领军计划试题和高考全国卷中都有此应用.
【例 2】将 6 个数2,0,1,9,20,19 按任意次序排成一行,拼成一个八位数 (首
位不为 0)，则产生的不同的八位数的个数为_____.
【分析】本题关键是解决 “ 1,9 ”与 19 ；“ 2,0 ”与 20 的重复问题，故
可用容斥原理进行求解.
将2,0,1,9,20,19 的首位不为 0 的排列的全体记为 A ,可得 |A)=5×5!=600
(这里及以下， |X ) 表示有限集 X 的元素个数)，
将 A 中由 1 和 9 组成“19”的排列的全体记为 B ;
将 A 中由 2 和 0 组成“20”的排列的全体记为 C ,
则 |B)= 4×4!
2
= 48,|C)= 5!
2 =60,|B∩C)=C4
2 =6 ,
因
此
满
足
条
件
的
八
位
数
的
个
数
为
|A)−|B)−|C)+|B∩C)=600−48−60+6= 498 .
【解答】 498
【例 3】从正 15 边形的顶点中选出 3 个点构成钝角三角形,则不同的钝
角三角形有( )
A.1105 个 B. 225 个 C. 315 个 D. 420 个
【分析】先考虑顶点的位置,可考虑钝角三角形的个数,也可考虑锐角三角形
的个数,
解法一: 设正 15 边形的顶点为 Ai (其中 i=1,2,3,⋯,15 ),
先从 15 个顶点中任选一个点 (以 A15 为例),那么以该点为顶点的三角形
共有 C14
2 =91 个, 接下来考虑这些三角形中锐角三角形的个数,
易知三角形内部包含正 15 边形的中心时为锐角三角形,
因此锐角三角形的另外两个顶点必然分别在 A1, A2,⋯, A7 以及
A8, A9,⋯, A14 中,
当其中一个顶点为 A1, A2,⋯, A7 时,另一顶点的可能位置分别有 1,2,⋯,7
个,
共 1+2+3+ 4 +5+6+7 =28 个,
这样可得所有的钝角三角形有 1
3 ×(91−28)×15=315 个.
解法二: 规定以逆时针方向为正方向,若某个三角形在正方向意义下的“起
点”为 A1 ,则 “该三角形为钝角三角形”的充要条件是“其余两个顶点选自
于 A2, A3,⋯, A8 这 7 个点”,
故以 A1 为“起点”的钝角三角形共有 C7
2=21 个,
因此所有的钝角三角形有 21×15=315 个.
解法三: 设 △ABC 是以 A 为钝角顶点的三角形,
作正 15 边形的外接圆,则 BAC
⏜
中顶点数小于等于 8 个,
则两侧顶点数之和小于等于 7,共有 1+2+⋯+6=21 种情况,
所以钝角三角形有 21×15=315 个.
【解答】C
评注: 一般地,对于正 2k +1 边形,钝角三角形有 1
2 k (k −1)(2k +1) 个.
【例 4】设 S ={1,2,3,4 ,5} ,求满足 f (f (x))= x 的映射 f :S→S 的个数.
【分析】两次映射后对应自身,可以考虑两种情形,一种是 f (x)= x ,一种是
f (a)=b,f (b)=a .
【解答】① 当全都满足 f (x)= x 时,这样的映射有 1 个;
②当有一组满足 f (a)=b,f (b)=a ，其余 3 个满足 f (x)= x ，这样的映射
有 C5
2=10 个；
③当有两组满足 f (a)=b,f (b)=a ，另外 1 个满足 f (x)= x ，这样的映射
有 C5
2C3
2
A2
2 =15 个； 综上符合条件的映射个数为 1+10+15=26 .
【
例
5
】
已
知
组
合
数
Cn
k =
n!
k !(n−k )!
,
则
C2018
0
+3C2018
1
+5C2018
2
+⋯+ 4037C2018
2018= ( )
A.1106 ×2
2018 B. 2018 !
C. 2019×2
2018 D. 以上选项都不对
【分析】处理 Cn
1+2Cn
2+3Cn
3+⋯+nCn
n 的计算问题常用公式 k Cn
k =nCn−1
k −1 .
因为 C2018
0
+C2018
1
+C2018
2
+⋯+C2018
2018=2
2018 ,
所
以
C2018
0
+3C2018
1
+5C2018
2
+⋯+ 4037C2018
2018=2
2018+2C2018
1
+ 4C2018
2
+⋯+ 4036C2018
2018=2
2018+2(C2018
1
+2C2018
2
+⋯
又因为 k Cn
k =nCn−1
k −1 ,
所
以
2(C2018
1
+2C2018
2
+⋯+2018C2018
2018)=2(2018C2017
0
+2018C2017
1
+⋯+2018C2017
2017)=2018×2
2018
,
因此,原式 =2
2018+2018×2
2018=2019×2
2018 .
【解答】C
【例 6 】设整数数列 a1,a2,⋯,a10 满足 a10=3a1,a2+a8=2a5 , 且
ai+1∈{1+ai,2+) ai),i=1,2,⋯,9 ，则这样的数列的个数为_____.
【分析】由条件 ai+1∈{1+ai,2+ai) 可知 ai+1−ai=1 或 ai+1−ai=2 ,若由
此考虑构造新数列, 则得到解法一, 若由此联系到 “走阶梯” 的模型, 则得到
解法二, 而这两种解法本质上是对同一思路的两种不同的表达.
解法一: 设 bi=ai+1−ai∈{1,2}(i=1,2,⋯,9) ,
则有 2a1=a10−a1=b1+b2+⋯+b9 ①,
b2+b3+b4=a5−a2=a8−a5=b5+b6+b7
.
②
用 t 表示 b2,b3,b4 中值为 2 的项数.
由②知, t 也是 b5,b6,b7 中值为 2 的项数,其中 t ∈{0,1,2,3} .
因此 b2,b3,⋯,b7 的取法数为 (C3
0)
2+(C3
1)
2+(C3
2)
2+(C3
3)
2=20 ,
取定 b2,b3,⋯,b7 后,任意指定 b8,b9 的值,有 2
2= 4 种方式.
最后由①知，应取 b1∈{1,2} 使得 b1+b2+⋯+b9 为偶数，
这样的 b1 的取法是唯一的,并且确定了整数 a1 的值,
进而数列 b1,b2,⋯,b9 唯一对应一个满足条件的数列 a1,a2,⋯,a10 ,
综上可知,满足条件的数列的个数为 20×4 =80 .
解法二:原问题等价于 “用 9 步从第 a1 级阶梯上到第 a10 级阶梯,每步可
以上 1 级或 2 级, 且从 a2 到 a5 的级数与从 a5 到 a8 的级数相同,共有几种
不同的走法?”
由 1≤3a1−a1
9
≤2 ,得 a1∈{5,6,7,8,9} ,
①当 a1=5 时，从第 5 级到第 15 级，需要 8 步上 1 级，1 步上 2
级，则 a2 到 a5 及 a5 到 a8 每步上 1 级，所以共有 C3
1=3 种；
②当 a1=6 时，从第 6 级到第 18 级，需要 6 步上 1 级，3 步上 2
级，
若 a2 到 a5 每步上 1 级,则有 C3
3=1 种,
若 a2 到 a5 需 2 步上 1 级，1 步上 2 级，则共有 C3
1C3
1C3
1=27 种，
所以此情况下共有 1+27 =28 种;
③当 a1=7 时，从第 7 级到第 21 级，需要 4 步上 1 级，5 步上 2
级，
若 a2 到 a5 需 1 步上 1 级,2 步上 2 级,则有 C3
2C3
2C3
1=27 种,
若 a2 到 a5 需 2 步上 1 级,1 步上 2 级,则有 C3
1C3
1C3
3=9 种,
所以此情况下共有 27+9=36 种;
④当 a1=8 时，从第 8 级到第 24 级，需要 2 步上 1 级，7 步上 2
级，
若 a2 到 a5 需 1 步上 1 级，2 步上 2 级，则有 C3
2C3
2=9 种，
若 a2 到 a5 每步上 2 级,则有 C3
1=3 种,
所以此情况共有 9+3=12 种;
⑤当 a1=9 时，每步上 2 级，共有 1 种；
因此，共有 3+28+36+12+1=80 种.
【解答】80
