10.8　习题解答Solutions to exercises

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

习题 1

译文. 给定 \((a,b,c,d)\)，我们可以算出 \[\varphi(a,b,c,d)=(a,\;2a+d-c,\;a+b+d-c,\;b+d).\] 反过来，给定 \((e,f,g,h)=(a,\,2a+d-c,\,a+b+d-c,\,b+d)\)，我们可以由 \[a=e,\quad b=e-f+g,\quad c=e-g+h,\quad d=-e+f-g+h\] 反算出 \((a,b,c,d)\)。因此 \(\varphi\) 存在逆映射，从而 \(\varphi\) 是一个双射（bijection）。

1. 把 \(\varphi\) 的四个分量写成方程组： \[e=a,\qquad f=2a+d-c,\qquad g=a+b+d-c,\qquad h=b+d.\]
2. 解 \(a\)：第一式直接给出 \(a=e\)。
3. 解 \(b\)：计算 \(e-f+g=a-(2a+d-c)+(a+b+d-c)=b\)。逐项相消：\(a-2a+a=0\)，\(-d+d=0\)，\(+c-c=0\)，只剩 \(b\)。故 \(b=e-f+g\)。
4. 解 \(c\)：计算 \(e-g+h=a-(a+b+d-c)+(b+d)=c\)。相消：\(a-a=0\)，\(-b+b=0\)，\(-d+d=0\)，只剩 \(c\)。故 \(c=e-g+h\)。
5. 解 \(d\)：计算 \(-e+f-g+h=-a+(2a+d-c)-(a+b+d-c)+(b+d)=d\)。相消：\(-a+2a-a=0\)，\(-c+c=0\)，\(-b+b=0\)，\(d+d-d=d\)。故 \(d=-e+f-g+h\)。
6. 四个未知数都被 \((e,f,g,h)\) 唯一确定，说明 \(\varphi\) 有逆，\(\varphi\) 是双射。♦

习题 2

译文. 不等式 (10.5) 与 (10.6) 都是多余的（redundant），因为 \(d\) 非负，而 \(c\) 比 \(a\) 和 \(b\) 都小。不等式 (10.3) 也是多余的，因为它由 (10.7) 推出。事实上， \[r-a-d\;\ge\;r-a-d-(b-c)\;\ge\;0,\] 这里第一个不等号成立是因为 \(b>c\)（故 \(b-c\ge0\)），第二个不等号正是 (10.7)。最后，(10.4) 同样多余，因为它也由 (10.7) 推出。事实上， \[r-b-d\;\ge\;r-b-d-(a-c)\;\ge\;0,\] 这里因为 \(a>c\)。

1. (10.5)、(10.6) 多余：它们形如“某个表达式 \(\ge0\)”，而其左边可写成“非负量 \(d\) 加上 \(a-c\) 或 \(b-c\)”。因为 \(d\ge0\) 且 \(c0,\;b-c>0\)），三个非负数相加必非负，结论自动成立。
2. (10.3) 多余的链式推理：要证 \(r-a-d\ge0\)。关键是先减去一个非负量 \(b-c\) 再说明仍非负： \[r-a-d\;\ge\;\underbrace{r-a-d-(b-c)}_{\text{这正是 (10.7) 的左边}}\;\ge\;0.\] 第一步成立是因为减去了非负数 \(b-c\)（\(b>c\)），所以原式更大；第二步就是已知条件 (10.7)。两步合起来得 \(r-a-d\ge0\)，即 (10.3)。
3. (10.4) 多余：完全对称地，减去非负量 \(a-c\)（\(a>c\)）： \[r-b-d\;\ge\;r-b-d-(a-c)\;\ge\;0.\] 同样第二个不等号是 (10.7)，于是得 \(r-b-d\ge0\)，即 (10.4)。♦

习题 3

译文. 设 \(p(x)=a_mx^m+a_{m-1}x^{m-1}+\cdots+a_1x+a_0\)。把 \(x=0,1,\dots,m\) 代入，得到一个含 \(m+1\) 个方程、\(m+1\) 个未知数 \(a_m,a_{m-1},\dots,a_0\) 的线性方程组。于是可用线性代数解出该方程组。

1. 代入 \(x=0\)：\(p(0)=a_0\)。代入 \(x=1\)：\(p(1)=a_m+a_{m-1}+\cdots+a_1+a_0\)。一般地代入 \(x=j\)： \[p(j)=a_m j^m+a_{m-1}j^{m-1}+\cdots+a_1 j+a_0,\qquad j=0,1,\dots,m.\]
2. 把已知值 \(p(0),p(1),\dots,p(m)\) 看成常数，未知数是 \(a_0,\dots,a_m\)，这就是 \(m+1\) 个一次方程、\(m+1\) 个未知数的线性方程组。
3. 它的系数矩阵是范德蒙德矩阵（Vandermonde matrix），由 \(x=0,1,\dots,m\) 这 \(m+1\) 个互不相同的取值构成，其行列式不为零，故方程组有唯一解。线性代数保证系数 \(a_0,\dots,a_m\) 可被唯一解出。♦

习题 4

译文. 以 \(k\) 为下标的那一项，是恰含 \(k\) 个数字 2 的 \(n\) 阶双幻方（double magic square）的个数。在这些双幻方中，有 \(\binom{n}{k}\) 种方式选出放这些 2 的“行对”，再有 \(\dfrac{n!}{(n-k)!}\) 种方式选出对应的“列对”。由于这些 2 可以落在一对列中的任一列，但必须落在每个行对的上面那一行，所以行对、列对选定后，确定它们确切位置有 \(2^k\) 种方式。删去含 2 的行对与列对后，得到的是某个 \((2n-2k)!\) 阶（即 \((2n-2k)\times(2n-2k)\)）的置换矩阵之一。

1. 选行对：从 \(n\) 个行对里挑出 \(k\) 个来安放 2，无序选取，共 \(\binom{n}{k}\) 种。
2. 选列对：给这 \(k\) 个 2 各配一个列对，要求互不相同且有先后对应（有序），即从 \(n\) 个列对里有序取 \(k\) 个，共 \(n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}\) 种。
3. 定每个 2 的精确格子：每个 2 必须放在它所在行对的上行，但左列或右列二选一，故每个 2 有 \(2\) 种位置；\(k\) 个 2 相互独立，乘起来是 \(2^k\) 种。
4. 剩下的部分：把含 2 的 \(k\) 个行对、\(k\) 个列对全部删去，剩下一个 \((2n-2k)\times(2n-2k)\) 的 0–1 矩阵，它恰是一个置换矩阵（permutation matrix），共有 \((2n-2k)!\) 个。
5. 由乘法原理，恰含 \(k\) 个 2 的双幻方个数为 \[\binom{n}{k}\cdot\frac{n!}{(n-k)!}\cdot 2^{k}\cdot(2n-2k)!\,. \] 对 \(k\) 求和即得双幻方总数。♦

习题 5

译文 (a). 映射 \(f\) 的定义极其简单。给定 \(A\in S\)，令 \(f(A)\) 为这样的幻方：其 \((i,j)\) 元等于 \(A\) 的第 \(i\) 个行对与第 \(j\) 个列对相交处那四个元素之和。于是若 \(A\) 是图 10.10 所示的双幻方，则 \(f(A)\) 是图 10.12 所示的幻方。由双幻方定义中的第一条判据可知 \(f(A)\in T\)。剩下要证：对每个 \(B\in T\)，恰有 \(2^{2n}\) 个 \(A\in S\) 满足 \(f(A)=B\)。

设 \(B\in T\)。我们如下找出 \(B\) 在 \(f\) 下的所有原像。第一步，把 \(B\) 的列加倍：将 \(B\) 变成一个 \(n\times2n\) 的矩阵 \(B'\)，旧的第 \(j\) 列变成新的列对 \((2j-1,2j)\)；旧的 \((i,j)\) 元告诉我们新位置 \((i,2j-1)\) 与 \((i,2j)\) 该填什么。具体地：若第 \(j\) 列原有两个 1（在 \((i,j)\) 与 \((i',j)\)），则对应列对在两列之一得到一个 1，并在相对位置也得到一个 1；故每个不含 2 的列让我们二选一。若 \(B\) 的 \((i,j)\) 元是 2，则同样有两种可能：把 \(B'\) 的 \((i,2j-1)\) 元或 \((i,2j)\) 元设为 2（见图 10.13）。注意 \(B'\) 的每一列至多有一个非零元，且每个列对之和为 2。

第二步，把 \(B'\) 的行加倍（规则略有不同）。若 \(B\) 的第 \(i\) 行原有两个 1，则对应行对在对角位置得到两个 1，又是二选一。换言之，若第 \(i\) 行在第 \(j\) 列、第 \(j'\) 列各有一个 1，则新矩阵 \(B''\) 中，对应 \((i,j)\) 处的 1 落在 \((2i-1,j)\) 或 \((2i,j)\)；无论怎么选，对应 \((i,j')\) 处的 1 必须取相反的选择。然而一个 2 既可以留在行对的上行，也可以拆成位于该 2 所对应 \(2\times2\) 块对角线上的两个 1（见图 10.14）。

注意无论作出怎样的选择序列，\(B''\) 都是 \(S\) 中的一个双幻方。又由定义可知 \(f(B'')=B\)，因为 \(B''\) 第 \(i\) 行对与第 \(j\) 列对相交处之和正是 \(B\) 的 \((i,j)\) 元。再由定义，\(B\) 在 \(f\) 下的所有原像都能用此程序作为 \(B''\) 得到。由于整个过程共作了 \(2n\) 次独立的二选一（拆列阶段 \(n\) 列各一次，给出 \(2^{n}\) 种；拆行阶段 \(n\) 行各一次，给出 \(2^{n}\) 种），故原像总数为 \(2^{n}\cdot2^{n}=2^{2n}\)，命题得证。

译文 (b). 对上一题的结果应用除法原理（division principle）与 (a) 的结果即可。

1. \(f\) 的定义（合块求和）：把双幻方 \(A\) 的行、列两两成对，每个 \(2\times2\) 小块（第 \(i\) 行对 × 第 \(j\) 列对）的四个数加起来，作为新幻方 \(f(A)\) 的 \((i,j)\) 元。这样 \(n\times n\) 个块就给出一个 \(n\times n\) 的幻方。
2. 为何 \(f(A)\in T\)：每个 \(2\times2\) 块求和后，新方阵的行和、列和都由原双幻方的行和、列和合并而来，仍处处相等，故 \(f(A)\) 确为合法幻方（满足 \(T\) 的判据）。
3. 数原像：恰有 \(2^{2n}\) 个。反过来从 \(B\in T\) 复原 \(A\)。先“拆列”：每一列变成两列，每个非零项有“放左列还是右列”两种独立选择；\(n\) 列对应 \(2^{n}\) 种？——书中按列、行两阶段各自给出独立的二选一，合计独立选择次数为 \(2n\)，故组合数为 \(2^{2n}\)。每一种选择都还原出一个合法的 \(A\in S\) 且 \(f(A)=B\)，且所有原像都这样得到，互不重复。
4. 结论 (a)：每个 \(B\) 恰有 \(2^{2n}\) 个原像。
5. 结论 (b)：由除法原理 \(|T|=\dfrac{|S|}{2^{2n}}\)，把上一题求得的 \(|S|\) 代入即得 \(T\) 的计数。♦

习题 6

译文. 不是。如图 10.15 所示，三个元素 \(a,b,c\) 完全决定了这样一个幻方。所以若 \(P_3(r)\) 是多项式，其次数不会超过 3。计算 \(P_3(r)\) 的前五个值，得 \[P_3(0)=1,\quad P_3(1)=4,\quad P_3(2)=11,\quad P_3(3)=23,\quad P_3(4)=42.\] 于是不难验证 \(\Delta^3(P_3)(0)\neq\Delta^3(P_3)(1)\)；因此 \(P_3(n)\) 不可能是多项式。

1. 为何次数 \(\le3\)：这种 \(3\times3\) 幻方只有 \(a,b,c\) 三个自由元（其余由线和约束定出）。每个自由元的取值范围由 \(r\) 线性界定，故计数至多是 \(r\) 的三次量级——若它是多项式，次数不超过 3。
2. 列出前五个值并逐阶差分： \[\begin{array}{c|ccccc} P_3 & 1 & 4 & 11 & 23 & 42\\\hline \Delta & 3 & 7 & 12 & 19 &\\ \Delta^2 & 4 & 5 & 7 & &\\ \Delta^3 & 1 & 2 & & & \end{array}\] 一阶差分：\(4-1=3,\,11-4=7,\,23-11=12,\,42-23=19\)。二阶：\(7-3=4,\,12-7=5,\,19-12=7\)。三阶：\(5-4=1,\,7-5=2\)。
3. 判定：\(\Delta^3(P_3)(0)=1\) 而 \(\Delta^3(P_3)(1)=2\)，三阶差分不是常数。若 \(P_3\) 是次数 \(\le3\) 的多项式，三阶差分必为常数；矛盾。故 \(P_3(n)\) 不是多项式。♦

习题 7

译文. 设 \(P\) 是被 \(P_{n+1}(1)\) 计数的一个幻方（即 \((n+1)\times(n+1)\) 的对称置换矩阵）。则 \(P\) 的第一行含一个 1。这个 1 要么在第一个位置，此时余下的 \(n\times n\) 对称幻方有 \(P_n(1)\) 种可能；要么在别处，此时它可在 \(n\) 个不同位置，每个都在主对角线之外。无论在哪个位置，该位置的镜像位置也必须含一个 1，于是余下的 \((n-1)\times(n-1)\) 对称幻方有 \(P_{n-1}(1)\) 种可能。

1. 第一行恰有一个 1（置换矩阵每行恰一个 1）。分两种情况。
2. 情况一：这个 1 在 \((1,1)\)。由对称性，第一列的 1 也在 \((1,1)\)。删去第一行与第一列，剩下 \(n\times n\) 的对称置换矩阵，共 \(P_n(1)\) 种。
3. 情况二：这个 1 在 \((1,t)\)，\(t\neq1\)。共 \(n\) 个这样的位置（第 \(2\) 到第 \(n+1\) 列），都在主对角线外。由对称性，\((t,1)\) 处也必有一个 1。删去第 \(1,t\) 两行与第 \(1,t\) 两列，剩下 \((n-1)\times(n-1)\) 的对称置换矩阵，共 \(P_{n-1}(1)\) 种。
4. 两种情况互斥，由加法原理与乘法原理： \[P_{n+1}(1)=P_n(1)+n\,P_{n-1}(1).\,\square\]

习题 8

译文. 设 \(P(x)=\sum_{n\ge0}\dfrac{P_n(1)}{n!}x^n\)。把上一题的递推关系两边乘以 \(\dfrac{x^n}{n}\)（按求导整理后）对所有 \(n\ge0\) 求和，导出函数方程 \[P'(x)=(1+x)P(x),\] 从而 \[\frac{P'(x)}{P(x)}=1+x,\qquad \ln P(x)=x+\frac{x^2}{2}.\] 因此 \(P(x)=e^{x+\frac{x^2}{2}}\)。注意这恰好等于长度为 \(n\) 的全体对合的指数型生成函数（exponential generating function, EGF）。这并不意外：一个置换矩阵关于主对角线对称，当且仅当它是某个对合的置换矩阵。

1. 关键求导事实：若 \(P(x)=\sum_{n\ge0}\dfrac{P_n(1)}{n!}x^n\)，则 \(P'(x)=\sum_{n\ge1}\dfrac{P_n(1)}{(n-1)!}x^{n-1}=\sum_{n\ge0}\dfrac{P_{n+1}(1)}{n!}x^n\)。即“求导”把下标 \(n\) 移到 \(n+1\)。
2. 把递推 \(P_{n+1}(1)=P_n(1)+n\,P_{n-1}(1)\) 代入上式分子： \[P'(x)=\sum_{n\ge0}\frac{P_n(1)}{n!}x^n+\sum_{n\ge0}\frac{n\,P_{n-1}(1)}{n!}x^n.\]
3. 第一项就是 \(P(x)\)。第二项把 \(\dfrac{n}{n!}=\dfrac{1}{(n-1)!}\)，并提出一个 \(x\)： \[\sum_{n\ge1}\frac{P_{n-1}(1)}{(n-1)!}x^{n}=x\sum_{m\ge0}\frac{P_m(1)}{m!}x^m=xP(x).\] 故 \(P'(x)=P(x)+xP(x)=(1+x)P(x)\)。
4. 解微分方程：分离变量 \(\dfrac{P'}{P}=1+x\)，即 \((\ln P)'=1+x\)。两边积分得 \(\ln P(x)=x+\dfrac{x^2}{2}+C\)。由 \(P(0)=P_0(1)/0!=1\) 得 \(C=0\)。故 \[P(x)=e^{\,x+\frac{x^2}{2}}.\,\square\]
5. 含义：这正是对合的 EGF，印证了“对称置换矩阵 ↔ 对合”。

习题 9

译文. 不是。\(n=3\) 的一个反例见图 10.16： \[\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}.\] 事实上，这个幻方不能分解为两个对称置换矩阵之和。由于所有对角元都是 0，参与分解的对称置换矩阵 \(Q\) 必须含偶数个 1。这是不可能的，因为 \(Q\) 须含 2 个或 4 个 1，而要使其线和为 1 需要恰好 3 个 1。

1. 给定矩阵 \(M\)（上方那个）的所有对角元都是 0。假设它能写成 \(M=Q+Q'\)，其中 \(Q,Q'\) 都是对称置换矩阵。
2. 因为 \(M\) 对角元全 0 且元素非负，\(Q,Q'\) 的对角元也必须全 0。
3. 对称置换矩阵若对角元全 0，则它的 1 必成对出现：非对角的 1 在 \((i,j)\) 出现时，对称性要求 \((j,i)\) 也是 1，二者配成一对。故 \(Q\) 中 1 的总数是偶数。
4. 但线和为 1 的 \(3\times3\) 置换矩阵恰含 3 个 1（每行一个，共 3 行），3 是奇数。偶数 \(\neq\) 3，矛盾。
5. 故 \(M\) 无法分解为两个对称置换矩阵之和，反例成立。♦

习题 10

译文. 我们已经看到 \(n=3\) 时不存在这样的例子。\(n=4\) 的一个例子见图 10.17。

1. \(n=3\)：由习题 9 的奇偶性论证，反例不可分解，故“总能分解”不成立。
2. \(n=4\)：奇偶性障碍消失——\(4\times4\) 置换矩阵含 4 个 1（偶数），与“对角元全 0 时 1 必成对”不再冲突。图 10.17 给出的 \(4\times4\) 例子可以分解为对称置换矩阵之和（三组都求和为全 1 阵 \(J_4\)）。
3. 因此结论依 \(n\) 而异：\(n=3\) 不行，\(n=4\) 可以。♦

习题 11

译文. 记 \(b_n\) 为准幻方（almost magic square）的个数。我们称一个元素为 0 或 1 的 \(n\times n\) 矩阵为准幻方，如果除第一行与第一列外，每行每列都恰含两个 1，而第一行恰含一个 1，第一列也恰含一个 1。我们断言 \[T_n(2)=\binom{n}{2}(n-1)\,b_{n-1}. \tag{10.23}\] 事实上，取一个被 \(T_n(2)\) 计数的矩阵。其第一列可放两个 1 的位置对共有 \(\binom{n}{2}\) 个。在这两个 1 中第一个所在的行 \(R\) 里，第二个 1 有 \((n-1)\) 个可能位置。最后，删去第一列与行 \(R\)，得到一个 \((n-1)\times(n-1)\) 矩阵，它（在行列置换意义下）是一个准幻方。

另一方面，我们断言 \(b_n\) 也能由 \(T_n(2)\) 得到。事实上， \[b_n=T_{n-1}(2)+(n-1)^2\,b_{n-1}. \tag{10.24}\] 确实，准幻方第一行与第一列的那两个 1 要么重合，此时余下的 \((n-1)\times(n-1)\) 矩阵是一个幻方；要么不重合，此时它们可在 \((n-1)^2\) 个不同位置，删去含这两个 1 的行与列（它们既非第一行也非第一列），得到一个 \((n-1)\times(n-1)\) 的准幻方。

把 \(T_{n+1}(2)\) 用 (10.23) 表出，再在所得表达式中用 (10.24) 表出 \(b_n\)，得到 \[T_{n+1}(2)=\binom{n+1}{2}\,n\cdot b_n=\frac12(n+1)n^2\,T_{n-1}(2)+\frac12(n+1)n^2(n-1)^2\,b_{n-1}.\] 最后注意，若把 \(\tfrac12 n(n-1)^2 b_{n-1}\) 替换为 \(T_n(2)\)（这由 (10.23) 允许），最后一项会更简单。于是得到 \[T_{n+1}(2)=\binom{n+1}{2}\,n\cdot T_{n-1}(2)+T_n(2)\,n(n+1),\] 此即所求。

1. 推 (10.23)（用 \(b_{n-1}\) 表 \(T_n(2)\)）：看被 \(T_n(2)\) 计数的矩阵的第一列。第一列恰有两个 1，其位置对有 \(\binom{n}{2}\) 种。设上面那个 1 在行 \(R\)；行 \(R\) 也须恰有两个 1，第二个 1 在 \((n-1)\) 个剩余列中任选。删去第一列与行 \(R\) 后，剩下 \((n-1)\times(n-1)\) 的准幻方（共 \(b_{n-1}\) 个）。相乘得 \(T_n(2)=\binom{n}{2}(n-1)b_{n-1}\)。
2. 推 (10.24)（用 \(T_{n-1},b_{n-1}\) 表 \(b_n\)）：看准幻方第一行的那个 1 与第一列的那个 1。
   • 若两者重合（都在 \((1,1)\)）：删去第一行第一列，剩下 \((n-1)\times(n-1)\) 的真幻方，共 \(T_{n-1}(2)\) 个。
   • 若不重合：第一行的 1 在某列、第一列的 1 在某行，共 \((n-1)^2\) 种摆法；删去这两个 1 所在的行与列，剩下 \((n-1)\times(n-1)\) 的准幻方，共 \(b_{n-1}\) 个。
   相加得 \(b_n=T_{n-1}(2)+(n-1)^2 b_{n-1}\)。
3. 代入消元：把 (10.23) 用于 \(n+1\)：\(T_{n+1}(2)=\binom{n+1}{2}\,n\,b_n\)。再把 \(b_n\) 用 (10.24) 展开： \[T_{n+1}(2)=\binom{n+1}{2}n\big[T_{n-1}(2)+(n-1)^2 b_{n-1}\big]=\tfrac12(n+1)n^2 T_{n-1}(2)+\tfrac12(n+1)n^2(n-1)^2 b_{n-1}.\]
4. 回代化简：由 (10.23) 知 \(T_n(2)=\binom{n}{2}(n-1)b_{n-1}=\tfrac12 n(n-1)^2 b_{n-1}\)，故 \(\tfrac12 n(n-1)^2 b_{n-1}=T_n(2)\)。把第二项写成 \((n+1)n\cdot\big[\tfrac12 n(n-1)^2 b_{n-1}\big]=(n+1)n\,T_n(2)\)。于是 \[T_{n+1}(2)=\binom{n+1}{2}\,n\,T_{n-1}(2)+n(n+1)\,T_n(2).\,\square\]

习题 12

译文. 把递推关系两边乘以 \(\dfrac{x^n}{(n!)^2(n+1)}\)，再对所有非负整数 \(n\) 求和，得到 \[\sum_{n\ge0}\frac{T_{n+1}(2)}{(n!)^2(n+1)}x^n=\sum_{n\ge0}\frac{\tfrac12\cdot 1\cdot n^2\cdot T_{n-1}(2)}{(n!)^2}x^n+\sum_{n\ge0}\frac{T_n(2)\,n}{(n!)^2}x^n.\] 现在注意，上式可写成更短的形式 \[T'(x)=xT(x)/2+xT'(x).\] 由此得到 \[\frac{T'(x)}{T(x)}=\frac{x}{2(1-x)}.\] 两边积分。左边现在是 \((\ln T(x))'\)，故积分得 \(\ln T(x)\)。右边的积分很容易，只要注意到 \(\dfrac{x}{2(1-x)}=\dfrac12\sum_{n\ge1}x^n\)。这给出 \[\ln T(x)=\frac12\sum_{n\ge1}\frac{x^{n+1}}{n+1}=-\frac{x}{2}-\frac12\ln(1-x),\] 取指数即得 \[T(x)=\frac{e^{-x/2}}{\sqrt{1-x}}.\]

1. 把递推整理成微分方程：逐项比对后，三个求和分别对应 \(T'(x)\)、\(\tfrac{x}{2}T(x)\)、\(xT'(x)\)，得 \(T'(x)=\tfrac{x}{2}T(x)+xT'(x)\)。
2. 分离 \(T'\)：移项 \(T'(x)-xT'(x)=\tfrac{x}{2}T(x)\)，即 \((1-x)T'(x)=\tfrac{x}{2}T(x)\)，故 \(\dfrac{T'(x)}{T(x)}=\dfrac{x}{2(1-x)}\)。
3. 右边的级数展开：由 \(\dfrac{1}{1-x}=\sum_{n\ge0}x^n\)，得 \(\dfrac{x}{1-x}=\sum_{n\ge1}x^n\)，故 \(\dfrac{x}{2(1-x)}=\tfrac12\sum_{n\ge1}x^n\)。
4. 积分：左边积分得 \(\ln T(x)\)。右边逐项积分 \(\tfrac12\sum_{n\ge1}\dfrac{x^{n+1}}{n+1}\)。把它合成闭式： \[\tfrac12\sum_{n\ge1}\frac{x^{n+1}}{n+1}=\tfrac12\Big(\sum_{m\ge2}\frac{x^{m}}{m}\Big)=\tfrac12\big(-\ln(1-x)-x\big)=-\frac{x}{2}-\frac12\ln(1-x),\] 这里用了 \(-\ln(1-x)=\sum_{m\ge1}\dfrac{x^m}{m}\)，再扣掉 \(m=1\) 的项 \(x\)。
5. 取指数：由 \(\ln T(0)=0\)（积分常数为 0，因 \(T(0)=1\)）得 \[T(x)=\exp\!\Big(-\frac{x}{2}-\frac12\ln(1-x)\Big)=e^{-x/2}\,(1-x)^{-1/2}=\frac{e^{-x/2}}{\sqrt{1-x}}.\,\square\]

习题 13

译文. 取生成函数之积 \(H(x)=\sum_{n\ge0}H_n(2)\dfrac{x^n}{(n!)^2}\) 与 \(T(x)=\sum_{n\ge0}T_n(2)\dfrac{x^n}{(n!)^2}\)，并记起推论 10.17 与引理 10.18，得 \[H(x)T(x)=\frac{e^{x/2}}{\sqrt{1-x}}\cdot\frac{e^{-x/2}}{\sqrt{1-x}}=\frac{1}{1-x}. \tag{10.25}\] 另一方面，展开乘积 \(T(x)H(x)\)，得 \[H(x)T(x)=\sum_{n\ge0}x^n\sum_{k=0}^{n}\frac{H_k(2)}{k!^2}\cdot\frac{T_{n-k}(2)}{(n-k)!^2}. \tag{10.26}\] 由于最后两式左边相同，右边也必相同，特别地，两个右边中 \(\dfrac{x^n}{(n!)^2}\) 的系数也必相同。在 (10.25) 的右边，该系数是 \(n!^2\)（因为 \(\dfrac{1}{1-x}=\sum_{n\ge0}x^n\)）。在 (10.26) 的右边，该系数是 \[\sum_{k=0}^{n}\frac{n!^2\,H_k(2)\,T_{n-k}(2)}{k!^2(n-k)!^2}=\sum_{k=0}^{n}\binom{n}{k}^2 H_k(2)\,T_{n-k}(2),\] 这就证明了我们的断言。

1. 左路（合并闭式）：由习题 12 与对应结论，\(H(x)=\dfrac{e^{x/2}}{\sqrt{1-x}}\)，\(T(x)=\dfrac{e^{-x/2}}{\sqrt{1-x}}\)。相乘指数项抵消、根号相乘成一次：\(H(x)T(x)=\dfrac{1}{1-x}=\sum_{n\ge0}x^n\)。所以 \(x^n\) 的系数恒为 1，写成 \(\dfrac{x^n}{(n!)^2}\) 的系数就是 \(n!^2\)。
2. 右路（柯西乘积）：两个形如 \(\sum c_n \dfrac{x^n}{(n!)^2}\) 的级数相乘，\(x^n\) 项来自所有 \(k+(n-k)=n\) 的搭配： \[[x^n]\,H(x)T(x)=\sum_{k=0}^n \frac{H_k(2)}{k!^2}\cdot\frac{T_{n-k}(2)}{(n-k)!^2}.\]
3. 令两路系数相等：把右路系数乘 \(n!^2\)（即看 \(\dfrac{x^n}{(n!)^2}\) 的系数）： \[\sum_{k=0}^n \frac{n!^2}{k!^2(n-k)!^2}H_k(2)T_{n-k}(2)=\sum_{k=0}^n\binom{n}{k}^2 H_k(2)T_{n-k}(2),\] 用了 \(\dfrac{n!}{k!(n-k)!}=\binom{n}{k}\)，平方后即 \(\binom{n}{k}^2\)。左路系数是 \(n!^2\)。两者相等即得恒等式。♦

习题 14

译文. 注意，定义 \(a_{-1}=0\) 后，所要证的递推公式对 \(n=1\) 也成立。因为该公式对所有 \(n\ge1\) 成立，我们可以取所有这样的 \(n\)，把公式乘以 \(\dfrac{n\,x^{n-1}}{n!^2}\)，再把所得诸方程相加，得到 \[\sum_{n\ge1}n\cdot\frac{H_n(2)}{n!^2}x^{n-1}=\sum_{n\ge1}n\cdot\frac{H_{n-1}(2)}{(n-1)!^2}x^{n-1}-\frac12\sum_{n\ge1}\frac{H_{n-2}(2)}{(n-2)!^2}x^{n-1}.\] 注意逐项比较表明这等价于 \[H'(x)=xH'(x)+H(x)-\tfrac12 xH(x),\] 由此得到 \[\frac{H'(x)}{H(x)}=\frac12+\frac12\cdot\frac{1}{1-x},\] 而这一最后方程的解确实是 \(H(x)\)。一个不使用 \(H_n(2)\) 显式公式的证明可见参考文献 [4]。

1. 统一起点：设 \(a_{-1}=0\)（即让 \(H_{-1}(2)=0\)），则递推对 \(n=1\) 也成立，求和可从 \(n=1\) 起，无需额外讨论边界。
2. 整理三项：逐项与 \(H(x),H'(x)\) 比对：左边 \(\to H'(x)\)；右边第一项 \(\to xH'(x)+H(x)\)；第二项 \(\to -\tfrac12 xH(x)\)。得微分方程 \(H'(x)=xH'(x)+H(x)-\tfrac12 xH(x)\)。
3. 解出对数导数：移项整理为 \((1-x)H'(x)=\big(1-\tfrac{x}{2}\big)H(x)\)，故 \(\dfrac{H'(x)}{H(x)}=\dfrac{1-\frac{x}{2}}{1-x}=\dfrac{2-x}{2(1-x)}=\dfrac12+\dfrac{1}{2(1-x)}\)。验证 \(H=\dfrac{e^{x/2}}{\sqrt{1-x}}\)：直接算 \[\frac{H'(x)}{H(x)}=\frac{d}{dx}\Big(\frac{x}{2}-\frac12\ln(1-x)\Big)=\frac12-\frac12\cdot\frac{-1}{1-x}=\frac12+\frac{1}{2(1-x)}.\] 两式一致，故 \(H(x)=\dfrac{e^{x/2}}{\sqrt{1-x}}\) 满足方程，且由 \(H(0)=1\) 唯一确定。♦

习题 15

译文. 为底层选取六个 \(3\times3\) 置换矩阵中的任意一个。若选了矩阵 \(\pi\)，则有两个矩阵有资格放到中层和顶层，它们就是把 \(\pi\) 乘以两个长度为 3 的无不动点置换（fixed point–free permutation）之一所得的两个矩阵。我们可把其中任一个放到中层，那么另一个就必须放到顶层。因此 \[C_3(1)=6\cdot2\cdot1=12.\]

1. 底层：\(3\times3\) 置换矩阵共有 \(3!=6\) 个，任选其一记为 \(\pi\)，故 6 种。
2. 中层：为保证每条竖直线恰一个 1，中层置换 \(\sigma\) 必须与 \(\pi\) 在每一列都不同，即 \(\sigma\pi^{-1}\)（或写成 \(\pi\) 乘上某置换）必须无不动点。长度 3 的无不动点置换（错位排列）恰有 \(D_3=2\) 个，故中层 2 种。
3. 顶层：顶层置换须同时不同于底层与中层。一旦底、中两层定下，顶层被唯一确定（剩下的那个错位选择），故 1 种。
4. 由乘法原理 \(C_3(1)=6\cdot2\cdot1=12\)。♦

习题 16

译文. 不用字母填拉丁方（Latin square），改用数字 \(1\) 到 \(n\) 填。设 \(L\) 是这样一个拉丁方。现在把 \(L\) 的所有元素都变成 0，唯独把等于 \(i\) 的那 \(n\) 个元素变成 1，这给出置换矩阵 \(L_i\)。令 \(f(L)\) 为以 \(L_i\) 作为第 \(i\) 层的幻立方。容易验证这是一个双射。

1. 正向 \(f\)：给定用 \(1,\dots,n\) 填好的拉丁方 \(L\)。对每个 \(i\)，把 \(L\) 中值为 \(i\) 的格子标 1、其余标 0，得 0–1 矩阵 \(L_i\)。因为 \(L\) 每行每列各出现一次 \(i\)，所以 \(L_i\) 每行每列恰一个 1，是置换矩阵。把 \(L_1,\dots,L_n\) 依次叠成第 \(1\) 到第 \(n\) 层，得立方 \(f(L)\)。
2. 每条竖直线恰一个 1：位置 \((r,c)\) 在 \(L\) 中只有唯一一个值 \(i_0\)，故只有第 \(i_0\) 层在 \((r,c)\) 处为 1，竖直方向恰一个 1。于是 \(f(L)\) 是线和 1 的幻立方。
3. 逆向：给定这样一个幻立方，位置 \((r,c)\) 上唯一为 1 的那一层编号 \(i\) 就还原出 \(L(r,c)=i\)，得到拉丁方。正逆互为反演，故 \(f\) 是双射。♦

习题 17

译文. 这可以用一个聪明的分情况证明来完成。如果某个立方中存在一层（或其某个旋转副本）含有三个等于 2 的元素，那么该立方不是不可约的（irreducible）。不可能存在恰含两个等于 2 的元素的层。我们还需考虑：某层（或其旋转副本）上等于 2 的元素的最大个数 \(m\) 为 0 或 1 的情形。若 \(m=0\)，则该立方是“全 1 立方”与某个线和为 1 的立方 \(C\) 之差，因而是可约的（事实上，它是 \(C\) 的两个循环平移之和）。最后，若 \(m=1\)，则我们就得到图 10.9 所示的例子。

1. \(m\ge3\)（某层有三个 2）：这一层每行每列和为 2、共三格全是 2，则该层为 \(2\) 倍置换矩阵；可拆出一个线和 1 的部分，立方可约。排除。
2. \(m=2\) 不可能：线和恒为 2 的层若恰有两个 2，会与“每行每列和为 2”冲突（第三格须同时配平多行多列而矛盾），故不存在这种层。
3. \(m=0\)（任何层都没有 2，全是 0/1）：整个立方各元素为 0 或 1，每线和 2，可写成“全 1 立方”减去一个线和 1 的立方 \(C\)；而全 1 立方本身是 \(C\) 的若干循环平移之和，于是该立方等于 \(C\) 的两个循环平移之和——可约。排除。
4. \(m=1\)（恰好某层最多一个 2）：逐情形构造，唯一得到的就是图 10.9 的那个立方，它不可约。
5. 综合：唯一的不可约者是图 10.9（及其各线置换所得副本）。♦

习题 18

译文. 习题 15 告诉我们，边长 3、线和 1 的幻立方有 12 个。把其中任意两个相加，就得到一个被 \(C_3(2)\) 计数的幻立方。而且，所有这种两元素之和都互不相同（为什么？）。这给出 \[\binom{12+2-1}{2}=\binom{13}{2}=78\] 个可约的幻立方。为数出不可约的，考虑图 10.9。那里所示的不可约幻立方可变换成 54 个不可约立方。事实上，那唯一的元素 2 可放在 27 个不同位置，然后不含该元素的两层可用两种方式置换。上一题随即表明再无其他不可约立方。因此 \[C_3(2)=78+54=132.\]

1. 可约部分：线和 2 的可约立方 = 从 12 个线和 1 的立方里可重复地取两个相加。由于不同的无序取法给出不同的和（题中“为什么？”：和的分解唯一，故不会重合），这是“12 取 2 的可重组合”： \[\binom{12+2-1}{2}=\binom{13}{2}=\frac{13\cdot12}{2}=78.\]
2. 不可约部分：由习题 17，不可约者本质上只有图 10.9 一个，再数它在对称变换下的不同副本。那个唯一的 2 可放在 \(3\times3\times3=27\) 个位置；放定后，不含该 2 的另两层可互换，有 2 种。故 \(27\cdot2=54\) 个不可约立方。
3. 相加：\(C_3(2)=78+54=132\)。♦

习题 19

译文. 第一种解法。置换幻立方的 \(n\) 个层。这 \(n!\) 个置换各自给出一个不同的幻立方，因为所有 \(n\) 层都互不相同。于是被 \(C_n(1)\) 计数的幻立方可被分成若干子集，每个子集恰含 \(n!\) 个立方。

第二种解法。一个线和为 1 的幻立方就是叠在一起的 \(n\) 个置换矩阵。记这些矩阵对应的置换为 \(p_1,p_2,\dots,p_n\)。这些置换的关键性质是：不存在 \(i\in[n]\) 使得对某 \(j\neq k\) 有 \(p_j(i)=p_k(i)\)。我们断言：若把所有 \(p_j\) 同乘以同一个置换 \(q\)，此性质仍保持。事实上，假设 \(q(p_j(i))=q(p_k(i))\) 对某 \(j\neq k\) 成立，这是不可能的，因为双射 \(q\) 不能把不同的元素 \(p_j(i)\) 与 \(p_k(i)\) 映到同一个元素。因此，对任意 \(n\)-置换 \(q\)，置换 \(qp_1,qp_2,\dots,qp_n\) 的矩阵也构成一个幻方（幻立方）。我们于是再次把幻立方分成了每个大小为 \(n!\) 的子集。

1. 第一种（置换层）：给定一个幻立方，它的 \(n\) 层两两不同（线和 1 时不可能有两层相同）。把这 \(n\) 层重新排列，有 \(n!\) 种排法，得到 \(n!\) 个互不相同的合法幻立方。这把全体幻立方划分成大小均为 \(n!\) 的“轨道”，故 \(n!\mid C_n(1)\)。
2. 第二种（左乘置换 \(q\)）：把幻立方看成置换组 \((p_1,\dots,p_n)\)，其“竖线恰一个 1”条件等价于：对每个位置 \(i\)，\(p_1(i),\dots,p_n(i)\) 两两不同。
3. 用任一置换 \(q\) 同时左乘得 \((qp_1,\dots,qp_n)\)。因为 \(q\) 是双射，\(p_j(i)\neq p_k(i)\Rightarrow q(p_j(i))\neq q(p_k(i))\)，所以“两两不同”的条件被保持，仍是合法幻立方。
4. 不同的 \(q\)（共 \(n!\) 个）给出不同的立方，于是又得到大小 \(n!\) 的分组，再次推出 \(n!\mid C_n(1)\)。♦

习题 20

译文. 下面是一个计算 \(C_3(8)\) 的 Maple 程序。改变第一行中 \(r\) 的值即可得到 \(C_3(r)\) 的其他取值。

r:=8;
i:=0;
for a from 0 to r do
 for b from 0 to r do
  for c from 0 to r do
   for d from 0 to r do
    for e from 0 to r do
     for f from 0 to r do
      for g from 0 to r do
       for h from 0 to r do
        if a+b < r+1 and c+d < r+1 and a+c < r+1 and b+d < r+1
         and a+b+c+d > r-1 and e+f < r+1 and g+h < r+1 and
         e+g < r+1 and f+h < r+1 and e+f+g+h > r-1 and
         a+e < r+1 and b+f < r+1 and c+g < r+1 and d+h < r+1
         and a+b+e+f > r-1 and c+d+g+h > r-1 and a+c+e+g > r-1
         and b+d+f+h > r-1 and a+b+c+d+e+f+g+h < r+r+r+1 then
          i := i+1;
        fi;
       od; od; od; od; od; od; od; od;
i;
r;

1. 变量与约束：8 个自由元 \(a,b,c,d\)（某一层四角）与 \(e,f,g,h\)（另一层），其余格子写成 \(r\) 减去某些已知元。条件 \(\text{某两元之和}\le r\)（即 < r+1）保证被推出的格子非负；条件 \(\text{某四元之和}\ge r\)（即 > r-1）保证推出的格子不超过 \(r\)（其实是 \(\le r\) 经移项的形式）。所有线和都被强制为 \(r\)。
2. 八重循环：对 \((a,\dots,h)\in\{0,\dots,r\}^8\) 全部组合逐一检查，合法则 \(i\) 加一。
3. 输出：循环结束后 \(i\) 即 \(C_3(r)\)。把首行 \(r:=8\) 改为别的值就算别的 \(C_3(r)\)。♦

习题 21

译文. 我们对 \(m\) 用归纳法证明该命题。当 \(m=1\) 时命题为真，因为在两个自然数之间总有一个不小于另一个。现在假设对 \(m-1\) 已知命题成立，并对 \(m\) 来证明。

假设 \(A=\{d_1,d_2,\dots\}\) 是 \(\mathbb N^m\) 中的一个无限反链（antichain）。对 \(a=(a_1,a_2,\dots,a_m)\in A\)，定义 \(f(a)=(a_1,a_2,\dots,a_{m-1})\)。令 \(f(A)=\{f(a)\mid a\in A\}\)。则 \(f(A)\subset\mathbb N^{m-1}\)，故 \(f(A)\) 不含无限反链。\(f(A)\) 的元素两两不可比……换言之，\(f\) 是单射（为什么？）。

因为 \(f(A)\) 是一个不含无限反链的无限集，\(f(A)\) 必含一个无限的元素序列 \(x_1,x_2,\dots\)，使得 \(x_1\le x_2\le\cdots\)（这并不显然；请读者解释为什么）。现在看序列 \(S=f^{-1}(x_1),f^{-1}(x_2),\dots\)，其元素都来自 \(A\)。\(S\) 要不违反反链条件，唯一的可能是：\(S\) 各元素的最后一个坐标构成严格递减序列。然而这显然不可能，因为这些坐标都是非负整数。

1. 基础 \(m=1\)：\(\mathbb N^1=\mathbb N\) 全序，任意两数总能比较大小，故反链至多含一个元素——有限。
2. 归纳假设：设 \(\mathbb N^{m-1}\) 中所有反链都有限。反证：设 \(\mathbb N^m\) 中有无限反链 \(A=\{d_1,d_2,\dots\}\)。
3. 投影 \(f\)：令 \(f\) 去掉最后一个坐标。为什么 \(f\) 在 \(A\) 上是单射？若 \(f(a)=f(a')\)（前 \(m-1\) 坐标相同），则第 \(m\) 坐标可比，整体上 \(a\le a'\) 或 \(a'\le a\)，与 \(A\) 是反链矛盾；故 \(a=a'\)，\(f\) 单射。于是 \(f(A)\) 也无限。
4. 找单调链：\(f(A)\subset\mathbb N^{m-1}\) 是无限集且（由归纳假设）不含无限反链。为什么必有无限递增链？一个无限偏序集若没有无限反链，则必有无限链（这是 Dilworth/König 型结论）：可抽出 \(x_1\le x_2\le\cdots\)（在 \(\mathbb N^{m-1}\) 的逐坐标序下）。
5. 回拉到 \(A\)：取原像 \(S=f^{-1}(x_1),f^{-1}(x_2),\dots\subset A\)。它们前 \(m-1\) 坐标已满足 \(x_1\le x_2\le\cdots\)。若某两项的第 \(m\) 坐标也满足 \(\le\)，则这两个完整向量可比，违反反链。故为避免可比，第 \(m\) 坐标必须沿序列严格递减。
6. 导出矛盾：非负整数不可能无限严格递减（最多降到 0 就到底）。矛盾。故 \(\mathbb N^m\) 中不存在无限反链，所有反链有限。♦

返回 全书目录