整数分拆中的一个出人意料的结论

把 6 分成一个或多个正整数之和，本质不同的方案只有以下 11 种：

其中，每一行右边的那个数表示，该分拆方案中含有多少种不同的数。把右列的所有数全部加起来，结果是 19 。神奇的是，如果你数一数所有分拆方案中 1 出现的总次数，你会发现结果也是 19 。

这并不是巧合。事实上，对于任意一个正整数来说，各个分拆方案中不同的数的个数之和，一定都等于所有方案中 1 出现的总次数。这是为什么呢？这个结论还有一个比较直接的推广，你能想到吗？

这个结论可以推广为，对于任意一个正整数 n 来说，各个分拆方案中出现了至少 k 次的数的个数之和，一定等于所有方案中 k 出现的总次数。以 n = 6, k = 2 为例：

右列的总和是 8 ，这正好是所有分拆方案中 2 出现的总次数。再比如，上面的分拆方案列表中一共只出现了一个 6 ，同时也确实只发生了一次某个方案中的某个数出现 6 次的情况。这说明结论对于 n = 6, k = 6 的情形也成立。前文给出的结论，其实就是 k = 1 时的特殊情形。

接下来，我们将直接证明推广之后的结论。不妨让我们以 n = 6, k = 2 的情形为例来说明吧。我们先列出所有在某个分拆方案中出现了至少 2 次的数：

(4, 1, 1) 里的 1

(3, 3) 里的 3

(3, 1, 1, 1) 里的 1

(2, 2, 2) 里的 2

(2, 2, 1, 1) 里的 2

(2, 2, 1, 1) 里的 1

(2, 1, 1, 1, 1) 里的 1

(1, 1, 1, 1, 1, 1) 里的 1

然后，我们再用分拆方案加下标的方式，列出所有含有 2 的分拆方案。一个分拆方案中含有多少个 2 ，该方案就要重复列出多少次，并用下标 1, 2, 3, … 来区分。

(4, 2)₁

(3, 2, 1)₁

(2, 2, 2)₁

(2, 2, 2)₂

(2, 2, 2)₃

(2, 2, 1, 1)₁

(2, 2, 1, 1)₂

(2, 1, 1, 1, 1)₁

我们要做的，就是在这两个列表之间建立一一对应的关系。很简单：如果某个分拆方案中出现了至少 2 次 i ，我们就把其中 2 个 i 换成 i 个 2 ，并为所得的分拆方案添加下标 i 。容易看出，把 2 个 i 换成 i 个 2 ，所有数的总和不变，因而所得的仍然是一个合法的分拆方案；并且由于所得的分拆方案中已经有至少 i 个 2 了，因而添加的下标 i 确实在应有的范围内。因此，前一个列表里的任意一项都可以用这种方法变换为后一个列表里的其中一项。反过来，后一个列表里的任意一项也都可以反过去变成前一个列表里的其中一项，你只需要把下标所示的这么多个 2 换成 2 个下标所示的这个数即可。这就证明了，两个列表之间存在一一对应的关系。

(4, 1, 1) 里的 1 —— (4, 2)₁

(3, 3) 里的 3 —— (2, 2, 2)₃

(3, 1, 1, 1) 里的 1 —— (3, 2, 1)₁

(2, 2, 2) 里的 2 —— (2, 2, 2)₂

(2, 2, 1, 1) 里的 2 —— (2, 2, 1, 1)₂

(2, 2, 1, 1) 里的 1 —— (2, 2, 2)₁

(2, 1, 1, 1, 1) 里的 1 —— (2, 2, 1, 1)₁

(1, 1, 1, 1, 1, 1) 里的 1 —— (2, 1, 1, 1, 1)₁

这个结论叫做 Elder 定理，它是由滑铁卢大学的一名学生 Paul Elder 在 1984 年证明的。有趣的是， Richard Stanley 早在 1972 年便发现了这个结论，并把它提交到了 The American Mathematical Monthly 的 Problems and Solutions 栏目，没想到却被编辑拒绝了。 Stanley 猜测，这可能是因为编辑没有看懂题目的意思。 Stanley 跟 Daniel Cohen 讲过这个题目，后者在 1978 年出版的 Basic Techniques of Combinatorial Theory 当中把 k = 1 的情形用作了一道练习题，并提到了 Stanley 的名字。因而， k = 1 的这种特殊情形有时也会叫做 Stanley 定理。上述证明方法则来自 Richard Stanley 本人的 Enumerative Combinatorics 一书。