10.7　习题Exercises

本页为译文 + 高中讲解合一：黑色正文（有序列表中的题目）为忠实翻译；彩色框（目标 / 思路 / 分步推演）与配图为面向高中生的解题方法提示，逐步推演、举例、画图，不用比喻。每题只给思路与方法，完整最终解答见对应“习题解答”一节。

1. 证明定理 10.2 证明的 (a) 部分中所作的论断：满足 (10.8) 的非负整数四元组 \((a,b,c,d)\)，与满足 (10.8) 的四元组 \((a,\,2a+d-c,\,a+b+d-c,\,b+d)\) 之间存在一个双射（bijection）。

   本题目标说明“把 \((a,b,c,d)\) 按给定公式变换”这一映射是一一对应，从而两类四元组个数相等。
   1. 要证双射，标准做法是显式写出逆映射。设映射 \(\varphi(a,b,c,d)=(a',b',c',d')\)，其中 \(a'=a,\ b'=2a+d-c,\ c'=a+b+d-c,\ d'=b+d\)。
   2. 把 \(a,b,c,d\) 反解为 \(a',b',c',d'\) 的式子（这是一组线性方程，逐个代入消元即可解出），得到候选逆映射 \(\psi\)。
   3. 验证 \(\psi\circ\varphi=\mathrm{id}\) 且 \(\varphi\circ\psi=\mathrm{id}\)；再验证 \(\varphi\) 把满足 (10.8) 的解仍映成满足 (10.8) 的解（即保持约束、保持非负整数性）。两边都做到，即得双射。
   小提示逆映射存在且把整数映成整数，是双射的充分条件——这正是“线性变换的矩阵可逆且逆矩阵也是整数矩阵”所保证的。

2. 证明定理 10.2 证明的 (c) 部分中所作的论断：若 \(a>c\) 且 \(b>c\)，则不等式 (10.3)–(10.6) 全部是冗余的（即可由其余条件推出，不增加新限制）。

   本题目标说明在条件 \(a>c,\ b>c\) 下，那四条不等式自动成立，因而不需要单独要求。
   1. 把 (10.3)–(10.6) 逐条写出，它们都是“某个表达式 \(\ge 0\)”的形式。
   2. 逐条把表达式用 \(a-c\ge 1\)、\(b-c\ge 1\)（因为是整数且严格大于）以及其它已知约束代入。
   3. 说明每条表达式都恒 \(\ge 0\)，于是这些不等式不会排除任何解——这就是“冗余”的含义。

3. 已知 \(p\) 是一个 \(m\) 次多项式，又已知它在 \(m+1\) 个点处的取值 \(p(0),p(1),\cdots,p(m)\)。如何求出 \(p\)？（给出一个能证明 \(p\) 可被确定的一般性策略。不要仅仅因为某种方法计算量大就舍弃它。）

   本题目标说明 \(m+1\) 个取值唯一确定一个 \(m\) 次多项式，并给出还原方法。
   1. 核心事实：次数 \(\le m\) 的多项式由 \(m+1\) 个不同点的值唯一决定（否则两式之差是次数 \(\le m\) 却有 \(m+1\) 个根的非零多项式，矛盾）。
   2. 方法一（待定系数）：设 \(p(x)=\sum_{j=0}^m a_j x^j\)，代入 \(m+1\) 个已知值得线性方程组，系数矩阵为范德蒙德（Vandermonde）矩阵，可逆，故 \(a_j\) 唯一可解。
   3. 方法二（拉格朗日插值）：直接写出 \[p(x)=\sum_{i=0}^{m} p(i)\prod_{\substack{0\le j\le m\\ j\ne i}}\frac{x-j}{\,i-j\,}.\] 验证它在每个 \(x=i\) 处取值 \(p(i)\) 即可。
   数字小例设 \(m=2\)，已知 \(p(0)=1,p(1)=4,p(2)=9\)。用拉格朗日插值或观察可得 \(p(x)=(x+1)^2\)。

4. 设 \(A\) 是一个 \(2n\times 2n\) 的非负整数矩阵。对任意 \(i\in[n]\)，称第 \(2i-1\) 行与第 \(2i\) 行构成一个行对，第 \(2i-1\) 列与第 \(2i\) 列构成一个列对。若 \(A\) 满足以下条件，则称它为 \(n\) 阶双幻方（double magic square）：

   1. 每个行对、每个列对的元素之和都为 \(2\)；
   2. 若某行对含有一个 \(2\)，则这个 \(2\) 必须位于该行对的上面一行；
   3. 任意一行或一列中最多只有一个正整数。

   例见图 10.10。证明 \(n\) 阶双幻方的个数 \(DM(n)\) 为 \[DM(n)=\sum_{k=0}^{n}\binom{n}{k}\frac{n!}{(n-k)!}\,2^{k}\,(2n-2k)!.\]

   本题目标用分类计数把双幻方造出来，按“出现多少个 \(2\)”分情形求和。
   1. 条件 (a)(c) 表明：每个行对里的“和 \(2\)”要么由一个 \(2\) 贡献，要么由两个分处不同列对的 \(1\) 贡献。设恰有 \(k\) 个行对采用“一个 \(2\)”的方式。
   2. 选哪 \(k\) 个行对放 \(2\)：\(\binom{n}{k}\) 种；由条件 (b)，每个 \(2\) 固定在行对上行，但它落在哪个列对、以及列对内哪一列，要计入因子 \(2^k\) 与排列。
   3. 把“含 \(2\) 的行对”对应到“被占用的列对”，是一个单射安排，贡献 \(\dfrac{n!}{(n-k)!}\) 这类下降阶乘因子；剩下的 \(2n-2k\) 行/列用 \(1\) 来配对，贡献 \((2n-2k)!\)。
   4. 对 \(k=0,1,\dots,n\) 求和即得公式。逐项核对各因子来源是本题关键。

5. (a) 证明：存在一个从“所有 \(n\) 阶双幻方之集合 \(S\)”到“所有行列和均为 \(2\) 的 \(n\times n\) 幻方之集合 \(T\)”的 \(2^{2n}\) 对一映射 \(f\)。

   (b) 由此推出定理 10.19。

   本题目标建立 \(S\to T\) 的“多对一”对应，并用 \(|S|=2^{2n}\,|T|\) 反推 \(T\) 的计数公式。
   1. (a) 构造 \(f\)：把双幻方的“行对/列对”各压缩成一行/一列（例如把每个行对两行相加、列对两列相加），得到一个行列和为 \(2\) 的 \(n\times n\) 矩阵。验证它确实是 \(T\) 的元素。
   2. 数“每个像 \(B\in T\) 有多少原像”：把 \(B\) 的一个表项还原成行对、列对中的位置时有自由选择。条件 (b) 锁住了 \(2\) 的上下位置，而其余自由度恰好贡献 \(2^{2n}\) 个原像——逐处计数即得 \(2^{2n}\) 对一。
   3. (b) 于是 \(|S|=2^{2n}\,|T|\)，即 \(DM(n)=2^{2n}H_n(2)\)（或定理 10.19 中相应式子），代入第 4 题的 \(DM(n)\) 公式即得 \(H_n(2)\) 的封闭式。

6. 设 \(P_3(r)\) 为关于主对角线对称、且幻和为 \(r\) 的 \(3\times 3\) 幻方的个数。\(P_3(r)\) 是关于 \(r\) 的多项式吗？

   本题目标判断这个受限计数是否仍是 \(r\) 的多项式，并说明理由。
   1. “关于主对角线对称”意味着 \(a_{ij}=a_{ji}\)，独立变量减少。把 \(3\times 3\) 对称非负整数矩阵的所有约束（行列和、对角线和均为 \(r\)）写成线性方程组。
   2. 本质是数“某线性方程组在非负整数中、以 \(r\) 为参数的解个数”。这类问题由艾哈特（Ehrhart）理论/拟多项式理论判定：解数关于 \(r\) 是拟多项式，何时退化为真正的多项式取决于多胞形的顶点是否为整点。
   3. 对 \(n=3\) 的具体情形，把自由参数解出后直接数解，观察结果是否对所有 \(r\) 由单一多项式给出（注意可能出现按 \(r\) 奇偶分情形的拟多项式）。

7. 证明递推关系 \(P_{n+1}(1)=P_n(1)+n\,P_{n-1}(1)\)。

   本题目标用组合分解证明幻和为 \(1\) 的幻方（即对称置换矩阵计数）满足此递推。
   1. 关键观察：幻和为 \(1\) 的 \(n\times n\) 幻方就是对称的置换矩阵，等价于一个 \([n]\) 上的对合（involution，即满足 \(\sigma^2=\mathrm{id}\) 的排列）。所以 \(P_n(1)=\) “\([n]\) 上对合的个数”。
   2. 对元素 \(n+1\) 分两种情况：它是不动点（贡献 \(P_n(1)\)），或它与前 \(n\) 个元素之一配成一对（\(n\) 种选法，余下 \(n-1\) 个元素作对合，贡献 \(n\,P_{n-1}(1)\)）。
   3. 由加法原理两情形相加，即得 \(P_{n+1}(1)=P_n(1)+n\,P_{n-1}(1)\)。
   数字验证\(P_1(1)=1,\ P_2(1)=2,\ P_3(1)=2+2\cdot 1=4,\ P_4(1)=4+3\cdot2=10\)，与对合个数序列 \(1,2,4,10,\dots\) 一致。

8. 求数列 \(P_n(1)\) 的指数型生成函数（exponential generating function）。

   本题目标把第 7 题的递推转成关于 EGF 的微分方程并解出。
   1. 设 \(y(x)=\sum_{n\ge 0}P_n(1)\dfrac{x^n}{n!}\)。把递推 \(P_{n+1}(1)=P_n(1)+nP_{n-1}(1)\) 乘以 \(\dfrac{x^n}{n!}\) 求和。
   2. 利用 EGF 运算法则：左移一位对应求导 \(y'\)；乘以 \(n\) 对应 \(x\dfrac{d}{dx}\) 等。整理得一阶常微分方程 \(y'=(1+x)y\)。
   3. 解之并用初值 \(P_0(1)=1\)，得 \[y(x)=\exp\!\Big(x+\frac{x^2}{2}\Big).\] 这正是对合的经典 EGF。

9. 设 \(P\) 是一个关于主对角线对称的幻方。是否一定有：\(P\) 可表示为若干个对称置换矩阵之和？

   本题目标判断对称版本的“伯克霍夫–冯·诺依曼”分解是否成立（是/否并给理由或反例）。
   1. 回忆非对称情形：行列和相等的非负整数矩阵总能写成置换矩阵之和（伯克霍夫–冯·诺依曼定理的整数版）。本题问的是对称受限版本。
   2. 正面尝试：能否把对称矩阵每次减去一个对称置换矩阵（对应一个对合），使行列和同步下降并保持非负与对称？若总能进行到归零，则结论成立。
   3. 反面尝试：寻找一个对称、行列和相等却无法如此分解的小矩阵作反例。建议从 \(3\times 3\) 或 \(4\times 4\)、幻和为 \(2\) 的对称矩阵入手逐一检验。

10. 给出一个例子：三个互不相交的置换矩阵集合，它们的（各自元素之）和相同。

    本题目标构造三组没有公共置换矩阵、但元素求和后得到同一矩阵的例子。
    1. 目标矩阵应是某个行列和为 \(s\) 的非负整数矩阵 \(M\)，它能以多种不同的“置换矩阵分拆”表示。
    2. 取较小的全 \(s\) 矩阵（如 \(3\times3\) 全 \(1\) 矩阵 \(J\)，行列和为 \(3\)）。\(J\) 等于任意三个两两不同且并起来覆盖全部位置的置换矩阵之和——而 \(3\times 3\) 共有 \(6\) 个置换矩阵，可拆出多组。
    3. 从这 \(6\) 个置换矩阵中挑出三组（每组 \(3\) 个、组间无公共元素）使每组之和都等于同一矩阵，写出它们即可。三组互不相交是要点。

11. 证明（最好用直接论证）递推关系 \[T_{n+1}(2)=\frac{n^2(n+1)}{2}\,T_{n-1}(2)+n(n+1)\,T_n(2).\]

    本题目标对“行列和与主对角线和均为 \(2\) 的矩阵”计数 \(T_n(2)\)，用组合分解直接得到递推。
    1. 把 \(T_n(2)\) 看作某种受限的“2-正则”结构（行列和为 \(2\)、且主对角线和为 \(2\)）。考虑新增第 \(n+1\) 行与第 \(n+1\) 列时，新增的两个单位如何放置。
    2. 按新元素的放置方式（落在对角线上 / 落在非对角位置、与已有元素配对的不同方式）分情形，分别数出每种情形的方案数。
    3. 各情形的方案数分别对应系数 \(\dfrac{n^2(n+1)}{2}\) 与 \(n(n+1)\)；逐项核对它们来自“选行/选列/选配对”的乘法计数，求和即得递推。

12. 利用上题结果，求双重指数型生成函数 \[T(x)=\sum_{n\ge 0}\frac{T_n(2)}{(n!)^2}\,x^n.\]

    本题目标把第 11 题递推转写为关于 \(T(x)\) 的方程并解出闭式。
    1. 用 \(\dfrac{x^n}{(n!)^2}\) 作权重对递推求和。注意权重含 \((n!)^2\)，故 \(n^2\)、\(n(n+1)\) 等因子在移位求和时与阶乘平方相消，化简很关键。
    2. 逐项把 \(\sum T_{n+1}(2)\dfrac{x^{n}}{(n!)^2}\)、\(\sum n^2T_{n-1}(2)\dfrac{x^n}{(n!)^2}\) 等用 \(T(x)\) 及其导数表示。
    3. 得到关于 \(T(x)\) 的（微分）方程后求解，并用初值 \(T_0(2)=1\) 定常数，写出闭式 \(T(x)\)。

13. 证明 \[\sum_{k=0}^{n}\binom{n}{k}^{2}H_k(2)\,T_{n-k}(2)=(n!)^{2}.\]

    本题目标这是一个卷积恒等式，用生成函数相乘或双计数证明。
    1. 识别结构：左边是带权重 \(\binom{n}{k}^2\) 的卷积，正对应“双重指数型生成函数相乘”。设 \(H(x)=\sum H_n(2)\dfrac{x^n}{(n!)^2}\)、\(T(x)\) 同前。
    2. 则左边 \(=\big[H(x)\,T(x)\big]\) 在 \(\dfrac{x^n}{(n!)^2}\) 处的系数；而右边 \((n!)^2\) 对应生成函数 \(\sum \dfrac{(n!)^2 x^n}{(n!)^2}=\sum x^n=\dfrac{1}{1-x}\)。
    3. 于是只需证明 \(H(x)\,T(x)=\dfrac{1}{1-x}\)。结合第 12 题求得的 \(T(x)\) 与 \(H_n(2)\) 的生成函数（见第 14 题），相乘验证即可。
    小例核对\(n=0\)：左边 \(=\binom00^2H_0(2)\,T_0(2)=1\cdot1\cdot1=1\)，右边 \((0!)^2=1\)，两边相等。一般情形不必逐个 \(n\) 验证，而是由生成函数等式 \(H(x)\,T(x)=\dfrac{1}{1-x}\)（其中 \(H_0(2)=T_0(2)=1\)）比较 \(\dfrac{x^n}{(n!)^2}\) 的系数一次性得证。

14. 用任意方法证明：递推关系 \[H_n(2)=n^2H_{n-1}(2)-\binom{n}{2}(n-1)\,H_{n-2}(2)\] 对 \(n\ge 2\) 成立。

    本题目标对“行列和均为 \(2\) 的非负整数矩阵”计数 \(H_n(2)\) 建立二阶递推。
    1. 组合解释：\(H_n(2)\) 数的是把每行两个单位放置、使每列也恰得两个单位的方案。可把它对应到“\(n\) 个点上的 2-正则多重图/对集结构”。
    2. 考虑第 \(n\) 行两个单位所在列：分“两个单位在同一列（成一个 \(2\)）”与“分处两列”两类，分别与去掉一行后的较小计数 \(H_{n-1}(2),H_{n-2}(2)\) 挂钩。
    3. 由容斥/分类得到带正负号的递推，正项 \(n^2H_{n-1}(2)\) 来自一种放法的乘法计数，负项 \(\binom{n}{2}(n-1)H_{n-2}(2)\) 修正重复计数。逐项核对系数即证。
    4. 另一条路：用 \(H_n(2)\) 的已知封闭式（来自第 5 题 \(H_n(2)=2^{-2n}DM(n)\) 或经典公式）直接代入验证递推，也是“任意方法”允许的。

15. 计算 \(C_3(1)\)。

    本题目标求幻和为 \(1\) 的 \(3\times3\times3\) 幻立方（magic cube）的个数。
    1. 幻和为 \(1\) 意味着每条“线”（沿三个坐标方向的行）之和都为 \(1\)，故每条线上恰有一个 \(1\)、其余为 \(0\)。
    2. 于是 \(C_3(1)\) 数的是：把 \(3^3\) 个格子里放若干个 \(1\)，使得沿 \(x,y,z\) 三个方向的每条线都恰含一个 \(1\)。这等价于一个 \(3\times3\) 的拉丁方（见第 16 题）——把第三维坐标看作格子里填的符号。
    3. 因此 \(C_3(1)=\)（\(3\times3\) 拉丁方的个数）\(=12\)。可由“第一行固定为 ABC 后数补全方式”再乘以行列重排来核对。

16. 拉丁方（Latin square）是一个 \(n\times n\) 的方格阵，用 \(n\) 个字母填满，使每个字母在每行、每列中恰好出现一次。图 10.11 给出一个 \(3\times3\) 的拉丁方。

    说明本条是定义性条目，引入“拉丁方”概念，供前面第 15 题以及后续讨论使用。
    1. 识别要点：每行是字母的一个排列，每列也是字母的一个排列，且行约束与列约束同时满足。
    2. 与幻立方的联系：幻和为 \(1\) 的 \(n\times n\times n\) 幻立方与 \(n\times n\) 拉丁方一一对应（把“第三坐标”当作填入的字母），这正是第 15 题用到的桥梁。
    3. 可自行验证图中方阵：每行 \(\{A,B,C\}\)、每列 \(\{A,B,C\}\) 各出现一次，符合定义。

返回 全书目录