数学 / 排列组合 · 从计数原理到 P(n,k) 与 C(n,k) / 十二重计数法 待审核 19 / 25
twelvefold way · 球盒总表

十二重计数法

「从若干类型里取几个」与「把若干个球放进若干个盒」是同一件事的两种说法：第 ii 次取到哪个类型，就是第 ii 个球进了哪个盒。换成球盒的说法之后，此前分散在各页的公式可以按三个维度排成一张表：球是否可辨、盒是否可辨、每盒的容量是否受限，交叉出十二格。这张表由 Rota 命名为十二重计数法（twelvefold way）。

1 · 球盒模型的坐标

一次放法就是一个函数 f:[n]→[m]f : [n] \to [m]，把第 ii 个球送进第 f(i)f(i) 号盒。三个维度都是对这个函数施加的约束或等同：

  • 球可辨或不可辨。不可辨时 ff 与 f∘σf \circ \sigma 算同一种放法，σ\sigma 取遍球的重排。
  • 盒可辨或不可辨。不可辨时 ff 与 τ∘f\tau \circ f 算同一种放法，τ\tau 取遍盒的重排。
  • 映射任意、单射（每盒至多一球）、满射（每盒至少一球）。

前两项各二值，第三项三值，2×2×3=122 \times 2 \times 3 = 12。

2 · 十二格总表

n 球 → m 盒 · 2 × 2 × 3 = 12 格
图 2-1 · 十二格在给定 nn 与 mm 下的取值。可拖动球数 nn 与盒数 mm，点击任一格查看它的公式、对应页面与该格的全部放法枚举。
球 盒 映射 方案数 本系列
可辨 可辨 任意 mnm^n 可重复选取
可辨 可辨 单射 mn‾=P(m,n)m^{\underline{n}} = P(m, n) 排列
可辨 可辨 满射 m! S(n,m)m!\,S(n, m) Stirling 数
不可辨 可辨 任意 (n+m−1n)\binom{n+m-1}{n} 可重复选取
不可辨 可辨 单射 (mn)\binom{m}{n} 组合
不可辨 可辨 满射 (n−1m−1)\binom{n-1}{m-1} 隔板法，每盒先垫一球
可辨 不可辨 任意 ∑k≤mS(n,k)\sum_{k \le m} S(n, k) Stirling 数
可辨 不可辨 单射 [n≤m][n \le m] 只是一个判定
可辨 不可辨 满射 S(n,m)S(n, m) Stirling 数
不可辨 不可辨 任意 ∑k≤mpk(n)\sum_{k \le m} p_k(n) 整数分拆
不可辨 不可辨 单射 [n≤m][n \le m] 只是一个判定
不可辨 不可辨 满射 pm(n)p_m(n) 整数分拆

可重复选取 §2 的四种取样模型正好落在「盒可辨」两行的任意与单射四格上：类型是盒，取的第几次是球，放回与否对应映射是否被限成单射。

警示 · 两套记号的字母是对调的。取样模型里的 nn 是类型数，在球盒模型里是盒数 mm；取的个数 kk 则是球数 nn。C(n+k−1,k)C(n+k-1, k) 与 (n+m−1n)\binom{n+m-1}{n} 是同一个公式的两种写法，直接套字母会得到另一格的答案。

3 · 盒的标号与不整除的商

27 / 5 不是整数 · 空盒让轨道变小

盒有标号时可以逐盒决策，公式因而有乘积形式：每个球独立地挑一个盒，nn 个球相乘得 mnm^n。去掉标号相当于在盒的重排下取轨道，若每条轨道都恰有 m!m! 个成员，去标号就是一次除法。含空盒的放法破坏了这一点——两个空盒互换不改变放法，轨道随之缩到 m!/e!m!/e!，其中 ee 是空盒数。n=m=3n = m = 3 时盒可辨的任意放法 27 种，盒不可辨 5 种，27/527/5 连整数都不是。

图 3-1 · 盒的重排把放法分成轨道，同一轨道在盒不可辨下算一种。可拖动 nn 与 mm 观察含空盒的轨道如何缩到 m!m! 以下，切换到只看满射后所有轨道恢复为 m!m! 个成员。

满射那一列没有空盒，轨道大小恒为 m!m!，m! S(n,m)m!\,S(n, m) 与 S(n,m)S(n, m) 干净地差一个 m!m!。其余各格没有这样的除法可用，只能改口用划分数 S(n,m)S(n, m) 与分拆数 pm(n)p_m(n) 这类量来定义——它们要么按递推逐行推出，要么写成带交错符号的求和，都不是乘积形式的闭式。十二格里公式最短的四格与最难算的四格因此分居两侧。

注 · 退化格的口径按空函数取。00 个球放进 00 个盒有 11 种放法（唯一的空函数，空虚地既是单射也是满射），十二格一律为 11；n>0n > 0 个球放进 00 个盒无函数可言，十二格一律为 00；00 个球放进 m>0m > 0 个盒时任意与单射为 11、满射为 00。

警示 · 闭式在 n=0n = 0 且 m=0m = 0 处会失灵。把十二格逐一与暴力枚举对照（枚举全部 f:[n]→[m]f : [n] \to [m] 再按可辨性归一化去重），n,m≤5n, m \le 5 全覆盖共 432432 个组合，只报出两处不符，且都落在同一个 (n,m)(n, m) 上：球不可辨且盒可辨的任意格，公式 (n+m−1n)\binom{n+m-1}{n} 给 00 而枚举给 11；同行的满射格，(n−1m−1)\binom{n-1}{m-1} 给 00 而枚举也给 11。根子在实现里 comb(n, k) 对 k<0k < 0 或 k>nk > n 一律返回 00，于是 (−10)\binom{-1}{0} 与 (−1−1)\binom{-1}{-1} 都成了 00。改的是公式一侧：m=0m = 0 时直接返回 [n=0][n = 0]，枚举的归一化不动。

4 · 参考文献

  1. Twelvefold way. Wikipedia. 十二格的完整列表、各格的组合意义与等价说法。https://en.wikipedia.org/wiki/Twelvefold_way
  2. Stirling numbers of the second kind. Wikipedia. S(n,m)S(n, m) 的递推、显式求和与生成函数。https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
  3. Partition (number theory). Wikipedia. 整数分拆与 pm(n)p_m(n) 的递推。https://en.wikipedia.org/wiki/Partition_(number_theory)
  4. Stanley, R. P. (2011). Enumerative Combinatorics, Volume 1 (2nd ed.). Cambridge University Press.