Bóna · 枚举与解析组合学导论 · 第 9 章 组合学中的序列
9.3 实根性质The real zeros property
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
序列还有一条相关的性质，它比对数凹性（log-concavity）更强。我们称正实数序列 \(a_0,a_1,\cdots,a_n\) 只有实根（has real zeros only），当且仅当多项式 \(\sum_{k=0}^{n}a_kx^k\) 只有实数根。注意，在这种情形下，这些根不可能是正数，因为当 \(x>0\) 时，\(\sum_{k=0}^{n}a_kx^k>0\)。
本节目标把一个正实数序列“放进多项式的系数里”，再研究这个多项式的根。我们要证明：如果这个多项式的根全是实数，那么这个序列一定是对数凹的。也就是说，“只有实根”是判断对数凹性的一把更锋利的钥匙。本节给出定义、用罗尔定理（Rolle's theorem）搭好工具、完成证明，最后用第一类无符号斯特林数（signless Stirling numbers of the first kind）展示它的威力。
定义（只有实根）设 \(a_0,a_1,\cdots,a_n\) 是正实数。若多项式
\[p(x)=\sum_{k=0}^{n}a_kx^k\]
的所有根都是实数，则称序列 \(a_0,a_1,\cdots,a_n\) 只有实根。
为什么这些根一定不是正数？把它拆成一句话的推演：
- 所有系数 \(a_k\) 都是正数。
- 取任意 \(x>0\)，则每一项 \(a_kx^k\) 都 \(>0\)。
- 正数相加仍为正，故 \(p(x)>0\)，它不可能等于 \(0\)。
- 所以 \(p\) 在 \(x>0\) 处没有根；既然根全是实数，它们就只能落在 \(x\le 0\) 这一侧（实际上是 \(x<0\)，因为 \(p(0)=a_0>0\)）。
例 9.21 对任意固定的正整数 \(n\)，二项式系数序列 \(\binom{n}{0},\binom{n}{1},\cdots,\binom{n}{n}\) 只有实根。
读者将在补充习题 5 中被要求证明这个简单的命题。
把例 9.21 算给你看 把二项式系数装进多项式，正是二项式定理：
\[\sum_{k=0}^{n}\binom{n}{k}x^k=(1+x)^n.\]
方程 \((1+x)^n=0\) 的根是 \(x=-1\)，且重数（multiplicity）为 \(n\)。这 \(n\) 个根全是实数（都等于 \(-1\)），所以序列 \(\binom{n}{0},\cdots,\binom{n}{n}\) 只有实根。
具体取 \(n=4\)：序列是 \(1,4,6,4,1\)，多项式 \((1+x)^4\) 的根是四重根 \(-1\)，确实全部为实数。
下面这条定理正是我们在本章讨论实根性质的原因，但它并非实根性质唯一有趣的推论。其他有趣的推论将在“注记”（Notes）一节中提及。
定理 9.22 若一个正实数序列只有实根，则它是对数凹的。
注意，其逆命题不成立。序列 \(1,1,1\) 就是一个反例。
为什么 1,1,1 是逆命题的反例
- 序列 \(1,1,1\) 是否对数凹？对数凹要求 \(a_1^2\ge a_0a_2\)，即 \(1^2\ge 1\cdot 1\)，成立。所以它是对数凹的。
- 它是否只有实根？对应多项式是 \(1+x+x^2\)，判别式 \(\Delta=1^2-4\cdot1\cdot1=-3<0\)，根为复数。所以它不只有实根。
- 于是“对数凹”不能推出“只有实根”，逆命题被这个例子推翻。
为证明定理 9.22，我们需要下面这条来自实分析的经典结果。
定理 9.23（罗尔定理，Rolle's theorem） 设 \(f:\mathbb{R}\to\mathbb{R}\) 是一个在闭区间 \([a,b]\) 上连续、在开区间 \((a,b)\) 上可导的函数。再假设 \(f(a)=f(b)=y\)。则存在一点 \(t\in[a,b]\)，使得 \(f'(t)=0\)。
证明. 由于 \(f\) 在闭的有限区间 \([a,b]\) 上连续，从而 \(f\) 在此区间 \([a,b]\) 上取到最大值与最小值。若这两个值都等于 \(y\)，则 \(f\) 在 \([a,b]\) 上是常数，于是对所有 \(x\in(a,b)\) 都有 \(f'(x)=0\)。
若 \(f\) 在 \([a,b]\) 上的最小值或最大值 \(c\) 不等于 \(y\)，则不妨设 \(c\) 是最大值，且 \(f(t)=c\)，其中 \(t\in(a,b)\)。此时 \(f'(t)=0\)，因为 \(f\) 在 \(t\) 处取到最大值。♦
若 \(f\) 在 \([a,b]\) 上的最小值或最大值 \(c\) 不等于 \(y\)，则不妨设 \(c\) 是最大值，且 \(f(t)=c\)，其中 \(t\in(a,b)\)。此时 \(f'(t)=0\)，因为 \(f\) 在 \(t\) 处取到最大值。♦
下面这个特例，是组合应用中最常用的形式。
推论 9.24 若实系数多项式 \(r(x)\) 只有实根，则它的导数 \(r'(x)\) 也只有实根。
证明. 为简单起见，先假设 \(r\) 的 \(n\) 个根两两不同。那么，对 \(y=0\) 应用罗尔定理：在 \(r\) 的任意两个相邻的根之间，多项式 \(r'\) 必有一个根。这样就给出了 \(n-1\) 个实根，因此 \(r'\) 的全部 \(n-1\) 个根都是实数。参见图 9.8 的图示。
现在再假设 \(r\) 也有一些重根。设 \(a_1,a_2,\cdots,a_k\) 是 \(r\) 的 \(k\) 个不同根的重数，且 \(\sum_{i=1}^{k}a_i=n\)。由乘积的求导法则可知：若 \(r_i\) 是 \(r\) 的一个重数为 \(a_i\) 的根，则 \(r_i\) 是 \(r'\) 的一个重数为 \(a_i-1\) 的根。因此，\(r\) 的这些根 \(r_i\) 总共给出 \(r'\) 的 \(\sum_{i=1}^{k}(a_i-1)=n-k\) 个实根。然后，对 \(r\) 的每一对相邻的不同根应用罗尔定理，又得到额外的 \(k-1\) 个实根。这就完成了证明。♦
现在再假设 \(r\) 也有一些重根。设 \(a_1,a_2,\cdots,a_k\) 是 \(r\) 的 \(k\) 个不同根的重数，且 \(\sum_{i=1}^{k}a_i=n\)。由乘积的求导法则可知：若 \(r_i\) 是 \(r\) 的一个重数为 \(a_i\) 的根，则 \(r_i\) 是 \(r'\) 的一个重数为 \(a_i-1\) 的根。因此，\(r\) 的这些根 \(r_i\) 总共给出 \(r'\) 的 \(\sum_{i=1}^{k}(a_i-1)=n-k\) 个实根。然后，对 \(r\) 的每一对相邻的不同根应用罗尔定理，又得到额外的 \(k-1\) 个实根。这就完成了证明。♦
把推论 9.24 的计数对上
- 有重根时，重根贡献：每个重数 \(a_i\) 的根，在求导后变成重数 \(a_i-1\) 的根，共贡献 \(\sum(a_i-1)=n-k\) 个根。
- 相邻不同根之间的“罗尔根”：\(k\) 个不同根之间有 \(k-1\) 个间隔，每个间隔由罗尔定理产生 \(1\) 个根，共 \(k-1\) 个。
- 两类相加：\((n-k)+(k-1)=n-1\)。而 \(r'\) 的次数恰为 \(n-1\)，根数也恰为 \(n-1\)，于是 \(r'\) 的根全部被实数“占满”，即 \(r'\) 只有实根。
现在我们可以证明定理 9.22 了。
证明（定理 9.22）. 设 \(p(x)=\sum_{i=0}^{n}a_ix^i\) 是一个只有实根的实系数多项式。考虑二元多项式
\[q(x,y)=\sum_{i=0}^{n}a_ix^iy^{n-i}=p(x/y)\,y^n.\]
那么 \(q\) 可能有含复数的根 \((x,y)\)，但即便在这些根处，比值 \(x/y\) 也必须是实数。事实上，上面的分解表明：若 \(q(x,y)=0\) 且 \(x\) 或 \(y\) 不是实数，则必有 \(p(x/y)=0\)，这迫使 \(x\) 与 \(y\) 之比为实数。
现在，对任意固定的实数 \(x\)，我们把函数 \(q(x,y)\) 看作 \(y\) 的函数。这个函数只有实根。因此，若对它关于 \(y\) 求导，由推论 9.24，所得函数也只有实根。这进而意味着：对 \(\partial q/\partial y\) 的任意根 \((x,y)\)，比值 \(x/y\) 都必须是实数。把 \(y\) 换成 \(x\)，同样的论证也成立。反复迭代这个论证可知：只要偏导数 \(\partial^{a+b}q/\partial x^a\partial y^b\) 不恒为零（即只要 \(a+b\le n-1\)），它也只有实根。
由于我们要证明的是 \(a_j^2\ge a_{j-1}a_{j+1}\)，即一个涉及三个参数的不等式，因此从 \(q(x,y)\) 出发去寻找二次多项式是合理的。这样的多项式可以通过把 \(q\) 求导共 \(n-2\) 次得到。于是令 \(a=j-1\)，令 \(b=(n-2)-(j-1)=n-j-1\)，并考虑 \[T(x,y)=\frac{\partial^{a+b}q}{\partial x^a\partial y^b}=\frac{\partial^{n-2}q}{\partial x^{j-1}\partial y^{n-j-1}}.\] “好吧，”读者此刻或许会说，“可是关于这么复杂的偏导数，我们又能说出什么呢？”幸运的是，能说的相当多。注意 \(\partial x^m/\partial x^{j-1}=0\)，除非 \(m\ge j-1\)；并且 \(\partial y^s/\partial y^{n-j-1}=0\)，除非 \(s\ge n-j-1\)。所以 \(T(x,y)\) 中不消失的项，只来自 \(q(x,y)\) 中那些 \(i\in[j-1,j+1]\) 的项。这导出 \[T(x,y)=\frac{(j-1)!}{2}a_{j-1}(n-j+1)!\,y^2+a_jj!(n-j)!\,xy+\frac{(j+1)!}{2}a_{j+1}(n-j-1)!\,x^2.\] 我们已经看到，\(T(x,y)\) 作为 \(q(x,y)\) 的偏导数，只有实根——意思是：在该方程的任意根 \((x,y)\) 处，比值 \(x/y\) 必须是实数。另一方面，\(T(x,y)/y^2\) 也是关于 \(x/y\) 的二次多项式；因此，“它只有实根”这件事等价于“它的判别式非负”，即 \[\big[a_jj!(n-j)!\big]^2-a_{j-1}a_{j+1}(n-j+1)!(n-j-1)!(j-1)!(j+1)!\ge 0,\] \[\tag{9.4}a_j^2\ge a_{j-1}a_{j+1}\cdot\frac{n-j+1}{n-j}\cdot\frac{j+1}{j},\] 这甚至比要证明的不等式 \(a_j^2\ge a_{j-1}a_{j+1}\) 更强。♦
现在，对任意固定的实数 \(x\)，我们把函数 \(q(x,y)\) 看作 \(y\) 的函数。这个函数只有实根。因此，若对它关于 \(y\) 求导，由推论 9.24，所得函数也只有实根。这进而意味着：对 \(\partial q/\partial y\) 的任意根 \((x,y)\)，比值 \(x/y\) 都必须是实数。把 \(y\) 换成 \(x\)，同样的论证也成立。反复迭代这个论证可知：只要偏导数 \(\partial^{a+b}q/\partial x^a\partial y^b\) 不恒为零（即只要 \(a+b\le n-1\)），它也只有实根。
由于我们要证明的是 \(a_j^2\ge a_{j-1}a_{j+1}\)，即一个涉及三个参数的不等式，因此从 \(q(x,y)\) 出发去寻找二次多项式是合理的。这样的多项式可以通过把 \(q\) 求导共 \(n-2\) 次得到。于是令 \(a=j-1\)，令 \(b=(n-2)-(j-1)=n-j-1\)，并考虑 \[T(x,y)=\frac{\partial^{a+b}q}{\partial x^a\partial y^b}=\frac{\partial^{n-2}q}{\partial x^{j-1}\partial y^{n-j-1}}.\] “好吧，”读者此刻或许会说，“可是关于这么复杂的偏导数，我们又能说出什么呢？”幸运的是，能说的相当多。注意 \(\partial x^m/\partial x^{j-1}=0\)，除非 \(m\ge j-1\)；并且 \(\partial y^s/\partial y^{n-j-1}=0\)，除非 \(s\ge n-j-1\)。所以 \(T(x,y)\) 中不消失的项，只来自 \(q(x,y)\) 中那些 \(i\in[j-1,j+1]\) 的项。这导出 \[T(x,y)=\frac{(j-1)!}{2}a_{j-1}(n-j+1)!\,y^2+a_jj!(n-j)!\,xy+\frac{(j+1)!}{2}a_{j+1}(n-j-1)!\,x^2.\] 我们已经看到，\(T(x,y)\) 作为 \(q(x,y)\) 的偏导数，只有实根——意思是：在该方程的任意根 \((x,y)\) 处，比值 \(x/y\) 必须是实数。另一方面，\(T(x,y)/y^2\) 也是关于 \(x/y\) 的二次多项式；因此，“它只有实根”这件事等价于“它的判别式非负”，即 \[\big[a_jj!(n-j)!\big]^2-a_{j-1}a_{j+1}(n-j+1)!(n-j-1)!(j-1)!(j+1)!\ge 0,\] \[\tag{9.4}a_j^2\ge a_{j-1}a_{j+1}\cdot\frac{n-j+1}{n-j}\cdot\frac{j+1}{j},\] 这甚至比要证明的不等式 \(a_j^2\ge a_{j-1}a_{j+1}\) 更强。♦
把这条证明拆成主线
- 齐次化：把一元多项式 \(p(x)\) 升级成二元齐次多项式 \(q(x,y)=p(x/y)y^n\)。这样“只有实根”被翻译成“每个根的比值 \(x/y\) 都是实数”，更便于反复求导。
- 降次：对 \(q\) 一共求导 \(n-2\) 次（关于 \(x\) 求 \(j-1\) 次、关于 \(y\) 求 \(n-j-1\) 次），把它降成一个二次多项式 \(T(x,y)\)。由推论 9.24，求导不破坏“只有实根”。
- 筛项：求导会把次数太低的项变成 \(0\)，所以 \(T\) 中只剩下原来 \(q\) 里 \(i=j-1,j,j+1\) 这三项——正好对应我们关心的三个系数 \(a_{j-1},a_j,a_{j+1}\)。
- 判别式：把 \(T\) 看成关于 \(t=x/y\) 的二次式。一元二次式“只有实根” \(\iff\) 判别式 \(\ge 0\)。写出判别式条件并化简阶乘，就得到 (9.4)。
- 收尾：(9.4) 右边的两个因子 \(\frac{n-j+1}{n-j}\ge 1\) 与 \(\frac{j+1}{j}\ge 1\) 都不小于 \(1\)，所以 \(a_j^2\ge a_{j-1}a_{j+1}\cdot(\ge 1)\ge a_{j-1}a_{j+1}\)，对数凹性成立，而且结论比原目标更强。
阶乘是怎么消成 (9.4) 的把判别式
\[\big[a_jj!(n-j)!\big]^2\ge a_{j-1}a_{j+1}\,(j-1)!(j+1)!\,(n-j-1)!(n-j+1)!\]
两边同时除以 \(\big[j!(n-j)!\big]^2\)。利用
\[\frac{(j-1)!(j+1)!}{(j!)^2}=\frac{j+1}{j},\qquad \frac{(n-j-1)!(n-j+1)!}{\big((n-j)!\big)^2}=\frac{n-j+1}{n-j},\]
（例如 \((j+1)!=(j+1)\,j!\)、\(j!=j\,(j-1)!\)，相乘即得 \(\tfrac{j+1}{j}\)），立即得到 (9.4)。
下面的例子展示了定理 9.22 的威力。
例 9.25 对所有正整数 \(n\)，第一类无符号斯特林数序列 \(\{c(n,k)\}_{1\le k\le n}\) 只有实根，因此是对数凹的。
解. 我们在定理 4.21 中已经看到
\[\sum_{k=1}^{n}c(n,k)x^k=(x+n-1)(x+n-2)\cdots(x+1)x.\]
因此，该序列（对应多项式）的根是 \(0,-1,\cdots,-n+1\)。♦
把例 9.25 算给你看（n = 4） 第一类无符号斯特林数 \(c(4,k)\) 满足
\[\sum_{k=1}^{4}c(4,k)x^k=x(x+1)(x+2)(x+3).\]
- 把右边展开：\(x(x+1)(x+2)(x+3)=6x+11x^2+6x^3+x^4\)。
- 读出系数：\(c(4,1)=6,\ c(4,2)=11,\ c(4,3)=6,\ c(4,4)=1\)。
- 根一目了然，就是让每个因子为零的点：\(0,-1,-2,-3\)，全是实数。
- 用对数凹验证（取 \(j=2\)）：\(c(4,2)^2=11^2=121\)，而 \(c(4,1)\,c(4,3)=6\cdot 6=36\)，确有 \(121\ge 36\)。对数凹成立。
因此，借助定理 9.22，我们可以毫不费力地证明序列 \(\{c(n,k)\}_{1\le k\le n}\) 的对数凹性。若没有定理 9.22，要证明那个对数凹性结果会困难得多。不过，为一个组合事实找到一个纯组合的证明，总是有趣的。这样一个证明——即序列 \(\{c(n,k)\}_{1\le k\le n}\) 对数凹性的一个单射证明（injective proof）——由 Bruce Sagan 在文献 [64] 中给出。在同一篇论文中，Sagan 还给出了序列 \(\{S(n,k)\}_{1\le k\le n}\) 对数凹的组合证明。这个序列也已知只有实根，但那个事实的证明并不简单。
虽然许多自然定义的组合序列——例如二项式系数序列、斯特林数（Stirling numbers）序列和欧拉数（Eulerian numbers）序列——都已知只有实根，但这一领域里仍有一些引人入胜的猜想。感兴趣的读者可查阅文献 [20]。也鼓励读者阅读接下来的“注记”，以了解实根性质的更多应用。
即时自测
- 设 \(n\) 为固定的正整数，令 \(a_k=\binom{n}{k}2^k\)。证明序列 \(\{a_k\}_{0\le k\le n}\) 是对数凹的。
提示（按本节方法）：把它装进多项式 \(\sum_{k=0}^{n}\binom{n}{k}2^kx^k=\sum_{k=0}^{n}\binom{n}{k}(2x)^k=(1+2x)^n\)。它的根是 \(x=-\tfrac12\)，重数为 \(n\)，全是实数；由定理 9.22，序列只有实根，故对数凹。
返回 全书目录