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

10.2　固定阶数的幻方Magic squares of fixed size

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

本节目标把幻方（magic square）的阶数 \(n\) 固定下来，研究“行列和为 \(r\) 的 \(n\times n\) 幻方共有多少个”。本节先把最小的两种情形 \(n=1\) 与 \(n=2\) 算清楚，得到计数函数 \(H_n(r)\) 的前两个公式。

预备：幻方与记号 \(H_n(r)\)

为方便阅读，先回顾上一节用到的定义与记号。

定义 10.1 一个幻方（magic square）是指一个元素为非负整数的方阵，并且其中所有的行和（row sum）与列和（column sum）都相等。

幻方还有其他定义。例如，我们可以额外要求两条对角线之和也与行、列之和相等；或者要求任何一行、任何一列中不出现重复的数字。然而在本书中，我们只采用定义 10.1。

注意，在一个幻方中，不可能出现“所有行和都等于 \(a\)，而所有列和都等于 \(b\)，且 \(a\neq b\)”的情形。事实上，若如此，则按行统计时方阵中全部元素之和等于 \(na\)，按列统计时又等于 \(nb\)，这就产生了矛盾。

我们把行（rows）与列（columns）统称为线（lines），并记 \(H_n(r)\) 为线和（line sum）等于 \(r\) 的 \(n\times n\) 幻方的个数。本章开头的例子问的就是 \(H_3(20)\) 的值。更一般地，我们可以对任意给定的线和 \(r\) 询问 \(H_3(r)\) 的值，也可以对任意边长 \(n\) 询问 \(H_n(60)\) 的值。换句话说，我们既可以固定幻方的阶数、研究 \(H_n(r)\) 如何随 \(r\) 变化，也可以固定线和 \(r\)、考察 \(H_n(r)\) 如何随 \(n\) 变化。本节走的是前一条路：固定 \(n\)。

例（看清记号） 下面是一个线和 \(r=20\) 的 \(3\times3\) 幻方：每一行之和、每一列之和都等于 \(20\)。它就是 \(H_3(20)\) 所计数的对象之一。
929 479 7112 行和 20行和 20行和 20 列 20列 20列 20
所有元素为非负整数，三行三列之和都等于 \(20\)，故它是一个线和 \(20\) 的 \(3\times3\) 幻方（这里不要求对角线相等）。

从最小的 \(n\) 开始

让我们从小的固定 \(n\) 值开始。

情形 \(n=1\)

若 \(n=1\)，那么构造一个线和为 \(r\) 的 \(n\times n\) 幻方只有一种办法：把它唯一的那个元素置为 \(r\)。因此

\[\tag{$n=1$}H_1(r)=1.\]
例（\(n=1\) 一目了然） \(1\times1\) 的方阵只有一个格子，它既是“第一行”，又是“第一列”。要让行和与列和都等于 \(r\)，这个格子里只能填 \(r\)，没有别的选择。所以无论 \(r\) 取多少，都恰有 \(1\) 个这样的幻方，\(H_1(r)=1\)。

情形 \(n=2\)

这并不太难。\(n=2\) 的情形也不复杂。事实上，只要我们知道一个线和为 \(r\) 的 \(2\times2\) 幻方左上角的元素，就能算出它的所有元素，如图 10.2 所示。

设左上角元素为 \(x\)。由“第一行之和为 \(r\)”知右上角为 \(r-x\)；由“第一列之和为 \(r\)”知左下角为 \(r-x\)；再由“第二行之和为 \(r\)”（或“第二列之和为 \(r\)”）知右下角为 \(r-(r-x)=x\)。于是整个幻方完全由 \(x\) 决定：

\[\tag{图 10.2}\begin{pmatrix} x & r-x\\[2pt] r-x & x \end{pmatrix}.\]
xr−x r−xx ← 行和 r ← 行和 r ↑列和 r↑列和 r 给定 x， 其余三格 被唯一确定
图 10.2：一旦左上角填入 \(x\)，由各条线之和为 \(r\) 即可依次推出其余三个元素，整张幻方完全由 \(x\) 决定。
推导. 把“为什么左上角一确定，整张幻方就确定”拆成最小的步子：
  1. 设左上角 \(=x\)。第一行两数之和须为 \(r\)，故右上角 \(=r-x\)。
  2. 第一列两数之和须为 \(r\)，故左下角 \(=r-x\)。
  3. 第二行（左下 \(+\) 右下）之和须为 \(r\)，故右下角 \(=r-(r-x)=x\)。
  4. 验证第二列：右上 \(+\) 右下 \(=(r-x)+x=r\)，与列和要求一致，没有矛盾。

因为 \(x\) 与 \(r-x\) 都必须是非负整数，所以必有 \(0\le x\le r\)，这就给 \(x\) 留下了 \(r+1\) 种可能。又因为 \(x\) 完全决定了整个幻方，于是得到

\[\tag{$n=2$}H_2(r)=r+1.\]
为什么是 \(r+1\) 种.
  1. 非负性要求 \(x\ge 0\)，同时要求 \(r-x\ge 0\)，即 \(x\le r\)。
  2. 合起来 \(0\le x\le r\)，且 \(x\) 取整数。
  3. 满足这一范围的整数为 \(x=0,1,2,\dots,r\)，恰好 \(r+1\) 个。
  4. 每一个 \(x\) 给出一张不同的幻方，且每张幻方对应唯一的 \(x\)（即左上角），所以幻方个数 \(=x\) 的取值个数 \(=r+1\)。♦
例（数一数 \(H_2(3)\)） 取 \(r=3\)。按公式应有 \(H_2(3)=3+1=4\) 个。直接把 \(x=0,1,2,3\) 逐一写出：
0330 1221 2112 3003 x=0x=1x=2x=3
线和 \(r=3\) 的全部 \(2\times2\) 幻方：左上角 \(x\) 依次取 \(0,1,2,3\)，共 \(4\) 张，正好等于 \(H_2(3)=r+1=4\)。
例（更多取值） 由 \(H_2(r)=r+1\) 立刻得到：\(H_2(0)=1\)（唯一的全 \(0\) 幻方），\(H_2(1)=2\)，\(H_2(2)=3\)，\(H_2(5)=6\)。可见对固定阶数 \(n=2\)，幻方个数随线和 \(r\) 线性增长。
即时自测
  1. 把上面图 10.2 的推导用到 \(r=0\) 上：写出全部线和为 \(0\) 的 \(2\times2\) 幻方，并核对它确实只有 \(H_2(0)=1\) 个。
  2. 若把“非负整数”改成“任意整数”（允许出现负数），那么 \(H_2(r)\) 还有限吗？为什么？（提示：此时 \(x\) 可取任意整数。）
  3. 仿照 \(n=2\) 的思路想一想：对 \(n=3\)，是否仅凭左上角一个元素就能确定整张幻方？这预示着 \(H_3(r)\) 会比 \(r+1\) 复杂多少？

返回 全书目录