Bóna · 枚举与解析组合学导论 · 第 7 章 解析组合学

7.6　习题Exercises

本页为译文 + 高中讲解合一：黑色正文为忠实翻译（每道习题逐题翻译，保留编号与全部条件）；彩色框（解题思路 / 分步推演 / 例）与配图为面向高中生的方法提示。本节只给思路与切入点，完整最终答案见对应的“习题解答”一节。逐步推演、举例、画图，不用比喻。

本章核心工具回顾解这一节几乎所有题，都要反复用到第 7.5 节的两条结论：
  1. 数列 \(a_0,a_1,\dots\) 的指数增长率（exponential growth rate）定义为 \(\displaystyle\limsup_{n\to\infty}\sqrt[n]{|a_n|}\)。直观说，若 \(a_n\approx C\cdot r^n\)，则增长率就是 \(r\)。
  2. 奇点法（singularity analysis）：若幂级数 \(F(x)=\sum_{n\ge0}f_n x^n\) 的模最小的奇点（singularity）到原点的距离为 \(M\)，则系数 \(f_n\) 的指数增长率等于 \(1/M\)。所以解题套路通常是：写出生成函数 → 找模最小的奇点（多为分母最小的正实根）→ 取其倒数。

  1. （多项式带余除法与增长率）设 \(P(x),Q(x),A(x),R(x)\) 为多项式，满足 \(P(x)=Q(x)A(x)+R(x)\)，其中 \(R(x)\) 的次数小于 \(Q(x)\) 的次数。换言之，\(R(x)\) 是 \(P(x)\) 除以 \(Q(x)\) 的余式。证明：两个有理函数 \(P(x)/Q(x)\) 与 \(R(x)/Q(x)\) 的系数有相同的指数增长率。

    思路提示关键观察：两边同除以 \(Q(x)\) 得 \[\frac{P(x)}{Q(x)}=A(x)+\frac{R(x)}{Q(x)}.\] 而 \(A(x)\) 是多项式，它只有有限多个非零系数。因此当 \(n\) 大于 \(\deg A\) 时，\(P/Q\) 与 \(R/Q\) 的第 \(n\) 个系数完全相等。增长率是 \(n\to\infty\) 的极限，只看“尾部”，有限多项的差异对 \(\limsup\sqrt[n]{|a_n|}\) 没有任何影响。

  2. （最小模根是正实数）用分析（analysis）的论证（不借助任何软件包）证明：当 \(k,\ell\) 是互素（relatively prime）的正整数时，多项式 \(1-x^k-x^\ell\) 的模最小的根 \(r_0\) 是一个正实数。

    思路提示设 \(g(x)=1-x^k-x^\ell\)。先在正实轴上找一个根：
    1. 令 \(\varphi(t)=t^k+t^\ell\)（\(t>0\)）。注意 \(\varphi(0)=0\)，\(\varphi\) 连续且严格递增，\(\varphi(t)\to\infty\)。由介值定理，存在唯一正实数 \(t=r_0\) 使 \(\varphi(r_0)=1\)，即 \(g(r_0)=0\)。这个 \(r_0\in(0,1)\)。
    2. 再证没有更小模的根。设 \(z\) 是任一根，\(|z|=\rho\)。由 \(1=z^k+z^\ell\) 取模并用三角不等式 \(1\le|z|^k+|z|^\ell=\rho^k+\rho^\ell=\varphi(\rho)\)。由 \(\varphi\) 严格递增且 \(\varphi(r_0)=1\)，得 \(\rho\ge r_0\)。
    等号成立需要 \(z^k,z^\ell\) 同向（同辐角且为正实数），这里互素条件保证只有 \(z=r_0\) 满足，故 \(r_0\) 是唯一的最小模根。

  3. （比较两个多项式的最小模根）用分析的论证（不借助软件包）证明：多项式 \(Q_a(x)=1-x-x^4\) 的模最小根，小于多项式 \(Q_b(x)=1-x^2-x^3\) 的模最小根。

    思路提示沿用上题的函数：设 \(a\) 满足 \(a+a^4=1\)，\(b\) 满足 \(b^2+b^3=1\)，二者都在 \((0,1)\) 内，是各自的最小模正根。要证 \(a
  4. 把 \(b\) 代入 \(Q_a\) 对应的方程左端：比较 \(\varphi_a(t)=t+t^4\) 与 \(\varphi_b(t)=t^2+t^3\) 在区间 \((0,1)\) 上的大小。当 \(0t^2\) 且 \(t^40\)。
  5. 所以在 \((0,1)\) 上 \(\varphi_a(t)>\varphi_b(t)\)。两函数都从 \(0\) 增到大于 \(1\)，但 \(\varphi_a\) 处处更高，故它更早达到 \(1\)，即根更小：\(a
（小验算：\(a\approx0.7245\)，\(b\approx0.7549\)，确有 \(a

  • （满射的指数生成函数）设 \(h_n\) 为从 \([n]\) 到 \([k]\) 的满射（surjection）个数之和，其中 \(k\) 从 \(1\) 取到 \(n\)。约定 \(h_0=1\)。求指数生成函数 \(\displaystyle H(x)=\sum_{n\ge0}h_n\frac{x^n}{n!}\) 的显式公式，再求 \(H(x)\) 的系数 \(h_n/n!\) 的指数增长率。

    思路提示从 \([n]\) 到 \([k]\) 的满射，对应把 \([n]\) 分成 \(k\) 个有标号、有顺序的非空块。固定 \(k\) 时其指数生成函数是 \((e^x-1)^k\)。对所有 \(k\ge1\) 求和（再补上 \(h_0=1\) 即 \(k=0\) 项）得几何级数 \[H(x)=\sum_{k\ge0}(e^x-1)^k=\frac{1}{1-(e^x-1)}=\frac{1}{2-e^x}.\] 找模最小奇点：分母 \(2-e^x=0\) 即 \(e^x=2\)，最小正实解 \(x=\ln 2\)（它就是模最小的奇点）。故增长率为 \(\dfrac{1}{\ln 2}\)。

  • （解释上题的含义）通过比较定义在 \([n]\) 上的满射数目与 \([n]\) 上的双射（bijection）数目，解释上一题结果的意义。

    思路提示\([n]\) 到自身的双射就是排列，共 \(n!\) 个。上题给出 \(h_n\approx C\cdot n!\,/(\ln 2)^{\,n}\)（按 \(h_n/n!\) 增长率 \(1/\ln2\) 反推）。把 \(h_n\) 与 \(n!\) 相比： \[\frac{h_n}{n!}\sim \frac{C}{(\ln 2)^n},\qquad \ln 2\approx0.693<1.\] 由于 \(1/\ln2>1\)，这个比值随 \(n\) 指数增长。结论：所有满射（到任意 \(k\le n\)）的总数远多于双射，多出一个约 \((1/\ln2)^n\) 的因子。

  • （递减非平面 1-2 树）递减非平面 1-2 树（decreasing nonplane 1-2 trees）在 5.5.2.2 节定义过。为便于查阅：顶点集为 \([n]\) 的这种树满足——每个顶点至多有两个孩子，且每个孩子的标号都小于其父节点的标号；树不是平面树，因此不区分左孩子与右孩子。设 \(T_n\) 为这种树的数目。注意 \(T_0=T_1=T_2=1\)，而 \(T_3=2\)，\(T_4=5\)（见原书图 7.2 的四点情形五棵树）。令 \(\displaystyle T(x)=\sum_{n\ge0}T_n\frac{x^n}{n!}\) 为数列 \(T_n\) 的指数生成函数。求数列 \(T_n/n!\) 的指数增长率。

    链 / 分叉 等 5 种
    根（标号最大者）在最上方，向下标号递减；不区分左右，故同形状只算一次。
    思路提示对“根 + 至多两棵子树”做递归，注意非平面意味着两棵子树无序，要除以对称性。可推出 \(T(x)\) 满足一个微分方程，例如形如 \(T'(x)=1+T(x)+\tfrac12 T(x)^2\)。解之并找其奇点（解会出现 \(\tan\) 型函数，奇点是分母为零处），最小模奇点的倒数即增长率。

  • （第二类 Stirling 数的生成函数）回忆第二类 Stirling 数 \(S(n,k)\) 表示把 \([n]\) 分成 \(k\) 个块的方法数。令 \(\displaystyle F_k(x)=\sum_{n\ge k}S(n,k)x^n\)，即固定 \(k\) 时 Stirling 数 \(S(n,k)\) 的（普通）生成函数。

    (a) 证明：当 \(k\ge2\) 时 \[F_k(x)=\frac{x}{1-kx}\,F_{k-1}(x).\]

    (b) 计算数列 \(\{S(n,k)\}_{n\ge k}\) 的指数增长率。

    思路提示(a) 用递推 \(S(n,k)=k\,S(n-1,k)+S(n-1,k-1)\)（把元素 \(n\) 放进已有 \(k\) 个块之一，或单独成一个新块）。两边乘 \(x^n\) 求和，整理出 \(F_k\) 与 \(F_{k-1}\) 的关系即得。
    (b) 由 (a) 反复迭代，并注意 \(F_1(x)=\dfrac{x}{1-x}\)，得 \[F_k(x)=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}.\] 模最小的奇点是分母诸因子中根模最小者：\(1-kx=0\Rightarrow x=\tfrac1k\) 给出最小值 \(1/k\)。故增长率为 \(1/(1/k)=k\)。

  • （有根平面 1-2 树，无标号）设 \(t_n\) 为 \(n\) 个无标号顶点上的有根平面树（rooted plane tree）数目，其中每个顶点至多有两个孩子；令 \(t_0=0\)（见原书图 7.3）。求数列 \(t_n\) 的指数增长率。（注：第 5 章习题 32 曾用 Lagrange 反演公式（Lagrange Inversion Formula）算过 \(t_n\)，但本题不要用那个结果；请改用生成函数与奇点分析。）

    思路提示设普通生成函数 \(T(x)=\sum t_n x^n\)。一棵树 = 根 + （空 / 一棵子树 / 两棵有序子树），翻译成方程 \[T(x)=x\bigl(1+T(x)+T(x)^2\bigr).\] 这是关于 \(T\) 的二次方程，解之得含 \(\sqrt{\;}\) 的显式：\(T=\dfrac{1-x-\sqrt{1-2x-3x^2}}{2x}\)。奇点来自根号内变号处（平方根分支点）：解 \(1-2x-3x^2=0\) 即 \((1-3x)(1+x)=0\)，最小模正根 \(x=\tfrac13\)。增长率为 \(3\)。

  • （二叉平面树）设 \(T_n\) 为 \(n\) 个无标号顶点上的二叉平面树（binary plane tree）数目。这种树中每个顶点至多两个孩子，且孩子区分左右，即使是独子也分左孩子或右孩子。原书图 7.4 给出三个顶点上的五棵二叉平面树。约定 \(T_0=1\)。求数列 \(T_n\) 的指数增长率。你在哪里见过这些数？

    思路提示区分左右意味着方程里独子有两种放法： \[T(x)=1+xT(x)\cdot? \quad\text{更标准地}\quad T(x)=\frac{1}{1-?}.\] 实际上每个非空树 = 根 + 左子树 + 右子树（各可空），得 \(T(x)=1+xT(x)^2\)（按顶点计或按节点计取相应形式）。这是Catalan 数（Catalan numbers）的生成函数，\(T_n=C_n=\frac1{n+1}\binom{2n}{n}\)。其根式奇点在 \(x=\tfrac14\)，故增长率为 \(4\)。这正是“你见过的数”——Catalan 数。

  • （任意度数的有根平面树）设 \(b_n\) 为 \(n\) 个无标号顶点上的有根平面树数目，其中任一非叶顶点可有任意多个孩子（此类树在定义 5.26 中正式定义）。约定 \(b_0=0\)。求数列 \(b_n\) 的指数增长率。

    思路提示根下挂任意多棵（有序）子树，构成序列： \[B(x)=\frac{x}{1-B(x)}.\] 解二次方程 \(B^2-B+x=0\) 得 \(B(x)=\dfrac{1-\sqrt{1-4x}}{2}\)。平方根分支点在 \(1-4x=0\)，即 \(x=\tfrac14\)。增长率为 \(4\)（这同样是 Catalan 数，符合预期）。

  • （人分组、围桌、桌又围圈）设 \(m_n\) 为如下做法的数目：把 \(n\) 个人分成若干非空子集，每个子集围一张圆桌坐下，再把这些桌子排成一个圈。求数列 \(m_n/n!\) 的指数增长率。两种安排视为相同，若每个人的左邻相同，且每张桌子的左邻相同。

    思路提示这是指数公式（exponential formula）的“圈中套圈”结构。一张圆桌坐 \(j\ge1\) 人有 \((j-1)!\) 种圆排列，其指数生成函数是 \(\sum_{j\ge1}(j-1)!\,x^j/j!=\sum x^j/j=-\ln(1-x)=\ln\frac1{1-x}\)。把这些桌子再排成一个大圈（外层也是圆排列结构），整体生成函数形如 \[M(x)=\ln\frac{1}{\,1-\ln\frac1{1-x}\,}.\] 奇点：内层 \(\ln\frac1{1-x}\) 在 \(x=1\) 出问题，但外层更早出问题——当 \(\ln\frac1{1-x}=1\)，即 \(1-x=e^{-1}\)，\(x=1-e^{-1}\approx0.632\)。这是更小的奇点，增长率为 \(\dfrac{1}{1-e^{-1}}\)。

  • （每个连通分量都是长 \(\ge3\) 的圈的图）设 \(t_n\) 为顶点集 \([n]\) 上的无向图数目，其中每个连通分量都是长度至少为 \(3\) 的圈（cycle）。求 \(t_n\) 的指数生成函数，再求数列 \(t_n/n!\) 的指数增长率。

    思路提示一个长 \(j\ge3\) 的无向圈在 \(j\) 个有标号点上有 \(\dfrac{(j-1)!}{2}\) 种（圆排列再除以反向对称）。其指数生成函数为 \(C(x)=\sum_{j\ge3}\dfrac{(j-1)!}{2}\dfrac{x^j}{j!}=\dfrac12\sum_{j\ge3}\dfrac{x^j}{j}=\dfrac12\Bigl(\ln\frac1{1-x}-x-\frac{x^2}{2}\Bigr)\)。整个图是若干这种分量的集合，用指数公式取 \(\exp\)： \[T(x)=\exp\!\Bigl[\tfrac12\bigl(-\ln(1-x)-x-\tfrac{x^2}{2}\bigr)\Bigr]=\frac{e^{-x/2-x^2/4}}{\sqrt{1-x}}.\] 模最小奇点在 \(x=1\)，故 \(t_n/n!\) 增长率为 \(1\)。

  • （每个分量都是路径的图）设 \(p_n\) 为顶点集 \([n]\) 上的无向图数目，其中每个连通分量都是一条路径（path）。求数列 \(p_n/n!\) 的指数增长率。（允许只含一个顶点的分量。）

    思路提示\(j\) 个有标号点上的路径有 \(\dfrac{j!}{2}\) 条（\(j\ge2\)），单点路径 \(1\) 条（\(j=1\)）。分量的指数生成函数 \(P_1(x)=x+\sum_{j\ge2}\dfrac{j!/2}{j!}x^j=x+\dfrac12\dfrac{x^2}{1-x}\)。整个图为 \(\exp(P_1(x))\)，即 \[P(x)=\exp\!\Bigl(x+\frac{x^2}{2(1-x)}\Bigr).\] 唯一奇点在 \(x=1\)（指数里 \(\frac{x^2}{2(1-x)}\) 处发散，是本性奇点）。最小模为 \(1\)，故增长率为 \(1\)。

  • （棒球队：分组并把组围成圈）一位棒球教练让他的 \(n\) 名队员分成若干个每组至少一人的子集，再让这一组组站成一个圈（每组内部无任何附加结构）。设 \(c_n\) 为可行方法数。求数列 \(c_n/n!\) 的指数阶（exponential order）。两种安排视为相同，若两者中队员的划分相同，且每组的左邻是同一组。

    思路提示与第 11 题相比，这里每组内部没有圆桌结构，只是一个非空集合，其指数生成函数为 \(e^x-1\)。外层把这些组排成一个圈（圆排列），用 \(\ln\frac1{1-u}\) 套上去： \[C(x)=\ln\frac{1}{\,1-(e^x-1)\,}=\ln\frac{1}{2-e^x}.\] 奇点在 \(2-e^x=0\)，即 \(x=\ln2\)。增长率为 \(\dfrac{1}{\ln2}\)。

  • （足球队：奇数大小的块，每块排成一行）一位足球教练把 \(n\) 名队员的集合划分成若干块，使每块恰含奇数名队员，再让每块排成一行。设 \(L_n\) 为方法数。求数列 \(L_n/n!\) 的指数增长率。（块的集合上无附加结构。）

    思路提示“一块奇数人排成一行”——\(j\) 人排成一行有 \(j!\) 种，故单块的指数生成函数取奇数项：\(g(x)=\sum_{j\text{ 奇}}\dfrac{j!}{j!}x^j=\sum_{j\text{ 奇}}x^j=\dfrac{x}{1-x^2}\)。块的集合用 \(\exp\)： \[L(x)=\exp\!\Bigl(\frac{x}{1-x^2}\Bigr).\] 奇点在 \(1-x^2=0\) 的最小正根 \(x=1\)（本性奇点）。增长率为 \(1\)。

  • （上题加“块之间有线性序”）修改上一题：对各块施加一个线性序（即现在有第一块、第二块……），换言之把块的集合排成一行。设 \(w_n\) 为完成这整套任务的方法数。求数列 \(w_n/n!\) 的指数增长率。

    思路提示块内部仍是“奇数人排成一行”，单块生成函数 \(g(x)=\dfrac{x}{1-x^2}\)。但现在外层是序列（有序）而非集合，用 \(\dfrac{1}{1-g}\) 代替 \(\exp\)： \[W(x)=\frac{1}{1-\dfrac{x}{1-x^2}}=\frac{1-x^2}{1-x-x^2}.\] 这是有理函数，奇点在 \(1-x-x^2=0\)，最小模正根 \(x=\dfrac{\sqrt5-1}{2}\approx0.618\)（黄金比例倒数）。增长率为 \(\dfrac{2}{\sqrt5-1}=\dfrac{1+\sqrt5}{2}\approx1.618\)。

  • （一行人切段，每段选三名队长）一群足球队员站成一行。教练沿队列走过，把队列切成若干段（教练也可以把整条队列保留为一段）。然后她要求每段选出三名队长。设 \(b_n\) 为方法数。求数列 \(b_n\) 的指数增长率。

    思路提示队员站成一行、被切段——用普通生成函数（位置有序，不带 \(n!\)）。一段长 \(j\ge3\)（要能选三名不同队长）选三名队长有 \(\binom{j}{3}\) 种，单段生成函数 \(s(x)=\sum_{j\ge3}\binom{j}{3}x^j=\dfrac{x^3}{(1-x)^4}\)。整行是段的序列： \[B(x)=\frac{1}{1-s(x)}=\frac{(1-x)^4}{(1-x)^4-x^3}.\] 增长率为 \(1/r_0\)，其中 \(r_0\) 是分母 \((1-x)^4-x^3=0\) 的最小模正根（数值约 \(r_0\approx0.43\)，可用上面第 2、3 题的实根分析法定位）。

  • （不含子词 ABA 的字）设 \(f(n)\) 为字母表 \(\{A,B\}\) 上长度为 \(n\) 的字（word）的数目，要求其中不含连续出现的子词（subword）\(ABA\)。求数列 \(f(n)\) 的指数增长率。

    思路提示这是“禁止模式”计数，可用自动机 / 转移矩阵或直接建递推得到有理生成函数 \(F(x)=\dfrac{N(x)}{D(x)}\)。增长率为 \(1/r_0\)，\(r_0\) 是分母 \(D(x)\) 的最小模正实根。
    小验算（穷举）：\(f(0)=1,f(1)=2,f(2)=4,f(3)=7\)（八个长度 3 的字里去掉 \(ABA\) 一个），可据此校验你的递推。增长率约为 \(1.7549\)（对应 \(D(x)=1-2x+x^2-x^3\) 一类分母的根）。

  • （圈 \(C_n\) 的极大独立集）考虑顶点集 \([n]\) 上的无向圈 \(C_n\)。称其顶点的子集 \(S\) 为极大独立集（maximal independent set），若 \(S\) 中任两顶点之间无边，但向 \(S\) 再加入任何新顶点都会破坏这一性质。对 \(n\ge3\)，设 \(P_n\) 为 \(C_n\) 的极大独立集数目。求数列 \(P_n\) 的指数增长率。

    \(C_5\)：极大独立集要求“不相邻、且无法再加点”——本质是没有连续三个空位的环形选点问题。
    思路提示“极大”等价于：所选顶点两两不相邻，且任意两个相邻的未选顶点不能连续超过限度——具体地，圈上每两个相邻选点之间的间隔为 \(1\) 或 \(2\)（间隔 \(\ge3\) 时中间点可加入，违反极大）。于是 \(P_n\) 满足类 Lucas/Perrin 递推 \(P_n=P_{n-2}+P_{n-3}\)。其特征方程 \(x^3=x+1\)（即 \(1-x^2-x^3\) 的倒数关系），增长率为该方程最大实根，即塑性数（plastic number） \(\approx1.3247\)。

  • （路径上任意大小的独立集）设 \(A_n\) 为顶点集 \([n]\) 上的路径中所有大小任意的独立集（independent set）数目。求数列 \(A_n\) 的指数增长率。独立集指一组顶点，其中任两点间无边。

    思路提示路径上独立集 = 长度 \(n\) 的 \(0/1\) 串中无两个相邻的 \(1\)。这正是经典的Fibonacci 计数：\(A_n=A_{n-1}+A_{n-2}\)，生成函数 \(\dfrac{1}{1-x-x^2}\)。最小模奇点 \(x=\dfrac{\sqrt5-1}{2}\)，增长率为黄金比例 \(\varphi=\dfrac{1+\sqrt5}{2}\approx1.618\)。

  • （圈上任意大小的独立集）设 \(n\ge3\)，\(B_n\) 为顶点集 \([n]\) 上的圈 \(C_n\) 中所有大小任意的独立集数目。求数列 \(B_n\) 的指数增长率。

    思路提示圈上独立集计数即Lucas 数：\(B_n=L_n\)，满足同样的递推 \(B_n=B_{n-1}+B_{n-2}\)（首尾相邻的约束改变初值，但不改变特征方程）。增长率与上题相同，仍是黄金比例 \(\varphi=\dfrac{1+\sqrt5}{2}\)。

  • （推广例 7.12：不含 \(k\) 连续正面的掷币）推广例 7.12：设 \(a_{n,k}\) 为 \(n\) 次掷币的结果序列中，不含 \(k\) 个连续正面（heads）的序列数目。求指数生成函数 \(\displaystyle A_k(x)=\sum_{n\ge0}a_{n,k}x^n\) 的闭形式，并解释当 \(k\) 变化时它的模最小奇点如何变化。

    思路提示（这里 \(A_k(x)\) 是普通生成函数。）把序列按“出现的反面 T 把正面段隔开”分解：每段连续正面长度 \(0\) 到 \(k-1\)，生成函数 \(1+x+\dots+x^{k-1}=\dfrac{1-x^k}{1-x}\)；再用反面把这些段连成序列，得 \[A_k(x)=\frac{1-x^k}{1-2x+x^{k+1}}.\] 分母最小模正根 \(r_0=r_0(k)\) 满足 \(1-2x+x^{k+1}=0\)。当 \(k\to\infty\) 时 \(x^{k+1}\to0\)，根趋于 \(1-2x=0\) 即 \(x\to\tfrac12\)，故奇点随 \(k\) 增大单调趋于 \(1/2\)，增长率从某值升向 \(2\)（无限制时两种结果，增长率正是 \(2\)）。

  • （顶点集 \([n]\) 上的递减平面 1-2 树）顶点集 \([n]\) 上的递减平面 1-2 树（decreasing plane 1-2 tree）是一棵平面树，其顶点用 \([n]\) 的元素双射地标号，使得每个顶点的标号都小于其父节点的标号。注意，这类树与（前文定义的）递减二叉树之间的唯一区别在于……（原文 PDF 在此处页面结束、语句被截断；本题完整陈述与解答见对应“习题解答”一节。）

    思路提示“平面 1-2 树”与“二叉树”的区别在于：当一个顶点只有一个孩子时，平面 1-2 树不区分这个孩子是左是右（二叉树则区分）。因此每棵此类树对应若干棵递减二叉树，计数时要在“独子”处合并。建立指数生成函数的微分方程（类似第 6 题，但保留平面有序性），再做奇点分析求增长率即可。
    • 解题总览：先认结构，再翻译，最后找奇点
    1. 判断用哪种生成函数：对象“有标号、可重排”（人、集合划分、满射、有标号图）→ 用指数生成函数（EGF），目标多为 \(a_n/n!\) 的增长率；对象“位置固定、无标号或排成一行”（无标号树、字、掷币序列）→ 用普通生成函数（OGF）。
    2. 把组合结构翻译成方程：序列 → \(\dfrac{1}{1-g}\)；集合（EGF）→ \(\exp(g)\)；圆排列 → \(\ln\dfrac{1}{1-g}\)；“根 + 子树”的树 → 自洽方程或微分方程。
    3. 找模最小奇点 \(M\)：有理 / 分式型看分母最小模正实根；含 \(\sqrt{}\) 型看根号内变号的分支点；含 \(\exp,\ln\) 型看其内部为零或发散处。
    4. 取倒数：增长率 \(=1/M\)。多数答案落在 \(\{1,\,\varphi,\,1.3247,\,1/\ln2,\,2,\,3,\,4,\,k\}\) 这些熟面孔里，可据此自检。

    返回 全书目录