Bóna · 枚举与解析组合学导论 · 第 10 章 幻方与幻立方的计数
10.3 固定行和的幻方Magic squares of fixed line sum
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
现在，让我们假设我们考虑的幻方具有固定的行和 \(r\)，而它们的边长 \(n\) 在变化。换句话说，我们把 \(H_n(r)\) 看作 \(n\) 的函数，其中 \(r\) 固定。如果你更喜欢分配（distribution）的例子，那就是：参加游戏的孩子越来越多，可供选择的玩具种类也越来越多，但每个孩子拿到的玩具数保持不变，每一种玩具的总数也保持不变。
本节目标上一节固定的是边长 \(n\)、让行和 \(r\) 变化，得到的 \(H_n(r)\) 是 \(r\) 的多项式。本节反过来：固定行和 \(r\)，让边长 \(n\) 变化，研究 \(H_n(r)\) 随 \(n\) 怎样增长。结论是它不再是多项式。重头戏是把 \(r=2\) 的情形彻底算出来——通过一个分配模型把幻方计数翻译成“给小朋友发积木”的问题，再用容斥原理与二重指数生成函数求出闭式公式。
\(r=1\) 的幻方就是置换矩阵；\(3\times 3\) 共 \(6\) 个，对应 \(3!=6\) 个排列。一般地 \(H_n(1)=n!\)。
第 \(i\) 行第 \(j\) 列填 \(1\) 表示“孩子 \(i\) 拿到一块颜色 \(j\) 的积木”。行和为 \(2\)＝每个孩子两块；列和为 \(2\)＝每种颜色两块；禁止元素 \(2\)＝同色不给同一孩子两块。
固定行和 \(r=2\) 时，\(H_n(2)\) 随 \(n\) 急剧增长，印证了它不是 \(n\) 的多项式函数。
对于较小的 \(r\) 值，能说些什么呢？如果 \(r=0\)，那么对所有 \(n\) 都有 \(H_n(0)=1\)，因为此时幻方的所有元素都必须等于零。如果 \(r=1\)，那么 \(H_n(1)=n!\)，这一点我们在命题 10.5 中已经见过。所以，即使在这个简单的情形里，\(H_n(r)\) 也不是 \(n\) 的多项式函数，而是一个增长快得多的函数。
例：理解 \(H_n(0)\) 与 \(H_n(1)\)
- \(r=0\)：每行每列之和都为 \(0\)，而元素是非负整数，所以每个格子只能填 \(0\)。无论 \(n\) 多大，这样的幻方只有一个（全零方阵），故 \(H_n(0)=1\)。
- \(r=1\)：每行恰有一个 \(1\)、其余为 \(0\)；每列也是如此。这正是一个 \(n\times n\) 的置换矩阵（permutation matrix），与 \(n\) 元排列一一对应，所以 \(H_n(1)=n!\)。
\(n!\) 比任何 \(n\) 的多项式都增长得快（例如 \(5!=120\)、\(10!=3628800\)），可见 \(H_n(r)\) 作为 \(n\) 的函数已经“逃出”了多项式的范围。
寻找 \(H_n(2)\) 的公式这一任务则要困难得多。我们证明中的关键一环是下面这条引理，它归功于 Békéssy。
引理 10.16 设 \(T_n(2)\) 为行和为 \(2\) 且不含等于 \(2\) 的元素的 \(n\times n\) 幻方的个数。则对所有 \(n\ge 2\)，
\[\tag{10.15}T_n(2)=\frac{\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}\,n!\,(2n-2k-1)!!}{2^n}.\]
先看清 \(T_n(2)\) 数的是什么“行和为 \(2\)、且没有元素等于 \(2\)”意味着每个格子只能填 \(0\) 或 \(1\)（填 \(2\) 被禁止，填 \(\ge 3\) 会超过行和）。于是每行恰有两个 \(1\)、每列也恰有两个 \(1\)。这就是“每行每列都恰好两个 \(1\) 的 \(0/1\) 方阵”的个数。
此外提醒两个记号：双阶乘 \((2m-1)!!=1\cdot 3\cdot 5\cdots(2m-1)\)，并约定 \((-1)!!=1\)；下降阶乘 \((n)_k=n(n-1)\cdots(n-k+1)\)。
此外提醒两个记号：双阶乘 \((2m-1)!!=1\cdot 3\cdot 5\cdots(2m-1)\)，并约定 \((-1)!!=1\)；下降阶乘 \((n)_k=n(n-1)\cdots(n-k+1)\)。
例：手算 \(T_2(2)\) 与 \(T_3(2)\)
- \(n=2\)：每行两个 \(1\) 而只有两列，所以每行只能是 \((1,1)\)，整张方阵就是 \(\begin{smallmatrix}1&1\\1&1\end{smallmatrix}\)，只有 \(1\) 个，即 \(T_2(2)=1\)。代入 (10.15)：\(\frac{1}{4}\big[\binom20 2!\cdot3!!-\binom21 2!\cdot1!!+\binom22 2!\cdot(-1)!!\big]=\frac{1}{4}[6-4+2]=1\)。✓
- \(n=3\)：每行恰两个 \(1\) 等价于每行恰一个 \(0\)；这些 \(0\) 的位置在各行各列都恰好一个，即一个置换，故 \(T_3(2)=3!=6\)。代入 (10.15)：\(\frac18[\,1\cdot6\cdot15-3\cdot6\cdot3+3\cdot6\cdot1-1\cdot6\cdot1\,]=\frac18(90-54+18-6)=\frac{48}{8}=6\)。✓
证明. 回忆本章开头的分配问题。用那个问题的语言，我们的问题可以表述如下：我们有 \(2n\) 块积木，其中两块红色、两块蓝色，依此类推，每种颜色各两块，共 \(n\) 种颜色。同色的积木彼此相同。问有多少种方式把这 \(2n\) 块积木分给 \(n\) 个孩子，使得每个孩子恰得两块，且没有孩子拿到两块同色的积木？
首先，考虑一个略有不同的问题：连同色积木也视为不同（例如把它们编号为 \(1\) 和 \(2\)）。如果所有这种分配的总数记为 \(T_n'(2)\)，那么我们有 \(T_n'(2)=2^n\,T_n(2)\)。这是因为：若颜色 \(i\) 的两块积木不同，我们可以交换它们而得到一种新的分配。（注意，这里用到了“没有孩子拿到两块同色积木”这一事实。）所以，我们不妨改去求 \(T_n'(2)\) 而非 \(T_n(2)\)。
我们将用容斥论证来求 \(T_n'(2)\)。设 \(A\) 为把这 \(2n\) 块（已编号的）积木分给 \(n\) 个孩子、使每个孩子恰得两块（颜色可同可不同）的全体分配之集。则
\[\tag{10.16}|A|=(2n)!/2^n=(2n-1)!!\,n!.\]
事实上，我们可以把这 \(2n\) 块积木排成一行，然后把前两块给第一个孩子、第三第四块给第二个孩子，依此类推。这样排法共有 \((2n)!\) 种。然而每种分配会被数到 \(2^n\) 次，因为交换排中位置 \((2i-1)\) 与 \(2i\) 上的两块积木并不产生新的分配。
现在我们来数这 \(|A|\) 个分配中有多少是“坏的”，即把两块同色积木给了某些孩子。设 \(A_i\) 为孩子 \(i\) 拿到两块同色积木的分配之集。则
\[|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|=(n)_k\,(2n-2k)!/2^{\,n-k}=n!\,(2n-2k-1)!!.\]
因为我们可以先选定孩子 \(i_1,i_2,\cdots,i_k\) 各自拿到的那 \(k\) 种颜色，有 \((n)_k\) 种选法；然后把剩下的 \(2(n-k)\) 块积木任意分配，按 (10.16) 的证明，有 \((2n-2k-1)!!\,(n-k)!\) 种方式。注意我们用到了 \((n)_k\,(n-k)!=n!\)。
利用容斥原理，我们得到
\[\begin{aligned}
T_n'(2)&=|A|-|A_1\cup A_2\cup\cdots\cup A_n|\\
&=(2n-1)!!\,n!-\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}n!\,(2n-2k-1)!!\\
&=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}n!\,(2n-2k-1)!!.
\end{aligned}\]
应用恒等式 \(T_n'(2)=2^n\,T_n(2)\)，命题即证。♦
为什么 \(|A|=(2n)!/2^n\)（拆解 (10.16)）
- 把 \(2n\) 块各不相同的积木排成一队，方法有 \((2n)!\) 种。
- 规定：队首两块给孩子 1，接下来两块给孩子 2……这样每种排队都给出一个“每孩子两块”的分配。
- 但同一分配被重复数了：在每一对位置 \((2i-1,\,2i)\) 内部交换两块并不改变“孩子 \(i\) 得到哪两块”。每个孩子内部有 \(2\) 种顺序，\(n\) 个孩子共 \(2^n\) 种重复。
- 所以 \(|A|=(2n)!/2^n\)。又因 \((2n)!=2^n\,n!\,(2n-1)!!\)，故 \(|A|=(2n-1)!!\,n!\)。
为什么 \(|A_{i_1}\cap\cdots\cap A_{i_k}|=n!\,(2n-2k-1)!!\)
- “坏事件 \(A_{i_1}\cap\cdots\cap A_{i_k}\)”要求第 \(i_1,\dots,i_k\) 个孩子各拿到两块同色。先给这 \(k\) 个孩子各指派一种专属颜色：从 \(n\) 种颜色里有序地取 \(k\) 种，\((n)_k\) 种方法（这恰好用掉这 \(k\) 种颜色的两块积木）。
- 剩下 \(2(n-k)\) 块积木自由分给剩下的孩子（每人两块），照第 (10.16) 步的算法是 \((2n-2k-1)!!\,(n-k)!\) 种。
- 相乘并用 \((n)_k\,(n-k)!=n!\)，得 \(n!\,(2n-2k-1)!!\)。注意它只依赖 \(k\)（与具体选哪 \(k\) 个孩子无关），因此容斥求和里第 \(k\) 项带因子 \(\binom nk\)。
下面这条推论乍看之下大概会让人有些意外。
推论 10.17 设 \(\displaystyle T(x)=\sum_{n=0}^{\infty}T_n(2)\,\frac{x^n}{(n!)^2}\)，其中约定 \(T_0(2)=1\)。则
\[\tag{10.17}T(x)=\frac{e^{-x/2}}{\sqrt{1-x}}.\]
回忆第 3.5 节：对一列实数 \(a_n\)，幂级数 \(\sum_{n\ge 0}a_n\dfrac{x^n}{(n!)^2}\) 称为序列 \(a_n\) 的二重指数生成函数（doubly exponential generating function）。所以 \(T(x)\) 是序列 \(T_n(2)\) 的二重指数生成函数，而推论 10.17 表明它有一个相当紧凑的形式。
证明（推论 10.17）. 我们将证明 (10.17) 两边的两个幂级数相等，办法是证明：对所有 \(n\)，两个幂级数中 \(x^n/(n!)^2\) 的系数都相同。
在左边，这个系数（由引理 10.16）等于
\[\frac{\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k}n!\,(2n-2k-1)!!}{2^n}.\]
右边是两个幂级数 \(e^{-x/2}\) 与 \((1-x)^{-1/2}\) 的乘积。\(e^{-x/2}\) 的展开是直接的，即
\[e^{-x/2}=\sum_{k\ge 0}(-1)^k\frac{x^k}{2^k k!}.\]
\((1-x)^{-1/2}\) 的展开可由二项式定理得到。注意
\[\binom{-1/2}{i}=\frac{(-1/2)(-3/2)\cdots((-2i+1)/2)}{i!}=\frac{(-1)^i(2i-1)!!}{2^i i!}.\]
因此，由二项式定理，
\[\tag{10.18}(1-x)^{-1/2}=\sum_{i\ge 0}\binom{-1/2}{i}(-x)^i=\sum_{i\ge 0}\frac{(2i-1)!!}{2^i i!}x^i.\]
把 \(e^{-x/2}\) 与 \((1-x)^{-1/2}\) 的展开相乘，我们得到 (10.17) 右边等于
\[\sum_{n\ge 0}x^n\sum_{k=0}^{n}\frac{(-1)^k}{2^k k!}\cdot\frac{(2n-2k-1)!!}{(n-k)!\,2^{\,n-k}}=\sum_{n\ge 0}x^n\sum_{k=0}^{n}\frac{(-1)^k(2n-2k-1)!!}{k!(n-k)!\cdot 2^n}.\]
(10.17) 右边 \(x^n\) 的系数是
\[\sum_{k=0}^{n}\frac{(-1)^k(2n-2k-1)!!}{k!(n-k)!\cdot 2^n},\]
这说明 \(x^n/(n!)^2\) 的系数是
\[(n!)^2\sum_{k=0}^{n}\frac{(-1)^k(2n-2k-1)!!}{k!(n-k)!\,2^n}=\frac{n!}{2^n}\sum_{k=0}^{n}(-1)^k\binom{n}{k}(2n-2k-1)!!,\]
它确实与左边相应的系数一致。这就证明了我们的推论。♦
两个关键变形说明
- 把 \(\binom{-1/2}{i}\) 化成双阶乘：分子 \((-\tfrac12)(-\tfrac32)\cdots(-\tfrac{2i-1}{2})\) 共 \(i\) 个因子，每个都含 \(-\tfrac12\)，提出 \((-1)^i/2^i\)，余下 \(1\cdot3\cdots(2i-1)=(2i-1)!!\)。代入 \((1-x)^{-1/2}\) 时 \((-x)^i\) 的 \((-1)^i\) 与之相消，符号变正——这正是 (10.18) 全为正号的原因。
- 把 \(x^n\) 系数乘回 \((n!)^2\)：因为系数是按 \(x^n/(n!)^2\) 提取的，要还原就乘 \((n!)^2\)；再把 \(\dfrac{(n!)^2}{k!(n-k)!}\) 写成 \(n!\binom nk\)，就得到与左边逐项相同的形状。
用 \(n=2\) 核对推论把 \(T_0=1,\ T_1=0,\ T_2=1\) 代入左边定义，\(x^2/(2!)^2\) 的系数应为 \(T_2(2)=1\)。右边按上式取 \(n=2\)：\(\frac{2!}{2^2}\sum_{k=0}^2(-1)^k\binom2k(3-2k)!! =\frac24[\,3!!-2\cdot1!!+(-1)!!\,]=\frac12[3-2+1]=1\)。✓ 两边吻合。
你也许会说，这很好，但你事先怎么知道 \(\dfrac{e^{-x/2}}{\sqrt{1-x}}\) 就是 \(T(x)\) 的正确表达式呢？这是一个非常恰当的问题。也就是说，上面这个证明的“问题”在于：结果是被验证出来的，而不是被推导出来的。一个真正把答案推导出来的证明，可见习题 11 与习题 12。
下面这条引理揭示了数 \(T_n(2)\) 与 \(H_n(2)\) 之间非常紧密的联系。
引理 10.18 设 \(\displaystyle H(x)=\sum_{n\ge 0}H_n(2)\,\frac{x^n}{(n!)^2}\) 为序列 \(H_n(2)\) 的二重指数生成函数。则
\[\tag{10.19}H(x)=\frac{e^{x/2}}{\sqrt{1-x}}.\]
证明. 注意到由推论 10.17，本引理等价于
\[H(x)=e^{x}T(x).\]
我们将通过证明两边 \(x^n/(n!)^2\) 的系数对所有 \(n\) 都相等来证明后者。
在左边，这个系数是 \(H_n(2)\)。我们把右边展开为
\[e^{x}T(x)=\left(\sum_{k\ge 0}\frac{x^k}{k!}\right)\cdot\left(\sum_{i\ge 0}T_i(2)\frac{x^i}{(i!)^2}\right)=\sum_{n\ge 0}\left(\sum_{k=0}^{n}\frac{1}{k!}\cdot\frac{T_{n-k}(2)}{((n-k)!)^2}\right)x^n.\]
因此，右边 \(x^n\) 的系数是 \(\displaystyle\sum_{k=0}^{n}\frac{1}{k!}\cdot\frac{T_{n-k}(2)}{((n-k)!)^2}\)，于是 \(x^n/(n!)^2\) 的系数是
\[\tag{10.20}(n!)^2\sum_{k=0}^{n}\frac{1}{k!}\cdot\frac{T_{n-k}(2)}{((n-k)!)^2}=\sum_{k=0}^{n}\binom{n}{k}^2 k!\,T_{n-k}(2).\]
因此，只要我们能证明上式 (10.20) 的右边等于 \(H_n(2)\)，本引理即得证。这可以如下完成：
设 \(H\) 是被 \(H_n(2)\) 所计数的一张幻方，它恰好含有 \(k\) 个等于 \(2\) 的元素。选择这 \(k\) 个元素位置的方法有 \(\binom nk^2 k!\) 种。然后我们必须填满剩下的 \((n-k)\times(n-k)\) 网格，使每行每列都含有两个等于 \(1\) 的元素，这有 \(T_{n-k}(2)\) 种方法。这就证明了 (10.20) 成立，从而完成了引理的证明。♦
为什么放 \(k\) 个 “2” 的位置有 \(\binom nk^2 k!\) 种
- 含有 \(k\) 个 \(2\) 的幻方，由于行和列和都是 \(2\)，每个 \(2\) 独占它所在的整行与整列（该行该列其余全为 \(0\)）。所以这 \(k\) 个 \(2\) 落在 \(k\) 个不同的行、\(k\) 个不同的列上。
- 选出哪 \(k\) 行：\(\binom nk\) 种；选出哪 \(k\) 列：\(\binom nk\) 种。
- 把这 \(k\) 行与这 \(k\) 列一一配对（决定每个 \(2\) 的具体格子）：\(k!\) 种。三者相乘得 \(\binom nk^2 k!\)。
- 去掉这些行列后，剩下的 \((n-k)\times(n-k)\) 子网格行和列和仍是 \(2\) 且不能再出现 \(2\)，恰被 \(T_{n-k}(2)\) 计数。对 \(k=0,1,\dots,n\) 求和即 (10.20)。
最后，我们终于可以陈述并证明关于数 \(H_n(2)\) 的公式了。
定理 10.19 对所有正整数 \(n\ge 1\)，
\[\tag{10.21}H_n(2)=\frac{n!}{2^n}\sum_{k=0}^{n}\binom{n}{k}(2n-2k-1)!!.\]
证明. 由引理 10.18，\(H_n(2)\) 是 \(H(x)=e^{x/2}/\sqrt{1-x}\) 中 \(x^n/(n!)^2\) 的系数。一方面，我们有
\[e^{x/2}=\sum_{k\ge 0}\frac{x^k}{2^k k!}.\]
另一方面，我们刚刚在 (10.18) 中算出了 \((1-x)^{-1/2}\)。利用那个公式，我们得到
\[H(x)=\sum_{n\ge 0}x^n\sum_{k=0}^{n}\frac{(2n-2k-1)!!}{k!(n-k)!\cdot 2^n}.\]
注意这个计算与推论 10.17 的证明完全相同，只是略去了 \((-1)^k\)。这表明 \(H(x)\) 中 \(x^n/(n!)^2\) 的系数 \(H_n(2)\) 是 \(\displaystyle\sum_{k=0}^{n}\frac{\binom nk\,n!\,(2n-2k-1)!!}{2^n}\)，正如所断言。♦
例：用 (10.21) 算出 \(H_1,H_2,H_3\)
- \(n=1\)：\(H_1(2)=\frac{1!}{2}\big[\binom10 1!!+\binom11 (-1)!!\big]=\frac12[1+1]=1\)。即 \(1\times1\) 方阵只有 \([\,2\,]\) 一张。
- \(n=2\)：\(H_2(2)=\frac{2!}{2^2}\big[\binom20 3!!+\binom21 1!!+\binom22 (-1)!!\big]=\frac24[3+2+1]=\frac12\cdot6=3\)。可直接枚举验证：三张分别是 \(\begin{smallmatrix}2&0\\0&2\end{smallmatrix},\ \begin{smallmatrix}0&2\\2&0\end{smallmatrix},\ \begin{smallmatrix}1&1\\1&1\end{smallmatrix}\)。
- \(n=3\)：\(H_3(2)=\frac{3!}{2^3}\sum_{k=0}^3\binom3k(5-2k)!! =\frac{6}{8}\,[\,15+3\cdot3+3\cdot1+1\,]=\frac{6}{8}\cdot28=21\)。
正确值序列为 \(H_1(2)=1,\ H_2(2)=3,\ H_3(2)=21\)；这与用引理 10.18 的关系式 \(H_n(2)=\sum_{k}\binom nk^2 k!\,T_{n-k}(2)\) 逐一核对的结果一致。
这里有几个问题值得一问。是否存在一个不使用生成函数、且相当简单的此公式的证明？如果有，那个组合证明能否解释分母里的 \(2^n\) 这一项？注意，为什么 \(n!\sum_{k=0}^{n}\binom nk n!\,(2n-2k-1)!!\) 应当能被 \(2^n\) 整除，绝非显然之事。
这两个问题的答案都是肯定的，正如 W. Griffiths 给出的一个漂亮论证 [40] 所示。我们邀请读者参阅习题 4 与习题 5，它们将引导读者走完那个有趣的证明。
即时自测
- 有多少个行和为 \(2\)、且含有 \(n-2\) 个数字 \(2\) 的 \(n\times n\) 幻方？
返回 全书目录