Part 2 组合计数基础#

计数基础#

乘法规则 (Multiplication Rule)#

定义：假定一个过程可以分解为两个任务。如果完成第一个任务有 $n_1$ 种方式，在第一个任务完成之后有 $n_2$ 种方式完成第二个任务，那么完成这个过程就有 $n_1 \cdot n_2$ 种方法。

示例：长度为七的位串有多少种？ 解答：由于每个比特位可以是 0 或 1，所以答案是 $2^7 = 128$。

集合论描述：如果 $A_1, A_2, \dots, A_m$ 是有限集，那么这些集合的笛卡尔积中的元素数量是每个集合元素数量的乘积。 $|A_1 \times A_2 \times \dots \times A_m| = |A_1| \cdot |A_2| \cdot \dots \cdot |A_m|$

加法规则 (Addition Rule)#

定义：如果完成一项任务有 $n_1$ 种方式或 $n_2$ 种方式，并且 $n_1$ 和 $n_2$ 的方式之间没有重叠，那么完成任务的方式总共有 $n_1 + n_2$ 种。

示例：数学系选一名代表，有 37 名教师和 83 名学生，没有人既是教师又是学生。 解答：$37 + 83 = 120$ 种。

集合论描述：当 A 和 B 是不相交集合时，$|A \cup B| = |A| + |B|$。

减法规则 (Subtraction Rule) / 容斥原理#

定义：如果完成某项任务有 $n_1$ 种方式或 $n_2$ 种方式，那么完成任务的总方式数量为 $n_1 + n_2$ 减去以两类方式中执行这个任务相同的方式。

$$|A \cup B| = |A| + |B| - |A \cap B|$$

示例：长度为八的二进制串有多少个要么以 1 开始，要么以 00 结束？ 解答：

• 以 1 开头：$2^7 = 128$
• 以 00 结尾：$2^6 = 64$
• 既以 1 开头又以 00 结尾：$2^5 = 32$
• 总数：$128 + 64 - 32 = 160$

除法规则 (Division Rule)#

定义：如果某项任务可以通过 $n$ 种方式完成，且对于每一种方式 $w$，正好有 $d$ 种方式对应于方式 $w$，那么完成这项任务的方式总数为 $n/d$。

示例：围绕圆桌有多少种不同的方式排列四个人？（旋转视为相同） 解答：

• 直线排列有 $4! = 24$ 种。
• 每个圆桌排列对应 4 种直线排列（旋转）。
• 结果：$24 / 4 = 6$。

鸽巢原理 (Pigeonhole Principle)#

基础鸽巢原理#

定理：如果 $k$ 是一个正整数，并且将 $k+1$ 个物体放入 $k$ 个盒子中，那么至少有一个盒子包含 2 个或更多的物体。

推论：从一个具有 $k+1$ 个元素的集合到一个具有 $k$ 个元素的集合的函数 $f$ 不是一对一函数。

示例：在任意 367 人的群体中，必定至少有两人有相同的生日（一年 366 天）。

广义鸽巢原理#

定理：如果将 $N$ 个物体放入 $k$ 个盒子中，则至少有一个盒子包含至少 $\lceil N/k \rceil$ 个物体。

示例：从 52 张牌中至少选多少张才能保证有 3 张同花色？ 解答： $k=4$ (花色)，要求 $\lceil N/4 \rceil \ge 3$。 最小的 $N$ 为 $2 \times 4 + 1 = 9$。

排列 (Permutations)#

定义#

一组不同对象的排列是这些对象的有序排列。具有 $n$ 个元素的集合的 $r$-排列的数量记为 $P(n,r)$。

公式#

$$P(n, r) = n(n-1)(n-2)\dots(n-r+1) = \frac{n!}{(n-r)!}$$

示例：推销员访问 8 个城市，起点固定，其余 7 个任意顺序。 解答：$P(7,7) = 7! = 5040$。

组合 (Combinations)#

定义#

集合元素的一个 $r$-组合是从集合中无序选择 $r$ 个元素。记作 $C(n,r)$ 或 $\binom{n}{r}$。

公式与定理#

$$C(n, r) = \frac{n!}{r!(n-r)!}$$

推论：$C(n, r) = C(n, n-r)$。

组合证明 (Combinatorial Proof)：

• 双计数证明：证明恒等式两边以不同方式计算相同对象。
• 双射证明：展示两边计数的对象集合间存在双射。

二项式系数与恒等式#

二项式定理 (Binomial Theorem)#

设 $x$ 和 $y$ 为变量，$n$ 为非负整数。

$$(x+y)^n = \sum_{j=0}^{n} \binom{n}{j} x^{n-j} y^j$$

示例：求 $(2x - 3y)^{25}$ 中 $x^{12}y^{13}$ 的系数。 解答：令 $j=13$，系数为 $\binom{25}{13} 2^{12} (-3)^{13}$。

重要恒等式#

1. 总子集数：$\sum_{k=0}^{n} \binom{n}{k} = 2^n$（令 $x=1, y=1$）。
2. 帕斯卡恒等式 (Pascal’s Identity)： $$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$ 这是帕斯卡三角形及其递推关系的理论基础。

广义排列和组合#

带重复的排列#

定理：允许重复的情况下，从 $n$ 个对象的集合中选取 $r$ 个对象的排列数为 $n^r$。

带重复的组合#

定理：当允许元素重复时，从一个包含 $n$ 个元素的集合中选择 $r$ 个元素的组合数是 $C(n+r-1, r) = C(n+r-1, n-1)$

证明思路：隔板法（Stars and Bars）。$r$ 个物体（星号）和 $n-1$ 个隔板（竖线）。

示例：方程 $x_1 + x_2 + x_3 = 11$ 的非负整数解的个数。 解答：$n=3, r=11$。$C(3+11-1, 11) = C(13, 11) = C(13, 2) = 78$。

具有不可区别物体的排列#

定理：设类型 1 的相同物体有 $n_1$ 个，…，类型 $k$ 的相同物体有 $n_k$ 个，总数 $n = n_1 + \dots + n_k$。则不同排列数为：

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

示例：重排单词 “SUCCESS”。 解答：总数 7，S 有 3 个，C 有 2 个，U 有 1 个，E 有 1 个。

$$\frac{7!}{3!2!1!1!} = 420$$

把物体放入盒子#

母函数 (Generating Functions)#

普通母函数 (Ordinary Generating Functions)#

定义：对于序列 $a_0, a_1, a_2, \dots$，函数 $G(x) = \sum_{k=0}^{\infty} a_k x^k$ 称为该序列的母函数。 应用：主要用于解决组合问题（选取物品，顺序无关）。

示例：两个骰子掷出 $n$ 点的方法数。 解答：

$$(x^1 + x^2 + \dots + x^6)(x^1 + x^2 + \dots + x^6)$$

展开式中 $x^n$ 的系数即为方法数。

整数拆分：

• 将整数 $N$ 无序拆分成 $\{a_1, a_2, \dots, a_n\}$ 的和。
• 不允许重复：$G(x) = (1+x^{a_1})(1+x^{a_2})\dots$
• 允许重复：$G(x) = (1+x^{a_1}+x^{2a_1}+\dots)(1+x^{a_2}+x^{2a_2}+\dots)\dots = \frac{1}{(1-x^{a_1})(1-x^{a_2})\dots}$

定理：整数拆分成不同整数的和的拆分数（不允许重复）等于拆分成奇数的拆分数（允许重复）。

指数型母函数 (Exponential Generating Functions)#

定义：对于序列 $a_0, a_1, a_2, \dots$，函数 $G_e(x) = \sum_{k=0}^{\infty} a_k \frac{x^k}{k!}$ 称为该序列的指数型母函数。 应用：主要用于解决排列问题（选取物品，顺序有关）。

基本构建块： 从多重集中取 $r$ 个排列，若某元素限制出现次数：

• 出现 0 次或 1 次：$(1 + \frac{x}{1!})$
• 出现任意次：$(1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots) = e^x$
• 出现偶数次：$\frac{e^x + e^{-x}}{2}$
• 出现奇数次：$\frac{e^x - e^{-x}}{2}$

示例：由 1, 3, 5, 7, 9 组成的 $n$ 位数，其中 3, 7 出现偶数次，其他不限。 解答：

$$G_e(x) = \left(\frac{e^x + e^{-x}}{2}\right)^2 (e^x)^3 = \frac{1}{4}(e^{2x} + 2 + e^{-2x})e^{3x} = \frac{1}{4}(e^{5x} + 2e^{3x} + e^x)$$

展开后 $x^n/n!$ 的系数即为答案：

$$a_n = \frac{1}{4}(5^n + 2 \cdot 3^n + 1)$$