离散数学计数知识点总结（含试卷题目详解）

前言

离散数学中的计数问题是组合数学的核心内容，也是各类考试的高频考点。本文整理了计数相关的核心公式、解题方法，并结合典型题目（含试卷真题）进行详细推导，帮助大家快速掌握并灵活运用。

---

一、速查表

模型	公式	条件/备注
可重组合（盒可空）	C(n+r-1,r)=C(n+r-1,n-1)	r 个相同球入 n 个不同盒，x₁+…+xₙ=r, xᵢ≥0
可重组合（盒不可空）	C(r-1,n-1)	每盒至少 1 个，需 r≥n
非降路径	C(m+n,m) 或 C(m+n,n)	从 (0,0) 到 (m,n) 只能向右、向上
全排列	n!	n 个不同元素排成一列
捆绑法	将相邻元素看作一个整体参与排列	注意整体内部是否需排列
插空法	先排无限制元素，再将不相邻元素插入空隙	常用于”不相邻/间隔”问题
无序等分分组	(2n)!/(2ⁿ·n!)	2n 人分 n 组，每组 2 人，组无编号
组有编号	(2n)!/2ⁿ	不除 n!
错位排列	D(n)=n!·Σ_{k=0}^{n}(-1)^k/k!	递推：D(n)=(n-1)(D(n-1)+D(n-2))
帕斯卡公式	C(n,r)=C(n-1,r-1)+C(n-1,r)	1≤r≤n-1
欧拉函数	φ(n)=n·Π(1-1/p)	p 取 n 的所有不同质因子
容斥原理	\|A∪B\|=\|A\|+\|B\|-\|A∩B\|	补集：\|S-(A∪B)\|=\|S\|-\|A∪B\|
棋盘多项式	R(C)=xR(Cᵢ)+R(Cₗ)	Cᵢ 删所在行列，Cₗ 仅删该格
常系数线性齐次递推	特征方程法（见第6节）	形如 aₙ=c₁aₙ₋₁+…+cₖaₙ₋ₖ，求通解后代入初值
常系数线性非齐次递推	齐次通解 + 非齐次特解	例：h(n)=2h(n-1)+1
不相邻贴纸	f(n)=f(n-1)+f(n-2)	f(1)=2, f(2)=3, f(n)=Fₙ₊₂

---

二、解释与说明

1. 可重组合（隔板法）

模型：r 个相同球放入 n 个不同盒子。 设第 i 个盒子放 xᵢ 个球，则 x₁+x₂+…+xₙ=r。

• 盒可空：xᵢ≥0。 r 个球与 n-1 块隔板共 n+r-1 个位置，选 r 个位置放球，或选 n-1 个位置放隔板。 公式：C(n+r-1,r)=C(n+r-1,n-1)。

• 盒不可空：xᵢ≥1。 先给每盒 1 个，剩 r-n 个再分到 n 个盒，允许空盒。 公式：C(n+(r-n)-1,r-n)=C(r-1,n-1)，需 r≥n。

注意：球相同、盒不同，才用此模型。

2. 非降路径

从点 (0,0) 到点 (m,n)，每次只能向右走（x 增加 1）或向上走（y 增加 1），总步数为 m+n，其中向右 m 步，向上 n 步。 总路径数：C(m+n,m) 或 C(m+n,n)。

若路径必须经过某点 (a,b)，则路径数等于”从起点到该点”与”从该点到终点”的路径数之积。

3. 排列问题（捆绑法与插空法）

• 捆绑法：要求某些元素必须相邻时，将它们看作一个整体参与排列，再乘以内部排列数。
• 插空法：要求某些元素不相邻时，先排其他元素，再在空隙中插入不相邻的元素。

4. 无序分组

2n 个人分成 n 组，每组 2 人。 先按顺序选组：C(2n,2)·C(2n-2,2)·…·C(2,2)=(2n)!/2ⁿ。 这个过程中 n 个组被隐式排了序。

• 组无编号：需除以 n!，得 N=(2n)!/(2ⁿ·n!)。
• 组有编号/有名字：不除 n!，得 N=(2n)!/2ⁿ。

一般规律：无编号且组大小相同的分组，要除以相同大小组数的阶乘。

5. 其他常用公式

错位排列 D(n)

定义：n 个元素全部不在原来位置上的排列。

• 通项：D(n)=n!·Σ_{k=0}^{n}(-1)^k/k!
• 递推：D(n)=(n-1)(D(n-1)+D(n-2))
• 常用值：D(0)=1, D(1)=0, D(2)=1, D(3)=2, D(4)=9, D(5)=44, D(6)=265

帕斯卡公式

C(n,r)=C(n-1,r-1)+C(n-1,r)，1≤r≤n-1 边界：C(n,0)=C(n,n)=1

欧拉函数 φ(n)

若 n=p₁^{k₁}p₂^{k₂}…pₘ^{kₘ}，则 φ(n)=n·Π(1-1/p)，p 取 n 的所有不同质因子。

容斥原理

• 二集合：|A∪B|=|A|+|B|-|A∩B|
• 补集：|S-(A∪B)|=|S|-|A∪B|
• 三集合：|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

棋盘多项式

R(C) 表示棋盘 C 上放置若干非攻击车的方案生成函数。 对选中一格：R(C)=xR(Cᵢ)+R(Cₗ)

• Cᵢ：去掉该格所在整行整列，表示在该格放一个车。
• Cₗ：仅去掉该格本身，表示该格不放车。

边界：空棋盘 R(∅)=1。

6. 常系数线性齐次递推方程求解

定义： 形如 aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ 的递推方程，其中 c₁,c₂,…,cₖ 为常数，且 cₖ≠0，称为 k 阶常系数线性齐次递推方程。

求解步骤（特征方程法）：

1. 写出特征方程： 将 aₙ 换为 xⁿ，得到 xᵏ - c₁xᵏ⁻¹ - c₂xᵏ⁻² - … - cₖ = 0。

2. 求特征根：解上述代数方程，得到 k 个根（可能有重根、复根）。

3. 根据根的情况写出通解：
   • 情况 1：特征根均为互异实根 x₁,x₂,…,xₖ 通解为：aₙ = A₁x₁ⁿ + A₂x₂ⁿ + … + Aₖxₖⁿ。
   • 情况 2：特征根有重根 若 x₁ 是 m 重根，则对应部分为： (A₁ + A₂n + A₃n² + … + Aₘnᵐ⁻¹)x₁ⁿ。 其余单根仍按情况 1 处理。
   • 情况 3：特征根为共轭复根（了解即可） 若 x = α ± βi，对应部分为： rⁿ(C₁cos(nθ) + C₂sin(nθ))，其中 r=√(α²+β²)，θ=arctan(β/α)。
4. 代入初值求常数： 利用给定的初始条件（如 a₀,a₁,…,aₖ₋₁）代入通解，解出 A₁,A₂,…,Aₖ。

示例：斐波那契数列 f(n)=f(n-1)+f(n-2)，f(1)=1，f(2)=1。 特征方程：x²-x-1=0，特征根 x₁=(1+√5)/2，x₂=(1-√5)/2。 通解：f(n)=A₁x₁ⁿ+A₂x₂ⁿ。 代入初值可解得 A₁=1/√5，A₂=-1/√5， 所以 f(n)=[(1+√5)/2]ⁿ/√5 - [(1-√5)/2]ⁿ/√5。

7. 常系数线性非齐次递推方程（了解）

形如 aₙ = c₁aₙ₋₁ + … + cₖaₙ₋ₖ + f(n) 其中 f(n) 为非零函数。

求解思路：通解 = 齐次通解 + 非齐次特解。 特解的形式根据 f(n) 的类型设定（如常数、多项式、指数函数等），代入原方程确定系数。

例：h(n)=2h(n-1)+1，齐次解 A·2ⁿ，设特解 B，代入得 B=-1，通解 h(n)=A·2ⁿ-1，代入 h(1)=1 得 h(n)=2ⁿ-1。

---

三、例题详细推导（含试卷题目）

例1：选择题 — 错位排列

题目：设 D(n) 表示错位排列的方法数，则 D(5) = ( )。 A. 22 B. 33 C. 44 D. 55

详细推导：

方法一：递推公式 D(n)=(n-1)(D(n-1)+D(n-2)) 已知 D(1)=0, D(2)=1, D(3)=2, D(4)=9。 D(5)=(5-1)(D(4)+D(3))=4×(9+2)=4×11=44。

方法二：通项公式 D(5)=5!·(1-1/1!+1/2!-1/3!+1/4!-1/5!) =120·(1-1+1/2-1/6+1/24-1/120) =120·(0+0.5-0.1667+0.0417-0.0083) =120·(0.3667)=44。

答案：C. 44

---

例2：选择题 — 组合恒等式

题目：设 n, r 为正整数，则下列选项正确的是 ( )。 A. C(n,r) = C(n+1,r-1) + C(n+1,r) B. C(n,r) = C(n-1,r+1) + C(n-1,r) C. C(n,r) = C(n-1,r-1) C(n-1,r) D. C(n,r) = C(n-1,r-1) + C(n-1,r)

详细推导：

帕斯卡公式为：C(n,r)=C(n-1,r-1)+C(n-1,r)。 代入选项验证：

• A：错误，右边是 C(n+1,r) 的展开。
• B：错误，r+1 不符合帕斯卡公式。
• C：错误，应为加法而非乘法。
• D：正确。

答案：D

---

例3：填空题 — 欧拉函数

题目：欧拉函数 φ(50) = ____。

详细推导：

分解质因数：50=2×5²。 不同质因子为 2 和 5。 φ(50)=50×(1-1/2)×(1-1/5) =50×1/2×4/5 =20。

答案：20

---

例4：填空题 — 可重组合

题目：8 本相同的书放到 4 个不同的书架上，每个书架放书数量不限，则放书的方法数为 ____。

详细推导：

设 4 个书架放书数为 x₁,x₂,x₃,x₄。 x₁+x₂+x₃+x₄=8，xᵢ≥0。 用隔板法：8 个球与 3 块隔板共 8+3=11 个位置，选 3 个位置放隔板： C(11,3)=165。

答案：165

---

例5：填空题 — 非降路径

题目：从点 (0,0) 到点 (3,2) 的非降路径总数有 ____ 条，从点 (0,0) 经过点 (2,1) 到达点 (3,2) 的非降路径总数有 ____ 条。

详细推导：

（1）从 (0,0) 到 (3,2)： 总步数 3+2=5，向右 3 步，向上 2 步。 路径数：C(5,3)=C(5,2)=10。

（2）从 (0,0) 经过 (2,1) 到 (3,2)： 第一段：(0,0) 到 (2,1)，向右 2 步，向上 1 步，共 3 步。 路径数：C(3,2)=C(3,1)=3。 第二段：(2,1) 到 (3,2)，向右 1 步，向上 1 步，共 2 步。 路径数：C(2,1)=2。 总路径数：3×2=6。

答案：10；6

---

例6：填空题 — 容斥原理

题目：设有全集 S，|S|=36，集合 A 与 B 都是 S 的子集，且 |A|=18，|A∩B|=6，~|A∪B|=12，则 |B| = ____。

详细推导：

补集 ~|A∪B| 表示 S-(A∪B)。 已知 |S-(A∪B)|=12，所以 |A∪B|=|S|-12=36-12=24。

由容斥原理： |A∪B|=|A|+|B|-|A∩B| 24=18+|B|-6 24=12+|B| |B|=12。

答案：12

---

例7：证明题 — 棋盘多项式

题目：Cᵢ 为去掉某个给定方格所在的行和列之后剩余棋盘；Cₗ 为去掉某个给定方格之后剩余棋盘。 证明：棋盘多项式 R(C)=xR(Cᵢ)+R(Cₗ)

详细推导：

考虑棋盘 C 上放置非攻击车的方案。选中某个给定方格，有两种情况：

1. 在该格放一个车： 放一个车后，该格所在的行和列都不能再放车。 剩余可放车的棋盘为 Cᵢ。 该格已放一个车，对生成函数贡献因子 x。 所以此情况贡献 xR(Cᵢ)。

2. 在该格不放车： 该格不能放车，但其他格子不受影响。 剩余棋盘相当于去掉该格本身，即 Cₗ。 所以此情况贡献 R(Cₗ)。

两种情况互斥且完备，所以： R(C)=xR(Cᵢ)+R(Cₗ)。

证毕。

---

例8：分析问答题 — 排列问题

题目：9 名同学，其中有男同学 4 人，女同学 5 人，从左至右排成一队。 1) 9 名同学的排列方式有多少种？ 2) 如果要求女同学必须都挨在一起，有多少种排列方法？ 3) 如果要求男同学必须都挨在一起，女同学也必须都挨在一起，则有多少种排法？ 4) 如果要求男、女同学必须间隔排队，有多少种排法？

详细推导：

（1）9 名同学全排列 N=9!

（2）女同学必须都挨在一起（捆绑法） 将 5 名女同学看作一个整体，与 4 名男同学共 5 个”元素”全排列： 5! 女同学内部排列：5! 总排列数：N=5!×5!=14400。

（3）男同学必须都挨在一起，女同学也必须都挨在一起（捆绑法） 将 4 名男同学看作一个整体，5 名女同学看作一个整体，两个整体全排列： 2! 男同学内部排列：4! 女同学内部排列：5! 总排列数：N=2!×4!×5!=2×24×120=5760。

（4）男、女同学必须间隔排队 男 4 人，女 5 人。 间隔排队只能以女同学开头和结尾： 排列顺序为：女 男 女 男 女 男 女 男 女。 女同学在 5 个位置全排列：5! 男同学在 4 个位置全排列：4! 总排列数：N=5!×4!=2880。

答案：(1) 9! (2) 14400 (3) 5760 (4) 2880

---

例9：分析问答题 — 选修方案数

题目：A、B、C、D 四人，课程 L、J、Z、S。限制：A 不选 J，B 不选 J、Z，C 不选 Z、S，D 不选 S。每人选一门且每门课一人，求方案数。

详细推导：

总排列数：4! = 24。

设禁止事件： A_J（A 选 J），B_J（B 选 J），B_Z（B 选 Z）， C_Z（C 选 Z），C_S（C 选 S），D_S（D 选 S）。

用容斥计算至少违反一个禁止事件的排列数：

• 单个事件：每个 3! = 6，共 6 个，总和 36。
• 两个事件同时发生：6 个事件两两组合共 C(6,2)=15 对。 不相容的对：
  • 同一人冲突：B_J与B_Z，C_Z与C_S（2 对）
  • 同一课程冲突：A_J与B_J，B_Z与C_Z，C_S与D_S（3 对） 共 5 对不相容，剩余 10 对相容，每对排列数 2! = 2，总和 20。
• 三个事件同时发生：相容的三元组有 4 个： (A_J,B_Z,C_S)，(A_J,B_Z,D_S)，(A_J,C_Z,D_S)，(B_J,C_Z,D_S)。 每个排列数 1! = 1，总和 4。
• 四个事件同时发生：不可能，0。

违反至少一个的事件数：36 - 20 + 4 - 0 = 20。 合法方案数：24 - 20 = 4。

答案：4 种

---

例10：分析问答题 — 线性递推方程（非齐次）

题目：求解递推方程 h(n)=2h(n-1)+1，h(1)=1。

详细推导：

（1）求齐次方程 h(n)=2h(n-1) 的通解： 特征方程 r=2，齐次解 h_h(n)=A·2ⁿ。

（2）求特解： 设特解为常数 B，代入原方程： B=2B+1 解得 B=-1。

（3）通解： h(n)=A·2ⁿ-1。

（4）代入初值 h(1)=1： A·2¹-1=1 2A=2 A=1。

所以： h(n)=2ⁿ-1。

验证：h(1)=1, h(2)=3, h(3)=7，符合递推关系。

答案：h(n)=2ⁿ-1

---

例11：分析问答题 — 容斥原理

题目：玩具店中有库存卡通玩偶若干个，具体包括：3 个相同款式规格的”大头儿子”玩偶、4 个相同款式规格的”海绵宝宝”玩偶、5 个相同款式规格的”喜洋洋”玩偶。现欲将这些玩偶打包促销出售，问：按照每包 10 个玩偶的方式进行打包，一共能形成多少种不同的组合方式？（本题要求使用容斥原理来求解）

详细推导：

设”大头儿子”取 x₁ 个，”海绵宝宝”取 x₂ 个，”喜洋洋”取 x₃ 个。 x₁+x₂+x₃=10，其中 0≤x₁≤3, 0≤x₂≤4, 0≤x₃≤5。

先不考虑上限，允许空盒的可重组合数为： C(10+3-1, 3-1)=C(12,2)=66。

设：

• A₁：x₁≥4
• A₂：x₂≥5
• A₃：x₃≥6

用容斥原理减去不符合上限的情况：

（1）单个上限违反：

• |A₁|：x₁'=x₁-4≥0，x₁'+x₂+x₃=6，C(6+2,2)=C(8,2)=28
• |A₂|：x₂'=x₂-5≥0，x₁+x₂'+x₃=5，C(5+2,2)=C(7,2)=21
• |A₃|：x₃'=x₃-6≥0，x₁+x₂+x₃'=4，C(4+2,2)=C(6,2)=15 总和：28+21+15=64。

（2）两个上限同时违反：

• |A₁∩A₂|：x₁'=x₁-4, x₂'=x₂-5，x₁'+x₂'+x₃=1，C(1+2,2)=C(3,2)=3
• |A₁∩A₃|：x₁'=x₁-4, x₃'=x₃-6，x₁'+x₂+x₃'=0，C(0+2,2)=C(2,2)=1
• |A₂∩A₃|：x₂'=x₂-5, x₃'=x₃-6，x₁+x₂'+x₃'=-1，不可能，0 总和：3+1+0=4。

（3）三个上限同时违反：

• |A₁∩A₂∩A₃|：x₁'=x₁-4, x₂'=x₂-5, x₃'=x₃-6，总和为 10-4-5-6=-5<0，不可能，0。

由容斥原理，合法组合数： 66 - 64 + 4 - 0 = 6。

答案：6 种

---

例12：分析问答题 — 不相邻贴纸问题

题目：在一个 1*n 的方格图形中用气球图案和红旗图案两种贴纸做装饰（两种贴纸数量足够多），如果每个格子里都必须贴上且只能贴上一种贴纸，且不允许两个气球图案贴纸相邻，问有多少种贴纸方案？（要求列出关于方案数的递推方程并求解该递推方程）

详细推导：

设 f(n) 为 1*n 方格的合法贴纸方案数。

考虑第 n 格：

• 第 n 格贴红旗：前 n-1 格只要合法即可，有 f(n-1) 种。
• 第 n 格贴气球：第 n-1 格必须贴红旗；前 n-2 格只要合法即可，有 f(n-2) 种。

所以递推方程为： f(n)=f(n-1)+f(n-2)

初值：

• n=1：贴红旗或气球，f(1)=2
• n=2：红旗-红旗、红旗-气球、气球-红旗，共 f(2)=3

求解递推方程： 特征方程 r²=r+1，特征根 r=(1±√5)/2。 通解 f(n)=A·((1+√5)/2)ⁿ + B·((1-√5)/2)ⁿ。 代入初值可解得 A、B。 若斐波那契数列取 F₁=1, F₂=1，则 f(n)=Fₙ₊₂。

答案：f(n)=f(n-1)+f(n-2)，f(1)=2, f(2)=3，f(n)=Fₙ₊₂

---

例13：补充例题 — 常系数线性齐次递推方程

题目：求解递推方程 aₙ = 5aₙ₋₁ - 6aₙ₋₂，a₀ = 1，a₁ = 0。

详细推导：

（1）写出特征方程： x² = 5x - 6，即 x² - 5x + 6 = 0。

（2）求特征根： (x-2)(x-3)=0 所以 x₁=2，x₂=3，为两个互异实根。

（3）写出通解： aₙ = A·2ⁿ + B·3ⁿ。

（4）代入初值求常数： 由 a₀=1： A·2⁰ + B·3⁰ = 1 ⇒ A + B = 1

由 a₁=0： A·2¹ + B·3¹ = 0 ⇒ 2A + 3B = 0

联立方程组：

A + B = 1
2A + 3B = 0

由第一式得 A = 1 - B，代入第二式： 2(1-B) + 3B = 0 ⇒ 2 - 2B + 3B = 0 ⇒ 2 + B = 0 ⇒ B = -2 所以 A = 1 - (-2) = 3。

（5）最终结果： aₙ = 3·2ⁿ - 2·3ⁿ。

验证： a₀ = 3·1 - 2·1 = 1 ✓ a₁ = 3·2 - 2·3 = 6 - 6 = 0 ✓ a₂ = 3·4 - 2·9 = 12 - 18 = -6 递推验证：5a₁ - 6a₀ = 5×0 - 6×1 = -6 ✓

答案：aₙ = 3·2ⁿ - 2·3ⁿ

---

结语

计数问题的核心在于建模——判断题目属于哪种模型（排列、组合、可重组合、递推等），然后选择对应的方法求解。建议大家在练习时多关注”为什么用这个方法”，而不仅仅是”怎么算”。掌握了原理，无论题目怎么变，都能从容应对。