十二重计数 · yxshu

1、引入

十二重计数(the twelvefold way)问题研究的是把 $n$ 个球放入 $m$ 个盒子中，有多少种不同的方法。

之所以是 12 重，是因为有 3 个维度：

球是否可区分
盒子是否可区分
每一个盒子中采取的放法：任意放、最多 1 个、至少一个

概览：

\begin{array}{ccccc} n 个球 & m 个箱子 & 无任何限制 & 每个箱子至多 1 球 (m \geq n) & 每个箱子至少 1 球 (n \geq m) \\ 不同 & 不同 & m^{n} & (m)_{n} & m! S (n, m) \\ 相同 & 不同 & (\binom{n + m - 1}{m - 1}) & (\binom{m}{n}) & (\binom{n - 1}{m - 1}) \\ 不同 & 相同 & \sum_{k = 1}^{m} S (n, k) & {\begin{cases} 1, & n \leq m, \\ 0, & n > m \end{cases} & S (n, m) \\ 相同 & 相同 & \sum_{k = 1}^{m} p (n, k) & {\begin{cases} 1, & n \leq m, \\ 0, & n > m \end{cases} & p (n, m) \end{array}

2、证明

1.1： $n$ 个不同的球， $m$ 个不同的箱子，无任何限制

对于每一个球，都有 $m$ 种选择，所以方法数为 $n$ 个 $m$ 连乘，即

m^{n}

1.2： $n$ 个不同的球， $m$ 个不同的箱子，每个箱子至多一个球

由题意，我们知道必须有： $m \geq n$ 。

从 $m$ 个箱子中选出 $n$ 个箱子放入球，然后进行全排列即可。

(m)_{n}

注：本文用 $(m)_{n}$ 表示下降阶乘。

1.3： $n$ 个不同的球， $m$ 个不同的箱子，每个箱子至少一个球

由题意，我们知道必须有： $m \leq n$ 。

我们引入第二类 Stirling 数解决这个问题。

用 $S (n, m)$ 表示将 $n$ 个不同的元素划分为 $m$ 个非空集合的方法数。

考虑第 $n$ 个元素，如果它单独划分为一个集合，剩下的元素划分方法数： $S (n - 1, m - 1)$ 。

如果它不单独划分为一个集合，先考虑剩下的 $n - 1$ 个元素，将它们划分为 $m$ 个非空集合，有 $S (n - 1, m)$ 种方法，再将第 $n$ 个元素放入其中一个集合即可。

故

S (n, m) = S (n - 1, m - 1) + m S (n - 1, m)

求解第二类 Stirling 数时，我们利用递推式将目标推至边界情况如下,然后代值计算：

S (n, n) = S (n, 1) = S (0, 0) = 1

S (n, m) = 0 (当 m > n)

回到原题， $n$ 个不同的球， $m$ 个不同的箱子，每个箱子至少一个球，即将 $n$ 个不同的球先划分为 $m$ 个非空集合，然后对 $m$ 个非空集合做全排列(因为箱子是不同的)。所以

m! S (n, m)

2.1： $n$ 个相同的球， $m$ 个不同的箱子，无任何限制

这类问题可以采用隔板法。

简单来说，我们在小球之间插入 $m - 1$ 个隔板以划分出箱子，并且可以利用隔板划分出的 $m$ 个空间从左到右的顺序区分箱子的不同。

由于放入方式无任何限制，所以隔板与隔板之间可以没有小球，隔板可以出现在队伍最左端或最右端。也就是说，隔板的插入方式亦无任何限制，故我们可以把隔板“当作”小球，统一放入一个队列进行排列。

由于有 $n$ 个小球， $m - 1$ 个隔板，所以方法数为：

(\binom{n + m - 1}{m - 1})

2.2： $n$ 个相同的球， $m$ 个不同的箱子，每个箱子至多一个球

显然我们需要 $m \geq n$ 。

只需选出 $n$ 个箱子装球即可。答案为：

(\binom{m}{n})

2.3： $n$ 个相同的球， $m$ 个不同的箱子，每个箱子至少一个球

显然我们需要 $m \leq n$ 。

这类问题也可以采用隔板法。

我们给每一个箱子预先装入 1 个小球，然后回到问题 2.1。

现在我们还有 $n - m$ 个球（ $n - m \geq 0$ ），依然需要插入 $m - 1$ 个隔板，所以方法数为：

(\binom{n - 1}{m - 1})

3.1： $n$ 个不同的球， $m$ 个相同的箱子，无任何限制

回顾前文提到的 Stirling 数的概念：

$S (n, k)$ 表示将 $n$ 个不同的元素划分为 $k$ 个非空集合的方法数。

我们发现两个问题的唯一不同是，本题箱子可以为空，故分类讨论：有且仅有 1 个箱子里放入球、有且仅有 2 个箱子里放入球……有且仅有 m 个箱子里放入球。

也就是取 $k$ 为1、2…… $m$ ，所以方法数为：

\sum_{k = 1}^{m} S (n, k)

3.2： $n$ 个不同的球， $m$ 个相同的箱子，每个箱子至多一个球

首先需要满足： $m \geq n$ 。

在 $m$ 个箱子中，有 $n$ 个箱子装了 1 个球，然而，由于箱子是相同的，即使球不同，也只会存在 1 种划分。

故方法数为：

1

3.3： $n$ 个不同的球， $m$ 个相同的箱子，每个箱子至少一个球

这就是前文提到的 Stirling 数的概念：

$S (n, m)$ 表示将 $n$ 个不同的元素划分为 $m$ 个非空集合的方法数。

方法数为：

S (n, m)

4.3： $n$ 个相同的球， $m$ 个相同的箱子，每个箱子至少一个球

为了说明的方便，此处先讲解问题4.3。

我们引入整数的无序分拆问题，即将正整数 $n$ 拆分为 $m$ 个无序的正整数。将方法数记为： $p (n, m)$ 。

我们首先得出其递推关系。如果存在单元素的划分（即拆分出的数中有数字 1），那么除去一个划分出的单元素，剩下的元素做 $p (n - 1, m - 1)$ 的划分。反之，如果不存在单元素的划分，那么每一个元素都大于等于 2，故不妨先给每一个拆分结果（也就是我们最终要得到的 $m$ 个无序的正整数）先分配一个 $1$ ，然后用剩下的 $n - m$ 做 $p (n - m, m)$ 。故

p (n, m) = p (n - 1, m - 1) + p (n - m, m)

边界情况如下：

p (n, n) = p (n, 1) = p (0, 0) = 1

p (n, m) = 0 (m > n)

于是该问题的答案为：

p (n, m)

4.1： $n$ 个相同的球， $m$ 个相同的箱子，无任何限制

整数的无序拆分描述了每一个箱子至少有 1 个球的情形（因为拆分要求是得到 $m$ 个正整数）。那么仿照问题3.1的思路，分类讨论的情形如下：有 1 个箱子里有球、有 2 个箱子里有球……有 $m$ 个箱子里有球。

即

p (n, 1) + p (n, 2) + \dots + p (n, m)

所以本题的方法数为：

\sum_{k = 1}^{m} p (n, k)

4.2： $n$ 个相同的球， $m$ 个相同的箱子，每个箱子至多一个球

此问题与问题3.2区别不大。首先需要满足： $m \geq n$ 。

在 $m$ 个箱子中，有 $n$ 个箱子装了 1 个球，只会存在 1 种划分。

故方法数为：

1

至此，我们简要推导出了十二重计数中的所有情形：

\begin{array}{ccccc} n 个球 & m 个箱子 & 无任何限制 & 每个箱子至多 1 球 (m \geq n) & 每个箱子至少 1 球 (n \geq m) \\ 不同 & 不同 & m^{n} & (m)_{n} & m! S (n, m) \\ 相同 & 不同 & (\binom{n + m - 1}{m - 1}) & (\binom{m}{n}) & (\binom{n - 1}{m - 1}) \\ 不同 & 相同 & \sum_{k = 1}^{m} S (n, k) & {\begin{cases} 1, & n \leq m, \\ 0, & n > m \end{cases} & S (n, m) \\ 相同 & 相同 & \sum_{k = 1}^{m} p (n, k) & {\begin{cases} 1, & n \leq m, \\ 0, & n > m \end{cases} & p (n, m) \end{array}

杂谈

十二重计数可以用来解决概率论中的许多有趣的问题。

01 生日问题

有 $K$ 个人 ( $K$ < 365), 每个人的生日等可能地出现于 365 天中的任意一天

$Q 1$ : 至少有 2 人生日相同的概率是？

$Q 2$ : 有且仅有 2 人生日相同的概率？

$A$ :

生日问题实际上对应的是十二重计数中的“球不同、箱子不同”的情形。总的事件数为

365^{K}

即每一个人都任意的从 365 天里“选择”自己的生日。

先解决 $Q 1$ ,“至少有 2 人生日相同”的对立事件是“没有人生日相同”，也就是“每一个盒子里最多放入一个球”。故

P (至 少 有 2 人 生 日 相 同) = 1 - \frac{(365)_{K}}{365^{K}}

然后来看 $Q 2$ ,有且仅有 2 人生日相同，故先从 $K$ 人中选出这 2 人，放入同一天，剩下的人遵从“没有人生日相同”的原则。

P (有 且 仅 有 2 人 生 日 相 同) = \frac{(\binom{K}{2}) (\binom{365}{1}) (364)_{K - 2}}{365^{K}}

02 满射问题

$n$ 个学生分进 $k$ 个编号不同的小组，每组至少一人。

满射的定义： $设函数 f : A \to B ， A 是定义域， B 是陪域。$ $如果对于集合 B 中每一个元素 y ，都至少存在一个 x \in A ，使得 f (x) = y ，则称 f 是满射。$ 这里的每组至少一人正好满足了满射的定义。

显然，这就是十二重计数问题中的“球不同，箱子不同，每一个箱子至少 1 个球”的问题。故答案为：

k! S (n ， k)

不过，该问题还有一种解法，由此我们可以得到一个恒等式。

考虑容斥原理，设

A_{i} = {第 i 个小组没人} .

则原事件的对立事件：

| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k + 1} \sum_{1 \leq i_{1} < \dots < i_{k} \leq n} | A_{i_{1}} \cap \dots \cap A_{i_{k}} | = (\binom{k}{1}) (K - 1)^{n} - (\binom{k}{2}) (K - 2)^{n} + \dots + (- 1)^{k} (\binom{k}{k - 1}) 1^{n}

所以原事件的势：

“势”就是一个集合中元素的个数，也叫基数（cardinality）。通常记作 $| A |$ 。

k^{n} - (\binom{k}{1}) (k - 1)^{n} + (\binom{k}{2}) (k - 2)^{n} + \dots + (- 1)^{k - 1} (\binom{k}{k - 1}) 1^{n}

即

(\binom{k}{0}) k^{n} - (\binom{k}{1}) (k - 1)^{n} + (\binom{k}{2}) (k - 2)^{n} + \dots + (- 1)^{k - 1} (\binom{k}{k - 1}) 1^{n}

故有恒等式

k! S (n ， k) = \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n}

再议容斥原理

这个式子与夫妻匹配问题的答案很相似：

夫妻匹配问题：有 $n$ 对夫妻参加一次聚会，现将所有参会人员任意分成一男一女 $n$ 组，没有任何丈夫匹配到自己的妻子，有多少种匹配？关于夫妻匹配问题的blog

即

(\binom{k}{0}) k^{n} - (\binom{k}{1}) (k - 1)^{n} + (\binom{k}{2}) (k - 2)^{n} + \dots + (- 1)^{k} (\binom{k}{k}) (k - k)^{n}

与

(\binom{n}{0}) n! - (\binom{n}{1}) (n - 1)! + (\binom{n}{2}) (n - 2)! + \dots + (- 1)^{n} (\binom{n}{n}) 0!

二者使用容斥原理的基本思路相同。我们总是先考虑问题的反面，比如，因为原命题是事件“第 $i$ 对夫妻没有匹配成功”的交，而容斥原理要求的是事件的并。由一些布尔代数的知识，原命题取反后便是“第 $i$ 对夫妻匹配成功”的并。由此，我们可以轻易地使用容斥原理解题。

1、引入

2、证明

1.1： n 个不同的球，m 个不同的箱子，无任何限制

1.2： n 个不同的球，m 个不同的箱子，每个箱子至多一个球

1.3： n 个不同的球，m 个不同的箱子，每个箱子至少一个球

2.1： n 个相同的球，m 个不同的箱子，无任何限制

2.2： n 个相同的球，m 个不同的箱子，每个箱子至多一个球

2.3： n 个相同的球，m 个不同的箱子，每个箱子至少一个球

3.1： n 个不同的球，m 个相同的箱子，无任何限制

3.2： n 个不同的球，m 个相同的箱子，每个箱子至多一个球

3.3： n 个不同的球，m 个相同的箱子，每个箱子至少一个球

4.3： n 个相同的球，m 个相同的箱子，每个箱子至少一个球

4.1： n 个相同的球，m 个相同的箱子，无任何限制

4.2： n 个相同的球，m 个相同的箱子，每个箱子至多一个球