小八博客

1. 图：

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

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

1. 欧拉回路与欧拉通路

(1) 欧拉回路（Eulerian Circuit）

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

(2) 欧拉通路（Eulerian Path）

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

(3) 性质

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

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

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

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

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

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

(3) 判定条件

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

(4) 性质

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

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

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

平面图与欧拉公式

1. 平面图的定义

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

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

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

公式：

e + 2 = v + m

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

推论：

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

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

(1) 判断是否是平面图

如果图的边数 e 超过 $3 v - 6$ （简单图）或 $2 v - 4$ （二分图），则图不是平面图。
示例：
- 一个简单图有 10 个顶点和 30 条边。
- 检查是否是平面图： $e \leq 3 v - 6 \Rightarrow 30 \leq 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 定理

Kuratowski 定理：
- 如果图中存在子图是 $K_{5}$ 或 $K_{3,3}$ 的子图（通过边的收缩或顶点的删减得到），则该图不是平面图。
非平面图的常见例子：
- 完全图 $K_{5}$ ：包含 5 个顶点，每对顶点都有边相连。
- 完全二分图 $K_{3,3}$ ：两组顶点分别是 $\{A, B, C\}$ 和 $\{X, Y, Z\}$ ，每组顶点中的每个顶点都与另一组的所有顶点相连。

连通性问题

1. 连通性的基本概念

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

2. 连通性度量

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

3. 连通性的性质与定理

(1) 基本性质

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

(2) 图的连通性定理

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

解答：

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

例题 2：判断点连通度

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

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

解答：

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

例题 3：强连通分量

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

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

解答：

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

例题 4：割点和割边

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

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

解答：

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

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

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

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

解答：

图是连通的。
生成树可以选择以下结构：
```
A - B - C
|
D
```

6. 总结

连通性概念：

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

连通性度量：

点连通度 $κ (G)$ ：最少删除多少点使图不连通。
边连通度 $λ (G)$ ：最少删除多少边使图不连通。

算法：

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

2. 树：

[ ] 树的定义及性质

树的定义及性质

1. 树的定义

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

2. 树的性质

边数与顶点数关系：

e = v - 1

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

树中至少两个节点的度数为 1：
- 树至少有两个叶子节点（度数为 1）。
有根树的高度和最大叶子节点数：
高度为 h 的 m-叉树最多有：
$m^h \, (\text{叶子节点数})$
满 m-叉树顶点数与内点、叶子节点关系：
- $i$ 为内点数，即非叶子节点数
- 总顶点数： $n = m \cdot i + 1$ 每个内部节点 i 有 m 个子节点，总共产生 $m \cdot i$ 个子节点。加上根节点 1，得到整个树的总顶点数 n。
- 叶子节点数： $l = (m - 1) \cdot i + 1$ 每个内部节点 i 为树贡献 (m−1) 个叶子节点，因为一个子节点变成内部节点时，它本身不再是叶子节点。
顶点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}$$
满二叉树：
- 节点总数： $n = 2^{h+1} - 1 = 2i +1$
- 内部节点数： $i = \frac{n - 1}{2}$
- 叶子节点数： $l = i + 1 = \frac {n+1}{2}$

3. 树的分类

无根树：
没有指定根节点的树。
有根树：
指定一个根节点的树。
二叉树：
每个节点最多有两个子节点的树（m = 2）。
满二叉树：
每个内部节点都有两个子节点，叶子节点都在同一层。
完全二叉树：
除了最后一层外，其余各层节点都满，最后一层的节点尽量靠左。
生成树：
从图中选取 v−1v - 1 条边构成的连通无环子图。
决策树：
表示决策逻辑或选择的有根树。

4. 经典例题

例题 1：树的边数

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

e = 10 - 1 = 9

答案：树有 9 条边。

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

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

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

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

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

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

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

答案：树有 15 个顶点。

例题 4：森林中树的数量

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

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

答案：森林中有 3 棵树。

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

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

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

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

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

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

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

3. 计数：

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

鸽巢原理（Pigeonhole Principle）

定义

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

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

推广形式（强形式）：

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

其中， $⌈ x ⌉$ 表示 向上取整。

理解鸽巢原理

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

经典题目 1：生日问题

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

解答：

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

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

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

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

解答：

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

经典题目 3：整数问题

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

解答：

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

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

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

解答：

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

经典题目 5：序列问题

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

解答：

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

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

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

解答：

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

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

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

解答：

棋盘有 8 行和 8 列，因此可以把行或列看作“容器”。
9 个棋子是“对象”。
根据鸽巢原理，若棋子超过 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^{n-k}
- 二项式系数出现在展开式的每一项中，系数为 (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）

公式：

$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}, \quad n, k > 0, \, n \geq k$

证明：

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

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

公式：

$\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}, \quad m, n, r \geq 0$

证明：

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

特殊情况：

当 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}{r}

证明思路：

(n+1r+1)\binom{n+1}{r+1} 表示从 n+1n+1 个元素中选出 r+1r+1 个元素的方法数。
对于选出的 r+1r+1 个元素中的最大元素 jj，选出 jj 之前的 rr 个元素的方法共有 (jr)\binom{j}{r} 种。
对所有可能的最大元素 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} 的值，并验证范德蒙德恒等式。
解答：
根据公式：

(5+34)=∑k=04(5k)(34−k)\binom{5+3}{4} = \sum_{k=0}^4 \binom{5}{k} \binom{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 \binom{n}{k} = 2^n$
- \sum_{k=0}^n (-1)^k \binom{n}{k} = 0
- 帕斯卡恒等式： $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$
- 范德蒙德恒等式： $\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{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}$ 个，
$\dots \dots$
第 k 种类型的物体有 $n_{k}$ 个。

总共的排列数为：

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

解释：

这是在 $n = n_{1} + n_{2} + \dots + 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 个字母，允许重复，求组合数。

解答：

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

例题 2：去重排列

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

解答：

字母总数： $$n = 6, \quad n_1 = 2, n_2 = 2, n_3 = 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 个：
- 剩下的糖果数量为 10 - 4 = 6。
使用隔板法：
- $n = 4, r = 6$ 。
- 总分配方法为： $$C(4+6-1, 6) = C(9, 6) = C(9, 3) = 84$$

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

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

解答：

总球数： $$n = 8, \quad n_1 = 2, n_2 = 3, n_3 = 3$$
不同排列数： $$\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. 高级计数：

[ ] 递推关系

线性递推, Linear Recurrence Relations

核心公式

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

一般形式： $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$
特征方程： $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0$
通解（根据特征方程的根）：
1. 简单根（Distinct Roots）： $a_{n} = C_{1} r_{1}^{n} + C_{2} r_{2}^{n} + \dots + 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} + \dots + 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}, \quad a_0 = 1, \quad a_1 = 2

求通解。

解：

写出特征方程： $r^{2} - 4 r + 4 = 0 \Rightarrow (r - 2)^{2} = 0$
双重根 r = 2，通解形式为： $a_{n} = C_{1} \cdot 2^{n} + C_{2} \cdot n \cdot 2^{n}$
利用初始条件 $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$
通解： $a_{n} = 2^{n}$

例题 2：非齐次递推关系

已知递推关系：

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

求通解。

解：

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

1.基础

2.流程控制语句

3.数组

4.函数

5.关键字

10.正则表达式

11.枚举

6.面向对象

1.多态包权限final

2.抽象类接口内部类

3.继承封装类

4.泛型

7.异常File类

8.多线程

容器笔记

数据结构体系

集合

1.流&方法引用&IO

2.网络编程

JavaIO

模块 java.base

包 java.lang

1.折线图

2.地图可视化

3.柱状图

1.CSS基础

2.CSS进阶

排版

文本样式

3.CSS应用

HTML语法

API

DOM

WEB API

标准内置对象

JavaScript学习

0.入门

1.初级

2.中级

3.高级

4.JS精讲

参考

JSON

函数

声明和语句

更多

类

表达式和运算符

1.算法基础

2.线性结构

3.栈与队列

4.哈希表

5.树

6.堆(heap)

7.图(graph)

1.搜索

2.排序

3.分治

4.回溯

5.动态规划

6.贪心

7.数学运算

HTTP

TCP.IP

相关插件

Hooks

1.Redis入门

2.Redis进阶

Redis故障排查

Mybatics

Spring

Spring Boot

Spring Cache

Spring Cloud

Spring Security

Spring Task

Application.yml配置

Springboot基本注解

第三方工具