Bóna · 枚举与解析组合学导论 · 第 5 章 图的计数

5.2　图与函数Graphs and functions

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

我们已经看到，顶点集为 \([n]\) 的所有树（tree）的数目，等于所有函数 \(f:[n-2]\to[n]\) 的数目。这并不是把函数的计数与图的计数联系起来的唯一一条恒等式。

本节中所有的函数都将是函数 \(f:[n]\to[n]\)。我们用“它们是 \([n]\) 上的函数（functions on \([n]\)）”这一说法来表述这一事实。

本节目标把“函数”和“图”这两个看起来毫不相干的对象对应起来，从而用数图的办法去数函数、或反过来。第一步是给每个函数画一张图（它的“短图”），再据此定义一类特殊的函数——无圈函数。
先把上一句的恒等式算清楚 这里 \([n]=\{1,2,\dots,n\}\)。“顶点集为 \([n]\) 的树的数目”由 5.1 节的凯莱公式（Cayley's formula）给出，等于 \(n^{\,n-2}\)。
  1. 一个函数 \(f:[n-2]\to[n]\)，要给定义域里的每一个元素指定一个像。定义域 \([n-2]\) 有 \(n-2\) 个元素。
  2. 每个元素都可以独立地取 \([n]\) 中 \(n\) 个值之一。
  3. 按乘法原理，这样的函数共有 \(\underbrace{n\cdot n\cdots n}_{n-2\ \text{个}}=n^{\,n-2}\) 个。
  4. 于是“树的数目”\(=n^{\,n-2}=\)“函数 \(f:[n-2]\to[n]\) 的数目”，两边相等。♦
本节要研究的是另一类联系：把函数 \(f:[n]\to[n]\)（定义域与值域同为 \([n]\)）本身画成图。

5.2.1　无圈函数Acyclic functions

若一个函数 \(f:[n]\to[n]\) 的短图（short diagram）中除了环（loop）以外不含任何圈（cycle），则称该函数 \(f\) 为无圈的（acyclic）。环是必须被允许的，因为 \(f\) 的短图含有 \(n\) 条边，从而短图不可能是无圈的（cycle free，即“不含任何圈”）。

把“短图”说清楚对一个函数 \(f:[n]\to[n]\)，它的短图是这样一张有向图：顶点集就是 \([n]=\{1,2,\dots,n\}\)；对每一个顶点 \(i\)，从 \(i\) 画一条有向边指向 \(f(i)\)。
例：\(f(1)=2,\ f(2)=3,\ f(3)=3\)（顶点上方标注 \(f\) 的值） 123 环
短图：顶点 \(1\) 指向 \(2\)，\(2\) 指向 \(3\)，\(3\) 指向自己（一个环）。三个顶点共发出三条边，与公式“\(n\) 条边”一致。
为什么“环必须被允许”——一步步推
  1. 短图有 \(n\) 个顶点，且恰好 \(n\) 条边（每个顶点出发一条）。
  2. 从任意顶点 \(i_0\) 出发，顺着唯一的出边走：\(i_0\to f(i_0)\to f(f(i_0))\to\cdots\)。每走一步都还能继续走，因为每个顶点都有出边。
  3. 但顶点只有有限个 \(n\) 个，走 \(n+1\) 步必然会踩到一个之前到过的顶点（鸽巢原理）。
  4. 一旦重复访问某个顶点，就形成了一条闭合路线，也就是一个圈。所以短图一定含有圈，绝不可能“无圈”。
  5. 因此，若想定义一类“尽量没有圈”的函数，能允许的最短的圈就是长度为 \(1\) 的环。把这种最短的圈排除在“禁止”之外，就得到“无圈函数”的定义。♦

例 5.20　设 \(n=6\)。则由 \[ f(i)=\begin{cases} i+1, & i\ \text{不被 } 3\text{ 整除},\\[2pt] i, & \text{否则（即 } i\text{ 被 } 3 \text{ 整除）}\end{cases} \] 所定义的函数 \(f:[n]\to[n]\) 是无圈的，正如图 5.21 所示。

例 5.20 的逐点计算 把 \(i=1,2,\dots,6\) 一个个代入：
  1. \(i=1\)：\(1\) 不被 \(3\) 整除，\(f(1)=1+1=2\)。
  2. \(i=2\)：\(2\) 不被 \(3\) 整除，\(f(2)=2+1=3\)。
  3. \(i=3\)：\(3\) 被 \(3\) 整除，\(f(3)=3\)（环 / 不动点）。
  4. \(i=4\)：\(4\) 不被 \(3\) 整除，\(f(4)=4+1=5\)。
  5. \(i=5\)：\(5\) 不被 \(3\) 整除，\(f(5)=5+1=6\)。
  6. \(i=6\)：\(6\) 被 \(3\) 整除，\(f(6)=6\)（环 / 不动点）。
于是短图被拆成两段互不相连的链：\(1\to2\to3\circlearrowleft\) 和 \(4\to5\to6\circlearrowleft\)。两条链各自只在末端有一个环，没有出现长度 \(\ge 2\) 的圈，所以 \(f\) 是无圈的。
123 456 两条链顶端各有一个环（不动点 3 和 6），没有更长的圈
图 5.21　\([6]\) 上的一个无圈函数。箭头由 \(i\) 指向 \(f(i)\)；顶端的环是允许的最短的圈。
对照：一个不是无圈的函数 取 \(g:[2]\to[2]\)，\(g(1)=2,\ g(2)=1\)。它的短图里 \(1\to2\to1\) 形成一个长度为 \(2\) 的圈（而不是环）。这样的圈是不被允许的，所以 \(g\) 不是无圈函数。
12
\(1\to2\) 且 \(2\to1\)：长度为 \(2\) 的圈，故 \(g\) 不是无圈函数。
对比之下，图 5.21 里每条链末端都只是一个环（长度 \(1\) 的圈），没有这种“两步绕回”的圈，所以那个函数才是无圈的。

返回 全书目录