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

10.1　一个分配问题A distribution problem

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

第 10 章 幻方与幻立方的计数（Counting magic squares and magic cubes）引言。

在前面的各章里，我们考虑过各式各样的分配问题（distribution problem）。现在我们回到这个主题，但这一回的分配问题在某种意义上将是多维的（multidimensional）。

10.1　一个分配问题

假设我们要把 \(60\) 块积木分给三个孩子。设其中 \(20\) 块是红色的，\(20\) 块是蓝色的，\(20\) 块是绿色的。为了维护世界和平，我们打算给每个孩子 \(20\) 块。如果同色的积木被视为彼此相同，那么这件事一共有多少种不同的分法？（请注意，如果连同色的积木也彼此不同，那么这个问题就没多大意思了；事实上，那种情形下所有积木都两两不同，答案是 \(\binom{60}{20}\cdot\binom{40}{20}\)。）

本节目标把第 10 章要研究的对象立起来：把“把同色积木按人数均分”这一分配问题翻译成一张方格表，并观察到这张表的每一行之和、每一列之和都相等。这个观察正是后文“幻方”定义的出发点。
例：括号里那句“没意思”的答案从哪来 若所有 \(60\) 块积木两两不同，要给每人各 \(20\) 块：
  1. 先从 \(60\) 块里挑 \(20\) 块给第一个孩子：\(\binom{60}{20}\) 种。
  2. 再从剩下的 \(40\) 块里挑 \(20\) 块给第二个孩子：\(\binom{40}{20}\) 种。
  3. 最后剩下的 \(20\) 块全给第三个孩子，只有 \(1\) 种。
  4. 由乘法原理，总数为 \(\binom{60}{20}\cdot\binom{40}{20}\cdot 1=\binom{60}{20}\cdot\binom{40}{20}\)。
正因为积木全不同时这只是“反复用组合数挑选”的老问题，所以作者说它“没多大意思”。真正困难、也是本章主角的，是同色积木相同的版本。♦

这个分配问题比我们在前面各章见过的那些都要困难。为了更好地理解它，我们将用一张正方形方格表（square grid）来表示一种可能的分法，如图 10.1 所示。

红 Red 蓝 Blue 绿 Green Miki Benny Vinnie 758 686 776
图 10.1　一种可能的分配方式。第 \(i\) 行第 \(j\) 列的数表示第 \(i\) 个孩子拿到的第 \(j\) 种颜色的积木块数。

请注意，每一行各元素之和都等于 \(20\)（因为每个孩子都拿到 \(20\) 块），而每一列各元素之和也都等于 \(20\)，因为每种颜色都恰有 \(20\) 块。正是这个观察，引出了下面的定义。

把图 10.1 的行和、列和逐个核对一遍
  1. 看“分法 ↔ 方格表”的对应：把第 \(i\) 个孩子拿到的第 \(j\) 种颜色的块数填在第 \(i\) 行第 \(j\) 列。一种分法就唯一对应一张这样的整数方格表，反之亦然。
  2. 行和（每个孩子拿到的总块数）。Miki：\(7+5+8=20\)；Benny：\(6+8+6=20\)；Vinnie：\(7+7+6=20\)。三行都是 \(20\)，因为每人正好拿 \(20\) 块。
  3. 列和（每种颜色被分掉的总块数）。红：\(7+6+7=20\)；蓝：\(5+8+7=20\)；绿：\(8+6+6=20\)。三列都是 \(20\)，因为每色正好有 \(20\) 块。
  4. 一致性检验：所有格子之和应等于积木总数 \(60\)。按行加：\(20\times 3=60\)；按列加：\(20\times 3=60\)，两种数法相符。
于是“给三个孩子各 \(20\) 块、三色各 \(20\) 块”的一种分法，恰好就是“一张 \(3\times 3\) 的非负整数方格表，且每行之和、每列之和都等于 \(20\)”。数分法的个数，就化成了数这种方格表的个数——这正是本章把分配问题“多维化”的关键一步。♦
承上启下这张“行和、列和处处相等”的方格表，就是即将给出的幻方（magic square）一类对象的雏形。本节到此为分配问题搭好了表格模型；下一步将据此给出正式定义，并着手计数这种方格表的数目。

返回 全书目录