第五章 - 计数

约 1919 个字预计阅读时间 6 分钟

计数基础

基本的计数原则

基本的计数原则有两个，即乘积法则和求和法则。

乘积法则 (product rule)：如果一个过程可以被分解成两个任务，完成第一个任务有 \(n_{1}\) 种方式，在第一个任务完成后有 \(n_{2}\) 种方式完成第二个任务，那么完成整个任务共有 \(n_{1} n_{2}\) 种方式。
求和法则 (sum rule)：如果完成第一项任务有 \(n_{1}\) 种方式，完成第二项任务有 \(n_{2}\) 种方式，并且这些任务不能同时执行，那么完成第一项或第二项任务有 \(n_{1} + n_{2}\) 种方式。

减法法则

减法法则 (subtraction rule)，也即集合容斥原理 (inclusion-exclusion for sets)，指如果一个任务或者可以通过 \(n_{1}\) 种方法执行，或者可以通过 \(n_{2}\) 种另一类方法执行，那么执行这个任务的方法数是 \(n_{1} + n_{2}\) 减去两类方法中相同的方法。

其集合表述为，令 \(A_{1}\) 和 \(A_{2}\) 是集合，\(|A_{1}|\) 是从 \(A_{1}\) 选择一个元素的方法数，\(|A_{2}|\) 是从 \(A_{2}\) 选择一个元素的方法数，那么 \(|A_{1} \cap A_{2}|\) 表示从 \(A_{1}\) 和 \(A_{2}\) 中同时选择一个元素的方法数，\(|A_{1} \cup A_{2}|\) 表示从 \(A_{1}\) 或者 \(A_{2}\) 中选择一个元素的方法数。且满足

\[|A_{1} \cup A_{2}| = |A_{1}| + |A_{2}| - |A_{1} \cap A_{2}|\]

除法法则

除法法则 (division rule) 是指，如果一个任务能由一个可以用 \(n\) 种方式完成的过程实现，而对于每种完成任务的方式 \(w\)，在 \(n\) 种方式中正好有 \(d\) 种与之对应，那么完成这个任务的方法数为 \(\frac{n}{d}\)。

其集合表述为，如果一个有限集 \(A\) 是 \(n\) 个有 \(d\) 个元素的互斥集合的并集，那么 \(n = \frac{|A|}{d}\)。

鸽巢原理

我们直接介绍广义鸽巢原理 (the generalised pigeonhole principle)：如果 \(N\) 只鸽子关入 \(k\) 个笼子，那么至少有一个笼子包含了至少 \(\lceil \frac{N}{k} \rceil\) 只鸽子。

鸽巢原理是计数中非常重要的定理，其正确性是显然的。应用鸽巢原理解决问题的关键在于正确地构造「鸽子」和「笼子」。

排列和组合

我们给出本课程中对于排列和组合的记法：

具有 \(n\) 个不同元素的集合的 \(r\) 排列数是 \(P(n, r) = n (n - 1) (n - 2) \cdots (n - r + 1) = \frac{n!}{(n - r)!}\)
具有 \(n\) 个不同元素的集合的 \(r\) 组合数是 \(C(n, r) = \frac{n!}{r! (n - r)!}\)，也记作 \({{n} \choose {r}}\)。

排列和组合应当是读者在数学学习中熟悉的内容，关于其数学性质此处就不过多展开，读者可以参阅组合数学相关教科书或网络资料进一步学习。

二项式系数和恒等式

二项式定理

二项式定理：设 \(x\) 和 \(y\) 是变量，\(n\) 是非负整数，则

\[(x + y)^{n} = \sum_{k = 0}^{n} {{n} \choose {k}} x^{n - k} y^{k}\]

由二项式定理可以推出的几个常见恒等式有：

\(\sum_{k = 0}^{n} {{n} \choose {k}} = 2^{n}\)
\(\sum_{k = 0}^{n} (-1)^{k} {{n} \choose {k}} = 0\)
\(\sum_{k = 0}^{n} m^{k} {{n} \choose {k}} = (m + 1)^{n}\)

详细证明请读者参阅组合数学相关教科书或网络资料。

帕斯卡恒等式

帕斯卡恒等式：设 \(n\) 和 \(k\) 是满足 \(n \geq k\) 的正整数，则有

\[{{n + 1} \choose {k}} = {{n} \choose {k - 1}} + {{n} \choose {k}}\]

其它二项式系数恒等式

范德蒙德恒等式：设 \(m, n\) 和 \(r\) 是非负整数，其中 \(r\) 不超过 \(m\) 或 \(n\)，则有

\[{{m + n} \choose {r}} = \sum_{k = 0}^{r} {{m} \choose {r - k}} {{n} \choose {k}}\]

一个常见的由范德蒙德恒等式推出的恒等式是：

\({{2n} \choose {n}} = \sum_{k = 0}^{n} {{n} \choose {k}}^{2}\)

另一个重要的组合恒等式为：设 \(n\) 和 \(r\) 是非负整数，\(r \leq n\)，那么

\[{{n + 1} \choose {r + 1}} = \sum_{k = r}^{n} {{k} \choose {r}}\]

以上恒等式的详细证明请读者参阅组合数学相关教科书。

排列与组合的推广

在许多计数问题中，元素可以被重复使用。因此我们需要对一般的排列与组合进行推广以解决问题。

有重复的排列

当元素允许重复时，使用乘积法则可以很容易地计数。

具有 \(n\) 个物体的集合允许重复的 \(r\) 排列数是 \(n^{r}\)。

有重复的组合

具有 \(n\) 个物体的集合允许重复的 \(r\) 组合数是 \(C(n + r - 1, r) = C(n + r - 1, n - 1)\) 个。

事实上这一定理的证明是相对巧妙的，要利用隔板法这样的方法。囿于篇幅，详细证明请读者参阅组合数学相关教科书。

具有不可区别物体的集合的排列

在计数问题中，某些元素可能是没有区别的。

设类型 1 的相同物体有 \(n_{1}\) 个，类型 2 的相同物体有 \(n_{2}\) 个，\(\cdots\)，类型 \(k\) 的相同物体有 \(n_{k}\) 个，且 \(n_{1} + n_{2} + \cdots + n_{k} = n\)，则 \(n\) 个物体的不同排列数为

\[\frac{n!}{n_{1}! n_{2}! \cdots n_{k}!}\]

把物体放入盒子

许多计数问题都可以抽象为「把不同物体放入不同盒子」，因此我们将对这一模型进行分类讨论。

可区别的物体与可区别的盒子

把 \(n\) 个不同的物体分配到 \(k\) 个不同的盒子使得 \(n_{i}\) 个物体放入盒子 \(i (i = 1, 2, \cdots, k)\) 的方式数为

\[\frac{n!}{n_{1}! n_{2}! \cdots n_{k}!}\]

不可区别的物体和可区别的盒子

将 \(n\) 个不可区别的物体放入 \(k\) 个可区别的盒子的方法数，其结果等价于在允许重复计数的情况下，对具有 \(k\) 个元素的集合计算 \(n\) 组合数的问题。其正确性不难想见。

可区别的物体和不可区别的盒子

事实上，这种情况相较于其他情况是非常棘手的，无法给出一个闭公式进行计算。我们需要给出单独的定义：

设 \(S(n, j)\) 表示将 \(n\) 个可区别的物体放入 \(k\) 个不可区别的盒子的方法数，其中不允许有空的盒子，则数 \(S(n, j)\) 称作第二类斯特林数 (Stirling numbers of the second kind)。

利用容斥原理，我们可以给出一个求和计算公式：

\[S(n, k) = \frac{1}{k!} \sum_{i = 0}^{k - 1} (-1)^{i} {{k} \choose {i}} (k - i)^{n}\]

有关斯特林数的更多知识，读者可以参阅组合数学相关教科书或网络资料。

不可区别的物体和不可区别的盒子

这是一个组合数学上非常经典的问题。形式化地说，将 \(n\) 个不可区别的物体放入 \(k\) 个不可区别的盒子，等价于将 \(n\) 写成最多 \(k\) 个非递增正整数的和。如果 \(a_{1} + a_{2} + \cdots + a_{k} = n\)，其中 \(a_{1}, a_{2}, \cdots a_{k} \in \mathbb{Z}^{+}\)，且 \(a_{1} \geq a_{2} \geq \cdots \geq a_{k}\)，那么就称 \(a_{1}, a_{2}, \cdots a_{k}\) 是将正整数 \(n\) 划分成 \(k\) 个正整数的一个划分 (partition)，其方案数称作分拆数 (integer partition)，记作 \(p_{k} (n)\)。

分拆数的计算和研究一直是重要的研究课题，其背后的研究非常深入，读者可以参阅组合数学相关教科书或网络资料。