Bóna · 枚举与解析组合学导论 · 第 9 章 组合学中的序列

9.7　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为对原书每道解答的忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节的核心主题是对数凹性（log-concavity）：一个正数序列 \(a_0,a_1,a_2,\dots\) 称为对数凹，若对每个内部下标 \(k\) 都有 \(a_k^2\ge a_{k-1}\,a_{k+1}\)。下面所有题目都围绕“如何证明某个序列是对数凹的”展开。

先记住一个等价转化把对数凹条件 \(a_k^2\ge a_{k-1}a_{k+1}\) 两边变形为 \(\dfrac{a_k}{a_{k-1}}\ge\dfrac{a_{k+1}}{a_k}\)。也就是说：相邻两项之比 \(r_k=\dfrac{a_k}{a_{k-1}}\) 随 \(k\) 增大而不增，就等价于序列对数凹。本节多道题（第 1、2 题）正是用“算出比值、说明它递减”这一招完成的。

第 1 题　高斯二项式系数的比值

我们来计算比值 \[\frac{\left[{n\atop k}\right]}{\left[{n\atop k-1}\right]}.\] （这里 \(\left[{n\atop k}\right]\) 表示高斯二项式系数，即 \(q\)-二项式系数。）我们得到分式 \[\frac{q^{\,n-k}-1}{(q^{k}-1)\,q^{\,k-1}},\] 它随着 \(k\) 增大而减小。事实上，分子在减小，而分母在增大。

分步推演
  1. 把对数凹条件 \(\left[{n\atop k}\right]^2\ge\left[{n\atop k-1}\right]\left[{n\atop k+1}\right]\) 改写为比值不增：\(\dfrac{\left[{n\atop k}\right]}{\left[{n\atop k-1}\right]}\ge\dfrac{\left[{n\atop k+1}\right]}{\left[{n\atop k}\right]}\)。于是只要证明比值 \(r_k=\dfrac{\left[{n\atop k}\right]}{\left[{n\atop k-1}\right]}\) 是关于 \(k\) 的递减序列即可。
  2. 把求出的比值写成 \(r_k=\dfrac{q^{\,n-k}-1}{(q^{k}-1)\,q^{\,k-1}}\)，并固定一个 \(q>1\)。
  3. 看分子 \(q^{\,n-k}-1\)：随着 \(k\) 增大，指数 \(n-k\) 减小，所以 \(q^{\,n-k}\) 减小，分子减小。
  4. 看分母 \((q^{k}-1)\,q^{\,k-1}\)：随着 \(k\) 增大，\(q^{k}-1\) 与 \(q^{\,k-1}\) 都增大，所以分母增大。
  5. “分子减小、分母增大”合在一起，整个分式 \(r_k\) 必然减小。比值递减，故序列对数凹。♦
例：取 \(q=2,\ n=4\) 直接用公式算 \(r_k=\dfrac{2^{\,4-k}-1}{(2^{k}-1)\,2^{\,k-1}}\)： 可见 \(7>0.5>0.036\)，比值确实一路递减，与结论吻合。

第 2 题　Narayana 数的对数凹性

(a) 同样地，考察比值 \[\frac{N(n,k)}{N(n,k-1)} =\frac{(k-1)!\,(n-k+1)!}{(k+1)!\,(n-k-1)!} =\frac{(n-k+1)(n-k)}{k(k+1)},\] 它仍然随着 \(k\) 增大而减小。

(b) 我们需要证明 \(N(n+1,k)^2\ge N(n,k)\,N(n+2,k)\)，也就是 \[\frac{\binom{n+1}{k}\binom{n+1}{k+1}\cdot\binom{n+1}{k}\binom{n+1}{k+1}}{(n+1)^2} \ \ge\ \frac{\binom{n}{k}\binom{n}{k+1}\cdot\binom{n+2}{k}\binom{n+2}{k+1}}{n(n+2)}.\] 两边同乘 \(\bigl(k!\,(k+1)!\bigr)^2\)，得到（用下降阶乘 \((m)_k=m(m-1)\cdots(m-k+1)\)） \[\bigl((n)_k\,(n+1)_k\bigr)^2\ \ge\ (n-1)_k\,(n)_k\,(n+1)_k\,(n+2)_k,\] 化简后归结为 \[n(n+2-k)\ \ge\ (n+2)(n-k).\] 最后这个不等式成立：要么通过例行化简得到等价的 \(0\ge -2k\)，要么注意到序列 \(1,2,3,\dots\) 本身是对数凹的。

名词：Narayana 数 Narayana 数（Narayana number）\(N(n,k)=\dfrac1n\dbinom{n}{k}\dbinom{n}{k+1}\)，它统计从 \((0,0)\) 到 \((n,n)\)、不越过主对角线、且恰有 \(k\) 个“拐角”的格点路径条数。把所有 \(N(n,k)\) 对 \(k\) 求和就得到第 \(n\) 个 Catalan 数。
把 (b) 末尾那步算清楚
  1. 把 \(n(n+2-k)\ge(n+2)(n-k)\) 两边展开：左边 \(=n^2+2n-nk\)；右边 \(=n^2+2n-nk-2k\)。
  2. 左边减右边 \(=\bigl(n^2+2n-nk\bigr)-\bigl(n^2+2n-nk-2k\bigr)=2k\)。
  3. 因为 \(k\ge0\)，所以 \(2k\ge0\)，即左边 \(\ge\) 右边，等价于 \(0\ge -2k\)。不等式成立，故 Narayana 数对数凹。♦
例：验证一行 Narayana 数 按本页约定 \(N(n,k)=\tfrac1n\binom{n}{k}\binom{n}{k+1}\)，\(n=4\) 时 \(N(4,0),N(4,1),N(4,2),N(4,3)=1,6,6,1\)（注意 \(1+6+6+1=14=c_4\) 是 Catalan 数）。检查对数凹：取内部一项 \(N(4,1)^2=36\ge N(4,0)\,N(4,2)=1\cdot6=6\)，成立。再看 (a) 的比值 \(\dfrac{N(4,1)}{N(4,0)}=6\)，\(\dfrac{N(4,2)}{N(4,1)}=1\)，确实 \(6>1\) 递减。

第 3 题　Catalan 数的组合（双射）证明

设 \(C_n\) 为从 \((0,0)\) 到 \((n,n)\)、不越过主对角线的向东北格点路径（northeastern lattice path）之集合。则 \(|C_n|=c_n\) 是第 \(n\) 个 Catalan 数。可如下定义一个单射（injection） \[f_k:\ C_n\times C_n\ \longrightarrow\ C_{n-1}\times C_{n+1}.\] 若 \((p,q)\in C_n\times C_n\)，先把 \(q\) 平移 \((-1,-1)\)，使它变成一条从 \((-1,-1)\) 到 \((n-1,n-1)\) 的路径 \(q'\)。从这里开始，证明就与正文中用格点路径证明二项式系数对数凹的做法相同：设 \(X\) 为 \(p\) 与 \(q'\) 的第一个交点，把 \(X\) 之后的 \(p\) 与 \(q'\) 两段互换。示例见图 9.10。这样就得到一条从 \((0,0)\) 到 \((n-1,n-1)\) 的路径和一条从 \((-1,-1)\) 到 \((n,n)\) 的路径。由于这个映射是单射，结论得证。

交换前：p（蓝）与 q'（红） 第一个交点 X 交换 X 之后的尾段
图 9.10　单射 \(f_k:\ C_n\times C_n\to C_{n-1}\times C_{n+1}\)。两条路径在第一个交点 \(X\) 处把尾段对调，长度从 \((n,n)\) 与 \((n,n)\) 变成 \((n-1,n-1)\) 与 \((n,n)\)（后者由 \(q'\) 的起点 \((-1,-1)\) 决定）。
这个单射给出 Catalan 数的什么性质 本题构造的单射方向是 \(C_n\times C_n\to C_{n-1}\times C_{n+1}\)。左边 \(c_n^2=|C_n\times C_n|\) 数的是“一对都到 \((n,n)\) 的路径”；右边 \(c_{n-1}c_{n+1}=|C_{n-1}\times C_{n+1}|\)。既然存在从左边集合到右边集合的单射，左边的元素个数就 \(\le\) 右边，于是 \(c_n^2\le c_{n-1}c_{n+1}\)，即 Catalan 数是对数凸（log-convex）的（相邻比 \(c_{n+1}/c_n\) 递增）。这里的关键直觉是：把 \(q\) 平移 \((-1,-1)\) 后，两条端点“错开”的路径一定相交，于是在第一个交点交换尾段，就得到一条短一格、一条长一格的路径对；这个操作可逆（再交换一次就回到原状），所以是单射。单射的存在 \(\Rightarrow\) 个数的不等式 \(\Rightarrow\) 对数凸。（注意这与“对数凹”方向相反——下面的例子会用数字印证。）
例：验证 \(c_n^2\le c_{n-1}c_{n+1}\)（对数凸） Catalan 数 \(c_1,c_2,c_3,c_4=1,2,5,14\)。取 \(n=3\)：\(c_3^2=25\)，\(c_2\,c_4=2\cdot14=28\)。\(25<28\)，可见 Catalan 数不是对数凹的——恰恰相反，它满足 \(c_n^2\le c_{n-1}c_{n+1}\)，是对数凸的，这正是本题单射方向 \(C_n\times C_n\to C_{n-1}\times C_{n+1}\) 所给出的不等号朝向。用数字核对：\(25\le28\)，成立。这个例子提醒我们：构造单射时一定要看清映射是从哪一边射向哪一边，方向决定了不等号的朝向。

第 4 题　Ferrers 图上路径数 \(M(m,n)\) 的对数凹性

本题及下一题的结果，都是作者与 Bruce Sagan 在研究中得到、并发表于文献 [17] 的——当时的目标是为 Rodica Simion 的猜想找一个组合证明，该猜想断言序列 \(\{M(i,n+m-i)\}_{0\le i\le m+n}\) 是单峰的（unimodal）。这个猜想以更强的形式（即该序列实际上是对数凹的）如今已有四个证明，不过其余两个并非组合证明。

(a) 这可以用一个简单的格点路径论证完成。设 \(p\) 为被 \(N(m,n+1)\) 统计的一条路径，\(q\) 为被 \(N(m+1,n)\) 统计的一条路径。则这两条路径必相交，像例 9.20 那样在它们的第一个交点处交换，就得到一对被 \(M(m,n)\cdot M(m+1,n+1)\) 统计的路径。该映射是单射。图 9.11 给出图示。

第一个交点 p q
图 9.11　在两条路径的交点处交换。这把一对 \(\bigl(N(m,n+1),N(m+1,n)\bigr)\) 路径单射地变成一对 \(\bigl(M(m,n),M(m+1,n+1)\bigr)\) 路径。

(b) 这一部分更微妙，因为被 \(M(m-1,n)\) 统计的路径与被 \(M(m+1,n)\) 统计的路径未必在到达终点之前相交。

设 \(p\) 为被 \(M(m-1,n)\) 统计的路径，\(q\) 为被 \(M(m+1,n)\) 统计的路径。在 \(p\) 上找到第一个点 \(P\)，使它恰好位于 \(q\) 的某点 \(Q\) 正下方一个单位处。这样的点必定存在，因为 \(p\) 与 \(q\) 的竖直距离从 \(2\) 变到了 \(0\)。然后把 \(p\) 中位于 \(P\) 之前的那一段向南平移一个单位并接到 \(Q\) 的后半段上；同时把 \(q\) 中位于 \(Q\) 之前的那一段向北平移一个单位并接到 \(p\) 的后半段上。图示见图 9.12。这就完成了对 \(p\) 与 \(q\) 初始段的“交换”，并给出所需的单射。请读者自行验证细节：即这个映射确实是单射，并且是一个合法映射（也就是说，得到的路径绝不会跑进 \(F\) 的内部）。

P Q 距离1
图 9.12　当 \(p\) 与 \(q\) 的竖直距离为 \(1\) 时交换路径：\(P\) 是 \(p\) 上第一个恰在 \(q\) 上某点 \(Q\) 正下方一格的点。

(c) 把 (a) 与 (b) 中证得的两个不等式相乘，再化简即可。

名词：Ferrers 图与 \(M(m,n)\) Ferrers 图（Ferrers shape）\(F\) 是把一个整数分拆画成的左上对齐方格阵列。\(M(m,n)\) 表示在以 \(F\) 为“禁区”的网格里、从某固定起点走到列坐标 \(m\)、行坐标 \(n\) 的合法格点路径条数（不许走进 \(F\) 内部）。这些题目的整体目标是证明：固定 \(m+n\) 时，序列 \(\{M(i,m+n-i)\}\) 是对数凹（从而单峰）的。
(a)(b)(c) 三步的逻辑骨架
  1. (a) 证一个“向一边偏”的不等式（对应相邻位置的一种交换）。
  2. (b) 证另一个“向另一边偏”的不等式（更难，因为路径不一定相交，要靠“竖直距离从 2 降到 0、中途必经过 1”这一介值式的观察找到交换点）。
  3. (c) 两式相乘得到 \(M(m,n)^2\ge M(m-1,n)\,M(m+1,n)\) 形式的对数凹不等式。乘法在这里的作用，是把两个“半步”的不等式拼成一个完整的“对数凹”不等式。♦

第 5 题　借助共轭 Ferrers 图与特例

(a) 设 \(F^{c}\) 为 Ferrers 图 \(F\) 的共轭（conjugate）。因为上一题 (c) 的结果对一切 Ferrers 图都成立，所以它对 \(F^{c}\) 也成立。另一方面，我们有 \(M(a,b)=M_{F^{c}}(b,a)\)。因此，若对 \(F^{c}\)（而非 \(F\)）应用 (9.7)，再利用上述对称性，就得到 \[M(n+1,m-1)\,M(n,m+1)\ \le\ M(n,m)\,M(n+1,m).\] 现在把 \(m\) 与 \(n\) 互换即可。

(b) 取 (9.7) 与 (a) 中证得的不等式之乘积，再化简。

(c) 若 \(F\) 为空 Ferrers 图，则我们证明为对数凹的那个序列，正是 \[\Bigl\{\tbinom{n+m}{i}\Bigr\}_{0\le i\le m+n}\] 即一行二项式系数。

(d) 不会，即便在非常简单的情形也不会成立。设 \(F\) 由一个方格组成，并令 \(m+n=4\)。这会导出多项式 \[3x^{3}+5x^{2}+3x,\] 它有两个复根。

(d) 在问什么？ 第 9 章里有三条逐渐变强的性质：单峰 \(\Leftarrow\) 对数凹 \(\Leftarrow\) “实根性质（real zeros property）”（即生成多项式的根全为实数）。(d) 问的是：我们证明对数凹的这个序列，其生成多项式是否一定只有实根？答案是否。
把 (d) 的反例算清楚
  1. 把多项式提出公因子 \(x\)：\(3x^{3}+5x^{2}+3x=x\,(3x^{2}+5x+3)\)。一个根是 \(x=0\)（实根）。
  2. 看二次因子 \(3x^{2}+5x+3\) 的判别式：\(\Delta=5^{2}-4\cdot3\cdot3=25-36=-11<0\)。
  3. 判别式为负，二次因子有一对共轭复根。于是该三次多项式共有两个复根、一个实根，不满足实根性质。
  4. 结论：序列可以对数凹却不具实根性质——这正说明“实根性质”比“对数凹”严格更强。♦

第 6 题　把路径切成三段、交换中段

取一条被 \(M(m-1,n+1)\) 统计的路径 \(p\) 与一条被 \(M(m+1,n-1)\) 统计的路径 \(q\)。我们要把这一对单射地映到一对 \((p',q')\)，其中两条路径都属于被 \(M(m,n)\) 枚举的集合。

为此，我们把路径 \(p\) 与 \(q\) 各切成三段（而非两段），并交换它们的中段。仿照第 4 题 (b) 的解法：设 \(P,Q\) 分别为 \(p,q\) 上使得 \(P\) 恰在 \(q\) 上方一个单位的第一对点；再设 \(P^{*},Q^{*}\) 分别为使得 \(P^{*}\) 恰在 \(Q^{*}\) 正东一个单位的最后一对点。于是这四个点把 \(p\) 分成三段 \(p_1,p_2,p_3\)，把 \(q\) 分成三段 \(q_1,q_2,q_3\)。然后把 \((p,q)\) 映为 \[(p,q)\ \longmapsto\ (p_1\,q_2\,p_3,\ \ q_1\,p_2\,q_3),\] 其中 \(p_1\) 向南移一个单位，\(p_3\) 向西移一个单位，\(q_1\) 向北移一个单位，\(q_3\) 向东移一个单位。示例见图 9.13。请读者验证：此映射是单射，且得到的路径不会走进 \(F\) 的内部。

P Q P* Q*
图 9.13　把 \(p\)、\(q\) 各切成 \(p_1,p_2,p_3\) 与 \(q_1,q_2,q_3\) 三段，交换中段 \(p_2\leftrightarrow q_2\)，并对首尾两段各作一个单位的平移。
为什么这次要切三段 第 4 题里相邻下标只差 \(1\)（如 \(m-1\) 与 \(m+1\) 之间隔着 \(m\)），交换“一刀”即可。本题里 \(p\) 偏离“目标 \(M(m,n)\)”的程度更大——一个差在第一坐标、一个差在第二坐标，方向不同。要把它们同时校正回 \(M(m,n)\)，需要在“前端”和“后端”各做一次配准（找到 \(P,Q\) 与 \(P^{*},Q^{*}\)），所以切成三段、只交换中段，让两头各自归位。

第 7 题

这由 (9.4) 经例行整理（routine rearrangements）即得。

讲解 原书把此题归结为“对前面已证的恒等式 (9.4) 做代数移项整理”，没有新思想。所谓“例行整理”，通常指：把 (9.4) 中的求和或乘积换一种写法、合并同类项、约去公因子，直接读出本题所需的等式或不等式。遇到这类题的标准做法就是：把 (9.4) 抄下来，逐步代数变形到目标形式，确认每一步都是恒等变换即可。

第 8 题　对数凹未必能推出实根

不，这是错的。一个反例是序列 \(1,3,3\)。

把这个反例讲透
  1. 本题问的是：“对数凹序列的生成多项式是否一定只有实根？”先验证 \(1,3,3\) 确实对数凹：唯一的内部检验是 \(a_1^2\ge a_0\,a_2\)，即 \(3^2=9\ge 1\cdot3=3\)，成立。
  2. 写出它的生成多项式 \(P(x)=3x^{2}+3x+1\)（系数按 \(a_2,a_1,a_0\) 排）。
  3. 求判别式：\(\Delta=3^{2}-4\cdot3\cdot1=9-12=-3<0\)。
  4. 判别式为负 \(\Rightarrow\) 两个根都是复数。于是 \(1,3,3\) 对数凹却不具实根性质，反例成立。♦
对照：实根 \(\Rightarrow\) 对数凹（反向是对的） 若一个多项式系数序列来自只有实根的多项式（例如 \((x+1)^2=x^2+2x+1\) 给出 \(1,2,1\)），则它一定对数凹。本题说明反向不成立：对数凹是比实根性质更弱的条件。这与第 5(d) 题是同一个道理的两个例子。

第 9 题　用 Hall 定理证明二项式系数单峰

设 \(k\le\bigl\lfloor (n-1)/2\bigr\rfloor\)。定义图 \(G\) 为这样一个二部图（bipartite graph）：其顶点对应于 \([n]\) 的所有 \(k\)-元子集与所有 \((k+1)\)-元子集；当 \(x\subset y\)（要求严格包含）时，令顶点 \(x\) 与 \(y\) 相邻。则 \(G\) 是二部图，两个色类 \(A\) 与 \(B\) 分别有 \(\binom{n}{k}\) 与 \(\binom{n}{k+1}\) 个顶点，因为它们对应于 \([n]\) 的 \(k\)-元与 \((k+1)\)-元子集族。我们要证的断言 \(\binom{n}{k}\le\binom{n}{k+1}\)，只要能证明 \(A\) 到 \(B\) 存在一个完美匹配（perfect matching）即可。

只需说明 Philip Hall 定理（Hall's theorem）的条件成立。为此注意 \(G\) 是正则的（regular）：事实上，\(A\) 的每个顶点度数为 \(n-k\)，\(B\) 的每个顶点度数为 \(k+1\)。因为已知 \(k\le\bigl\lfloor(n-1)/2\bigr\rfloor\)，可得 \(n-k\ge k+1\)，所以 \(A\) 中顶点的度数至少不小于 \(B\) 中顶点的度数。

现在取 \(G\) 中由 \(S\) 与 \(N(S)\) 的顶点导出的子图 \(H\)，其中 \(S\subseteq A\) 任意。由于 \(S\) 中顶点在限制到这个子图后没有失去任何邻居，它们的度数仍至少不小于 \(N(S)\) 中任何顶点的度数。又因为 \(S\) 与 \(N(S)\) 中所有顶点的度数总和必须相等（这是二部图边数从两侧分别统计的结果），便推出 \(|S|\le|N(S)|\)。因此 \(A\) 到 \(B\) 存在完美匹配，从而 \(|A|\le|B|\)，即 \(\binom{n}{k}\le\binom{n}{k+1}\)。其余的单峰性由序列的对称性 \(\binom{n}{k}=\binom{n}{n-k}\) 推出。

名词：Hall 定理（婚配定理） 设二部图两侧为 \(A,B\)。\(A\) 能完全匹配进 \(B\)（即每个 \(A\) 顶点都配到一个互不相同的 \(B\) 顶点）当且仅当对 \(A\) 的每个子集 \(S\)，其邻居集合都不更小：\(|S|\le|N(S)|\)。这就是“Hall 条件”。
为什么 \(|S|\le|N(S)|\) ——把度数账算清楚
  1. 在导出子图 \(H\)（顶点为 \(S\cup N(S)\)）里，统计边数有两种方式。从 \(S\) 一侧数：每个 \(S\) 顶点在 \(H\) 里度数仍是 \(n-k\)（它的邻居全在 \(N(S)\) 里，没丢），故边数 \(=(n-k)\,|S|\)。
  2. 从 \(N(S)\) 一侧数：每个 \(N(S)\) 顶点在 \(H\) 里度数至多是它在 \(G\) 里的度数 \(k+1\)，故边数 \(\le(k+1)\,|N(S)|\)。
  3. 同一批边数相等/受限，得 \((n-k)\,|S|\le(k+1)\,|N(S)|\)。
  4. 因为 \(n-k\ge k+1>0\)，两边除以可得 \(|S|\le\dfrac{k+1}{\,n-k\,}\,|N(S)|\le|N(S)|\)。Hall 条件成立。♦
例：\(n=4\) 一行二项式系数 \(\binom40,\dots,\binom44=1,4,6,4,1\)，确实单峰、对称、最高点在中间 \(\binom42=6\)。本题证明的是“到峰之前一路不减”，即 \(k\le\lfloor(n-1)/2\rfloor=1\) 时 \(\binom{4}{k}\le\binom{4}{k+1}\)：\(k=0\) 给 \(1\le4\)，\(k=1\) 给 \(4\le6\)。再由对称性 \(\binom4k=\binom4{4-k}\) 知道峰之后一路不增，于是整体单峰。

第 10 题　Narayana 数与二叉树的单射

我们在第 23 题已见到：Narayana 数 \(N(n,k)\) 统计 \(n\) 个顶点、恰有 \(k\) 条右边的无标号二叉树（binary tree）。设 \(\mathcal N(n,k)\) 为这种树的集合，并设 \(k\le(n-1)/2\)。我们将构造一个单射 \(f:\ \mathcal N(n,k)\to\mathcal N(n,k+1)\)。

设 \(T\in\mathcal N(n,k)\)。在 \(T\) 的顶点集上定义一个全序如下：先按顶点到根的距离排序（离根最远的排在前），再按从左到右排序。设 \(T_i\) 为 \(T\) 的前 \(i\) 个顶点导出的子图，则 \(T_i\) 是一片森林。进一步，\(T_i\) 的右边数要么与 \(T_{i-1}\) 相同，要么多一条。由于 \(T_0\) 的左边数与右边数相等（都是 \(0\)），而 \(T_n\) 的右边数至少比左边数多一条，上一句话便意味着：必存在一个（最小的）下标 \(j\)，使得 \(T_j\) 的右边数恰好比左边数多一条。

现在把 \(T_j\) 的每个连通分量，绕过它的根的一条竖直对称轴翻转（reflect）。把得到的树记为 \(f(T)\)。则 \(f(T)\) 比 \(T\) 多一条左边（相应地少一条右边），于是 \(f:\ \mathcal N(n,k)\to\mathcal N(n,k+1)\)。事实上，要找一棵树 \(T'\in\mathcal N(n,k+1)\) 的原像，只需找最小的下标 \(j\)，使得 \(T'_j\) 的左边数比右边数多一条（若存在这样的下标），再把 \(T'_j\) 的每个连通分量绕过其根的竖直对称轴翻转。图 9.14 给出一个例子。

T（右边偏多） 右边 左边 → f(T)（多一条左边）
图 9.14　本例中 \(j=5\)，因为此时 \(T_j\) 含两条左边、一条右边。沿过根的竖直轴翻转 \(T_j\) 的各分量，把右边换成左边，于是右边数减一、左边数加一。该操作可逆，故 \(f\) 是单射。
为什么这个 \(f\) 是单射（可逆） 关键在于“最小下标 \(j\)”这个选择是确定的、对称的：在 \(T\) 里 \(j\) 是“右边首次超出一条”的位置，翻转后在 \(f(T)\) 里同一个 \(j\) 恰好是“左边首次超出一条”的位置。于是从 \(f(T)\) 出发，用同样的规则找到同一个 \(j\)、再翻转一次，就回到 \(T\)。一个有明确逆映射的映射必为单射，故 \(|\mathcal N(n,k)|\le|\mathcal N(n,k+1)|\)，即 \(N(n,k)\le N(n,k+1)\)，得到（直到峰前的）单调不减，从而单峰。
例：右边/左边怎么数 二叉树里每个顶点最多有一个左孩子和一个右孩子；连向右孩子的边叫“右边”，连向左孩子的边叫“左边”。\(n=3\) 个顶点的二叉树共有 \(c_3=5\) 棵，按右边数分类：右边数 \(0,1,2\) 的棵数分别是 \(N(3,1),N(3,2),N(3,3)\) 的一种排布；翻转一棵树就把它的左右边数对调，这正是 \(f\) 的作用机理。

第 11 题　\(S(n,2)\) 的对数凹性

把 \([n]\) 分拆成一个有序对的两个块，可以用一个长度为 \(n\) 的二进制向量来描述：它的第 \(i\) 个坐标为 \(1\)，当且仅当 \(i\) 属于第一个块（否则为 \(0\)，表示 \(i\) 属于第二个块）。

说明：原书 PDF 在此处正好截断于本句中途（“…whose \(i\)th coordinate is 1 if \(i\) is part…”）。下面我们按其唯一自然的走向把这道解答补全——这是关于第二类 Stirling 数 \(S(n,2)\) 的标准论证，结论与方法都唯一确定。

这样的二进制向量共有 \(2^{n}\) 个。但要求两个块都非空，必须排除全 \(0\) 与全 \(1\) 这两个向量，于是有序对（ordered pair）的个数为 \(2^{n}-2\)。由于交换两个块给出同一个无序分拆，无序的分拆数为 \[S(n,2)=\frac{2^{n}-2}{2}=2^{\,n-1}-1.\] 现在直接验证序列 \(S(2,2),S(3,2),S(4,2),\dots\) 的对数凹性，即证 \[S(n,2)^{2}\ \ge\ S(n-1,2)\,S(n+1,2).\]

分步推演：用闭形式验证对数凹
  1. 代入 \(S(m,2)=2^{\,m-1}-1\)。左边 \[S(n,2)^2=\bigl(2^{\,n-1}-1\bigr)^2=2^{\,2n-2}-2\cdot2^{\,n-1}+1=2^{\,2n-2}-2^{\,n}+1.\]
  2. 右边 \[S(n-1,2)\,S(n+1,2)=\bigl(2^{\,n-2}-1\bigr)\bigl(2^{\,n}-1\bigr)=2^{\,2n-2}-2^{\,n-2}-2^{\,n}+1.\]
  3. 左边减右边： \[\bigl(2^{\,2n-2}-2^{\,n}+1\bigr)-\bigl(2^{\,2n-2}-2^{\,n-2}-2^{\,n}+1\bigr)=2^{\,n-2}.\]
  4. 因为 \(2^{\,n-2}>0\)，所以左边 \(>\) 右边，对数凹不等式严格成立。♦
这与“二进制向量”编码的联系 上面的二进制向量编码不仅给出闭形式 \(S(n,2)=2^{n-1}-1\)，也提示了组合证明的思路：把被 \(S(n-1,2)\cdot S(n+1,2)\) 统计的对象（一对“去掉一个元素”与“添上一个元素”的有序分拆，用一条长 \(n-1\) 与一条长 \(n+1\) 的非常向量表示）单射地配到被 \(S(n,2)^2\) 统计的对象（两条长 \(n\) 的非常向量）。差出来的那一份正好对应 \(2^{\,n-2}\) 这个“多出来的余量”，与上面的代数差额一致。无论走代数还是组合，结论都是：\(S(\cdot,2)\) 是对数凹的。
例：把前几项列出来核对 \(S(2,2),S(3,2),S(4,2),S(5,2)=1,3,7,15\)（即 \(2^{m-1}-1\)）。检验内部两项：
  • \(S(3,2)^2=9\ \ge\ S(2,2)\,S(4,2)=1\cdot7=7\)。\(9-7=2=2^{1}\)，与 \(2^{\,n-2}\)（\(n=3\)）吻合。
  • \(S(4,2)^2=49\ \ge\ S(3,2)\,S(5,2)=3\cdot15=45\)。\(49-45=4=2^{2}\)，与 \(2^{\,n-2}\)（\(n=4\)）吻合。
两处都成立，且差额恰为 \(2^{\,n-2}\)，验证完毕。
名词：第二类 Stirling 数 \(S(n,k)\) 表示把集合 \([n]=\{1,2,\dots,n\}\) 分拆成 \(k\) 个非空、无序块的方案数。特例 \(S(n,2)=2^{\,n-1}-1\)：把 \(n\) 个元素分成两个非空块，等价于给元素染两种颜色但去掉“全同色”与“颜色对调重复”这两类，故得此式。

返回 全书目录