组合学笔记

1. 集合与加乘原理

1.1 集合的基本概念

定义 1.1（集合） 集合是由确定的不同对象组成的整体，这些对象称为集合的元素。

一般用大写字母 $A, B, C, \ldots$ 表示集合，用小写字母 $a, b, c, \ldots$ 表示元素。

• 若 $a$ 是集合 $A$ 的元素，记作 $a \in A$（读作”$a$ 属于 $A$”）
• 若 $a$ 不是集合 $A$ 的元素，记作 $a \notin A$（读作”$a$ 不属于 $A$”）

定义 1.2（集合的表示法） 集合主要有两种表示方法：

1. 列举法：将集合的所有元素一一列举出来，用花括号括起来。 $A = \{1, 2, 3, 4, 5\}$

2. 描述法：用集合中元素所满足的性质来描述集合。 $A = \{x \mid x \text{ 是正整数}, x \leq 5\}$

定义 1.3（空集） 不含任何元素的集合称为空集，记作 $\varnothing$ 或 $\emptyset$。

定义 1.4（全集） 在特定问题中，包含所讨论的所有元素的集合称为全集，通常记作 $U$ 或 $\Omega$。

1.2 集合间的关系

定义 1.5（子集） 设 $A, B$ 是两个集合，若对于任意 $x \in A$ 都有 $x \in B$，则称 $A$ 是 $B$ 的子集，记作 $A \subseteq B$ 或 $B \supseteq A$。

定义 1.6（真子集） 若 $A \subseteq B$ 且 $A \neq B$，则称 $A$ 是 $B$ 的真子集，记作 $A \subsetneq B$。

定义 1.7（集合相等） 若 $A \subseteq B$ 且 $B \subseteq A$，则称集合 $A$ 与 $B$ 相等，记作 $A = B$。

定理 1.1（子集的基本性质） 设 $A, B, C$ 是任意集合，则：

1. 自反性：$A \subseteq A$
2. 反对称性：若 $A \subseteq B$ 且 $B \subseteq A$，则 $A = B$
3. 传递性：若 $A \subseteq B$ 且 $B \subseteq C$，则 $A \subseteq C$
4. 空集是任何集合的子集：$\varnothing \subseteq A$

1.3 集合的运算

定义 1.8（并集） 集合 $A$ 与 $B$ 的并集定义为： $A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}$

定义 1.9（交集） 集合 $A$ 与 $B$ 的交集定义为： $A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}$

若 $A \cap B = \varnothing$，则称 $A$ 与 $B$ 不相交。

定义 1.10（差集） 集合 $A$ 与 $B$ 的差集定义为： $A \setminus B = \{x \mid x \in A \text{ 且 } x \notin B\}$

定义 1.11（补集） 设 $U$ 为全集，$A \subseteq U$，则 $A$ 的补集定义为： $\overline{A} = U \setminus A = \{x \mid x \in U \text{ 且 } x \notin A\}$

定理 1.2（德摩根律） 设 $A, B$ 是全集 $U$ 的子集，则：

1. $\overline{A \cup B} = \overline{A} \cap \overline{B}$
2. $\overline{A \cap B} = \overline{A} \cup \overline{B}$

1.4 幂集

定义 1.12（幂集） 集合 $A$ 的所有子集组成的集合称为 $A$ 的幂集，记作 $\mathcal{P}(A)$ 或 $2^A$，即： $\mathcal{P}(A) = \{X \mid X \subseteq A\}$

定理 1.3（幂集的基数） 若 $|A| = n$（即 $A$ 含有 $n$ 个元素），则： $|\mathcal{P}(A)| = 2^n$

1.5 加法原理

定理 1.4（加法原理，分类计数原理） 设完成一件事有 $k$ 类不同的方法，第 $i$ 类方法有 $n_i$ 种具体的方式（$i = 1, 2, \ldots, k$），且任何两类方法之间没有公共的方式（即各类方法互斥），则完成这件事共有： $N = n_1 + n_2 + \cdots + n_k = \sum_{i=1}^{k} n_i$ 种不同的方法。

1.6 乘法原理

定理 1.5（乘法原理，分步计数原理） 设完成一件事需要 $k$ 个步骤，第 $i$ 步有 $n_i$ 种不同的方法（$i = 1, 2, \ldots, k$），且各步的选择相互独立，则完成这件事共有： $N = n_1 \times n_2 \times \cdots \times n_k = \prod_{i=1}^{k} n_i$ 种不同的方法。

2. 组合数排列数与恒等式

2.1 排列数

定义（排列） 从 $n$ 个不同元素中取出 $k$ 个元素（$0 \leq k \leq n$），按照一定顺序排成一列，称为从 $n$ 个元素中取 $k$ 个元素的一个排列。所有不同排列的个数称为排列数，记作 $P(n,k)$ 或 $A_n^k$。

公式： $P(n,k) = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdots(n-k+1)$

特例：当 $k = n$ 时，$P(n,n) = n!$，即 $n$ 个元素的全排列数为 $n!$。

2.2 组合数

定义（组合） 从 $n$ 个不同元素中取出 $k$ 个元素（$0 \leq k \leq n$），不考虑顺序，称为从 $n$ 个元素中取 $k$ 个元素的一个组合。所有不同组合的个数称为组合数，记作 $\binom{n}{k}$ 或 $C_n^k$。

公式： $\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}$

约定：当 $k < 0$ 或 $k > n$ 时，规定 $\binom{n}{k} = 0$。

性质 1：边界值 $\binom{n}{0} = \binom{n}{n} = 1, \quad \binom{n}{1} = \binom{n}{n-1} = n$

性质 2：对称性 $\binom{n}{k} = \binom{n}{n-k}$

2.3 帕斯卡恒等式

定理（Pascal’s Identity）：对于整数 $n \geq 1$ 和 $0 \leq k \leq n$，有： $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

组合证明：考虑集合 $S = \{1, 2, \ldots, n\}$，将所有 $k$ 元子集按是否包含元素 $n$ 分成两类：

• 包含元素 $n$ 的 $k$ 元子集：需要从其余 $n-1$ 个元素中选 $k-1$ 个，个数为 $\binom{n-1}{k-1}$
• 不包含元素 $n$ 的 $k$ 元子集：需要从其余 $n-1$ 个元素中选 $k$ 个，个数为 $\binom{n-1}{k}$

由加法原理即得结论。

2.4 范德蒙德恒等式

定理（Vandermonde’s Identity）：对于非负整数 $m, n, r$（其中 $r \leq \min\{m,n\}$），有： $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

组合证明：考虑两个不相交的集合 $A$ 和 $B$，其中 $|A| = m$，$|B| = n$。

• 左边：$\binom{m+n}{r}$ 表示从 $A \cup B$ 中选取 $r$ 个元素的方法数。
• 右边：按从 $A$ 中选取的元素个数 $k$ 分类，方法数为 $\binom{m}{k}\binom{n}{r-k}$

推论 1（Chu-Vandermonde）：令 $m = n = r$，得： $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$

2.5 二项式定理

定理：对于任意实数 $x, y$ 和正整数 $n$，有： $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

推论 1：令 $x = y = 1$，得： $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

推论 2：令 $x = 1, y = -1$，得： $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \quad (n \geq 1)$

2.6 曲棍球棒恒等式（Hockey-Stick Identity）

定理：对于 $0 \leq r \leq n$： $\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}$

2.7 插板法（Stars and Bars）

问题：将 $n$ 个相同的小球放入 $m$ 个不同的盒子，允许空盒，有多少种方法？

定理：方法数为： $\binom{n+m-1}{m-1} = \binom{n+m-1}{n}$

不允许空盒的情形：方法数为 $\binom{n-1}{m-1}$（要求 $n \geq m$）

2.8 算两次原理（Double Counting）

原理：对同一组对象用两种不同方式计数，所得结果相等。

例题（证明 $k\binom{n}{k} = n\binom{n-1}{k-1}$）：

算两次对象：从 $n$ 人中选 $k$ 人委员会并指定其中一人为主席的方案。

• 先选委员会再选主席：$k\binom{n}{k}$
• 先选主席再选委员会：$n\binom{n-1}{k-1}$

故 $k\binom{n}{k} = n\binom{n-1}{k-1}$。

2.9 双射计数（Bijective Proof）

原理：若存在集合 $A$ 到集合 $B$ 的双射（一一对应），则 $|A| = |B|$。

例题（组合数对称性）：定义 $f: A \to B$ 为 $f(S) = \{1,\ldots,n\} \setminus S$（取补集），这是双射，故 $\binom{n}{k} = \binom{n}{n-k}$。

3. 偏序集、容斥原理与莫比乌斯变换

3.1 偏序集基础

定义（偏序关系）：设 $P$ 是一个集合，$R$ 是 $P$ 上的二元关系。若 $R$ 满足：

1. 自反性：$\forall x \in P, x \leq x$
2. 反对称性：$\forall x, y \in P$，若 $x \leq y$ 且 $y \leq x$，则 $x = y$
3. 传递性：$\forall x, y, z \in P$，若 $x \leq y$ 且 $y \leq z$，则 $x \leq z$

则称 $R$ 为 $P$ 上的偏序关系，$(P, \leq)$ 称为偏序集（poset）。

例 1（幂集上的包含关系）：设 $S$ 是 $n$ 元集，$P = 2^S$ 是 $S$ 的幂集。定义 $A \leq B$ 当且仅当 $A \subseteq B$，则 $(2^S, \subseteq)$ 是偏序集，称为布尔格 $B_n$。

例 2（整除关系）：设 $P = \mathbb{Z}^+$，定义 $a \leq b$ 当且仅当 $a \mid b$，则 $(\mathbb{Z}^+, \mid)$ 是偏序集。

3.2 链与反链

定义（链）：偏序集 $(P, \leq)$ 的子集 $C \subseteq P$ 称为链，若 $C$ 中任意两个元素都可比较。

定义（反链）：子集 $A \subseteq P$ 称为反链，若 $A$ 中任意两个不同元素都不可比较。

3.3 Sperner 定理

定理（Sperner, 1928）：设 $S$ 是 $n$ 元集，$B_n = 2^S$ 是布尔格。则 $B_n$ 中最大反链的大小为 $\binom{n}{\lfloor n/2 \rfloor}$。

证明（LYM不等式）：设 $\mathcal{F} \subseteq B_n$ 是反链，则： $\sum_{A \in \mathcal{F}} \frac{1}{\binom{n}{|A|}} \leq 1$

由于对所有 $k$，$\binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor}$，故： $|\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor}$

3.4 容斥原理（PIE）

定理（容斥原理）：设 $A_1, A_2, \ldots, A_n$ 是有限全集 $U$ 的子集，则

$\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}|$

等价地，补集的交： $\left| \bigcap_{i=1}^n A_i^c \right| = |U| - \sum_{i} |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| + \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|$

应用 1：错排问题

错排数 $D_n$（无不动点的排列数）： $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$

应用 2：欧拉函数

若 $n = p_1^{a_1} \cdots p_r^{a_r}$，则： $\varphi(n) = n \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right)$

3.5 莫比乌斯反演

定义（莫比乌斯函数）：偏序集上的莫比乌斯函数 $\mu$ 定义为：

• $\mu(x, x) = 1$
• 对 $x < y$：$\mu(x, y) = -\sum_{x \leq z < y} \mu(x, z)$

定理（莫比乌斯反演）：设 $(P, \leq)$ 是局部有限偏序集，$f, g: P \to \mathbb{R}$。若 $g(y) = \sum_{x \leq y} f(x)$，则： $f(y) = \sum_{x \leq y} \mu(x, y) g(x)$

例 1（布尔格）：$\mu(A, B) = (-1)^{|B| - |A|}$

例 2（整除格）：若 $d \mid m$，则 $\mu(d, m) = \mu(m/d)$（经典数论莫比乌斯函数）

经典莫比乌斯反演：设 $f, g: \mathbb{Z}^+ \to \mathbb{R}$。

• 若 $g(n) = \sum_{d|n} f(d)$，则 $f(n) = \sum_{d|n} \mu(d) g(n/d)$

4. 鸽巢原理及其变种

4.1 基本鸽巢原理

定理 4.1（简单形式） 如果将 $n+1$ 个物体放入 $n$ 个盒子中，那么至少有一个盒子包含不少于 $2$ 个物体。

定理 4.2（一般形式） 如果将 $m$ 个物体放入 $n$ 个盒子中，那么至少有一个盒子包含不少于 $\lceil m/n \rceil$ 个物体。

4.2 Erdős–Szekeres 定理

定理（Erdős–Szekeres） 任意 $n^2+1$ 个不同实数构成的序列中，必存在长度为 $n+1$ 的单调子列（单调递增或单调递减）。

4.3 Dirichlet 逼近定理

定理（Dirichlet） 对于任意实数 $\alpha$ 和正整数 $n$，存在整数 $p, q$，其中 $1 \leq q \leq n$，使得： $\left|q\alpha - p\right| < \frac{1}{n}$

等价地：$\left|\alpha - \frac{p}{q}\right| < \frac{1}{nq} \leq \frac{1}{q^2}$

4.4 Ramsey 理论简介

定义（Ramsey 数） $R(s, t)$ 是最小的正整数 $n$，使得对完全图 $K_n$ 的边进行任意红蓝二染色后，必存在红色的 $K_s$ 或蓝色的 $K_t$。

定理：$R(3, 3) = 6$

5. 生成函数

5.1 普通生成函数（OGF）

定义：设 $\{a_n\}_{n=0}^{\infty}$ 是一个数列，其普通生成函数定义为： $G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$

乘法运算（卷积）： $G(x) \cdot H(x) = \sum_{n=0}^{\infty} c_n x^n, \quad c_n = \sum_{k=0}^{n} a_k b_{n-k}$

常见序列：

• 几何级数：$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$
• 二项式：$(1+x)^m = \sum_{n=0}^{m} \binom{m}{n} x^n$
• 负二项式：$\frac{1}{(1-x)^k} = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$

卡特兰数的生成函数： $C(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1-\sqrt{1-4x}}{2x}$

5.2 指数生成函数（EGF）

定义：设 $\{a_n\}_{n=0}^{\infty}$ 是一个数列，其指数生成函数定义为： $E(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = a_0 + a_1 \frac{x}{1!} + a_2 \frac{x^2}{2!} + \cdots$

乘积公式（二项卷积）： $E(x) \cdot F(x) = \sum_{n=0}^{\infty} c_n \frac{x^n}{n!}, \quad c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$

5.3 贝尔数的指数生成函数

贝尔数 $B_n$ 表示 $n$ 元集合的划分数。

定理：贝尔数的指数生成函数为： $B(x) = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$

5.4 狄利克雷生成函数（DGF）

定义：设 $\{a_n\}_{n=1}^{\infty}$ 是一个数列，其狄利克雷生成函数定义为： $F(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$

黎曼ζ函数： $\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}$

狄利克雷卷积： $(f * g)(n) = \sum_{d|n} f(d) \cdot g\left(\frac{n}{d}\right)$

5.5 分拆数的生成函数

定理（Euler）： $P(x) = \sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$

五边形数定理： $\prod_{k=1}^{\infty} (1-x^k) = \sum_{m=-\infty}^{\infty} (-1)^m x^{m(3m-1)/2}$

6. 特殊计数序列

6.1 卡特兰数（Catalan Numbers）

定义： $C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

前几项：$C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42$

递推关系： $C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$

组合解释：

• Dyck路径（从 $(0,0)$ 到 $(2n,0)$，不降到 $x$ 轴下方）
• $n$ 对括号的正确匹配
• $n+1$ 个叶子的满二叉树
• $(n+2)$ 边形的三角剖分

6.2 Dyck 路径

定义：从 $(0,0)$ 到 $(2n,0)$ 的格路，每步 $(1,1)$ 或 $(1,-1)$，不降到 $x$ 轴下方。

数目：$n$ 阶 Dyck 路径的数目等于第 $n$ 个卡特兰数 $C_n$。

Narayana数 $N(n,k)$ 计数恰有 $k$ 个峰的 $n$ 阶 Dyck 路径： $N(n,k) = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}$

6.3 斯特林数（Stirling Numbers）

第一类斯特林数 $c(n,k)$（或 $\left[{n \atop k}\right]$）：表示 $n$ 个元素恰好分成 $k$ 个轮换的排列数。

递推关系： $c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k)$

第二类斯特林数 $S(n,k)$（或 $\left\{{n \atop k}\right\}$）：将 $n$ 个元素的集合划分为 $k$ 个非空子集的方式数。

递推关系： $S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)$

显式公式： $S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$

与幂的关系： $x^n = \sum_{k=0}^{n} S(n,k) (x)_k$ 其中 $(x)_k = x(x-1)\cdots(x-k+1)$ 为下降阶乘。

6.4 施罗德数（Schröder Numbers）

大施罗德数 $R_n$：从 $(0,0)$ 到 $(2n,0)$ 的格路，每步 $(1,1)$、$(1,-1)$ 或 $(2,0)$，始终不低于 $x$ 轴。

前几项：$R_0 = 1, R_1 = 2, R_2 = 6, R_3 = 22, R_4 = 90$

生成函数： $R(x) = \frac{1-x-\sqrt{1-6x+x^2}}{2x}$

与卡特兰数的关系： $R_n = \sum_{k=0}^{n} \binom{n}{k} C_k$

6.5 分拆数（Partition Numbers）

定义：$p(n)$ 计数 $n$ 的整数分拆个数（不计顺序）。

递推公式（由五边形数定理）： $p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + \cdots$

其中符号按 $+,+,-,-,+,+,-,-,\ldots$ 周期变化。

7. 波利亚计数原理

7.1 群论基础

定义 7.1.1（群） 设 $G$ 是一个非空集合，$\cdot$ 是 $G$ 上的二元运算。如果满足以下条件，则称 $(G, \cdot)$ 为一个群：

1. 封闭性：对于任意 $a, b \in G$，有 $a \cdot b \in G$；
2. 结合律：对于任意 $a, b, c \in G$，有 $(a \cdot b) \cdot c = a \cdot (b \cdot c)$；
3. 单位元：存在 $e \in G$，使得对任意 $a \in G$，有 $e \cdot a = a \cdot e = a$；
4. 逆元：对于任意 $a \in G$，存在 $a^{-1} \in G$，使得 $a \cdot a^{-1} = a^{-1} \cdot a = e$。

例 7.1.1（对称群 $S_n$） 设 $X = \{1, 2, \ldots, n\}$，$S_n$ 是 $X$ 上所有置换构成的集合。$(S_n, \circ)$ 构成群，称为 $n$ 次对称群，$|S_n| = n!$。

例 7.1.2（循环群 $C_n$） $C_n = \{e, \rho, \rho^2, \ldots, \rho^{n-1}\}$，其中 $\rho$ 表示绕中心逆时针旋转 $\frac{2\pi}{n}$，$|C_n| = n$。

例 7.1.3（二面体群 $D_n$） 正 $n$ 边形的对称群，包含 $n$ 个旋转和 $n$ 个反射，$|D_n| = 2n$。

例 7.1.4（立方体旋转群） 立方体的旋转对称群有24个元素：

• 恒等旋转：1个
• 绕对面中心轴旋转 $90°, 180°, 270°$：$3 \times 3 = 9$个
• 绕对边中点轴旋转 $180°$：6个
• 绕对角顶点轴旋转 $120°, 240°$：$4 \times 2 = 8$个

7.2 置换的循环分解

定义 7.2.1（轮换） 设 $\sigma \in S_n$，如果存在互不相同的元素 $i_1, i_2, \ldots, i_k$ 使得 $\sigma(i_1) = i_2, \sigma(i_2) = i_3, \ldots, \sigma(i_k) = i_1$ 则称 $\sigma$ 为**$k$-轮换**，记作 $(i_1\, i_2\, \cdots\, i_k)$。

定理 7.2.2（循环分解定理） 任意置换 $\sigma \in S_n$ 都可以唯一地表示为不相交轮换的乘积。

定义 7.2.3（轮换指标） 设 $G$ 是 $S_n$ 的子群，$G$ 的轮换指标定义为： $Z_G(x_1, x_2, \ldots, x_n) = \frac{1}{|G|} \sum_{g \in G} x_1^{c_1(g)} x_2^{c_2(g)} \cdots x_n^{c_n(g)}$ 其中 $c_k(g)$ 表示置换 $g$ 中 $k$-轮换的个数。

例 7.2.4（循环群 $C_4$ 的轮换指标） 设 $\rho = (1\, 2\, 3\, 4)$，则 $C_4 = \{e, \rho, \rho^2, \rho^3\}$。

因此： $Z_{C_4}(x_1, x_2, x_3, x_4) = \frac{1}{4}(x_1^4 + x_2^2 + 2x_4)$

例 7.2.5（二面体群 $D_4$ 的轮换指标） $D_4$ 包含 $C_4$ 的4个元素，加上4个反射：

• 关于对角顶点的反射：$(1\, 2)(3\, 4)$ 和 $(1\, 4)(2\, 3)$，对应 $x_2^2$
• 关于对边中点的反射：$(2\, 4)$ 和 $(1\, 3)$，对应 $x_1^2 x_2$

因此： $Z_{D_4}(x_1, x_2, x_3, x_4) = \frac{1}{8}(x_1^4 + 2x_1^2 x_2 + 3x_2^2 + 2x_4)$

7.3 群作用

定义 7.3.1（群作用） 设 $G$ 是群，$X$ 是非空集合。映射 $G \times X \to X$，记作 $g \cdot x$，满足：

1. $e \cdot x = x$ 对所有 $x \in X$ 成立；
2. $(gh) \cdot x = g \cdot (h \cdot x)$ 对所有 $g, h \in G$，$x \in X$ 成立。

定义 7.3.2（轨道） $x \in X$ 的轨道：$G \cdot x = \{g \cdot x : g \in G\}$

定义 7.3.3（稳定子） $x \in X$ 的稳定子：$G_x = \{g \in G : g \cdot x = x\}$

定义 7.3.4（不动点集） 设 $g \in G$，$g$ 的不动点集：$X^g = \{x \in X : g \cdot x = x\}$

定理 7.3.5（轨道-稳定子定理） $|G \cdot x| = \frac{|G|}{|G_x|}$

7.4 伯恩赛德引理

定理 7.4.1（Burnside’s Lemma） 设有限群 $G$ 作用于有限集 $X$，则轨道的个数为： $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$

证明：考虑集合 $S = \{(g, x) \in G \times X : g \cdot x = x\}$。

方法1：$|S| = \sum_{g \in G} |X^g|$

方法2：$|S| = \sum_{x \in X} |G_x| = \sum_{O \in X/G} |O| \cdot \frac{|G|}{|O|} = |X/G| \cdot |G|$

因此 $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$。

应用 7.4.2（二色项链问题） 用2种颜色给正 $n$ 边形的顶点染色，考虑旋转等价：

对 $g = \rho^k$，$f \in X^g$ 当且仅当 $f$ 在 $\rho^k$ 的每个轮换上取常值。$\rho^k$ 的轮换数为 $\gcd(n,k)$，因此 $|X^{\rho^k}| = 2^{\gcd(n,k)}$。

由伯恩赛德引理： $|X/C_n| = \frac{1}{n} \sum_{k=0}^{n-1} 2^{\gcd(n,k)} = \frac{1}{n} \sum_{d|n} \varphi\left(\frac{n}{d}\right) 2^d$

当 $n = 6$ 时：$|X/C_6| = \frac{1}{6}(64 + 2 + 4 + 8 + 4 + 2) = 14$

应用 7.4.3（立方体面染色） 用2种颜色给立方体的面染色，考虑旋转等价：

轨道数 = $\frac{1}{24}(64 + 48 + 48 + 32 + 48) = 10$

7.5 波利亚计数定理

定理 7.5.1（Pólya Enumeration Theorem） 用 $m$ 种颜色对 $n$ 个对象进行染色的不同方案数（在群 $G$ 作用下）等于轮换指标中代入 $x_k = m$： $|X/G| = Z_G(m, m, \ldots, m) = \frac{1}{|G|}\sum_{g \in G} m^{c(g)}$

立方体面染色的轮换指标： $Z_G = \frac{1}{24}(x_1^6 + 6x_1^2x_4 + 3x_1^2x_2^2 + 8x_3^2 + 6x_2^3)$

用 $m$ 种颜色染色的方案数： $\frac{1}{24}(m^6 + 3m^4 + 12m^3 + 8m^2)$

当 $m = 2$ 时：$\frac{240}{24} = 10$

当 $m = 3$ 时：$\frac{1368}{24} = 57$

7.6 加权形式的波利亚定理

定理 7.6.1（加权波利亚计数定理） 设 $a_k = \sum_{c \in C} w(c)^k$ 是颜色 $k$ 次幂的权重和，则模式清单为： $PI(G) = Z_G(a_1, a_2, \ldots, a_n)$

例 7.6.2（立方体二色染色，按颜色数生成）设颜色为红(r)和蓝(b)：

$PI = Z_G(r+b, r^2+b^2, r^3+b^3, r^4+b^4)$

展开后： $PI = r^6 + r^5b + 2r^4b^2 + 2r^3b^3 + 2r^2b^4 + rb^5 + b^6$

其中 $r^k b^{6-k}$ 的系数表示有 $k$ 个红面的不同染色方案数。验证：$1+1+2+2+2+1+1 = 10$。

8. 图论基础

8.1 基本定义

定义（图）：图 $G = (V, E)$，其中 $V$ 是顶点集，$E$ 是边集。

有向图：边是有序对 $(u, v)$ 无向图：边是无序对 $\{u, v\}$ 简单图：无自环、无重边

完全图 $K_n$：$n$ 个顶点，每对顶点间都有边。$|E(K_n)| = \binom{n}{2}$

超立方体 $Q_n$：顶点为 $\{0,1\}^n$，边连接汉明距离为 1 的顶点。$|V| = 2^n, |E| = n \cdot 2^{n-1}$

环图 $C_n$：$n$ 个顶点排成环 路径 $P_n$：$n$ 个顶点排成链

8.2 度数与握手定理

定义：顶点 $v$ 的度数 $\deg(v)$ 是与 $v$ 关联的边数。

定理 8.1（点握手定理）： $\sum_{v \in V} \deg(v) = 2|E|$

推论：奇度顶点的个数必为偶数。

定理 8.2（面握手定理，平面图）： $\sum_{f \in F} \deg(f) = 2|E|$

8.3 图的表示

邻接矩阵 $A$：$a_{ij} = 1$ 若 $v_i v_j \in E$，否则为 0。

关联矩阵 $B$（无向图）：$b_{ij} = 1$ 若顶点 $v_i$ 与边 $e_j$ 关联。

邻接表：为每个顶点维护邻居列表。

8.4 匹配与 Hall 定理

定义：匹配 $M \subseteq E$ 是边集，其中任意两条边无公共端点。 完美匹配：饱和所有顶点的匹配。

二分图：顶点集可划分为 $X, Y$，使得每条边一端在 $X$，一端在 $Y$。

定理 8.3（Hall 婚姻定理）：二分图 $G = (X, Y; E)$ 存在完美匹配当且仅当对所有 $S \subseteq X$，有 $|N(S)| \geq |S|$。

8.5 图同态与同构

图同态：映射 $\varphi: V_G \to V_H$ 保持邻接关系。

图同构：双射 $\varphi: V_G \to V_H$ 使得 $uv \in E_G \iff \varphi(u)\varphi(v) \in E_H$。

自同构群 $\text{Aut}(G)$：图 $G$ 到自身的所有同构构成的群。

8.6 欧拉路与哈密顿路

欧拉定理：连通图 $G$ 存在：

• 欧拉回路 $\iff$ 所有顶点度数为偶数
• 欧拉路（非回路）$\iff$ 恰有两个顶点度数为奇数

超立方体的哈密顿路：

定理 8.4：对 $n \geq 2$，超立方体 $Q_n$ 存在哈密顿回路。

证明（格雷码）：$n$ 位格雷码是 $\{0,1\}^n$ 的排列，相邻码字恰有一位不同。格雷码对应 $Q_n$ 中的哈密顿路，且首尾也相邻，形成哈密顿回路。

格雷码构造：$G_1 = (0, 1)$，$G_{n+1} = (0G_n, 1\overline{G_n})$