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

9.6　习题Exercises

本页为译文 + 高中讲解合一：黑色正文为忠实翻译的题目；彩色框（目标 / 分步推演 / 例）与配图为面向高中生的解题思路与方法提示，告诉你“该用哪条原理、从哪里入手”，但不给出完整最终答案（完整解答见对应“习题解答”一节）。

本节预备概念回顾

  1. 证明：对任意固定的正整数 \(n\) 和任意 \(q>1\)，高斯系数（Gaussian coefficient）序列 \[\binom{n}{0}_q,\ \binom{n}{1}_q,\ \cdots,\ \binom{n}{n}_q\] 是对数凹的。（高斯系数在第 4 章习题 29 中定义。）

    思路提示 · 直接验证对数凹不等式 高斯系数（即 \(q\)-二项式系数）有显式公式 \[\binom{n}{k}_q=\frac{(q^n-1)(q^{n-1}-1)\cdots(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots(q-1)}.\] 要证对数凹，就是要证 \(\binom{n}{k-1}_q\binom{n}{k+1}_q\le \binom{n}{k}_q^{2}\)。
    1. 把不等式写成比值形式：考察相邻比 \(R_k=\dfrac{\binom{n}{k}_q}{\binom{n}{k-1}_q}\)，目标即证 \(R_{k+1}\le R_k\)（比值递减）。
    2. 用上面的显式公式约分，得到一项简洁的 \(R_k=\dfrac{q^{n-k+1}-1}{q^{k}-1}\)。
    3. 对 \(q>1\)，分子随 \(k\) 增大而减小、分母随 \(k\) 增大而增大，故 \(R_k\) 关于 \(k\) 单调递减，于是 \(R_{k+1}\le R_k\)，即得对数凹。

  2. (a) 回忆 (5.6) 中我们用 \[N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k+1}\] 定义了纳拉亚纳数（Narayana number）\(N(n,k)\)。证明：对任意固定的正整数 \(n\)，纳拉亚纳数序列 \[N(n,0),\ N(n,1),\ \cdots,\ N(n,n-1)\] 是对数凹的。

    (b) 证明：对任意固定的正整数 \(k\)，无穷序列 \[N(k+1,k),\ N(k+2,k),\ \cdots\] 是对数凹的。

    思路提示 · 把纳拉亚纳数化成二项式之积 关键是 \(N(n,k)\) 由两个二项式系数相乘构成，而两个对数凹序列逐项相乘仍对数凹。
    1. (a) 固定 \(n\)，让 \(k\) 变。要证 \(N(n,k-1)N(n,k+1)\le N(n,k)^2\)。公共因子 \(\frac1n\) 平方对称，可消去。剩下要证 \[\binom{n}{k-1}\binom{n}{k+1}\cdot\binom{n}{k}\binom{n}{k+2}\le \binom{n}{k}^2\binom{n}{k+1}^2.\]
    2. 这恰好是“二项式系数序列 \(\binom{n}{\bullet}\) 对数凹”这一已知事实用两次（一次对下标 \(k\)，一次对下标 \(k+1\)）相乘的结果。
    3. (b) 固定 \(k\)，让第一个参数 \(m=k+1,k+2,\dots\) 变。同样用显式公式写出相邻比 \(\dfrac{N(m+1,k)}{N(m,k)}\)，验证该比值随 \(m\) 递减即可。可先代入小数字（如 \(k=1\)：\(N(2,1),N(3,1),N(4,1)=1,3,6\)，验证 \(1\cdot 6\le 3^2\)）建立直觉。

  3. 若正实数序列 \(a_0,a_1,\cdots\) 对所有 \(k\ge 1\) 满足 \[a_{k-1}a_{k+1}\ge a_k^2,\] 则称它为对数凸的（log-convex）。请用组合论证证明卡塔兰数（Catalan number）序列 \(c_0,c_1,c_2,\cdots\) 是对数凸的。

    思路提示 · 构造单射 \(C_{k-1}\times C_{k+1}\hookrightarrow C_k\times C_k\)？反过来！ 对数凸要证 \(c_{k-1}c_{k+1}\ge c_k^2\)，即要构造一个单射 \[\{\text{大小 }k\text{ 的对象}\}\times\{\text{大小 }k\text{ 的对象}\}\ \hookrightarrow\ \{\text{大小 }k-1\}\times\{\text{大小 }k+1\}.\]
    1. 选一种被卡塔兰数计数的对象，例如长度 \(2k\) 的合法括号串（Dyck 路径），\(c_k\) 个。
    2. 取两条长度各为 \(2k\) 的 Dyck 路径 \((P,Q)\)。想办法“拆/接”出一条更短（\(2k-2\)）与一条更长（\(2k+2\)）的路径对 \((P',Q')\)，并保证这一操作可逆（即为单射）。常用技巧：找两条路第一次出现高度差异的位置，把后半段互换或挪动一个上/下步。
    3. 单射存在 \(\Rightarrow c_k\cdot c_k\le c_{k-1}\cdot c_{k+1}\)，即对数凸。
    用小数验证方向：\(c_0,c_1,c_2,c_3=1,1,2,5\)，检查 \(c_0c_2=2\ge c_1^2=1\)，\(c_1c_3=5\ge c_2^2=4\)，趋势正确。

  4. 如图 9.9 给方格网（square grid）的顶点标号，设 \(F\) 是位于网格西北角的一个 Ferrers 图形（Ferrers shape）。

    F (0,0)(0,1)(0,2)(0,3)(0,4) (1,0)(1,1)(1,2)(1,3)(1,4) (2,0)(2,1) 图 9.9　网格顶点的标号方式与 Ferrers 图形 F 的放置位置
    路径从 \((m,0)\) 出发到 \((0,n)\)，每步只能向东北方向（坐标 \((i,j)\to(i-1,j)\) 或 \((i,j)\to(i,j+1)\)），且不得进入 \(F\) 内部。

    设 \(M_F(m,n)=M(m,n)\) 为从 \((m,0)\) 到 \((0,n)\) 且不进入 \(F\) 内部的东北向格路（northeastern lattice path）的条数。

    (a) 证明 \[M(m,n+1)\,M(m+1,n)\le M(m,n)\,M(m+1,n+1).\tag{9.5}\]

    (b) (+) 证明 \[M(m-1,n+1)\,M(m+1,n+1)\le M(m,n+1)^2.\tag{9.6}\]

    (c) 由此推出 \[M(m-1,n+1)\,M(m+1,n)\le M(m,n)\,M(m,n+1).\tag{9.7}\]

    思路提示 · 路径配对（两条路径“交叉”技巧） 这类不等式的标准证法是路径对的交换/不交叉论证（类似 Lindström–Gessel–Viennot 思想）。
    1. (a) 不等式左边 \(M(m,n+1)M(m+1,n)\) 计数“一条从 \((m,0)\) 到 \((0,n+1)\) 的路径 \(P\)” 与 “一条从 \((m+1,0)\) 到 \((0,n)\) 的路径 \(Q\)”组成的有序对。由于这两条路的起点、终点是“交错”的，\(P\) 与 \(Q\) 必然相交。
    2. 在它们某个公共顶点处，把交点之后的两段互换，就得到一对从 \((m,0)\to(0,n)\) 与 \((m+1,0)\to(0,n+1)\) 的路径——恰由右边 \(M(m,n)M(m+1,n+1)\) 计数。这个交换给出一个单射，从而 \(\le\)。
    3. (b) 同理，对起点同为一行、终点相邻的两条路径作交换论证；带 (+) 表示较难，需更仔细地选取“第一个/最后一个”交点保证可逆。
    4. (c) 把 (9.5) 与 (9.6) 相乘并约去公共因子即可推出 (9.7)。具体地，将 (9.6) 用到合适的下标后与 (9.5) 联立，消去 \(M(m+1,n+1)\) 一类项。
    先用无 \(F\)（\(F=\varnothing\)）的情形验证：此时 \(M(m,n)=\binom{m+n}{n}\)，把它代入 (9.5) 检查不等式成立，建立信心。

  5. 沿用上一题的记号。

    (a) 证明 \(M(m+1,n-1)\,M(m,n+1)\le M(m,n)\,M(m+1,n)\)。

    (b) 由此推出 \(M(m+1,n-1)\,M(m-1,n+1)\le M(m,n)^2\)，也就是说，序列 \[\{M(i,\,n+m-i)\}_{0\le i\le m+n}\] 是对数凹的。

    (c) 解释这个结果如何推广了“对任意固定的 \(r\)，二项式系数 \(\binom{r}{k}\) 构成对数凹序列”这一事实。

    (d) 序列 \(\{M(i,\,n+m-i)\}_{0\le i\le m+n}\) 是否一定只有实根（即其对应多项式根全为实数）？

    思路提示
    1. (a) 与第 4 题完全同型——又是一组“交错起终点的路径对必相交”的交换论证，请仿照 (9.5) 的写法。
    2. (b) 把 (a) 与第 4 题 (9.7) 联立相乘、约分，即得 \(M(m+1,n-1)M(m-1,n+1)\le M(m,n)^2\)。注意序列下标 \(i\) 与 \(M(i,n+m-i)\) 中第一、二参数之和恒为 \(n+m\)（沿“反对角线”取值），这正是对数凹定义里相邻三项的形态。
    3. (c) 取 \(F=\varnothing\)：此时 \(M(i,n+m-i)=\binom{n+m}{i}\)。令 \(r=n+m\)，(b) 就退化为二项式系数行的对数凹。所以 (b) 是对“带障碍 \(F\)”的推广。
    4. (d) 这是开放式判断题：对数凹不蕴含“只有实根”。建议找一个 \(F\neq\varnothing\) 的小例子，把序列写出来，验证其多项式是否有复根作为反例（提示：答案为“不一定”）。

  6. (+) 为上一题 (b) 部分，即序列 \(\{M(i,\,n+m-i)\}_{0\le i\le m+n}\) 的对数凹性，找一个更直接的组合证明。

    思路提示 · 一步到位的单射 第 5 题 (b) 是“间接”地由 (a) 与 (9.7) 拼出来的。这里要求直接构造一个单射 \[\{(P,Q):P\text{ 从 }(i-1,*)\text{、}Q\text{ 从 }(i+1,*)\}\ \hookrightarrow\ \{(P',Q'):\text{都从 }(i,*)\},\] 两条路均沿同一条反对角线（参数和 \(=n+m\)）的端点出发/到达。核心仍是找两条必然相交的路径，在交点处一次性互换尾段，并说明该操作可逆（交点取“最靠后/最靠前”的那个以保证唯一性）。这样一步即得 \(a_{i-1}a_{i+1}\le a_i^2\)。

  7. 若正实数序列 \(a_0,a_1,\cdots,a_n\) 对 \(1\le i\le n-1\) 满足 \[\big(n-(i-1)\big)a_{i-1}\cdot(i+1)a_{i+1}\le (n-i)a_i\cdot i\,a_i,\] 则称它为强对数凹的（strongly log-concave）。证明：若正实数序列 \(a_0,a_1,\cdots,a_n\) 只有实根，则它是强对数凹的。

    思路提示 · 归一化到二项式权重 强对数凹其实就是“把 \(a_i\) 换成 \(b_i=a_i/\binom{n}{i}\) 后普通对数凹”。
    1. 注意 \(\dfrac{\binom{n}{i}}{\binom{n}{i-1}}=\dfrac{n-i+1}{i}\)。把题中不等式两边除以 \(\binom{n}{i-1}\binom{n}{i+1}\) 之类的组合数，可化为 \(b_{i-1}b_{i+1}\le b_i^2\)，其中 \(b_i=a_i/\binom{n}{i}\)。
    2. 已知“只有实根”的序列对数凹，并且这种性质在除以二项式系数这一变换下被保持（对应多项式作 \(x\mapsto\) 变量替换后仍只有实根）。本章正文里有相关引理可直接引用。
    3. 于是 \(b_i\) 序列对数凹，回代即得 \(a_i\) 强对数凹。

  8. 是否成立：若一个有限正实数序列是强对数凹的，那么它一定只有实根？

    思路提示 · 找反例还是给证明？ 第 7 题证了“只有实根 \(\Rightarrow\) 强对数凹”，本题问逆命题是否成立。一般这类逆命题为假。
    1. 策略：构造一个强对数凹、但对应多项式带复根的短序列（如 \(n=2\) 或 \(n=3\) 的三、四项序列）。
    2. 取小的 \(n\)，直接写出强对数凹的不等式（只是 \(i\) 取一两个值），挑一组满足它的 \(a_i\)，再解多项式 \(\sum a_i x^i\) 判别式，使之出现一对共轭复根。
    3. 找到一个这样的例子即否定了逆命题（答案：不成立）。

  9. 设 \(G\) 是一个二部图（bipartite graph），其颜色类（color class）为 \(A\) 与 \(B\)。对任意子集 \(X\subseteq A\)，记 \(N(X)\) 为 \(B\) 中与 \(X\) 里某顶点相邻的顶点集。

    称 \(A\) 能完美匹配进 \(B\)，若 \(G\) 中存在 \(|A|\) 条两两不共顶点的边，换言之，\(A\) 的每个顶点都能匹配到一个与它相邻的 \(B\) 顶点。

    图论中的经典定理——菲利普·霍尔定理（Philip Hall's theorem）——断言：\(A\) 能完美匹配进 \(B\) 当且仅当对所有 \(X\subseteq A\) 都有 \(|X|\le|N(X)|\)。请用此定理证明序列 \(\left\{\binom{n}{k}\right\}_{0\le k\le n}\) 是单峰的。

    思路提示 · 用匹配比较相邻两层的大小 要证单峰，只需证：当 \(k
  10. 令 \(A=\) 全部 \(k\)-元子集，\(B=\) 全部 \((k+1)\)-元子集；当 \(S\subset T\)（\(S\in A,\,T\in B\) 相差一个元素）时连一条边。
  11. 验证 Hall 条件 \(|X|\le|N(X)|\)：用双计数数 \(X\) 与其邻域之间的边数。每个 \(k\)-子集向上连 \(n-k\) 条边；每个 \((k+1)\)-子集向下被连 \(k+1\) 条边。比较两个方向的边数得 \((n-k)|X|\le(k+1)|N(X)|\)，当 \(k
  12. 由 Hall 定理，\(A\) 完美匹配进 \(B\)，故 \(|A|\le|B|\)，即 \(\binom{n}{k}\le\binom{n}{k+1}\)。对称处理右半，得单峰。
小数验证：\(n=4\) 时 \(1,4,6,4,1\) 确实先升后降。

  • (+) 设 \(n\) 为固定正整数。为纳拉亚纳数序列 \(N(n,0),N(n,1),\cdots,N(n,n-1)\) 的单峰性找一个组合的（即单射的）证明。提示：试用反射原理（reflection principle）。

    思路提示 · 反射原理造单射 单峰即要在左半段证 \(N(n,k)\le N(n,k+1)\)。组合证明就是构造一个单射 \[\{\text{被 }N(n,k)\text{ 计数的对象}\}\ \hookrightarrow\ \{\text{被 }N(n,k+1)\text{ 计数的对象}\}.\]
    1. 选纳拉亚纳数的一种组合解释：\(N(n,k)=\) 含恰好 \(k\) 个“峰”（或 \(k\) 次“上-下”转折）的长度 \(2n\) 的 Dyck 路径条数。
    2. 当峰数偏少（\(k<\) 峰数的中位）时，要把一条 \(k\)-峰路径“变”出一个新峰，得到 \((k+1)\)-峰路径。反射原理用来在某个选定位置把一段路径沿对角线翻折，从而精确地增加一个峰且操作可逆。
    3. 说明该映射是单射（可由翻折位置恢复原路径），于是 \(N(n,k)\le N(n,k+1)\)，得左半递增；对称得右半递减，故单峰。

    • 返回 全书目录