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

9.2　对数凹性Log-concavity

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

有意思的是，序列有一条性质，叫作对数凹性（log-concavity），它比单峰性（unimodality）更强，却往往更容易证明。

本节目标上一节我们关心一个序列是不是“先增后减”的单峰序列，难点在于要先找到峰在哪里。本节引入一条更苛刻、但反而更好验证的性质——对数凹性：只需逐项比较 \(d_{k-1}d_{k+1}\) 与 \(d_k^2\) 的大小，完全不必知道峰的位置，就能一举推出单峰性。

9.2.1　对数凹性蕴含单峰性

设 \(n\) 是一个固定的正整数，并记 \(a_{n,k}\) 为长度为 \(n\)、恰好含 \(k\) 个 2-循环（2-cycle）的对合（involution）的个数。容易算出（参见例 4.36）

\[\tag{9.2}a_{n,k}=\frac{n!}{k!\,(n-2k)!\cdot 2^{k}}.\]
先补上背景：什么是对合，公式 (9.2) 从哪来对合是满足 \(\sigma=\sigma^{-1}\) 的排列；把它写成不相交循环之积，只会出现两种循环：长度为 \(1\) 的不动点和长度为 \(2\) 的对换（即 2-循环）。若有 \(k\) 个 2-循环，则有 \(2k\) 个元素被两两配对、其余 \(n-2k\) 个元素是不动点。
1 2 3 4 5 6 2-循环 (1 2) 2-循环 (3 4) 不动点 5、6
\(n=6,\ k=2\) 的一个对合：\(2k=4\) 个元素配成两对，\(n-2k=2\) 个元素保持不动。
例：推导公式 (9.2) 从 \(n\) 个元素里数出“恰好 \(k\) 个 2-循环”的对合：
  1. 先从 \(n\) 个元素中挑出参与配对的 \(2k\) 个：\(\dbinom{n}{2k}\) 种。
  2. 把这 \(2k\) 个元素两两配成 \(k\) 对（完美匹配）的方法数是 \((2k-1)!!=\dfrac{(2k)!}{k!\,2^{k}}\)。（逐个配：第一个元素有 \(2k-1\) 个搭档，去掉这两个后下一个有 \(2k-3\) 个搭档……）
  3. 相乘并化简：\[a_{n,k}=\binom{n}{2k}\cdot\frac{(2k)!}{k!\,2^{k}}=\frac{n!}{(2k)!\,(n-2k)!}\cdot\frac{(2k)!}{k!\,2^{k}}=\frac{n!}{k!\,(n-2k)!\cdot 2^{k}},\] 正是 (9.2)。♦

对前几个 \(n\)，考察序列 \(a_{n,0},a_{n,1},\cdots,a_{n,\lfloor n/2\rfloor}\)。见图 9.4。

\(n\)\(a_{n,0},\ a_{n,1},\ a_{n,2},\ a_{n,3}\)
11
211
313
4163
511015
61154515
7121105105
图 9.4　序列 \(\{a_{n,k}\}_{0\le k\le \lfloor n/2\rfloor}\)，其中 \(n\le 7\)。

从这些数据看，对每个固定的 \(n\)，序列 \(\{a_{n,k}\}_{0\le k\le\lfloor n/2\rfloor}\) 似乎都是单峰的。然而直接证明这一点似乎很困难——即便我们有 \(a_{n,k}\) 的精确公式，也不清楚峰落在哪里。事实上，对 \(n=4\) 与 \(n=6\)，峰并不在序列末端；而对其余的 \(n\)，峰在末端，不过有时与倒数第二项相等。不知道峰的位置会带来麻烦：没有峰的位置，我们就无法用“序列在到达峰之前递增、之后递减”来证明单峰性。

例：亲眼看看“峰乱跑” 正因峰的位置随 \(n\) 跳来跳去，按“先增后减”的老办法逐个 \(n\) 去找峰非常累。这正是引入对数凹性的动机。

在类似情形下，证明序列的一条更强的性质往往反而更容易。

定义 9.6 若正实数序列 \(d_0,\cdots,d_m\) 对所有 \(k\in[m-1]\) 满足 \[\tag{9.3}d_{k-1}\,d_{k+1}\le d_k^{2},\] 则称它是对数凹（log-concave）的。
读懂 (9.3)：它说的是相邻三项取连续三项 \(d_{k-1},d_k,d_{k+1}\)，要求“两端之积不超过中间项的平方”。等价地（两边同除以 \(d_{k-1}d_k>0\)）就是 \[\frac{d_{k+1}}{d_k}\le\frac{d_k}{d_{k-1}},\] 即相邻两项之比一路不增。这就是对数凹性最好用的形式。

“对数凹”这个术语很容易解释。如果一个序列是对数凹的，那么它各项取对数后得到的序列（取任一固定底数）是凹的（concave）。事实上，把 (9.3) 两边取某个固定底数的对数再除以 \(2\)，对所有 \(k\in[m-1]\) 得到

\[\frac{\log d_{k-1}+\log d_{k+1}}{2}\le \log d_k.\]

也就是说，序列 \(\log d_k\) 的图象是凹的；换言之，\(\log d_k\) 落在连接 \(\log d_{k-1}\) 与 \(\log d_{k+1}\) 的直线上方。见图 9.5 的图示。

\(\log d_k\) 两邻居均值 \(\log d_{k-1}\) \(\log d_{k+1}\)
图 9.5　一个凹序列。每一项都大于它两个邻居的平均值：中间实心点（\(\log d_k\)）高于连接两邻居的虚线弦上的点（两邻居均值）。

对数凹性最关键的性质由下面的命题给出。

命题 9.7 若一个正实数序列是对数凹的，则它是单峰的。
证明. 一方面，序列 \(d_0,d_1,\cdots,d_m\) 是单峰的，当且仅当：一旦比值 \(d_{k+1}/d_k\) 降到 \(1\) 以下，它就一直保持在 \(1\) 以下。另一方面，序列 \(d_0,d_1,\cdots,d_m\) 是对数凹的，当且仅当序列 \(d_{k+1}/d_k\) 单调递减（把 (9.3) 两边同除以 \(d_kd_{k+1}\) 即可看出这一点）。由于第二个条件更强，命题得证。♦
把证明拆成最小的步子
  1. 记比值 \(r_k=\dfrac{d_{k+1}}{d_k}\)。序列各项都为正，所以 \(r_k>0\)，并且 \(d_{k+1}\) 与 \(d_k\) 谁大谁小完全由 \(r_k\) 与 \(1\) 的大小决定：\(r_k\ge 1\) 表示这一步“涨”，\(r_k<1\) 表示“跌”。
  2. 单峰的意思是“先涨后跌、跌了不再涨”，也就是：一旦某个 \(r_k<1\)，之后所有的 \(r\) 都 \(<1\)。
  3. 把 (9.3) 两边除以 \(d_kd_{k+1}>0\)：\(\dfrac{d_{k-1}}{d_k}\le\dfrac{d_{k}}{d_{k+1}}\)，两边取倒数（同为正数，不等号翻向）即 \(\dfrac{d_k}{d_{k-1}}\ge\dfrac{d_{k+1}}{d_k}\)，也就是 \(r_k\le r_{k-1}\)，所以对数凹 \(\Longleftrightarrow\) \(r_k\) 单调递减。
  4. 若 \(r_k\) 一路递减，那么它一旦跌破 \(1\)，后面的值只会更小，当然继续 \(<1\)。这恰好就是第 2 步要的单峰条件。所以“递减”比“跌破后不再涨”更强，能直接推出单峰。♦

由上面的证明可知，对数凹性是比单峰性严格更强的性质。事实上，序列 \(1,1,2\) 是单峰的，但不是对数凹的。

例：\(1,1,2\) 单峰却不对数凹 取 \(d_0=1,d_1=1,d_2=2\)。 所以“对数凹 \(\Rightarrow\) 单峰”成立，但反过来不成立——它确实更强。

让我们用刚学到的知识，来证明序列 \(\{a_{n,k}\}_k\) 是单峰的。

命题 9.8 设 \(a_{n,k}\) 如上定义。则对任意固定的 \(n\)，序列 \(a_{n,0},a_{n,1},\cdots,a_{n,\lfloor n/2\rfloor}\) 是对数凹的，因而是单峰的。
证明. 利用公式 (9.2)，记 \(b_{k}=\dfrac{a_{n,k}}{a_{n,k-1}}\)，得 \[b_{k+1}=\frac{a_{n,k+1}}{a_{n,k}}=\frac{\dfrac{n!}{(k+1)!\,(n-2k-2)!\,2^{k+1}}}{\dfrac{n!}{k!\,(n-2k)!\cdot 2^{k}}}=\frac{(n-2k)(n-2k-1)}{2(k+1)},\] 以及 \[b_{k}=\frac{a_{n,k}}{a_{n,k-1}}=\frac{\dfrac{n!}{k!\,(n-2k)!\,2^{k}}}{\dfrac{n!}{(k-1)!\,(n-2k+2)!\cdot 2^{k-1}}}=\frac{(n-2k+1)(n-2k+2)}{2k}.\] 因此，比较前面两式，得 \[\frac{b_{k+1}}{b_k}=\frac{n-2k}{n-2k+1}\cdot\frac{n-2k-1}{n-2k+2}\cdot\frac{k}{k+1}<1,\] 因为中间三个因子各自都小于 \(1\)。 所以比值 \(\dfrac{a_{n,k+1}}{a_{n,k}}\) 单调递减，这等价于序列 \(a_{n,k}\) 的对数凹性。♦
为什么三个因子都 \(<1\)这里 \(k\ge 1\) 且 \(2k\le n\)，所以 \(n-2k\ge 0\)。逐个看：
  1. \(\dfrac{n-2k}{n-2k+1}\)：分子比分母少 \(1\)，且分母为正，所以 \(<1\)。
  2. \(\dfrac{n-2k-1}{n-2k+2}\)：分子比分母少 \(3\)，所以 \(<1\)。
  3. \(\dfrac{k}{k+1}\)：分子比分母少 \(1\)，所以 \(<1\)。
三个小于 \(1\) 的正数相乘，结果仍 \(<1\)。于是 \(b_{k+1}
例：拿 \(n=6\) 的真实数字验一遍 序列为 \(a_{6,0},a_{6,1},a_{6,2},a_{6,3}=1,15,45,15\)。
  1. 相邻比值 \(b_1=\dfrac{15}{1}=15,\quad b_2=\dfrac{45}{15}=3,\quad b_3=\dfrac{15}{45}=\dfrac13\)。比值 \(15>3>\tfrac13\) 确实单调递减——对数凹。
  2. 逐条验 (9.3)：\(k=1\)：\(a_0a_2=1\cdot45=45\le a_1^2=225\)；\(k=2\)：\(a_1a_3=15\cdot15=225\le a_2^2=2025\)。都成立。
  3. 由命题 9.7，对数凹立刻给出单峰：比值在 \(b_3=\tfrac13<1\) 处跌破 \(1\)，之后不会再涨，所以序列先升 \((1\to15\to45)\) 后降 \((45\to15)\)，峰在 \(k=2\)。♦
k=0k=1k=2k=3 1154515
\(n=6\) 的序列 \(1,15,45,15\)：先升后降，峰在 \(k=2\)。对数凹性保证了这种单峰形状，而我们事先并不需要知道峰在 \(k=2\)。

我们要再次指出：在这个对数凹性的证明中，我们无需知道序列的峰落在哪里。

本节总结
  1. 对数凹：相邻三项满足 \(d_{k-1}d_{k+1}\le d_k^2\)，等价于比值 \(d_{k+1}/d_k\) 单调递减，也等价于 \(\log d_k\) 的图象是凹的。
  2. 命题 9.7：对数凹 \(\Rightarrow\) 单峰；反之不成立（\(1,1,2\) 是反例），所以对数凹是更强的性质。
  3. 方法上的好处：证对数凹只要比较相邻项，不必定位峰；这正是它在 \(\{a_{n,k}\}\)（命题 9.8）这种“峰位置随 \(n\) 漂移”的序列上比单峰性更好用的原因。

返回 全书目录