本页为译文 + 高中讲解 合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
在本章中，我们将考察整条序列 的组合性质，而不是只考察其中单个元素的性质。
本节目标 认识一种重要的序列形态——单峰 （unimodal）：一条数列先一路不降地上升 ，到达某个最高点（峰）后再一路不增地下降 。本节给出它的精确定义，并用两种方法证明：对任意固定的 \(n\)，二项式系数 \(\binom n0,\binom n1,\dots,\binom nn\) 正是这样一条单峰序列。
在上一章里，我们曾在另一情境下遇到下面这个问题。一位教授要为大量学生准备口试题目。身为数学教授，他列出了一份共 \(n\) 道题的清单。他想做到公平，于是给每名学生都恰好提问相同的 \(k\) 道题。同时他不想把同一组 题目向两名学生重复提问。为了让能被这样测试的学生人数最多，\(k\) 应当取多少？
由于 \([n]\) 共有 \(\binom nk\) 个 \(k\) 元子集，教授需要找出使 \(\binom nk\) 取得最大值的 \(k\)。看一看图 9.1（你或许还记得第 1 章里见过它），其中第 \(n\) 行的各项就是固定 \(n\) 时 \(\binom nk\) 的取值。它提示我们：数列 \(\binom n0,\binom n1,\dots\) 会持续增大，直到 \(k=\lfloor n/2\rfloor\) 为止，然后持续减小。这种规律是序列的一条重要性质，它有专门的名字。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
图 9.1 \(\binom nk\) 的取值。注意：固定 \(n\) 时，各值 \(\binom n0,\binom n1,\dots\) 构成帕斯卡三角形（Pascal triangle）的第 \(n\) 行。每一行都从两端的 \(1\) 开始向中间增大，到正中间（红色）达到最大，再向另一端减小。
定义 9.1 由非负实数组成的序列 \(a_0,a_1,\dots,a_n\) 称为单峰的 （unimodal），如果存在一个下标 \(m\)，使得
\[a_0\le a_1\le\cdots\le a_m\ge a_{m+1}\ge\cdots\ge a_{n-1}\ge a_n.\]
换句话说，一条序列是单峰的，是指它的各项先持续增大，再持续减小。
例（具体感受单峰） 取 \(n=6\)，把第 \(6\) 行的二项式系数列出来：
\[\binom60,\binom61,\dots,\binom66=1,\;6,\;15,\;20,\;15,\;6,\;1.\]
逐项比较：\(1\le 6\le 15\le 20\)（上升），随后 \(20\ge 15\ge 6\ge 1\)（下降）。峰出现在 \(m=3\)，峰值为 \(\binom63=20\)。这正符合定义 9.1，所以它是单峰序列。
1 6 15
20 15 6 1
k=0 k=3（峰） k=6
柱高即各 \(\binom6k\)。柱子先升后降，正中间最高——这就是“单峰”的形状。
事实表明，我们关于序列 \(\binom nk_{\,0\le k\le n}\) 单峰性的这一观察，对所有 \(n\) 都成立。
命题 9.2 对任意固定的正整数 \(n\)，序列 \(\binom nk_{\,0\le k\le n}\) 是单峰的。
这一著名事实有许多证明。我们先从最简单的一种——计算式的证明——讲起。
证明. 设 \(k\le\lfloor(n-1)/2\rfloor\)。我们断言此时 \(\binom nk\le\binom n{k+1}\)，也就是说序列在这一段是（弱）递增的。事实上，
\[\tag{9.1}\frac{\binom n{k+1}}{\binom nk}=\frac{(n-k)!\,k!}{(n-k-1)!\,(k+1)!}=\frac{n-k}{k+1}\ge 1.\]
此外，上面的计算同样表明：若 \(k>\lfloor(n-1)/2\rfloor\)，则 \(\binom nk>\binom n{k+1}\)，于是序列在这一段是递减的。这就证明了我们的断言。♦
把 (9.1) 这步算账拆开来看，关键在于那个比值 \(\dfrac{n-k}{k+1}\) 与 \(1\) 谁大谁小：
用阶乘写出 \(\binom nk=\dfrac{n!}{(n-k)!\,k!}\)，\(\binom n{k+1}=\dfrac{n!}{(n-k-1)!\,(k+1)!}\)。两者相除，分子分母里的 \(n!\) 约掉。
剩下的阶乘约分：\(\dfrac{(n-k)!}{(n-k-1)!}=n-k\)，\(\dfrac{k!}{(k+1)!}=\dfrac1{k+1}\)，于是比值恰为 \(\dfrac{n-k}{k+1}\)。
判断这个比值是否 \(\ge 1\)：\(\dfrac{n-k}{k+1}\ge 1\iff n-k\ge k+1\iff n-1\ge 2k\iff k\le\dfrac{n-1}2\)。
所以当 \(k\le\lfloor(n-1)/2\rfloor\) 时下一项不小于当前项（上升）；当 \(k\) 超过这个界限时比值小于 \(1\)，下一项变小（下降）。先升后降，正是单峰。
例（用比值法走一遍 n=6） 比值 \(\dfrac{n-k}{k+1}=\dfrac{6-k}{k+1}\)。
\[k=0:\tfrac61=6>1,\quad k=1:\tfrac52>1,\quad k=2:\tfrac43>1,\quad k=3:\tfrac34<1,\quad k=4:\tfrac25<1,\dots\]
前三步比值大于 \(1\)（数列在涨：\(1\to6\to15\to20\)），从 \(k=3\) 起比值小于 \(1\)（数列在落：\(20\to15\to6\to1\)）。峰恰在 \(k=3=\lfloor6/2\rfloor\)。
于是，教授若取 \(k=\lfloor n/2\rfloor\)，就能最有效地使用他的题目。
注意，我们的序列 \(\binom nk_{\,0\le k\le n}\) 不仅是单峰的，它还是对称的 ，因为 \(\binom nk=\binom n{n-k}\)。这一点意味着序列的最大值必定落在正中间。
为什么对称就保证“峰在正中” 等式 \(\binom nk=\binom n{n-k}\) 说明：把序列从两端向中间看，第 \(k\) 项和倒数第 \(k\) 项一样大。所以整条序列关于中点左右对称；一条既单峰又对称的序列，它的峰只能出现在对称轴上，即 \(k=\lfloor n/2\rfloor\)（当 \(n\) 为奇数时，中间两项相等，并列为峰）。
上面的证明虽然简单，却并不太能给人启发。它强烈依赖于这样一个事实：我们手上有一个计算 \([n]\) 的 \(k\) 元子集个数的公式，而且还是个简单的公式。我们希望发展出别的方法，使得在没有这种公式的情形下也能证明单峰性结论。我们将首先用一种叫做反射原理 （reflection principle）的方法来重新证明命题 9.2。作为额外收获，我们还会得到一个关于 \(\binom nk\le\binom n{k+1}\)（当 \(k\le\lfloor(n-1)/2\rfloor\)）的组合证明 。
思路转换 第一种证明是“算比值”，靠公式硬算。第二种证明换一个角度：不去比较两个数的大小，而是去构造一个从“\(k\) 元子集的集合”到“\((k+1)\) 元子集的集合”的单射 （injection，一对一映射）。一旦能把前者一对一地塞进后者，就立刻得到前者个数 \(\le\) 后者个数，即 \(\binom nk\le\binom n{k+1}\)。这就把“数的不等式”变成了“图形的对应”。
为此，我们回到第 1 章的例 1.26，在那里我们隐含地定义了一个简单的双射 （bijection），它把 \([n]\) 的全体 \(k\) 元子集，与从 \((0,0)\) 到 \((n-k,k)\) 的全体东北向格路 （northeastern lattice path，即每一步只能向东 E 或向北 N）一一对应起来。为便于引用，这个双射 \(f\) 的作法是：若 \(k\) 元子集 \(A\subseteq[n]\) 的元素为 \(a_1,a_2,\dots,a_k\)，则 \(f(A)\) 是这样一条东北向格路，它的 \(k\) 个向北的步恰好是整条格路的第 \(a_1,a_2,\dots,a_k\) 步。
例 9.3 图 9.2 给出 \([8]\) 的两个 \(4\) 元子集在 \(f\) 下的像。
把 f 的规则走通（\([8]\) 中取 4 个） 这里 \(n=8,\ k=4\)，终点为 \((n-k,k)=(4,4)\)，整条路共 \(8\) 步、其中 \(4\) 步向北 N、\(4\) 步向东 E。
子集 \(\{1,2,4,8\}\)：第 \(1,2,4,8\) 步向北，其余第 \(3,5,6,7\) 步向东，得步序 N N E N E E E N 。
子集 \(\{3,4,6,7\}\)：第 \(3,4,6,7\) 步向北，其余第 \(1,2,5,8\) 步向东，得步序 E E N N E N N E 。
两条路都用 \(4\) 个 N、\(4\) 个 E，因此都从 \((0,0)\) 走到 \((4,4)\)。子集不同，路就不同——这正说明 \(f\) 是一一对应。
f(1,2,4,8)
f(3,4,6,7)
图 9.2 \(\{1,2,4,8\}\subseteq[8]\)（左）与 \(\{3,4,6,7\}\subseteq[8]\)（右）的像。两条路都从左下角 \((0,0)\) 走到右上角 \((4,4)\)。
有了这个双射，我们就可以把证明的其余部分用格路、而非 \([n]\) 的 \(k\) 元子集来叙述。我们提出如下策略：令 \(L_k\) 为从 \((0,0)\) 到 \((n-k,k)\) 的东北向格路之集合，并设 \(k\le\lfloor(n-1)/2\rfloor\)。我们将证明：在此情形下，存在一个单射 ，即一个一对一的映射 \(g:L_k\to L_{k+1}\)。这将证明 \(|L_k|\le|L_{k+1}|\)，从而推出我们这条对称序列 \(\binom nk_{\,0\le k\le n}\) 的单峰性。
设 \(p\in L_k\)。由于 \(k\le\lfloor(n-1)/2\rfloor\)，这意味着 \(p\) 的终点 \(P=(n-k,k)\) 位于主对角线 \(y=x\) 的下方 。令 \(Q\) 为点 \((n-k-1,k+1)\)，即属于 \(L_{k+1}\) 的那些路的终点。令 \(t\) 表示线段 \(PQ\) 的中垂线（垂直平分线）。于是 \(t\) 是直线
\[y=x-(n-2k-1),\]
请读者验证：\(p\) 的两个端点 \((0,0)\) 与 \(P\) 分别落在 \(t\) 的两侧。事实上，\(t\) 与横轴的交点是 \((n-2k-1,\,0)\)，由于我们对 \(k\) 的条件，它落在横轴的正半轴上。
译注：中垂线 t 的方程 \(P=(n-k,k)\)、\(Q=(n-k-1,k+1)\)，线段 \(PQ\) 斜率为 \(-1\)，故其中垂线斜率为 \(1\)。中垂线就是“到 \(P\) 与到 \(Q\) 距离相等”的点的集合，它把 \(P\) 与 \(Q\) 互相对称。沿斜率为 \(1\) 的直线 \(y=x+c\) 作反射，会把点 \((a,b)\) 送到 \((b-c,\,a+c)\)；要让 \(P\) 反射成 \(Q\)，解得 \(c=2k+1-n=-(n-2k-1)\)，即 \(t:\ y=x-(n-2k-1)\)。令 \(y=0\) 得 \(x=n-2k-1\)，这就是它与横轴的交点 \((n-2k-1,0)\)；当 \(k\le\lfloor(n-1)/2\rfloor\) 时 \(n-2k-1\ge0\)，落在正半轴上。（原书此处把直线写成 \(y=x+(n-2k)-1\)，与它自己给出的横轴交点 \((n-2k-1,0)\) 不自洽，应为正负号笔误，这里予以更正。）
因此，\(p\) 与 \(t\) 相交。令 \(X\) 为它们交点中最后一个（最靠东北的）。把部分路径 \(XP\) 关于 \(t\) 作反射，得到一段部分路径 \(XQ\)。现在定义 \(g(p)\) 为：\(p\) 中从 \((0,0)\) 到 \(X\) 的那一段，再接上我们刚才反射得到的 \(XQ\)。这种证明单峰性命题的方法称为反射原理 ，在 Bruce Sagan 的综述文章 [63] 中有更多例子加以说明。
例 9.4 图 9.3 展示了 \(g\) 如何把与 \(\{3,4,8\}\subset[8]\) 对应的格路，映成与 \(\{3,4,6,7\}\) 对应的格路。
把例 9.4 一步步算出来 这里 \(n=8\)。取 \(k=3\)，\(p=f(\{3,4,8\})\) 的步序为
E E N N E E E N ，终点 \(P=(n-k,k)=(5,3)\)。目标终点 \(Q=(n-k-1,k+1)=(4,4)\)，中垂线 \(t:\ y=x-(8-6-1)=x-1\)。
沿 \(p\) 找出它落在 \(t:\ y=x-1\) 上的格点：\((1,0),(2,1),(3,2)\)。最靠东北的是 \(X=(3,2)\)。
取 \(p\) 中从 \(X=(3,2)\) 到 \(P=(5,3)\) 的尾段 \(XP\)（步序 E E N，经过 \((4,2),(5,2),(5,3)\)）。
把 \(XP\) 关于 \(t\) 反射：反射规则 \((a,b)\mapsto(b+1,\,a-1)\)。于是 \((4,2)\to(3,3)\)，\((5,2)\to(3,4)\)，\((5,3)\to(4,4)=Q\)。得反射段 \(XQ\)：\((3,2)\to(3,3)\to(3,4)\to(4,4)\)，步序 N N E。
把 \(p\) 的前段（\((0,0)\) 到 \(X\)，步序 E E N N E）接上 \(XQ\)（N N E），得 \(g(p)\) 的步序 E E N N E N N E 。
读出 \(g(p)\) 的向北步在第 \(3,4,6,7\) 位，即 \(g(p)=f(\{3,4,6,7\})\)。从 \(3\) 元子集成功得到了一个 \(4\) 元子集。♦
t
(0,0)
X
P
Q
p
g(p)
图 9.3 反射原理的运作。蓝色为原路 \(p\)（终点 \(P\)）；从最东北交点 \(X\) 起，把尾段关于中垂线 \(t\)（绿色虚线）反射，得到红色尾段，终点变为 \(Q\)。前段不动、尾段反射，拼成 \(g(p)\in L_{k+1}\)。
注意，\(g(p)\) 与 \(t\) 总是相交。下面的引理表明反射原理确实奏效。
引理 9.5 对一切满足 \(k\le\lfloor(n-1)/2\rfloor\) 的正整数 \(k\)，上面定义的映射 \(g:L_k\to L_{k+1}\) 是一个单射。
证明. 设 \(q\in L_{k+1}\)，并令 \(P,Q,t\) 如上定义。若 \(q\) 与 \(t\) 不相交，则 \(q\) 不在 \(g\) 的值域中。否则，令 \(X\) 为 \(q\) 与 \(t\) 的交点中最靠东北的那一个。把 \(q\) 中从 \(X\) 到 \(Q\) 的尾段 \(XQ\) 关于 \(t\) 反射，得到一段尾段 \(XP\)；再把 \(q\) 中从 \((0,0)\) 到 \(X\) 的前段接上 \(XP\)，便得到一条以 \(P\) 为终点的格路 \(p\in L_k\)。这个 \(p\) 是唯一 满足 \(g(p)=q\) 的格路：因为反射是它自身的逆运算，由 \(q\) 反推回的 \(p\) 完全被 \(q\) 唯一确定。于是不同的 \(q\) 至多来自不同的 \(p\)，亦即 \(g\) 把不同的 \(p\) 送到不同的 \(q\)。所以 \(g\) 是单射。♦
回到结论 因为 \(g:L_k\to L_{k+1}\) 是单射，所以 \(|L_k|\le|L_{k+1}|\)，即 \(\binom nk\le\binom n{k+1}\)（对 \(k\le\lfloor(n-1)/2\rfloor\)）。再配合对称性 \(\binom nk=\binom n{n-k}\)，序列在过了中点后必然对称地下降。先升后降，于是 \(\binom nk_{\,0\le k\le n}\) 单峰——命题 9.2 得证。这一回，我们没有动用任何阶乘公式，只用了“把一条路一对一地变成另一条路”的几何构造。
返回 全书目录