Bóna · 枚举与解析组合学导论 · 第 10 章 幻方与幻立方的计数

10.4　为什么幻立方不同Why magic cubes are different

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标把幻方（magic square）的计数推广到三维的幻立方（magic cube），并回答一个出人意料的问题：幻方的计数函数 \(H_n(r)\) 总是 \(r\) 的多项式，可幻立方的计数函数 \(C_n(r)\) 为什么不再是多项式？我们要算出 \(C_3(r)\) 的前几个值，用有限差分判定它不是多项式，并找出证明在三维失效的那一步。

从分配问题到幻立方

现在考虑我们最初那个分配问题的一个加强版本。同样地，我们要把 \(60\) 块积木分给三个孩子，使每个孩子各得 \(20\) 块。其中 \(20\) 块是红色，\(20\) 块是蓝色，\(20\) 块是绿色，同色的积木彼此完全相同。最初的问题到此为止。然而，假设这些孩子明天还会再来玩，后天也会来。在这三天的每一天里，我们都按上述规则分配积木（每个孩子各得 \(20\) 块），但我们同时还追求一种长期的平衡。因此，我们要求：在三天结束之时，每个孩子在整个时间段内拿到的红色积木总数为 \(20\)，拿到的蓝色积木总数为 \(20\)，拿到的绿色积木总数为 \(20\)。这一切总共有多少种实现方式？

由第 10.1 节我们知道，某一天一个可行的积木分配方案可以用一个边长为 \(3\)、行列和（line sum）为 \(20\) 的幻方来表示，因此任意给定一天的可行分配数就是 \(H_3(20)\)。然而，我们不能随便取三个幻方、把它们叠放在一起，就声称所得到的 \(3\times 3\times 3\) 三维阵列代表整个问题的一个解。这是因为还有那个关于颜色平衡的额外要求。也就是说，我们要找的是这样的分配方案：当把对应的三个幻方叠放在一起时，每条竖直方向上的格子之和也等于 \(20\)。图 10.7 给出了一种可能的分配。用 \(A,B,C\) 表示三个孩子。

ABC 红 蓝 绿 569 677 974 今天 ABC 红 蓝 绿 866 758 596 明天 ABC 红 蓝 绿 785 785 6410 后天
图 10.7　一种可能的三天分配。三张表都是行列和为 \(20\) 的幻方；并且把三张表叠起来后，每个对应位置（同一颜色、同一孩子）三天之和也都恰为 \(20\)。
例：验证图 10.7 的三重平衡 取“蓝色行”作检验。
  1. 今天蓝行 \(6+7+7=20\)，明天蓝行 \(7+5+8=20\)，后天蓝行 \(7+8+5=20\)——每一天每个孩子各得 \(20\)（行约束）。
  2. 再看竖直方向的三天累计：蓝-\(A\) 为 \(6+7+7=20\)，蓝-\(B\) 为 \(7+5+8=20\)，蓝-\(C\) 为 \(7+8+5=20\)——每个孩子三天拿到的蓝色积木总数都是 \(20\)（竖直约束）。
  3. 其余颜色同理。例如红-\(C\)：\(9+6+5=20\)；绿-\(C\)：\(4+6+10=20\)。三个方向（行、列、竖直线）的和处处为 \(20\)，这正是幻立方的定义。♦

这样一种构造——一个 \(n\times n\times n\) 的非负整数阵列，其中每一条线（即每一行、每一列、每一条竖直线）的和都相同——称为一个幻立方（magic cube）。于是图 10.7 中的阵列就是一个边长为 \(3\)、线和为 \(20\) 的幻立方的例子。

行（同一天某颜色，3 个孩子） 列 竖直线（3 天）
幻立方有三个方向的“线”都要求和相同：行、列、以及贯穿三层的竖直线。这第三个方向正是幻方所没有的新约束。

计数函数 \(C_n(r)\) 与一个上界

设 \(C_n(r)\) 为边长为 \(n\)、线和为 \(r\) 的幻立方的个数。读者应当验证 \(C_1(r)=1\) 且 \(C_2(r)=r+1\)。在此之后，读者可能会以为幻立方的计数其实与幻方的计数非常相似。然而事实并非如此，最小的非平凡情形 \(n=3\) 就表明了这一点。一个 \(2\times 2\times 2\) 的子立方体就能完全决定一个 \(3\times 3\times 3\) 的幻立方，所以 \(C_3(r)\le r^8\)。因此，如果 \(C_3(r)\) 是一个多项式，那么它的次数至多为 \(8\)。不难（见习题 20）写一个计算机程序，算出 \(C_3(r)\) 的前 \(10\) 个值。这些值列在图 10.8 中。

例：为什么 \(C_2(r)=r+1\) 边长为 \(2\)、线和为 \(r\) 的幻立方由谁决定？
  1. 取最上层左上角的格子，设它为 \(a\)（\(0\le a\le r\)，共 \(r+1\) 种取值）。
  2. 它所在那一层的同行另一格必须是 \(r-a\)（行和 \(=r\)）；同列另一格也是 \(r-a\)；对角格则被逼成 \(a\)。这一层被 \(a\) 完全确定。
  3. 竖直方向：该格下方一格必须是 \(r-a\)（竖直线和 \(=r\)）。于是底层每一格也都被确定，整个 \(2\times2\times2\) 阵列由 \(a\) 唯一决定。
  4. 因此恰有 \(r+1\) 个，即 \(C_2(r)=r+1\)。♦
例：为什么 \(C_3(r)\le r^8\) 一个 \(3\times3\times3\) 的幻立方共有 \(27\) 个格子。任取它的一个 \(2\times2\times2\) 角块（\(8\) 个格子）。沿三个方向上，每一条线的第三个格子都由“线和 \(=r\) 减去已知两格”唯一补出，逐步推下去这 \(8\) 个角格就把整个 \(27\) 格阵列定死。每个角格的取值在 \(0\) 到 \(r\) 之间，至多 \(r+1\) 种，粗略地不超过 \(r\) 种数量级，故方案数 \(\le (r+1)^8\sim r^8\)。所以若 \(C_3(r)\) 是多项式，其次数 \(\le 8\)。
r C₃(r) 01 112 2132 3847 43921 514286 643687 7116757 8280656 9619219
图 10.8　\(C_3(r)\) 在 \(0\le r\le 9\) 处的值。

用有限差分判定它不是多项式

现在我们来说明，如何从这 \(10\) 个值推断出 \(C_3(r)\) 不是多项式。

设 \(f:\mathbb{N}\to\mathbb{R}\) 为任意函数，令 \(\Delta(f)(n)=f(n+1)-f(n)\)。类似地， \[\Delta^2(f)(n)=\Delta(\Delta(f))(n)=\big(f(n+2)-f(n+1)\big)-\big(f(n+1)-f(n)\big),\] 并可沿同样的方式得到 \(\Delta^d\)。下面的命题用 \(\Delta\) 刻画了次数至多为 \(d\) 的多项式。

命题 10.20 设 \(p:\mathbb{N}\to\mathbb{R}\) 为一个多项式。则 \(p\) 的次数至多为 \(d\)，当且仅当 \(\Delta^d(p)\) 是常值函数。
证明. 我们对 \(d\) 用归纳法证明该命题。当 \(d=0\) 时，结论显然成立。现假设结论对 \(d\) 成立，来证明它对 \(d+1\) 成立。

(a)（“仅当”部分）设 \(p\) 是次数为 \(d+1\) 的多项式。则 \[p(n)=a_{d+1}n^{d+1}+a_d n^d+\cdots+a_1 n+a_0.\] 于是 \[p(n+1)=a_{d+1}(n+1)^{d+1}+a_d(n+1)^d+\cdots+a_1(n+1)+a_0.\] 由此可见，在 \(p(n+1)-p(n)=\Delta(p)(n)\) 中，\(n^{d+1}\) 项相消，所以 \(\Delta(p)\) 是次数至多为 \(d\) 的多项式。因此，由归纳假设，\(\Delta^d(\Delta(p))\) 是常值的，换言之 \(\Delta^{d+1}(p)\) 是常值的。

(b)（“当”部分）设 \(p\) 是一个使 \(\Delta^{d+1}(p)\) 为常值的函数。则 \(\Delta^d(\Delta(p))\) 是常值的，于是由归纳假设，\(\Delta(p)\) 必为次数至多为 \(d\) 的多项式。这就推出 \(p\) 的次数至多为 \(d+1\)。事实上，若 \(p(n)=\sum_{i=0}^{h}a_i n^i\)，则 \[\Delta(p)(n)=\sum_{i=0}^{h}a_i(n+1)^i-\sum_{i=0}^{h}a_i n^i,\] 它含有一个次数为 \(h-1\) 的项。♦

我们指出，命题 10.20 即使稍微改动其措辞仍然成立。我们可以不要求 \(p\) 是多项式，而仅要求 \(p\) 是一个满足“\(\Delta^d(p)\) 为常值”这一条件的函数。那么上面的论证就会表明 \(p\) 是次数至多为 \(d\) 的多项式。不过，我们不需要这个更强的形式。

这条命题在说什么把它当成一台“次数检测器”：对一列数反复做逐项相减，做了 \(d\) 次以后如果变成一个常数，那这列数就是某个次数 \(\le d\) 的多项式生成的；反过来，若做满 \(d\) 次后还不是常数，它就不可能是次数 \(\le d\) 的多项式。这正是我们要用在 \(C_3(r)\) 上的工具——它的可能次数已被卡在 \(\le 8\)。
例：差分检测器在 \(p(n)=n^2\) 上的演示 取 \(0,1,4,9,16,25\)。
  1. 一阶差 \(\Delta\)：\(1,3,5,7,9\)（相邻相减）。
  2. 二阶差 \(\Delta^2\)：\(2,2,2,2\)——变成常数了。
  3. 做 \(2\) 次差就成常数，故 \(n^2\) 是次数 \(\le 2\) 的多项式，与事实相符。这就是命题 10.20 的具体运作方式。♦

利用我们的数值数据，我们可以轻松算出 \(\Delta^8(C_3(r))(0)\ne\Delta^8(C_3(r))(1)\)；因此 \(C_3(r)\) 不可能是次数至多为 \(8\) 的多项式，所以 \(C_3(r)\) 根本不可能是多项式。

例：把 \(\Delta^8\) 真的算出来 对图 10.8 的 \(10\) 个值反复做差分（每行都是上一行相邻两项相减），得到下面的差分三角：
  1. \(C_3\)：\(1,\;12,\;132,\;847,\;3921,\;14286,\;43687,\;116757,\;280656,\;619219\)
  2. \(\Delta^1\)：\(11,\;120,\;715,\;3074,\;10365,\;29401,\;73070,\;163899,\;338563\)
  3. \(\Delta^2\)：\(109,\;595,\;2359,\;7291,\;19036,\;43669,\;90829,\;174664\)
  4. \(\Delta^3\)：\(486,\;1764,\;4932,\;11745,\;24633,\;47160,\;83835\)
  5. \(\Delta^4\)：\(1278,\;3168,\;6813,\;12888,\;22527,\;36675\)
  6. \(\Delta^5\)：\(1890,\;3645,\;6075,\;9639,\;14148\)
  7. \(\Delta^6\)：\(1755,\;2430,\;3564,\;4509\)
  8. \(\Delta^7\)：\(675,\;1134,\;945\)
  9. \(\Delta^8\)：\(459,\;-189\)

第 \(8\) 阶差只剩两个数：\(\Delta^8(C_3)(0)=459\) 与 \(\Delta^8(C_3)(1)=-189\)。它们不相等，所以 \(\Delta^8(C_3)\) 不是常值函数。由命题 10.20，\(C_3(r)\) 不是次数 \(\le 8\) 的多项式；又因为它的次数若存在必 \(\le 8\)，故它不是任何多项式。

三维到底卡在哪一步

希望你现在正在好奇：究竟是什么导致了函数 \(C_3(r)\) 这种出人意料的行为？你或许还会想：\(C_3(r)\) 只是一个特例，还是说当 \(n\ge 3\) 时 \(C_n(r)\) 从来都不是多项式？

让我们试着照搬定理 10.3 的证明——那条定理表明 \(H_n(r)\) 总是多项式。我们卡住的地方是引理 10.6。该引理没有三维的类比。事实上，即便我们把注意力限制在边长为 \(3\)、线和为 \(2\) 的幻立方上，该引理也不成立。图 10.9 给出了一个反例。

200 011 011 第 1 层 011 101 110 第 2 层 011 110 101 第 3 层
图 10.9　一个线和为 \(2\) 的不可约幻立方（三层从左到右叠放）。

事实上，第一层只有唯一一种分解方式，而它右下角的格子使得另外两层的任何分解都无法拼进一个幻立方之中。

例：验证图 10.9 确为线和 2 的幻立方，并理解“卡住”
  1. 每层的每行、每列都验证：三层九个数排布下，行和、列和处处为 \(2\)。
  2. 竖直线（同一行列位置三层相加）：左上角 \(2+0+0=2\)；中心 \(1+0+1=2\)；右下角 \(1+0+1=2\)；其余位置同样为 \(2\)。三方向皆为 \(2\)，确是线和 \(2\) 的幻立方。
  3. 引理 10.6（二维版）说：线和 \(\ge 1\) 的幻方总能“剥掉”一个线和 \(1\) 的置换幻方。可在这里，第 \(1\) 层因左上角的 \(2\) 被迫成为 \(\begin{smallmatrix}2&0&0\\0&1&1\\0&1&1\end{smallmatrix}\) 这种唯一形态，它无法配上其余两层各剥出一个置换、又同时满足竖直方向的约束。剥离在三维被竖直约束“锁死”——这正是二维证明搬不过来的那一步。♦

我们称一个幻立方为不可约的（irreducible），如果它不能被分解为若干个更小线和的幻立方之和。上面的例子于是表明：并非所有不可约幻立方的线和都为 \(1\)。然而可以证明，边长为 \(3\) 的所有不可约幻立方的线和要么是 \(1\)，要么是 \(2\)。然后，可以用类似于定理 10.3 的证明的方式证明：\(C_3(2r)\) 与 \(C_3(2r+1)\) 都是多项式。既然我们已经知道存在边长为 \(3\)、线和为 \(2\) 的不可约幻立方，那么这一结果就并不令人意外。

本节小结第三个方向（竖直线）使幻立方的计数与幻方根本不同。
  1. 幻方的“剥离引理”（引理 10.6）无三维类比，图 10.9 给出反例：存在线和 \(2\) 的不可约幻立方。
  2. 因此 \(C_3(r)\) 不是单一多项式：差分检测器给出 \(\Delta^8(C_3)(0)=459\ne -189=\Delta^8(C_3)(1)\)。
  3. 但按奇偶拆开后，\(C_3(2r)\) 与 \(C_3(2r+1)\) 各自都是多项式——这正对应不可约幻立方的线和只能取 \(1\) 或 \(2\)。这种“按周期分段成多项式”的现象，是拟多项式（quasi-polynomial）的典型表现。

返回 全书目录