7.7　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为原书解答的忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步补全原书省略的步骤、配具体数字与图，不用比喻。

第 1 题

这是因为 \[\frac{P(x)}{Q(x)}=A(x)+\frac{R(x)}{Q(x)},\] 所以这两个有理函数（rational function）只相差一个多项式，也就是说，它们 \(x^n\) 的系数只在有限多个指数 \(n\) 上不同。

1. 这道题问的是：两个有理函数若只差一个多项式，它们系数序列的指数增长率是否相同。
2. 对分式 \(P(x)/Q(x)\) 做多项式带余除法：当分子次数可能不低于分母时，可把它写成“商多项式 \(A(x)\) 加上一个真分式 \(R(x)/Q(x)\)”（其中 \(\deg R<\deg Q\)）。这正是上式。
3. 多项式 \(A(x)\) 只有有限多个非零项，所以它只影响有限多个 \(x^n\) 的系数。
4. 因此当 \(n\) 充分大时，\(P(x)/Q(x)\) 与 \(R(x)/Q(x)\) 的第 \(n\) 个系数完全相等。指数增长率只看“\(n\) 很大时”的行为，故两者增长率必然一致。

第 2 题

假设 \(z\) 不是正实数，且 \(z^k+z^{\ell}=1\)。那么由三角不等式（triangle inequality）有 \(|z|^k+|z|^{\ell}>1\)。考虑定义在正实数上的递增函数 \(f(t)=t^k+t^{\ell}\)。因为 \(f(|z|)>1\) 而 \(f(0)=0\)，由 \(f\) 的连续性可知，存在某个 \(t\in(0,|z|)\) 使得 \(f(t)=1\)。

三角不等式是严格的，除非 \(z^k\) 与 \(z^{\ell}\) 是指向同一方向的向量，也就是除非 \(z^{k-\ell}\) 是正实数。然而，由 \(1=z^k+z^{\ell}=(1+z^{k-\ell})z^{\ell}\) 可知，那将意味着 \(z^{\ell}\) 也是正实数。这表明 \(\ell\) 与 \(k-\ell\) 都是 \(2\pi/\operatorname{Arg}(z)\) 的倍数，矛盾。

1. 目标：证明方程 \(z^k+z^\ell=1\)（\(k>\ell\)）的最小模根是正实数。思路是反证：假设最小模根 \(z\) 不是正实数，导出矛盾。
2. 复数的三角不等式：对任意复数 \(a,b\)，\(|a+b|\le|a|+|b|\)，且等号成立当且仅当 \(a,b\) 同向（即 \(a/b\) 为正实数）。
3. 把它用到 \(1=z^k+z^\ell\)：取模得 \(1=|z^k+z^\ell|\le|z|^k+|z|^\ell\)。若等号不成立，则 \(|z|^k+|z|^\ell>1\)。
4. 令 \(f(t)=t^k+t^\ell\)（\(t>0\)）。它严格递增，且 \(f(0)=0<1介值定理（连续函数取遍中间值），存在 \(t_0\in(0,|z|)\) 使 \(f(t_0)=1\)。这个 \(t_0\) 是正实数根，且模 \(t_0<|z|\)，与“\(z\) 是最小模根”矛盾。
5. 剩下要排除“等号成立”的情形：等号成立要求 \(z^k\) 与 \(z^\ell\) 同向，即 \(z^{k-\ell}\) 为正实数。代入 \(1=(1+z^{k-\ell})z^\ell\)，左边为正实数、\(1+z^{k-\ell}\) 为正实数，故 \(z^\ell\) 也是正实数。于是 \(z^\ell\) 和 \(z^{k-\ell}\) 都是正实数，意味着 \(z\) 的辐角 \(\operatorname{Arg}(z)\) 乘以 \(\ell\)、乘以 \(k-\ell\) 都是 \(2\pi\) 的整数倍。结合 \(z\) 非正实数（辐角非零）可推出矛盾。

第 3 题

只需证明：对所有正实数 \(x\)，不等式 \(x^4+x>x^3+x^2\) 成立。该不等式成立，是因为它等价于 \[\begin{aligned}x^4+x-x^3-x^2&>0,\\ (x+1)\,x\,(x-1)^2&>0,\end{aligned}\] 而后者对所有正实数 \(x\) 显然成立。现在，由上一题我们知道 \(Q_a(x)\) 与 \(Q_b(x)\) 的最小模根都是正实数。设 \(r_0\) 为 \(Q_a(x)\) 的该根，\(r_1\) 为 \(Q_b(x)\) 的该根。那么 \(r_0+r_0^4=1\)，由刚证的不等式可得 \(r_1^2+r_1^3<1\)。由于 \(f(x)=x^2+x^3\) 对正的 \(x\) 显然递增，命题得证。

1. 先验证因式分解 \(x^4-x^3-x^2+x=(x+1)x(x-1)^2\)。提公因式 \(x\)：\(x(x^3-x^2-x+1)\)；对括号分组 \(x^2(x-1)-(x-1)=(x-1)(x^2-1)=(x-1)(x-1)(x+1)=(x+1)(x-1)^2\)。乘回 \(x\) 即得。
2. 对正实数 \(x\)：\(x>0,\ x+1>0,\ (x-1)^2\ge0\)，且当 \(x\ne1\) 时 \((x-1)^2>0\)，故乘积 \(>0\)。于是 \(x^4+x>x^3+x^2\)（在 \(x=1\) 处取等，但这里关心的根 \(r_0,r_1\ne1\)）。
3. 设 \(r_0\) 满足 \(r_0+r_0^4=1\)（即 \(r_0^4+r_0=1\)），\(r_1\) 是另一方程的最小模正实根。利用刚证的 \(r^4+r>r^3+r^2\)，结合两方程的关系，可推出 \(r_1^2+r_1^3<1\)。
4. 因 \(g(x)=x^2+x^3\) 在正轴递增：由 \(r_1^2+r_1^3<1=r\,(\cdots)\) 比较得到两根大小关系，从而得出两序列指数增长率的大小关系。

第 4 题

我们使用指数型生成函数（exponential generating function, EGF）的复合公式（compositional formula），取 \(A(x)=e^x-1\)，\(B(x)=1/(1-x)\)。事实上，我们把 \([n]\) 划分为 \(k\) 个块（block），除了保证它们非空之外，对这些块不施加别的任务。然后把这些块的集合线性排序，把第一个块的元素映到 \(1\)、第二个块的元素映到 \(2\)，以此类推。把 \(k\) 个块线性排序有 \(k!\) 种方式，所以 \(b_k=k!\)，于是 \[B(x)=\sum_{k\ge0}k!\cdot\frac{x^k}{k!}=\frac{1}{1-x}.\] 因此复合公式给出 \[H(x)=B(A(x))=\frac{1}{1-A(x)}=\frac{1}{1-(e^x-1)}=\frac{1}{2-e^x}.\] 函数 \(e^x\) 是整函数（entire function，处处解析）；因此 \(H(x)\) 出现奇点的唯一途径是 \(e^x=2\)。满足 \(e^x=2\) 的复数 \(x\) 有无穷多个，但模最小的是实数 \(\ln 2\)。因此数 \(h_n\) 的指数阶为 \(1/\ln 2\approx 1.4427\)。注意这些数 \(h_n\) 称为满射数（surjection numbers）。

1. 复合公式：若结构由“先把 \([n]\) 分成若干非空块、每块内放结构 \(A\)、再对块整体放结构 \(B\)”得到，则总 EGF 为 \(H(x)=B(A(x))\)。这里“块非空、块内无额外结构”对应 \(A(x)=\sum_{n\ge1}\frac{x^n}{n!}=e^x-1\)。
2. 外层结构是“把 \(k\) 个块线性排成一列”，方式数 \(b_k=k!\)，其 EGF \(B(x)=\sum_{k\ge0}k!\frac{x^k}{k!}=\sum_{k\ge0}x^k=\frac1{1-x}\)（几何级数）。
3. 代入：\(H(x)=\dfrac{1}{1-(e^x-1)}=\dfrac{1}{2-e^x}\)。
4. 找最近奇点：分母为零即 \(e^x=2\Rightarrow x=\ln2+2\pi i\,m\)。模最小的是 \(x=\ln2\approx0.693\)。增长率 \(=1/\ln2\approx1.4427\)。

第 5 题

由于 \([n]\) 上的双射（bijection）个数为 \(n!\)，比值 \(h_n/n!\) 就是 \([n]\) 上所有满射（映到任意 \([k]\)）的个数与 \([n]\) 上双射个数之比。上一题的结果说明：当 \(n\) 很大时，满射的个数约为双射个数的 \(1.4427^n\) 倍。

1. \([n]\) 到自身的双射就是排列，共 \(n!\) 个。满射总数为 \(h_n\)。
2. 第 4 题给出 \(h_n\) 的指数阶约为 \(1.4427^n\)（更精确地 \(h_n\sim \dfrac{n!}{2(\ln2)^{n+1}}\)）。
3. 所以 \(\dfrac{h_n}{n!}\sim\dfrac{1}{2\ln2}\Big(\dfrac{1}{\ln2}\Big)^n\)，即满射与双射的数量比按 \(1.4427^n\) 增长。

第 6 题

我们在 5.5.2.2 节看到 \(T(x)=\sum_{n\ge0}T_n\dfrac{x^n}{n!}=\sec x+\tan x\)。由于 \(\sec x\) 与 \(\tan x\) 的最小模奇点都在距 \(0\) 为 \(\pi/2\) 处，故序列 \(T_n/n!\) 的指数增长率为 \(2/\pi\)。

1. \(T_n\) 是 \([n]\) 上交错排列（alternating permutation）的个数，其 EGF 是 \(\sec x+\tan x\)。
2. \(\sec x=1/\cos x\) 与 \(\tan x=\sin x/\cos x\) 都在 \(\cos x=0\) 处爆掉，离 \(0\) 最近的是 \(x=\pi/2\approx1.5708\)。
3. 增长率 \(=1/(\pi/2)=2/\pi\approx0.6366\)（即 \(T_n/n!\) 随 \(n\) 按 \((2/\pi)^n\) 衰减）。

第 7 题

(a) 考虑定理 2.10 证明的递推关系。两边同乘 \(x^n\)，再对所有 \(n\ge k\) 求和，得 \(F_k(x)=xF_{k-1}(x)+kxF_k(x)\)，这与我们的断言等价。

(b) 注意 \(F_1(x)=x/(1-x)\)。于是 (a) 中证得的递推加上对 \(k\) 的归纳，导出显式公式 \[F_k(x)=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}.\] 所以 \(F_k(x)\) 的最小模奇点在 \(x_0=1/k\)，这证明了其系数序列的指数增长率为 \(k\)。

1. (a) 第二类 Stirling 数递推 \(S(n,k)=S(n-1,k-1)+k\,S(n-1,k)\)。设 \(F_k(x)=\sum_n S(n,k)x^n\)，两边乘 \(x^n\) 求和：\(\sum S(n,k)x^n=x\sum S(n-1,k-1)x^{n-1}+kx\sum S(n-1,k)x^{n-1}\)，即 \(F_k=xF_{k-1}+kxF_k\)。
2. 整理：\(F_k(1-kx)=xF_{k-1}\Rightarrow F_k=\dfrac{x}{1-kx}F_{k-1}\)。
3. (b) 起点 \(F_1=\dfrac{x}{1-x}\)。反复套用：\(F_2=\dfrac{x}{1-2x}\cdot\dfrac{x}{1-x}\)，…，归纳得 \(F_k=\dfrac{x^k}{(1-x)(1-2x)\cdots(1-kx)}\)。
4. 分母因子 \((1-jx)\) 在 \(x=1/j\) 为零，\(j=1,\dots,k\) 中最小的根是 \(x_0=1/k\)。增长率 \(=1/x_0=k\)。

第 8 题

设 \(t(x)\) 为该序列的生成函数。删去这种树的根，得到的要么是空集，要么是一棵这样的树，要么是两棵这样的树构成的有序对。这导出函数方程 \[t(x)=x+x\,t(x)+x\,t(x)^2.\] 这是关于 \(t(x)\) 的二次方程，其解为 \[t_{1,2}(x)=\frac{1-x\pm\sqrt{(x-1)^2-4x^2}}{2x}.\] 我们知道 \(t(0)=0\)，因此需要满足该要求的那个解，即平方根前取负号的那个。这给出 \[t(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x}.\] 所以 \(t(x)\) 的最小模奇点在 \(1/3\)，故序列 \(t_n\) 的指数增长率为 \(3\)。乍看 \(x=0\) 像是 \(t\) 的奇点，但我们已定义 \(t(0)=0\)，这一定义使 \(t\) 在 \(0\) 处解析；这也是唯一能做到这点的定义，因为 \(\lim_{x\to0}t(x)=0\)。注意这些数 \(t_n=M_{n-1}\)，其中 \(M_n\) 是第 3 章习题 23 解答中出现的Motzkin 数（Motzkin numbers）。

术语说明：我们说 \(x=0\) 是函数 \(s(x)=\dfrac{1-x-\sqrt{1-2x-3x^2}}{2x}\) 的可去奇点（removable singularity），因为若恰当定义 \(s\) 在 \(0\) 的值，\(s\) 就在 \(0\) 处解析。一般地，当且仅当 \(s\) 在 \(0\) 的去心邻域内解析、且 \(\lim_{x\to0}s(x)=L\) 存在且有限时，这是可行的；此时令 \(s(0)=L\) 即可使 \(s\) 在 \(0\) 解析。例如 \(s(x)=-\ln(1-x)/x\) 在 \(0\) 有可去奇点，因 \(\lim_{x\to0}s(x)=1\)，故可设 \(s(0)=1\)。

1. 建立方程：一棵非空根可有 0、1 或 2 棵子树（有序）。空树贡献常数项，对应 \(x\)（根本身一个顶点）；一棵子树对应 \(x\,t(x)\)；两棵有序子树对应 \(x\,t(x)^2\)。合起来 \(t=x+xt+xt^2\)。
2. 解二次方程：\(xt^2+(x-1)t+x=0\)。判别式 \(\Delta=(x-1)^2-4x^2=1-2x+x^2-4x^2=1-2x-3x^2\)。故 \(t=\dfrac{(1-x)\pm\sqrt{1-2x-3x^2}}{2x}\)。
3. 选根：要 \(t(0)=0\)。取负号时，分子 \(\to 1-x-\sqrt{1-2x-3x^2}\)，在 \(x\to0\) 分子分母同趋 \(0\)，用洛必达或泰勒展开得极限 \(0\)，符合。取正号则分子 \(\to2\)，\(t\to\infty\)，舍去。
4. 找奇点：根号内 \(1-2x-3x^2=(1-3x)(1+x)\) 变号处 \(x=1/3\) 与 \(x=-1\)。最小模的是 \(x=1/3\)（\(x=0\) 是可去奇点不算）。增长率 \(=1/(1/3)=3\)。

第 9 题

删去这种树的根（当树非空时可这样做），得到一个由两棵这样的树构成的有序对，其中一棵或两棵可以为空。这导出函数方程 \[T(x)-1=x\,T(x)^2.\] 解这个关于 \(T(x)\) 的二次方程，得 \[T(x)=\frac{1\pm\sqrt{1-4x}}{2x}.\] 我们知道 \(T(0)=1\)，因此需要满足该要求的解，即平方根前取负号者。所以 \(T(x)=\dfrac{1-\sqrt{1-4x}}{2x}\)，且 \(T(x)\) 的最小模奇点为 \(1/4\)，故序列 \(T_n\) 的指数增长率为 \(4\)。注意 \(x=0\) 不是奇点，因为我们已定义 \(T(0)=1=\lim_{x\to0}T(x)\)。与上题相同，读者应解释为何 \(x=0\) 不是 \(T\) 的奇点。换言之，\(0\) 是 \(\dfrac{1-\sqrt{1-4x}}{2x}\) 的可去奇点（而非 \(T(x)\) 的奇点）。

由生成函数 \(T(x)\) 的闭形式可知，数 \(T_n\) 是Catalan 数（Catalan numbers）。

1. 根有左右两棵（可空）子树，含常数项（空树记 \(T(0)=1\)），故 \(T-1=xT^2\)，即 \(xT^2-T+1=0\)。
2. 判别式 \(1-4x\)，得 \(T=\dfrac{1\pm\sqrt{1-4x}}{2x}\)。取负号使 \(T(0)=1\)（正号给出 \(T\to\infty\)）。
3. 根号内 \(1-4x=0\Rightarrow x=1/4\) 是最小模奇点。增长率 \(=4\)。
4. 展开 \(T(x)=\sum_n C_n x^n\)，\(C_n=\frac1{n+1}\binom{2n}{n}\) 即 Catalan 数：\(1,1,2,5,14,42,\dots\)，比值趋于 \(4\)。

第 10 题

我们在 5.5.2.1 节证明过 \[B(x)=\frac{1-\sqrt{1-4x}}{2},\] 所以 \(B(x)\) 只有一个奇点，在 \(x=1/4\)。因此序列 \(b_n\) 的指数阶为 \(4\)。注意 \(b_n=c_{n-1}\)，即第 \((n-1)\) 个 Catalan 数。

1. 这里 \(B(x)\) 与第 9 题的 \(T(x)\) 几乎一样，只是分母没有 \(x\)：\(B(x)=\dfrac{1-\sqrt{1-4x}}{2}\)。
2. 唯一奇点来自根号 \(1-4x=0\)，即 \(x=1/4\)。增长率 \(=1/(1/4)=4\)。
3. 系数关系 \(b_n=c_{n-1}\)（Catalan 数平移一位），与第 9 题增长率一致。

第 11 题

我们使用指数型生成函数的复合公式。内函数为 \(\ln(1/(1-x))\)，外函数为 \(1+\ln(1/(1-x))\)。因此得 \[M(x)=1+\ln\!\big(1-\ln(1/(1-x))\big).\] 显然 \(M(x)\) 在 \(x=1\) 有奇点；并且当 \(1=\ln(1-\ln(1/(1-x)))\) 时也有奇点——这在 \(1=\ln(1/(1-x))\) 时发生，即 \(1/(1-x)=e\)，亦即 \(x=1-e^{-1}\)。这第二个奇点比第一个更接近 \(0\)，故序列 \(m_n\) 的指数增长率为 \(1/(1-e^{-1})=1+\dfrac{1}{e-1}\approx 1.582\)。

1. 复合 \(M(x)=B(A(x))\)，内层 \(A(x)=\ln\frac1{1-x}\)，外层 \(B(y)=1+\ln\frac1{1-y}\)。代入即得原书的 \(M(x)=1+\ln\big(1-\ln\frac1{1-x}\big)\)。下面只需找它离 \(0\) 最近的奇点。
2. 奇点一：\(x=1\)（来自内层 \(\ln\frac1{1-x}\)）。
3. 奇点二：外层对数自变量为零，即 \(\ln\frac1{1-x}=1\Rightarrow\frac1{1-x}=e\Rightarrow x=1-e^{-1}\approx0.632\)。
4. 比较 \(0.632<1\)，取更近的 \(x=1-e^{-1}\)。增长率 \(=\dfrac1{1-e^{-1}}\approx1.582\)。

第 12 题

我们将使用指数公式（exponential formula）。在 \(k\) 个顶点上放一个有向圈有 \((k-1)!\) 种方式，故放一个无向圈有 \((k-1)!/2\) 种方式（\(k\ge3\)）。因此 \[A(x)=\sum_{k\ge3}\frac{(k-1)!}{2}\cdot\frac{x^k}{k!}=\sum_{k\ge3}\frac{x^k}{2k}=\frac12\ln\!\Big(\frac{1}{1-x}\Big)-\frac{x}{2}-\frac{x^2}{4}.\] 因此指数公式给出 \[T(x)=\sum_{n\ge0}t_n\frac{x^n}{n!}=\exp(A(x))=\frac{e^{-\frac{x}{2}-\frac{x^2}{4}}}{\sqrt{1-x}}.\] 所以 \(T(x)\) 只有一个奇点，在 \(x=1\)，因此序列 \(t_n/n!\) 的指数增长率为 \(1\)。

1. 指数公式：若一个对象是“若干互不相连的连通块（这里是圈）”的无序并，且单块的 EGF 是 \(A(x)\)，则整体 EGF 为 \(\exp(A(x))\)。
2. 单块（无向圈）计数：\(k\) 个标号点排成有向圈 \((k-1)!\) 种，无向（不分顺逆时针）再除 \(2\)。从 \(k\ge3\) 开始（圈至少 3 点）。
3. 求和：\(\sum_{k\ge3}\frac{(k-1)!}{2}\frac{x^k}{k!}=\frac12\sum_{k\ge3}\frac{x^k}{k}=\frac12\Big(\ln\frac1{1-x}-x-\frac{x^2}{2}\Big)=\frac12\ln\frac1{1-x}-\frac x2-\frac{x^2}{4}\)，用到 \(\sum_{k\ge1}\frac{x^k}{k}=\ln\frac1{1-x}\)。
4. \(\exp(A)=\exp\big(\frac12\ln\frac1{1-x}\big)\cdot e^{-x/2-x^2/4}=\dfrac{e^{-x/2-x^2/4}}{\sqrt{1-x}}\)。
5. \(e^{(\cdots)}\) 处处解析，唯一奇点来自 \(\sqrt{1-x}\)，在 \(x=1\)。增长率 \(=1\)。

第 13 题

这与上一题类似。对 \(n\ge2\)，在 \(n\) 个顶点上放一条无向路径（path）有 \(n!/2\) 种方式，而在一个顶点上放路径只有 \(1\) 种方式。这给出 \[A(x)=x+\frac12\sum_{n\ge2}n!\frac{x^n}{n!}=x+\frac12\frac{1}{1-x}-\frac12-\frac x2=\frac{1}{2(1-x)}+\frac{x-1}{2}.\] 由于 \(A(x)\) 只有一个奇点，在 \(x=1\)，故 \(P(x)=\sum_{n\ge0}p_n x^n=\exp(A(x))\) 也只有此一奇点，因此序列 \(p_n/n!\) 的指数增长率为 \(1\)。

1. 单块是无向路径。\(n\ge2\) 时 \(n!\) 个排列两两端点对称重复，故 \(n!/2\) 条；\(n=1\) 时单点 \(1\) 条（这就是为什么要把 \(n=1\) 项单独写成 \(x\)）。
2. 求 \(\frac12\sum_{n\ge2}n!\frac{x^n}{n!}=\frac12\sum_{n\ge2}x^n=\frac12\Big(\frac1{1-x}-1-x\Big)=\frac{x^2}{2(1-x)}\)；再加单点项 \(x\)，整理即得上式。
3. \(P=\exp(A)\)，奇点只来自 \(A\) 中的 \(\frac1{1-x}\)，在 \(x=1\)。增长率 \(=1\)。

第 14 题

我们应用 EGF 的复合公式。内函数为 \(A(x)=\sum_{n\ge1}\dfrac{x^n}{n!}=e^x-1\)，因为每组选手内部无结构。由于这些选手组排成一个圈，外函数为 \(B(x)=1+\sum_{n\ge1}x^n/n=1+\ln(1/(1-x))\)。因此复合公式给出 \[H(x)=\sum_{n\ge0}h_n\frac{x^n}{n!}=B(A(x))=1+\ln\!\Big(\frac{1}{1-(e^x-1)}\Big)=1+\ln\!\Big(\frac{1}{2-e^x}\Big).\] 所以最小模奇点在 \(r_1=\ln 2\)；因此系数 \(h_n/n!\) 的指数增长率为 \(1/\ln 2\approx 1.4427\)。

1. 内层：每组（块）非空且内部无结构，\(A(x)=e^x-1\)。
2. 外层：把块排成一个圈，\(k\) 个块成圈有 \((k-1)!\) 种，EGF 系数 \(b_k/k!=1/k\)，故 \(B(y)=1+\sum_{k\ge1}\frac{y^k}{k}=1+\ln\frac1{1-y}\)。
3. 代入 \(y=e^x-1\)：\(\frac1{1-(e^x-1)}=\frac1{2-e^x}\)，得 \(H(x)=1+\ln\frac1{2-e^x}\)。
4. 奇点：\(2-e^x=0\Rightarrow x=\ln2\approx0.693\)（最小模）。增长率 \(=1/\ln2\approx1.4427\)。

第 15 题

由于对块的集合不施加任何结构，我们使用指数公式。我们有 \[A(x)=\sum_{n\ge0}\frac{x^{2n+1}}{(2n+1)!}(2n+1)!=\frac{x}{1-x^2}.\] 因此指数公式给出 \[L(x)=\sum_{n\ge0}L_n\frac{x^n}{n!}=\exp(A(x))=\exp\!\Big(\frac{x}{1-x^2}\Big),\] 所以 \(L(x)\) 有两个奇点，模都为 \(1\)。因此系数 \(L_n/n!\) 的指数增长率为 \(1\)。

1. 每块大小为奇数且块内排成一列（共 \((2n+1)!\) 种），故 \(A(x)=\sum_{n\ge0}\frac{x^{2n+1}}{(2n+1)!}\cdot(2n+1)!=\sum_{n\ge0}x^{2n+1}=\frac{x}{1-x^2}\)（几何级数，公比 \(x^2\)）。
2. 无序块的并 → 指数公式 \(L(x)=\exp(A(x))=\exp\frac{x}{1-x^2}\)。
3. 奇点来自 \(1-x^2=0\)，即 \(x=\pm1\)，模都为 \(1\)。增长率 \(=1\)。

第 16 题

现在我们必须使用 EGF 的复合公式，其中 \(A(x)\) 与上一题相同，但 \(B(x)=\sum_{n\ge0}n!\dfrac{x^n}{n!}=1/(1-x)\)。我们得到 \[W(x)=\sum_{n\ge0}w_n\frac{x^n}{n!}=\frac{1}{1-\frac{x}{1-x^2}}=\frac{1-x^2}{1-x-x^2}.\] 最小模奇点为 \(r_0=(\sqrt5-1)/2\)，于是序列 \(w_n/n!\) 的指数增长率为 \(1/r_0=(\sqrt5+1)/2\approx 1.618\)。

1. 内层同第 15 题 \(A(x)=\frac{x}{1-x^2}\)；外层把块线性排序 \(B(y)=\sum n!\frac{y^n}{n!}=\frac1{1-y}\)。
2. \(W=B(A)=\dfrac{1}{1-\frac{x}{1-x^2}}=\dfrac{1-x^2}{(1-x^2)-x}=\dfrac{1-x^2}{1-x-x^2}\)。
3. 奇点：\(1-x-x^2=0\Rightarrow x=\frac{-1\pm\sqrt5}{2}\)，最小模正根 \(r_0=\frac{\sqrt5-1}{2}\approx0.618\)。
4. 增长率 \(=1/r_0=\dfrac{2}{\sqrt5-1}=\dfrac{\sqrt5+1}{2}\approx1.618\)（黄金比例）。

第 17 题

由于选手站成一列，我们需要使用普通生成函数（ordinary generating function, OGF），即定理 3.25。内函数为 \[A(x)=\sum_{k\ge3}\binom{k}{3}x^k=x^3\sum_{k\ge3}\binom{k}{3}x^{k-3}=x^3\cdot\frac{1}{(1-x)^4}=\frac{x^3}{(1-x)^4}.\] 因此定理 3.25 给出 \[B(x)=\sum_{n\ge0}b_n x^n=\frac{1}{1-A(x)}=\frac{(1-x)^4}{1-4x+6x^2-5x^3+x^4}.\] 所以 \(B(x)\) 是有理函数。其最小模奇点在 \(r_1=0.4503\)，故系数 \(b_n\) 的指数增长率为 \(1/r_1\approx 2.2207\)。

1. 定理 3.25（OGF 的“序列复合”）：若每个块的 OGF 是 \(A(x)\)，块排成一列，则总 OGF 为 \(\dfrac{1}{1-A(x)}\)。
2. 单块计数 \(\binom k3\)，用恒等式 \(\sum_{k\ge3}\binom k3 x^{k-3}=\frac1{(1-x)^4}\)（即 \(\sum_{m\ge0}\binom{m+3}{3}x^m\)），得 \(A=\frac{x^3}{(1-x)^4}\)。
3. \(B=\dfrac1{1-A}=\dfrac{(1-x)^4}{(1-x)^4-x^3}\)。展开分母 \((1-x)^4=1-4x+6x^2-4x^3+x^4\)，减 \(x^3\) 得 \(1-4x+6x^2-5x^3+x^4\)。
4. 数值求该四次分母最小模根 \(r_1\approx0.4503\)，增长率 \(\approx2.2207\)。

第 18 题

我们将反复使用定理 3.25。设 \(f(0)=1\)，并令 \(F(x)=\sum_{n\ge0}f(n)x^n\)。若一个允许的词以字母 \(B\) 开头，那么这个 \(B\) 后面可接任意允许的词，这类词由生成函数 \(xF(x)\) 计数。否则，我们找词 \(w\) 中第一个字母 \(B\)。这个 \(B\) 紧接在一串字母 \(A\) 之后，所以它后面不能紧跟字母 \(A\)。因此第一个 \(B\) 之后，词 \(w\) 要么结束，要么继续接另一个 \(B\)，再接任意允许的词。前一种情形，\(w\) 由生成函数 \(\sum_{n\ge2}x^n=x^2/(1-x)\) 计数（因为 \(w\) 就是一串非空的 \(A\) 后跟单个 \(B\)）；后一种情形，\(w\) 由生成函数 \(\dfrac{x^2}{1-x}\cdot x\cdot F(x)\) 计数。最后，\(w\) 可以是空词（生成函数为 \(1\)），或只由字母 \(A\) 组成的词（生成函数为 \(x/(1-x)\)）。

这导出函数方程 \[F(x)=xF(x)+\frac{x^2}{1-x}+\frac{x^2}{1-x}\cdot x\cdot F(x)+1+\frac{x}{1-x}.\] 解此方程，得 \[F(x)=\frac{1+x^2}{1-2x+x^2-x^3}.\] \(F(x)\) 的最小模奇点为 \(r_1\approx 0.5698\)，故序列 \(f(n)\) 的指数增长率为 \(1/r_1\approx 1.755\)。

1. 按词的开头/第一个 \(B\) 的位置分类（如译文所列五种情形），把每种情形的 OGF 相加，得到含 \(F(x)\) 的方程。
2. 把含 \(F\) 的项移到一边：\(F\big(1-x-\frac{x^3}{1-x}\big)=1+\frac{x}{1-x}+\frac{x^2}{1-x}\)。
3. 两边乘 \((1-x)\) 通分，化简得 \(F(x)=\dfrac{1+x^2}{1-2x+x^2-x^3}\)。
4. 求分母 \(1-2x+x^2-x^3=0\) 的最小模根 \(r_1\approx0.5698\)，增长率 \(\approx1.755\)。

第 19 题

我们断言：当 \(n\ge6\) 时 \(P(n)=P(n-3)+P(n-2)\)，且 \(P(3)=3,P(4)=2,P(5)=5\)。为证此断言，设 \(n\ge6\)。设 \(i\) 是 \(S\) 中最小的顶点，\(j\) 是 \(S\) 中第二小的顶点。那么 \(j-i=2\) 或 \(j-i=3\)。无论哪种情形，把整条路径 \(i,i+1,\cdots,j\) 收缩成一个顶点（仍叫 \(i\)），并把所有大于 \(j\) 的顶点标号减少 \(j-i\)。由新顶点 \(i\) 与原 \(S\) 中其余顶点的像，构成新集合 \(S'\)。那么 \(S'\) 是所得 \(C_{n-2}\) 或 \(C_{n-3}\) 中的一个极大独立集（maximal independent set）。此外，这个构造是双射的，因为从 \(C_{n-2}\) 或 \(C_{n-3}\) 的极大独立集 \(T\) 出发，找到 \(T\) 中最小顶点 \(i\)，把它替换成一条三或四个顶点的路径（两端点属于 \(T\) 的原像），即可找回原像。

为求生成函数 \(P(x)=\sum_{n\ge0}P(n)x^n\)，我们可设 \(P(2)=2,P(1)=0,P(0)=3\)，以使递推对所有 \(n\ge3\) 成立。于是递推导出函数方程 \[P(x)-2x^2-3=x^3 P(x)+x^2(P(x)-3),\] \[P(x)=\frac{-x^2+3}{1-x^2-x^3}.\] 求此有理函数的最小模奇点，得出数 \(P(n)\) 的指数增长率为 \(1.3247\)。这些数 \(P(n)\) 称为Perrin 数（Perrin numbers）。

1. 递推 \(P(n)=P(n-2)+P(n-3)\) 通过“收缩最小间隔”建立 \(C_n\) 与 \(C_{n-2},C_{n-3}\) 极大独立集之间的双射。
2. 把递推 \(\times x^n\) 求和并配好初值 \(P(0)=3,P(1)=0,P(2)=2\)，整理得 \(P(x)=\dfrac{3-x^2}{1-x^2-x^3}\)。
3. 分母 \(1-x^2-x^3=0\) 的最小模根 \(r\approx0.7549\)，增长率 \(=1/r\approx1.3247\)（即 Perrin/Padovan 常数，方程 \(t^3=t+1\) 的根）。

第 20 题

设 \(A(x)=\sum_{n\ge0}A_n x^n\)。显然 \(A_0=1,A_1=2\)（注意空集也是独立集），且对 \(n\ge2\) 有 \(A_n=A_{n-1}+A_{n-2}\)——因为不含 \(n\) 的此类集合有 \(A_{n-1}\) 个，含 \(n\) 的有 \(A_{n-2}\) 个。这导出函数方程 \[A(x)-2x-1=x(A(x)-1)+x^2 A(x),\] \[A(x)=\frac{x+1}{1-x-x^2},\] 故序列 \(A_n\) 的指数增长率为 \((\sqrt5+1)/2\)。注意数 \(A_n\) 是第 \((n+1)\) 个 Fibonacci 数。

1. 路径上独立集的递推：考虑顶点 \(n\) 选或不选。不选 \(n\)：其余在 \([n-1]\) 路径上，\(A_{n-1}\) 种；选 \(n\)：则 \(n-1\) 不能选，其余在 \([n-2]\) 上，\(A_{n-2}\) 种。故 \(A_n=A_{n-1}+A_{n-2}\)。
2. 用初值 \(A_0=1,A_1=2\) 把递推乘 \(x^n\) 求和，整理得 \(A(x)=\dfrac{x+1}{1-x-x^2}\)。
3. 分母同第 16 题，最小模根 \(\frac{\sqrt5-1}{2}\)，增长率 \(=\frac{\sqrt5+1}{2}\approx1.618\)。

第 21 题

顶点集 \([n]\) 上的路径的独立集 \(S\) 同时是 \(C_n\) 中的独立集，当且仅当 \(S\) 不同时包含 \(1\) 与 \(n\)。若 \(S\) 确实同时含 \(1\) 与 \(n\)，则 \(S\) 的其余部分是从顶点 \(3\) 到顶点 \(n-2\) 的路径中的独立集，即 \(n\ge5\) 时一条 \(n-4\) 个顶点的标号路径中的独立集。所以对 \(n\ge5\)，有 \(B_n=A_n-A_{n-4}\)。令 \(B_0=B_1=B_2=0\)，并注意 \(B_3=4,B_4=7\)，我们有（其中 \(B(x)=\sum_{n\ge0}B_n x^n\)） \[B(x)=A(x)\big(1-x^4\big)-\big(1-2x-3x^2-x^3\big),\] 所以 \(B(x)\) 与 \(A(x)\) 有相同的奇点集，故序列 \(B_n\) 与序列 \(A_n\) 有相同的指数增长率，而我们已在上题解答中算出该增长率。注意数 \(B_n\) 称为 Lucas 数（Lucas numbers），对 \(n\ge3\) 满足递推 \(B_n+B_{n+1}=B_{n+2}\)，初值如上。

1. 圈 \(C_n\) 与路径的差别只在“\(1\) 与 \(n\) 相邻”这一条边。圈上独立集 = 路径上独立集中去掉“同时含 \(1\) 与 \(n\)”的那些。
2. 同时含 \(1,n\) 的独立集：\(2\) 与 \(n-1\) 必不选，其余落在 \(\{3,\dots,n-2\}\)（\(n-4\) 点路径），有 \(A_{n-4}\) 个。故 \(B_n=A_n-A_{n-4}\)。
3. 乘 \(x^n\) 求和：\(B(x)=A(x)-x^4A(x)-(\text{低阶修正})=A(x)(1-x^4)-(1-2x-3x^2-x^3)\)。乘 \((1-x^4)\) 不引入新奇点（\(x^4=1\) 的根模均为 1，比 \(A\) 的奇点远），故增长率与 \(A_n\) 相同 \(=\frac{\sqrt5+1}{2}\)。

第 22 题

类似于例 7.12 的解答，我们得到函数方程 \[A_k(x)=A_k(x)\,x\big(1+x+\cdots+x^{k-1}\big)+\big(1+x+\cdots+x^{k-1}\big).\] 这给出闭形式 \[A_k(x)=\frac{1+x+\cdots+x^{k-1}}{1-x-x^2-\cdots-x^k}.\] 也就是说，\(A_k(x)\) 的最小模奇点是 \(f_k(x)=x+\cdots+x^{k}-1\) 离 \(0\) 最近的根。容易证明（补充习题 4 在更一般情形下要求你证明）\(f_k(x)\) 有唯一这样的根，且它是正实数 \(r_k\)。由此可得 \(r_{k+1}

1. 本题数“掷硬币 \(n\) 次、不出现 \(k\) 个连续正面（H）”的序列数 \(a_{n,k}\)。把序列按“最后一段连续 H 的长度（0 到 \(k-1\)）”分解，得到关于 \(A_k(x)\) 的函数方程。
2. 解方程：\(A_k(1-x(1+\cdots+x^{k-1}))=1+\cdots+x^{k-1}\)。注意 \(x(1+x+\cdots+x^{k-1})=x+x^2+\cdots+x^k\)，故分母 \(=1-x-x^2-\cdots-x^k\)。
3. 分母最小正根 \(r_k\) 满足 \(r_k+r_k^2+\cdots+r_k^k=1\)。增长率 \(=1/r_k\)。
4. 比较 \(k\) 与 \(k+1\)：\(f_{k+1}\) 比 \(f_k\) 多正项 \(x^{k+1}\)，所以在同一正点处 \(f_{k+1}>f_k\)，使其根 \(r_{k+1}1/r_k\)。直观上：禁止更长的连续正面是更弱的限制，允许的序列更多，增长更快。

第 23 题

这个过程与 5.5.2.2 节求顶点集 \([n]\) 上非平面递减 1-2 树个数所用的方法非常相似。令 \(H(x)=\sum_{n\ge0}h_n x^n/n!\)。若 \(n\ge2\)，删去顶点集 \([n]\) 上一棵平面递减 1-2 树的根，我们得到的要么是两棵树构成的、合并顶点集为 \([n-1]\) 的有序序列，要么是仅一棵顶点集为 \([n-1]\) 的树。若 \(n=1\)，则得到空集。这导出微分方程 \[H'(x)=H(x)^2+H(x)+1.\] 利用初始条件 \(H(0)=0\)，我们可用喜欢的软件包解这个微分方程。化简后得到答案 \[H(x)=-\frac12+\frac{\sqrt3}{2}\cdot\tan\!\Big(\frac{\pi}{6}+\frac{\sqrt3}{2}x\Big).\]

1. 为何是微分方程：对 EGF 求导 \(H'(x)=\sum_{n\ge1}h_n\frac{x^{n-1}}{(n-1)!}\)，相当于“去掉最大标号的根”。删根后剩下：1 棵子树 → \(H(x)\)；2 棵有序子树 → \(H(x)^2\)；空（\(n=1\)）→ 常数 \(1\)。故 \(H'=H^2+H+1\)。
2. 分离变量解：\(\dfrac{dH}{H^2+H+1}=dx\)。配方 \(H^2+H+1=\big(H+\tfrac12\big)^2+\tfrac34\)。
3. 积分 \(\displaystyle\int\frac{dH}{(H+\frac12)^2+(\frac{\sqrt3}{2})^2}=\frac{2}{\sqrt3}\arctan\!\frac{H+\frac12}{\sqrt3/2}=x+C\)。
4. 用 \(H(0)=0\) 定 \(C\)：\(\frac{2}{\sqrt3}\arctan\frac{1/2}{\sqrt3/2}=\frac{2}{\sqrt3}\arctan\frac1{\sqrt3}=\frac{2}{\sqrt3}\cdot\frac{\pi}{6}=\frac{\pi}{3\sqrt3}\)。即 \(C=\frac{\pi}{3\sqrt3}\)。
5. 反解 \(H\)：\(\arctan\frac{H+1/2}{\sqrt3/2}=\frac{\sqrt3}{2}x+\frac{\pi}{6}\)，故 \(H+\frac12=\frac{\sqrt3}{2}\tan\big(\frac{\sqrt3}{2}x+\frac\pi6\big)\)，即 \(H(x)=-\frac12+\frac{\sqrt3}{2}\tan\big(\frac\pi6+\frac{\sqrt3}{2}x\big)\)。
6. 增长率（顺带）：\(\tan\) 最近的奇点在自变量 \(=\pi/2\) 处，即 \(\frac\pi6+\frac{\sqrt3}{2}x=\frac\pi2\Rightarrow x=\frac{2}{\sqrt3}\cdot\frac\pi3=\frac{2\pi}{3\sqrt3}\approx1.209\)，故 \(h_n/n!\) 的增长率约 \(1/1.209\approx0.827\)。

返回 全书目录