可能考

1. 图：

• [x] 欧拉回路/通路or哈密顿回路/通路
• [x] 平面图and欧拉公式
• [x] 连通性

欧拉回路/通路 & 哈密顿回路/通路

1. 欧拉回路与欧拉通路

(1) 欧拉回路（Eulerian Circuit）

• 定义：图中经过每一条边且仅经过一次，并且起点和终点相同的回路。
• 判定条件：
  1. 图是连通的（无向图中除孤立顶点外，任意两个顶点连通）。
  2. 图中所有顶点的度数都是偶数。

(2) 欧拉通路（Eulerian Path）

• 定义：图中经过每一条边且仅经过一次，但起点和终点可以不同的通路。
• 判定条件：
  1. 图是连通的。
  2. 图中最多有两个顶点的度数是奇数，其余顶点度数是偶数。

(3) 性质

1. 若图中存在欧拉回路，则从任意顶点出发都能找到欧拉回路。
2. 若图中存在欧拉通路，则通路的起点和终点是度数为奇数的两个顶点。
3. 如果图中有 0 个或 2 个奇顶点，才可能有欧拉通路/回路，否则没有。

---

2. 哈密顿回路与哈密顿通路

(1) 哈密顿回路（Hamiltonian Circuit）

• 定义：图中经过每一个顶点且仅经过一次，并且起点和终点相同的回路。

(2) 哈密顿通路（Hamiltonian Path）

• 定义：图中经过每一个顶点且仅经过一次，但起点和终点可以不同的通路。

(3) 判定条件

• 哈密顿回路/通路 没有简单的充分必要条件，但以下性质可以作为判断依据：
  1. Dirac定理（充分条件）：
     • 如果简单无向图的顶点数为 $n\ge 3$，且任意顶点的度数 $deg(v)\ge \frac{n}{2}$，则该图有哈密顿回路。
  2. Ore定理（充分条件）：
     • 如果简单无向图的顶点数为 $n\ge 3$，且任意两个不相邻顶点 $u,v$ 满足 $deg(u)+deg(v)\ge n$，则该图有哈密顿回路。
  3. 完全图：
     • 任意一个 n 阶完全图（$K_n$）都具有哈密顿回路。
  4. 其他常见条件：
     • 连通图中度数较高的顶点更可能存在哈密顿回路。

(4) 性质

1. 哈密顿通路与顶点的排列有关，路径上不能重复经过顶点。
2. 哈密顿回路与通路问题比欧拉回路问题更复杂，没有统一的判定标准。

---

3. 欧拉回路 vs 哈密顿回路

特性	欧拉回路	哈密顿回路
定义	每条边仅经过一次，起点终点相同	每个顶点仅经过一次，起点终点相同
判定条件	所有顶点的度数为偶数	没有统一判定条件（有充分条件，如Dirac定理）
复杂度	比较容易判定	判定较为复杂
与边/顶点的关系	关注是否经过每条边	关注是否经过每个顶点

平面图与欧拉公式

1. 平面图的定义

1. 平面图（Planar Graph）：
   • 如果一个图能够画在平面上，并且其边之间不相交（除了在顶点处），则称为平面图。
2. 平面图的特性：
   • 图的平面化绘制中，边之间不能有交叉。
   • 一个图是否是平面图，可以通过理论方法（如欧拉公式）或 Kuratowski 定理来判定。
3. 完全图 $K_n$ 的平面化：
   • $K_1,K_2,K_3,K_4$ 是平面图。
   • $K_5$ 及更高的完全图不是平面图。
4. 完全二分图 $K_{m,n}$ 的平面化：
   • $K_{3,3}$ 是非平面图，但 $K_{2,3}$ 是平面图。

---

2. 欧拉公式（Euler’s Formula）

欧拉公式是平面图的核心性质，用于描述平面图中顶点数、边数和区域数之间的关系。

公式：

$$e+2=v+m$$

• v：顶点数
• e：边数
• m：面数

推论：

1. 边数的上界：
   • 若平面图中没有多边和自环，则边数满足：$e\le 3v-6$
   • 如果是简单平面图（无多边和自环），且每个面至少是三角形，则总边数最多为：$e\le 3v-6$
   • 对于二分图（所有面至少是四边形），有： $e\le 2v-4$
2. 最少顶点数条件：
   • 平面图中如果度数较高的顶点数量太少，就可能无法满足 $v-e+m=2$。

---

3. 平面图与欧拉公式的应用

(1) 判断是否是平面图

• 如果图的边数 e 超过 $3v-6$（简单图）或 $2v-4$（二分图），则图不是平面图。
• 示例：
  • 一个简单图有 10 个顶点和 30 条边。
  • 检查是否是平面图： $e\le 3v-6\Rightarrow 30\le 3(10)-6=24$ 因为 $30>24$，所以这个图不是平面图。

(2) 面数计算

• 如果一个平面图给定了 v 和 e，可以通过欧拉公式求面数 m： $m=2-v+e$
• 示例：
  • 一个平面图有 6 个顶点和 10 条边。
  • 面数：$m=2-6+10=6$

(3) 验证平面图的顶点、边与区域关系

• 示例：
  • 一个平面图有 8 个顶点和 14 条边。
  • 验证 m 是否满足欧拉公式：$m=2-v+e=2-8+14=8$ 所以该图是平面图。

---

4. 非平面图的判定：Kuratowski 定理

1. Kuratowski 定理：

   • 如果图中存在子图是$K_5$ 或 $K_{3,3}$ 的子图（通过边的收缩或顶点的删减得到），则该图不是平面图。

2. 非平面图的常见例子：

   • 完全图 $K_5$：包含 5 个顶点，每对顶点都有边相连。
   • 完全二分图 $K_{3,3}$：两组顶点分别是$\{A,B,C\}$ 和$\{X,Y,Z\}$，每组顶点中的每个顶点都与另一组的所有顶点相连。

连通性问题

1. 连通性的基本概念

1. 连通图（Connected Graph）：
   • 如果无向图 G 中任意两个顶点之间都存在路径，则称图 G 是连通的。
2. 强连通图（Strongly Connected Graph）：
   • 对于有向图 G，如果任意两个顶点 u 和 v 之间都存在路径（包括从 u 到 v 和从 v 到 u 的路径），则称 G 是强连通的。
3. 弱连通图（Weakly Connected Graph）：
   • 对于有向图 G，如果将所有有向边替换为无向边后，得到的图是连通的，则称 G 是弱连通的。
4. 连通分量（Connected Component）：
   • 无向图的最大连通子图称为 连通分量。
   • 每个连通分量是一个连通子图，且这些子图互不连通。
5. 强连通分量（Strongly Connected Component，SCC）：
   • 有向图中，所有顶点之间两两强连通的最大子图。
6. 割点与割边：
   • 割点：删除某个顶点后，图不再连通。
   • 割边：删除某条边后，图不再连通。

---

2. 连通性度量

1. 点连通度（Vertex Connectivity，κ(G)\kappa(G)）：
   • 一个图的点连通度是指将图分割成不连通图所需删除的最少顶点数。
   • 点连通度公式：$\kappa (G)=min\{|S|:G-S\text{ 不连通}\}$ 其中 S 是被删除的顶点集。
2. 边连通度（Edge Connectivity，λ(G)\lambda(G)）：
   • 一个图的边连通度是指将图分割成不连通图所需删除的最少边数。
   • 边连通度公式：$\lambda (G)=min\{|E^{\prime }|:G-E^{\prime }\text{ 不连通}\}$ 其中 $E^{\prime }$ 是被删除的边集。
3. 图的连通性关系：
   • 对于简单图 $\kappa (G)\le \lambda (G)\le \delta (G$) 其中 $\delta (G)$ 是图的最小度数。

---

3. 连通性的性质与定理

(1) 基本性质

• 如果图是连通的，则其所有顶点都属于同一个连通分量。
• 连通图的边数 $e\ge v-1$，其中 v 是顶点数。

(2) 图的连通性定理

1. Menger定理：
   • G 是一个连通图。
   • 任意两个不同的顶点 u 和 v 之间的 点独立路径的最大数目 等于 u 和 v 之间的最小割点数。
   • 对于边的版本：边独立路径的最大数目等于最小割边数。
2. 连通性和生成树：
   • 图 G 连通，当且仅当 G 包含一个生成树。
3. 强连通分量的判定：
   • 有向图的强连通分量可以通过 Kosaraju 算法 或 Tarjan 算法 来高效判定。
4. 两点连通性：
   • 图 G 是 两点连通的，如果任意两个顶点之间至少有两个独立路径（即没有公共顶点）。
   • 两点连通图中不存在割点。
5. 两边连通性：
   • 图 G 是 两边连通的，如果任意两个顶点之间至少有两个边独立路径（即没有公共边）。
   • 两边连通图中不存在割边。

---

4. 连通性判定方法

(1) 判定无向图的连通性

• 使用 深度优先搜索（DFS） 或 广度优先搜索（BFS）：
  • 从某个顶点出发，标记访问过的所有顶点。
  • 如果所有顶点都被访问过，则图是连通的。
  • 如果某些顶点没有被访问到，则图是不连通的，可以通过未访问的顶点找到其他连通分量。

(2) 判定有向图的强连通性

• 使用 Kosaraju 算法：
  1. 对图 G 进行一次 DFS，记录顶点的 完成时间。
  2. 将图 G 的所有边反向，得到转置图 $G^T$。
  3. 按照完成时间的逆序，对 $G^T$ 进行第二次 DFS。
  4. 每次 DFS 得到的顶点集合即为一个强连通分量。

(3) 判定是否存在割点/割边

• 割点判定：
  • 使用 DFS 找到割点。如果在 DFS 树中，根节点的子树数大于等于 2，或者非根节点满足某些条件（子节点无法回到其祖先节点），则该节点是割点。
• 割边判定：
  • 使用 DFS 判定，若某条树边的子树节点不能回到祖先节点，则是割边。

---

5. 经典例题

例题 1：判断图的连通性

问题：下图是连通图吗？

图结构：
A - B   C - D

解答：

1. 从任意顶点（如 A）开始，无法通过路径到达顶点 C 或 D。
2. 图中存在两个连通分量。
3. 答案：图不是连通图。

---

例题 2：判断点连通度

问题：求以下图的点连通度。

图结构：
A - B - C
|       |
D       E

解答：

1. 任意删除顶点 B 或 D 会使图分成两个连通分支。
2. 点连通度$\kappa (G)=1$（删除 1 个顶点使图不连通）。

---

例题 3：强连通分量

问题：求以下有向图的强连通分量。

图结构：
A → B → C → A
D → E

解答：

1. 强连通分量是顶点之间相互可达的最大子图。
2. 图中存在两个强连通分量：
   • $\{A,B,C\}$。
   • $\{D,E\}$。

---

例题 4：割点和割边

问题：找出以下图中的割点和割边。

图结构：
A - B - C
|       |
D       E

解答：

1. 割点：
   • 删除 B，图分裂为两个连通分支$\{A,D\}$ 和$\{C,E\}$。
   • B 是割点。
2. 割边：
   • 删除A - B 或 B - C 会使图不连通。
   • 割边为A - B、B - C。

---

例题 5：判断连通性和生成树

问题：判断以下图是否是连通图，如果是，画出一棵生成树。

图结构：
A - B - C
|       |
D       E

解答：

1. 图是连通的。

2. 生成树可以选择以下结构：

   A - B - C
   |
   D

---

6. 总结

连通性概念：

• 连通图：无向图中任意两点之间都有路径。
• 强连通图：有向图中任意两点之间都有双向路径。
• 弱连通图：有向图中忽略边方向后连通。

连通性度量：

• 点连通度 $\kappa (G)$：最少删除多少点使图不连通。
• 边连通度 $\lambda (G)$：最少删除多少边使图不连通。

算法：

• DFS/BFS 判定连通性。
• Kosaraju/Tarjan 算法求强连通分量。
• DFS 判定割点和割边。

2. 树：

• [x] 树的定义及性质

树的定义及性质

1. 树的定义

1. 树：
   没有简单回路的连通无向图称为树。
2. 森林：
   每个连通分支都是树的无向图称为森林。
3. 有根树：
   在树中指定一个节点作为根，并且每条边的方向都离开根。
4. 树的等价定义：
   • 无回路的连通图。
   • 没有回路且边数为 $e=v-1$。
   • 连通且边数为 $e=v-1$。
   • 没有回路，但增加一条边会形成且仅形成一个回路。
   • 连通，但删去任意一条边后不再连通。
   • 每对结点之间有且仅有一条简单路径。
5. 无向图是树的充要条件：
   一个无向图是树，当且仅当该图中 任意两个顶点之间存在唯一简单通路。

---

2. 树的性质

1. 边数与顶点数关系：

$$e=v-1$$

• 对于 n 个顶点的树，必有 $n-1$ 条边。

2. 树中至少两个节点的度数为 1：

   • 树至少有两个叶子节点（度数为 1）。

3. 有根树的高度和最大叶子节点数：
   高度为 h 的 m-叉树最多有：

   $$m^h(\text{叶子节点数})$$

4. 满 m-叉树顶点数与内点、叶子节点关系：

   • $i$ 为内点数，即非叶子节点数
   • 总顶点数： $n=m\cdot i+1$ 每个内部节点 i 有 m 个子节点，总共产生 $m\cdot i$ 个子节点。 加上根节点 1，得到整个树的总顶点数 n。
   • 叶子节点数： $l=(m-1)\cdot i+1$ 每个内部节点 i 为树贡献 (m−1) 个叶子节点，因为一个子节点变成内部节点时，它本身不再是叶子节点。

5. 顶点n、内点i、叶子节点l 公式：

   • 已知 n： $$i = \frac{n - 1}{m}, \quad l = \frac{(m - 1)n + 1}{m}$$
   • 已知 i： $$n = m \cdot i + 1, \quad l = (m - 1) \cdot i + 1$$
   • 已知 l： $$n = \frac{m \cdot l - 1}{m - 1}, \quad i = \frac{l - 1}{m - 1}$$

6. 满二叉树：

   • 节点总数： $n=2^{h+1}-1=2i+1$
   • 内部节点数： $i=\frac{n-1}{2}$
   • 叶子节点数： $l=i+1=\frac{n+1}{2}$

---

3. 树的分类

1. 无根树：
   没有指定根节点的树。

2. 有根树：
   指定一个根节点的树。

3. 二叉树：
   每个节点最多有两个子节点的树（m = 2）。

4. 满二叉树：
   每个内部节点都有两个子节点，叶子节点都在同一层。

5. 完全二叉树：
   除了最后一层外，其余各层节点都满，最后一层的节点尽量靠左。

6. 生成树：
   从图中选取 v−1v - 1 条边构成的连通无环子图。

7. 决策树：
   表示决策逻辑或选择的有根树。

---

4. 经典例题

例题 1：树的边数

问题：一棵树有 10 个顶点，问这棵树有多少条边？
解答：
根据公式 $e=v-1$：

$$e=10-1=9$$

答案：树有 9 条边。

---

例题 2：满二叉树的节点关系

问题：一个满二叉树有 15 个顶点，问其叶子节点数和内部节点数分别是多少？
解答：

1. 满二叉树的公式：$$i = \frac{n - 1}{2}, \quad l = i + 1$$
2. 代入 n = 15： $$i = \frac{15 - 1}{2} = 7, \quad l = i + 1 = 7 + 1 = 8$$

答案：叶子节点数为 8，内部节点数为 7。

---

例题 3：高度为 h 的满二叉树

问题：高度为 3 的满二叉树有多少个顶点？
解答：

1. 满二叉树的顶点公式： $$n = 2^{h+1} - 1$$
2. 代入 h = 3： $$n = 2^{3+1} - 1 = 2^4 - 1 = 15$$

答案：树有 15 个顶点。

---

例题 4：森林中树的数量

问题：一个有 10 个顶点的无向图，若其是森林且有 7 条边，问其中有几棵树？
解答：

1. 森林中树的数量公式： $$\text{树的数量} = \text{顶点数} - \text{边数}$$
2. 代入数据： $$树的数量=10−7=3$$

答案：森林中有 3 棵树。

---

例题 5：满 m-叉树节点数

问题：一棵满 4 叉树有 21 个叶子节点，问其内部节点数和总节点数。
解答：

1. 使用公式： $$n = m \cdot i + 1, \quad l = (m - 1) \cdot i + 1$$
2. 已知$l=21,m=4$，解$$i： i = \frac{l - 1}{m - 1} = \frac{21 - 1}{4 - 1} = \frac{20}{3} = 7$$
3. 求总顶点数 n： $$n = m \cdot i + 1 = 4 \cdot 7 + 1 = 29$$

答案：内部节点数为 7，总节点数为 29。

---

例题 6：证明树中至少有两个叶子节点

问题：证明树中至少有两个节点的度数为 1。
解答：

1. 树的度数总和为 $2e=2(n-1)$。
2. 若每个节点的度数大于等于 2，或仅有一个节点度数为 1，则总度数会超过 $2(n-1)$，与树的性质矛盾。
3. 因此，至少有两个节点的度数为 1（即叶子节点）。

3. 计数：

• [x] 鸽巢原理
• [x] 二项式扩展排列组和
• [ ] 广义置换和组合

鸽巢原理（Pigeonhole Principle）

定义

基本形式（最简单的鸽巢原理）：

如果将 $n+1$ 个或更多的对象分配到 $n$ 个容器中，那么至少有一个容器中包含两个或更多的对象。

推广形式（强形式）：

如果将 N 个对象分配到 m 个容器中，那么至少有一个容器中包含至少 $\lceil N/m\rceil$ 个对象。

其中，$\lceil x\rceil$ 表示 向上取整。

---

理解鸽巢原理

• 假设有 10 只鸽子和 9 个鸽巢（容器）。如果每只鸽子必须进入一个鸽巢，根据鸽巢原理，至少有一个鸽巢会有两只或更多的鸽子。
• 关键思想：如果对象数（鸽子）大于容器数（鸽巢），必然会发生“冲突”或“重复”。

---

经典题目 1：生日问题

问题：在一个班级中有 23 名学生，证明至少有两个人的生日相同。

解答：

1. 一年有 365 天，因此可以将每一天看作一个“容器”。
2. 如果每个学生（对象）有不同的生日，那么最多容纳 365 人而无冲突。
3. 当学生人数超过 365 时，必然会有两个人生日相同。
4. 推广：只要有 n>365 的人，就能确保至少有两人生日相同。

即使人数为 23，这个问题可以通过概率计算得知重复的可能性高达约 50%。

---

经典题目 2：整数加法问题

问题：证明从集合 $\{1,2,3,\dots ,9\}$ 中任取 5 个数，至少有两数之和为 10。

解答：

1. 互补数对：将集合 $\{1,2,3,\dots ,9\}$ 分成以下 $4$ 对“互补数对”以及一个单独元素：$(1,9),(2,8),(3,7),(4,6),\{5\}$
2. 如果从中选取 5 个数，必定至少包含一个互补数对（比如 1 和 9），因为总共有 4 对互补数和 1 个单独的数。
3. 由于互补数对的和为 10，必然有两数之和等于 10。

---

经典题目 3：整数问题

问题：证明对于任意 5 个整数，总能找到两个数，它们的差是 4 的倍数。

解答：

1. 将所有整数按除以 4 的余数分成 4 个类：$\{0,1,2,3\}$（即 4 个“容器”）。
2. 如果有 5 个整数（对象），根据鸽巢原理，至少有两个数属于同一个余数类。
3. 两个同余的整数 $a,b$ 满足： $a-b=4k,k\in \mathbb{Z}$ 因此，差一定是 4 的倍数。

---

经典题目 4：抽屉中袜子的问题

问题：假设有 10 双不同颜色的袜子，全部混在一个抽屉里。为了保证一定拿到一双同色的袜子，最少需要取出几只？

解答：

1. 这是典型的鸽巢原理应用。
2. 把袜子的颜色看作“容器”（共 10 种颜色）。
3. 如果每种颜色最多拿 1 只袜子，那么拿 10 只袜子时，可能刚好每只袜子是不同颜色。
4. 第 11 只袜子必须和之前的某只袜子颜色相同。
5. 因此，最少需要取出 $10+1=11$ 只袜子，才能保证至少有一双同色的袜子。

---

经典题目 5：序列问题

问题：证明：从任意 6 个整数中，总能找到两个数，它们的差是 5 的倍数。

解答：

1. 根据整数除以 5 的余数，可以将所有整数分成 5 类：$\{0,1,2,3,4\}$。
2. 如果有 6 个数，根据鸽巢原理，至少有两个数 $a,b$落入同一类。
3. 这两个数满足： $a\equiv b(\mathrm{mod}5)\Rightarrow a-b=5k,k\in \mathbb{Z}$
4. 因此，这两个数的差是 5 的倍数。

---

经典题目 6：二维平面问题

问题：在边长为 1 的正方形区域内，放置 5 个点，证明至少有两个点之间的距离不超过$\sqrt{2}/2$。

解答：

1. 将正方形区域分成 4 个等分的小正方形（每个小正方形的边长为 1/2）。
2. 这 4 个小正方形是“容器”，而 5 个点是“对象”。
3. 根据鸽巢原理，至少有两个点位于同一个小正方形中。
4. 在任意一个小正方形中，两点之间的最远距离是小正方形的对角线长度：$\sqrt{(1/2{)}^2+(1/2{)}^2}=\sqrt{2}/2$
5. 因此，至少有两个点之间的距离不超过$\sqrt{2}/2$。

---

经典题目 7：棋盘覆盖问题

问题：在$8\times 8$ 的国际象棋棋盘上，放置 9 个棋子，证明至少有两个棋子位于同一行或同一列。

解答：

1. 棋盘有 8 行和 8 列，因此可以把行或列看作“容器”。
2. 9 个棋子是“对象”。
3. 根据鸽巢原理，若棋子超过 8 个，则至少有两个棋子在同一行，或者至少有两个棋子在同一列。

二项式扩展排列组和

1. 二项式系数定义

• 二项式系数：
  具有 n 个元素的 r 组集合的选择方式记作：

  (nr)=Cnr=n!r!(n−r)!,0≤r≤n\binom{n}{r} = C_n^r = \frac{n!}{r!(n-r)!}, \quad 0 \leq r \leq n

  • 表示从 nn 个不同元素中取出 rr 个元素的组合数。

• 二项式定理：

  (x+y)n=∑k=0n(nk)xkyn−k(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^

  • 二项式系数出现在展开式的每一项中，系数为 (nk)\binom{n}{k}。

---

2. 二项式定理的推论

推论 1：

∑k=0n(nk)=2n\sum_{k=0}^n \binom{n}{k} = 2^n

证明：
代入 x=1,y=1x = 1, y = 1 到二项式定理：

(1+1)n=∑k=0n(nk)⋅1k⋅1n−k=2n(1 + 1)^n = \sum_{k=0}^n \binom{n}{k} \cdot 1^k \cdot 1^{n-k} = 2^n

---

推论 2：

∑k=0n(−1)k(nk)=0(n>0)\sum_{k=0}^n (-1)^k \binom{n}{k} = 0 \quad (n > 0)

证明：
代入 x=1,y=−1x = 1, y = -1 到二项式定理：

(1−1)n=∑k=0n(nk)⋅1k⋅(−1)n−k=0(1 - 1)^n = \sum_{k=0}^n \binom{n}{k} \cdot 1^k \cdot (-1)^{n-k} = 0

---

推论 3（奇数项与偶数项相等）：

(n0)+(n2)+(n4)+⋯=(n1)+(n3)+(n5)+⋯\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots = \binom{n}{1} + \binom{n}{3} + \binom{n}{5} + \cdots

证明：
因为：

∑k=0n(nk)=2n,∑k=0n(−1)k(nk)=0\sum_{k=0}^n \binom{n}{k} = 2^n, \quad \sum_{k=0}^n (-1)^k \binom{n}{k} = 0

将奇数和偶数分开整理，得到二者相等。

---

推论 4：

∑k=0n2k(nk)=3n\sum_{k=0}^n 2^k \binom{n}{k} = 3^n

证明：
代入 x=1,y=2x = 1, y = 2 到二项式定理：

(1+2)n=∑k=0n(nk)⋅1k⋅2n−k=3n(1 + 2)^n = \sum_{k=0}^n \binom{n}{k} \cdot 1^k \cdot 2^{n-k} = 3^n

---

3. 帕斯卡恒等式（Pascal's Identity）

公式：

(n+1k)=(nk−1)+(nk),n,k>0, n≥k\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}, \quad n, k > 0, , n \geq k

证明：

1. 假设集合 TT 有 n+1n+1 个元素，从中选出 kk 个元素的方法共有 (n+1k)\binom{n+1}{k} 种。
2. 将集合分为两部分：
   • 包含特定元素 aa 的情况：从剩下的 nn 个元素中选出 k−1k-1 个元素，共 (nk−1)\binom{n}{k-1} 种。
   • 不包含 aa 的情况：从剩下的 nn 个元素中选出 kk 个元素，共 (nk)\binom{n}{k} 种。
3. 总数为： (n+1k)=(nk−1)+(nk)\binom{n+1}{k} = \binom{n}{k-1} + \binom

---

4. 范德蒙德恒等式（Vandermonde's Identity）

公式：

(m+nr)=∑k=0r(mk)(nr−k),m,n,r≥0\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}, \quad m, n, r \geq 0

证明：

1. 假设集合 TT 中共有 m+nm+n 个元素。
2. 将集合分为 RR（mm 个元素）和 SS（nn 个元素）。
3. 从 TT 中选出 rr 个元素的方法共有 (m+nr)\binom{m+n}{r} 种。
4. 其中，选出 kk 个元素在 RR 中，选出 r−kr-k 个元素在 SS 中的情况有： (mk)⋅(nr−k)\binom{m}{k} \cdot \binom
5. 对 kk 的所有情况求和： (m+nr)=∑k=0r(mk)⋅(nr−k)\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \cdot \binom

特殊情况：

当 m=nm = n 时：

(2nn)=∑k=0n(nk)2\binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2

---

5. 其他恒等式

公式 1：

(n+1r+1)=∑j=rn(jr)\binom{n+1}{r+1} = \sum_{j=r}^n \binom{j}

证明思路：

1. (n+1r+1)\binom{n+1}{r+1} 表示从 n+1n+1 个元素中选出 r+1r+1 个元素的方法数。
2. 对于选出的 r+1r+1 个元素中的最大元素 jj，选出 jj 之前的 rr 个元素的方法共有 (jr)\binom{j}{r} 种。
3. 对所有可能的最大元素 jj 进行求和，得到结果。

---

6. 经典例题

例题 1：计算组合数的奇偶性

问题：判断组合数 (53)\binom{5}{3} 的值及奇偶性。
解答：

(53)=5!3!(5−3)!=5⋅42⋅1=10\binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{5 \cdot 4}{2 \cdot 1} = 10

• 1010 是偶数。

---

例题 2：验证二项式系数恒等式

问题：验证 ∑k=0n(nk)=2n\sum_{k=0}^n \binom{n}{k} = 2^n 是否成立。
解答：
对于 n=3n = 3：

∑k=03(3k)=(30)+(31)+(32)+(33)\sum_{k=0}^3 \binom{3}{k} = \binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} =1+3+3+1=8= 1 + 3 + 3 + 1 = 8

• 23=82^3 = 8，恒等式成立。

---

例题 3：范德蒙德恒等式计算

问题：计算 (5+34)\binom{5+3}{4} 的值，并验证范德蒙德恒等式。
解答：
根据公式：

$$(\genfrac{}{}{0ex}{}{5+3}{4})=\sum _{k=0}^4(\genfrac{}{}{0ex}{}{5}{k})(\genfrac{}{}{0ex}{}{3}{4-k})$$

展开求和：

(84)=(50)(34)+(51)(33)+(52)(32)+(53)(31)+(54)(30)\binom{8}{4} = \binom{5}{0}\binom{3}{4} + \binom{5}{1}\binom{3}{3} + \binom{5}{2}\binom{3}{2} + \binom{5}{3}\binom{3}{1} + \binom{5}{4}\binom{3}{0} =0+5+30+30+35=70= 0 + 5 + 30 + 30 + 35 = 70

• 验证结果正确。

---

例题 4：验证帕斯卡恒等式

问题：计算 (63)\binom{6}{3} 和 (52)+(53)\binom{5}{2} + \binom{5}{3}。
解答：

• (63)=20\binom{6}{3} = 20。
• (52)+(53)=10+10=20\binom{5}{2} + \binom{5}{3} = 10 + 10 = 20。
• 两者相等，恒等式成立。

---

总结

• 常用恒等式：

  • $\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})=2^n$
  • \sum_{k=0}^n (-1)^k \binom{n}{k} = 0
  • 帕斯卡恒等式：$(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k-1})+(\genfrac{}{}{0ex}{}{n}{k})$
  • 范德蒙德恒等式：$(\genfrac{}{}{0ex}{}{m+n}{r})=\sum _{k=0}^r(\genfrac{}{}{0ex}{}{m}{k})(\genfrac{}{}{0ex}{}{n}{r-k})$

• 二项式定理是核心，赋值 x, y 可以推导出许多恒等式。

广义置换和组合

1. 隔板法的推广

对于 n 个种类的物体，允许重复选择，总共取 r 个物体的 组合数 为：

$$C(n+r-1,r)=C(n+r-1,n-1)$$

2. 去重排列的推广

假设有 n 个物体，其中：

• 第一种类型的物体有 $n_1$ 个，
• 第二种类型的物体有 $n_2$ 个，
• $\cdots \cdots$
• 第 k 种类型的物体有 $n_k$ 个。

总共的排列数为：

$$\frac{n!}{n_1!n_2!\cdots n_k!}$$

解释：

• 这是在$n=n_1+n_2+\cdots +n_k$ 个物体中排列的情况下，去除了相同物体排列的冗余。
• 如果所有物体都不同，总排列数为 $n!$。
• 如果有相同类型的物体，必须除以相同物体的排列数 $n_1!$, $n_2!$, 等。

推导：

• 总共 $n!$ 种排列。
• $n_1!$ 是第一种物体的冗余排列数。
• $n_2!$ 是第二种物体的冗余排列数，依此类推。
• 最终的有效排列数为：

$$\frac{n!}{n_1!n_2!\cdots n_k!}$$

---

3. 经典例题

例题 1：隔板法应用

问题：从 $\{A,B,C\}$ 三个字母中选取 5 个字母，允许重复，求组合数。

解答：

1. 使用隔板法：
   • n = 3, r = 5。
   • 总组合数为： $C(3+5-1,5)=C(7,5)=21$

---

例题 2：去重排列

问题：求排列字母 "AABBCC" 的所有不同排列数。

解答：

1. 字母总数： $$n = 6, \quad n_1 = 2, n_2 = 2, n_3 = 2$$
2. 排列数： $$\frac{n!}{n_1! n_2! n_3!} = \frac{6!}{2! \cdot 2! \cdot 2!} = \frac{720}{8} = 90$$

---

例题 3：隔板法的分配问题

问题：将 10 个相同的糖果分给 4 个孩子，每个孩子至少分到 1 个，问有多少种分配方法？

解答：

1. 每个孩子至少分到 1 个糖果，先分给每人 1 个：
   • 剩下的糖果数量为 10 - 4 = 6。
2. 使用隔板法：
   • $n=4,r=6$。
   • 总分配方法为： $$C(4+6-1, 6) = C(9, 6) = C(9, 3) = 84$$

---

例题 4：去重排列的复杂例子

问题：将 8 个球分为 2 红球、3 蓝球、3 绿球，求不同排列数。

解答：

1. 总球数： $$n = 8, \quad n_1 = 2, n_2 = 3, n_3 = 3$$
2. 不同排列数： $$\frac{n!}{n_1! n_2! n_3!} = \frac{8!}{2! \cdot 3! \cdot 3!} = \frac{40320}{6 \cdot 6 \cdot 2} = 560$$

---

4. 总结

• 隔板法：

  • 用于求解 允许重复的组合问题。
  • 总组合数公式：$$C(n+r-1, r)$$

• 去重排列：

  • 用于求解 重复元素的全排列问题。
  • 总排列数公式： $$\frac{n!}{n_1! n_2! \cdots n_k!}$$

• 关键技巧：

  1. 隔板法：将问题转化为隔板分隔的形式。
  2. 去重排列：通过 $n_1!$, $n_2!$, 等消除重复排列。

4. 高级计数：

• [x] 递推关系

线性递推, Linear Recurrence Relations

核心公式

1. 齐次线性递推关系（Homogeneous Recurrence Relations）

• 一般形式： $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$
• 特征方程：$r^k-c_1{r}^{k-1}-c_2{r}^{k-2}-\cdots -c_k=0$
• 通解（根据特征方程的根）：
  1. 简单根（Distinct Roots）： $a_n=C_1{r}_1^n+C_2{r}_2^n+\cdots +C_k{r}_k^n$
  2. 重根（Repeated Roots）： 如果某根 $r_i$ 的重数为 $m$，则通解包含： $$C_1 r_i^n + C_2 n r_i^n + C_3 n^2 r_i^n + \dots + C_m n^{m-1} r_i^n$$

---

2. 非齐次线性递推关系（Nonhomogeneous Recurrence Relations）

• 一般形式：

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}+f(n)$$

• 通解： $a_n=a_n^{(h)}+a_n^{(p)}$
  • $a_n^{(h)}$：对应齐次方程的通解。
  • $a_n^{(p)}$：特解，依赖于 $f(n)$ 的形式。
• 特解形式：
  1. 若 $f(n)$ 是常数：假设特解为常数。
  2. 若 $f(n)$ 是多项式：假设特解为多项式（同次）。
  3. 若 $f(n)$ 是指数函数：假设特解为指数函数形式。
  4. 若 $f(n)$ 是三角函数：假设特解为三角函数形式。

---

例题整理

例题 1：齐次递推关系

已知递推关系：

$$a_n=4a_{n-1}-4a_{n-2},a_0=1,a_1=2$$

求通解。

解：

1. 写出特征方程：$r^2-4r+4=0\Rightarrow (r-2{)}^2=0$
2. 双重根 r = 2，通解形式为： $a_n=C_1\cdot 2^n+C_2\cdot n\cdot 2^n$
3. 利用初始条件 $a_0=1,a_1=2$ 求 $C_1,C_2$：
   • $a_0=C_1=1$
   • $a_1=C_1\cdot 2+C_2\cdot 2=2\Rightarrow C_2=0$
4. 通解： $a_n=2^n$

---

例题 2：非齐次递推关系

已知递推关系：

$$a_n=2a_{n-1}+3,a_0=1$$

求通解。

解：

1. 对应的齐次方程： $a_n^{(h)}=C\cdot 2^n$
2. 求特解：
   • 非齐次项 $f(n)=3$，假设特解为常数 $a_n^{(p)}=k$： $$k = 2k + 3 \quad \Rightarrow \quad k = -3$$
   • 特解为 $a_n^{(p)}=-3$。
3. 通解：$$ a_n = a_n^{(h)} + a_n^{(p)} = C \cdot 2^n - 3$$
4. 利用初始条件$a_0$ = 1 求 C： $1=C\cdot 2^0-3\Rightarrow C=4$
5. 最终解： $a_n=4\cdot 2^n-3$