组合数学的两大分支是研究计数问题的计数组合学与研究最优组合的极值组合学, 我们这里主要涉及前者. 在全部内容开始前, 假定读者具有集合与映射的基本概念.

引言: 十二重计数方法

集合元素的计数

令 `X, Y` 为两个集合. 如果存在 `X` 到 `Y` 的一一对应 (即双射), 则称 `X` 与 `Y` 对等或等势.

如果存在正整数 `n`, 使得集合 `X` 与集合 `{1, 2, cdots, n}` 对等, 则称 `X` 为有限集, 称 `X` 中元素的个数或 `X` 的基数为 `n`, 记为 `|X| = n`. 我们也规定空集 `O/` 是有限集, 且 `|O/| = 0`. 若 `X` 不是有限集, 则称它是无限集, 或者说, 它的元素有无穷多个.

"集合中的元素个数" 的概念容易推广到无限集上, 即 "基数" 或 "势". 这在数学分析, 实变函数等课程中均有涉及. 在组合数学中, 我们将重点放在对有限集的讨论上.

设 `X = {x_1, x_2, cdots, x_k}` 是一集合, `k ge 0`, `n_1, n_2, cdots, n_k` 是非负整数, 则称二元组的集合 `S = {(x_1, n_1), (x_2, n_2), cdots, (x_k, n_k)}` 为 `x_1, x_2, cdots, x_k` 的多重集 (multiset), 记为 `S = {n_1 * x_1, n_2 * x_2, cdots, n_k * x_k}` 其中 `n_i` 称为元素 `x_i` 的重数, `i = 1, 2, cdots, k`. 如果一个元素 `x_i` 的重数 `n_i = 0`, 我们认为 `x_i !in S`. 因此我们认为下面两个多重集相等: `{1 * a, 0 * b, 3 * c} = {1 * a, 3 * c}` 定义多重集的基数为 `|S| = sum_(i=1)^k n_i`.

多重集合的一个例子是多项式的根, 每个根的重数对应于在多重集中的重数.

我们把计算集合 (多重集) 中元素个数的问题统称为计数问题.

十二重计数方法

在计数时, 尤其需要关注的问题是在什么意义下计数, 换言之, 设 `x_1, x_2 in X`, `x_1` 与 `x_2` 什么情况下被视为相等的? 这是计数的关键问题. 我们将看到, 在不同意义下, 看起来相似的计数问题有完全不同的结果, 其解答的难度与算法的复杂度也各不相同.

现在考虑如下一般的计数问题, 称为十二重计数方法 (twelvefold way). 它几乎涵盖了全部典型的计数问题, 有大量的实际问题背景, 我们将在具体讨论每一情形时举例说明.

    设 `X, Y` 为有限集合, `|X| = m`, `|Y| = n`, `F` 是全体 `X` 到 `Y` 上的映射 `f` 的集合, `I sube F` 是 `F` 中的单射 (injection) 形成的子集, `S sube F` 是 `F` 中的满射 (surjection) 形成的子集. 在以下 4 种意义下对 `F`, `I`, `S` 的元素进行计数:
  1. 通常意义. 采用映射相等的定义. 两个映射 `f_1, f_2 in F` 相等当且仅当它们把 `X` 中任意元素映到相同的像, 即 `(AA x in X)` `f_1(x) = f_2(x)`.
  2. 相差一个 `X` 上的排列的意义. 对 `X` 的元素不加区分, 映射 `f_1, f_2 in F` 相等当且仅当 `Y` 中的各个元素在 `f_1` 和 `f_2` 下有相等数目的原像, 即 `(AA y in Y)` `|f_1^-1(y)| = |f_2^-1(y)|`. 这类问题计数了多重集合的子集.
  3. 相差一个 `Y` 上的排列的意义. 对 `Y` 的元素不加区分. 映射 `f_1, f_2 in F` 相等当且仅当 `"Ker" f_1 = "Ker" f_2`. 其中 `"Ker" f = {(x_1, x_2) in X xx X: f(x_1) = f(x_2)}`. 这类问题计算集合的分划数.
  4. 相差 `X` 与 `Y` 上的排列的意义. 对 `X` 的元素不加区分, 对 `Y` 的元素也不加区分. 映射 `f_1, f_2 in F` 相等当且仅当下面的多重集合相等 `{|f_1^-1(y)|: y in Y} = {|f_2^-1(y)|: y in Y}`. 这类问题计算非负整数的分拆数.
    5. 3 个集合在 4 种意义下共形成 12 个计数问题, 用集合表示, 分别记为 `F_1 ~ F_4, I_1 ~ I_4, S_1 ~ S_4`, 见下表.
`f` 是普通映射 `f` 是单射 `f` 是满射
在通常意义下 `F_1` `I_1` `S_1`
在相差一个 `X` 上的排列的意义下 `F_2` `I_2` `S_2`
在相差一个 `Y` 上的排列的意义下 `F_3` `I_3` `S_3`
在相差 `X` 与 `Y` 上的排列的意义下 `F_4` `I_4` `S_4`
现在用物体与盒子的语言来重新叙述上面的计数问题.

假设有 `m` 件物体, `n` 个盒子, 现要计数将这些物体放入这些盒子的方法数. 容易看出物体-盒子语言与映射语言的对应关系: 如 `f(x)` 表示放有物体 `x` 的盒子; `f_1(x) = f_2(x)` 表示两种方法将物体 `x` 放进了同一个盒子; `f^-1(y)` 表示盒子 `y` 中的所有物体; 等等. 根据放入盒子时的限制条件 (不作要求/每个盒子的物体不超过一件/每个盒子不空) 和对物体与盒子是否标号 (labeled/unlabeled) (换言之, 是否作区分 (distinct)), 亦引出十二种不同的计数问题. 我们不作证明地在下表中给出答案.

不作要求 每个盒子的物体不超过一件 每个盒子不空
对物体与盒子都作区分 `n^m` `[n]_m` `n! S(m, n)`
对物体不作区分 `(m+n-1;m) = (-n; m) (-1)^m` `(n;m)` `(m-1;n-1)`
对盒子不作区分 `sum_(i=1)^n S(m, i)` `[m le n]` `S(m, n)`
对物体与盒子都不作区分 `sum_(i=1)^n p_i(m)` `[m le n]` `p_n(m)`
    其中
  1. `[n]_m = P(n, m)` `= n(n-1) cdots (n-m+1)` 是 `n` 选 `m` 的排列数.
  2. `(n;m) = C(n, m) = [n]_m//m!` 是 `n` 选 `m` 的组合数.
  3. `S(m, n) = {m;n}` `= 1/(n!) sum_(i=0)^n (n;i) (-1)^i (n-i)^m` 是第二类 Stirling 数.
  4. `p_n(m)` 是将整数 `m` 分拆成 `n` 部分的分拆数.
  5. `[m le n] = {1, if m le n","; 0, if "else".:}`

计数原理

鸽巢原理

鸽巢原理又名抽屉原理或 Dirichlet 原理, 概念直白浅显, 但是应用广泛, 形式灵活, 是组合数学和数论中常用的工具.

    鸽巢原理 令 `n in ZZ^+`,
  1. 将 `n+1` 个物体放入 `n` 个盒子, 不论怎么放, 至少有一个盒子中的物体多于一个;
  2. 将 `n-1` 个物体放入 `n` 个盒子, 不论怎么放, 至少有一个盒子是空的.
  1. 若每个盒子中的物体数目不多于一个, 则物体总数至多为 `n`, 引出矛盾;
  2. 若每个盒子中的物体数目不少于一个, 则物体总数至少为 `n`, 引出矛盾.

同年出生的 400 人中至少有两人同一天生日.

设有物体若干, 它们可以分成 `n` 类. 从中选 `n+1` 个物体, 必有两个物体属于同类.

做 `n` 个盒子, 将同类物体放在同一个盒子中. 这样一来, 被选中的 `n+1` 个物体也被放进了盒子. 由鸽巢原理, 被选中的物体中至少有两个被放入同一个盒子,

从 `n` 双手套中任取 `n+1` 只, 至少能配成一双手套.

    推广的鸽巢原理
  1. 将 `mn + 1` 个物体放入 `n` 个盒子, 则至少有一个盒子中的物体数目多于 `m` 个;
  2. 将 `mn - 1` 个物体放入 `n` 个盒子, 则至少有一个盒子中的物体数目少于 `m` 个.
    3. 证明方法类似.

将五条线段用红色或蓝色着色, 一定有三条线段颜色相同 (取 `m = n = 2`).

将 `mn` 个物体放入 `n` 个盒子, 则至少有一个盒子中的物体数目不少于 `m` 个, 至少有一个盒子中的物体数目不多于 `m` 个.

若再放入一个物体, 由推广的鸽巢原理, 有一个盒子中的物体数目多于 `m` 个, 说明它原先不少于 `m` 个; 若少放入一个物体, 由推广的鸽巢原理, 有一个盒子中的物体数目少于 `m` 个, 说明它原先不多于 `m` 个.

将正方体的每个面涂成红色或蓝色中的一种, 一定有三个面颜色相同 (取 `m = 3, n = 2`).

一般的鸽巢原理 将 `m` 个物体放入 `n` 个盒子, 则至少有一个盒子中的物体数目不少于 `|__ (m-1)/n __|+1` 个, 至少有一个盒子中的物体数目不多于 `|~ (m+1)/n ~|-1` 个.

鸽巢原理有它的非离散版本, 如: 三角形至少有一内角不小于 60 度.

鸽巢原理的应用

鸽巢原理可以用于一些存在性问题的证明. 运用鸽巢原理时, 要善于构造具有特定属性的盒子.

`n` 个人参加聚会, 他们中有一些人相互握了手 (和自己握手不算). 一定有两个人握手次数相同.

如果在聚会上, 每个人都至少握了一次手, 那么全部可能的握手次数是 `1, 2, cdots, n-1`; 如果有的人没有握过手, 全部可能的握手次数则是 `0, 1, cdots, n-2`. 不论哪一种情形, 可能的握手次数只有 `n-1` 种. 由鸽巢原理, 一定有两个人握手次数相同.

从 `1, 2, cdots, 15` 中任取 9 个数, 其中必有两个数之和是 17.

将全部 15 个数放入 8 个集合: `{1}, {2, 15}, {3, 14}, cdots, {8, 9}`. 由鸽巢原理, 所选的 9 个数中至少有两个属于同一集合. 它们的和就是 17.

从 `1, 2, cdots, 100` 中任取 51 个数, 必有两个数, 其中一个是另一个的倍数.

每个正整数都能写成 奇数`* 2^n` 的形式, 但所有可能的奇数只有 50 个: `1, 3, cdots, 99`. 因此必有两个正整数对应于同一个奇数, 设它们是 `a * 2^n`, `a * 2^m`, 显然一个是另一个的倍数.

    同色三角形问题
  1. 设空间中有 6 个点, 任意三点不共线. 现将每两点用红色或蓝色的线段连接, 则必存在一个三边同色的三角形. 这个问题的一个等价表述是: 在任意 6 人的集会上, 或者有 3 个人以前彼此相识, 或者有 3 个人以前彼此不相识.
  2. 设空间中有 17 个点, 任意三点不共线. 用 3 种颜色给所有连接这些点的线段着色, 则必存在一个三边同色的三角形.
  1. 任取其中一点, 由这点出发的 5 条线段中, 至少有 3 条同色, 假定是红色. 把这三条线段记为 `OA, OB, OC`, 考察三角形 `ABC`. 若三角形 `ABC` 其中一边是红色, 如 `AB` 是红色, 则三角形 `OAB` 的三边都是红色, 是同色三角形; 否则三角形 `ABC` 的三边都是蓝色, 是同色三角形.
  2. 取其中一点 `A`, 由这点出发的 16 条线段中, 至少有 6 条同色, 设它们具有颜色 `a`. 考虑这 6 条线段异于 `A` 的 6 个端点. 如果它们之间有一条连线具有颜色 `a`, 则同色三角形已经找到; 否则, 这 6 个点之间的连线只由另外两种颜色着色, 由 1 知必存在同色三角形.

鸽巢原理的映射表述

设集合 `X, Y != O/`. 考虑从 `X` 到 `Y` 的对应法则 `f`, 如果对任意 `x in X`, 根据法则 `f` 都存在唯一的 `y in Y` 与之对应, 则称 `f` 为 `X` 到 `Y` 的一个映射, 记为 `f: X to Y`. `y` 称为 `x` 在 `f` 下的像, 记为 `y = f(x)`.

设 `f: X to Y`. 对 `y in Y`, 称集合 `f^-1(y) = {x in X: f(x) = y}` 为 `y` 关于映射 `f` 的原像集.

    设映射 `f: X to Y`.
  1. 如果由 `f(x_1) = f(x_2)` 能推出 `x_1 = x_2`, 则称 `f` 是单射; 显然 `f` 是单射当且仅当对任意 `y in Y`, `|f^-1(y)| le 1`;
  2. 如果对任意 `y in Y`, 都存在 `x in X`, 使得 `y = f(x)`, 则称 `f` 是满射; 显然 `f` 是满射当且仅当对任意 `y in Y`, `|f^-1(y)| ge 1`;
  3. 如果 `f` 既是单射又是满射, 则称 `f` 是双射; 显然 `f` 是双射当且仅当对任意 `y in Y`, `|f^-1(y)| = 1`.

鸽巢原理 设 `X, Y != O/` 为有限集, 则存在 `X to Y` 的单射的充要条件是 `|X| le |Y|`, 存在 `X to Y` 的满射的充要条件是 `|X| ge |Y|`; 因此, 存在 `X to Y` 的双射的充要条件是 `|X| = |Y|`.

我们只证明单射的情形, 满射的证明类似. 设 `X = {x_1, x_2, cdots, x_m}`, `Y = {y_1, y_2, cdots, y_n}`, 则 `|X| = m`, `|Y| = n`.
充分性: 当 `m le n` 时, 显然 `f(x_i) = y_i`, `i = 1, 2, cdots, m` 是 `X` 到 `Y` 的单射.
必要性: 若 `f: X to Y` 是单射, 对每个 `y_i in Y`, 考虑原像集 `f^-1(y_i)`, 有 `|f^-1(y_i)| le 1`. 注意到 `X` 是各 `f^-1(y_i)` 的不交并, 由加法原理, ` |X| = |uuu_(i=1)^n f^-1(y_i)| = sum_(i=1)^n |f^-1(y_i)| le n`.

设映射 `f: X to Y`. 若 `X_1 sube X`, 定义映射 `f|_(X_1): X_1 to Y`
`x to f(x)`. 称为 `f` 在子集 `X_1` 上的限制.

设 `X, Y != O/` 为有限集, 且 `|X| = |Y|`. 若 `f: X to Y`, 则 `f` 是单射当且仅当 `f` 是满射, 从而当且仅当 `f` 是双射.

  1. 设 `f` 不是满射, 由定义, 存在 `y in Y`, 对任意 `x in X`, `f(x) != y`. 所以 `f` 也是从 `X` 到 `Y\\{y}` 的映射. 但 `|Y\\{y}| lt |Y| = |X|`, 所以由, `f` 不是单射.
  2. 设 `f` 不是单射, 则存在 `x_1, x_2 in X`, `x_1 != x_2`, `f(x_1) = f(x_2)`. 所以 `f` 限制在 `X\\{x_1}` 上是 `X\\{x_1}` 到 `Y` 的映射. 但 `|X\\{x_1}| lt |X| = |Y|`, 所以由, `f` 限制在 `X\\{x_1}` 上不是满射, 即存在 `y in Y`, 对任意 `x in X\\{x_1}`, `f(x) != y`. 因为 `x_2 in X\\{x_1}`, 所以 `f(x_1) = f(x_2) != y`. 因而 `f` 不是满射.

现在我们可以解决引言中 `I_3, I_4` 的计数问题. `I_3` 表示 `X` 所有可能的分划, 且每一类中只含不超过一个元素. `I_4` 表示数字 `|X|` 的分拆, 每一部分不超过 1. 显然这样的分划 (分拆) 都只有一种取法 (如果它存在), 因此二者的结论都是平凡的. 由鸽巢原理, `I_3` (或 `I_4`) 非空当且仅当 `m le n`, 所以 `|I_3| = |I_4| = {1, if m le n","; 0, if "else.":}`