Bóna · 枚举与解析组合学导论 · 第 4 章 排列的计数

4.1　欧拉数Eulerian numbers

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

第 4 章引言　排列的计数

两辆满载游客的大巴抵达了一处大型休息区。乘第一辆大巴而来的 \(n\) 位游客逐个进入自助餐区（我们按他们下车的先后顺序用 \([n]\) 的元素来表示他们），并在 \(k\) 个不同的营业窗口前各自排起了队。没有人插队，所以最先下车的人最先排队，第二个下车的人第二个排队，以此类推。乘第二辆大巴而来的 \(n\) 位游客则进入了一家提供全程服务的餐厅，他们围坐在 \(k\) 张完全相同的圆桌旁。每辆大巴上的游客各有多少种安排方式？

上面提出的两个问题都是组合学中基本的计数问题。它们都与排列（permutation）密切相关，即把 \([n]\) 的元素排成一行、每个元素恰好用一次的排法。这两个问题的答案也都与集合划分密切相关，更确切地说，与第二类斯特林数（Stirling numbers of the second kind）密切相关。

本章/本节目标本节只研究第一辆大巴的游客：把 \([n]\) 排成一行后，按“连续上升”的规律自然分成若干段。我们要回答两件事——（1）这种“分段”到底是什么、怎样数；（2）恰好分成 \(k\) 段的排列有多少个。后者就是欧拉数 \(A(n,k)\)。本节要给它的显式公式、递推公式，并展示它在别的计数问题中也会冒出来。

4.1　欧拉数

我们先来考虑第一辆大巴上的游客，他们在 \(k\) 个柜台前各排成一队。如果我们按游客到达餐区的先后顺序，用 \([n]\) 的元素来表示这 \(n\) 位游客，那么 \(k\) 个窗口前的 \(k\) 条队伍就对应 \(k\) 个递增子序列（increasing subsequences）。（例如，若 \(n=6\)、\(k=2\)，且第 \(1\)、\(4\)、\(5\) 个人去第一个窗口，第 \(2\)、\(3\)、\(6\) 个人去第二个窗口，则我们得到两个递增子序列 \(145\) 与 \(236\)。）如果我们把这 \(k\) 个递增子序列按某个指定顺序（比如按窗口所在位置的顺序）一个接一个地写下来，就得到集合 \([n]\) 的一个排列 \(p_1p_2\cdots p_n\)。在这个排列中，至多有 \(k-1\) 个位置 \(i\) 满足其后一项更小，即 \(p_i>p_{i+1}\)。事实上，这种情形只可能在 \(p_{i+1}\) 开启一个新的递增子序列（来自一个新窗口前的队伍）时出现，而这只会发生 \(k-1\) 次。

窗口一 窗口二 145 236 拼起来：145 | 236 → 排列 145236（在第 3、4 项之间 5>2，出现 1 次下降）
每条队伍内部按下车先后排，所以自上而下号码递增；\(k=2\) 条队伍拼接后只会出现 \(k-1=1\) 处“前大后小”。

这种把排列分解为连续元素所构成的递增子序列的方式，正是本节的主题。因此，我们把这个概念形式化。

定义 4.1 若 \(k\) 是使排列 \(p=p_1p_2\cdots p_n\) 能分解成 \(k\) 个由连续项构成的递增子序列的最小整数，则称 \(p\) 有 \(k\) 个上升段（ascending runs），在不致混淆时简称段（runs）。
例 4.2 排列 \(p=245169378\) 有三个上升段，即 \(245\)、\(169\) 与 \(378\)。

于是，第一辆大巴上的游客所形成的排列，至多有 \(k\) 个上升段。

有时候，与其直接处理上升段本身，不如处理它们之间的分界点更方便。显然，每当一个较大的元素后面跟着一个较小的元素时，就必须开启一个新的上升段。这同样是一个基本现象，它也有自己的名字。

定义 4.3 设 \(p=p_1p_2\cdots p_n\) 为一个排列。若 \(p_i>p_{i+1}\)，则称 \(i\in[n-1]\) 是 \(p\) 的一个下降位（descent）。若 \(i\in[n-1]\) 不是下降位，则称它为一个上升位（ascent）。

请注意，下降位指的是 \(p\) 的位置，而不是它的元素值。

例 4.4 排列 \(p=245169378\) 有两个下降位，即 \(i=3\) 与 \(i=6\)。因此 \(p\) 有六个上升位。
读者请验证此时读者应停下来验证：\(p\) 有 \(k-1\) 个下降位，当且仅当 \(p\) 有 \(k\) 个上升段。下面的图 4.1（展示例 4.4 中的排列）应能帮助读者把这一事实可视化。
2 4 5 1 6 9 3 7 8 段一 245 段二 169 段三 378
图 4.1　排列中的上升段与下降位。三条实线（绿、蓝、紫）是三个上升段；两条红色虚线是两个下降位（\(5\to1\) 在 \(i=3\)，\(9\to3\) 在 \(i=6\)）。可见“\(3=2+1\)”：段数 \(=\) 下降位数 \(+1\)。
例：自己数一遍 \(p=245169378\)
  1. 逐位比较相邻两项：\(2<4<5\)（一直升）→ 第 3、4 项 \(5>1\)，出现下降位 \(i=3\)。
  2. \(1<6<9\)（一直升）→ 第 6、7 项 \(9>3\)，出现下降位 \(i=6\)。
  3. \(3<7<8\)（一直升），到末尾结束。
  4. 下降位共 \(2\) 个；每个下降位“切一刀”，把序列切成 \(2+1=3\) 段。这就是“段数 \(=\) 下降位数 \(+1\)”的直接含义。

在本书余下部分，集合 \([n]\) 的排列都称为 \(n\)-排列。如果我们能算出恰好有 \(k\) 个上升段的 \(n\)-排列有多少个，那么由加法原理，我们也就能算出至多有 \(k\) 个上升段的 \(n\)-排列有多少个。事实证明，这是一条好走的路，因为计数恰好有 \(k\) 个上升段的排列比计数至多有 \(k\) 个上升段的排列更容易。因此，我们给前者起个名字。

定义 4.5 设 \(k\) 与 \(n\) 为满足 \(k\le n\) 的正整数。则恰好有 \(k\) 个上升段的 \(n\)-排列的个数记为 \(A(n,k)\)，称为欧拉数（Eulerian number）。
例 4.6 恰好有两个上升段的 \(3\)-排列共有四个，它们是 \(132\)、\(213\)、\(231\) 与 \(312\)。因此 \(A(3,2)=4\)。
把全部 \(6\) 个 3-排列列出来核对
  1. \(123\)：处处上升，无下降位 → \(1\) 段。计入 \(A(3,1)\)。
  2. \(132\)：\(3>2\)，\(1\) 个下降位 → \(2\) 段。计入 \(A(3,2)\)。
  3. \(213\)：\(2>1\)，\(1\) 个下降位 → \(2\) 段。计入 \(A(3,2)\)。
  4. \(231\)：\(3>1\)，\(1\) 个下降位 → \(2\) 段。计入 \(A(3,2)\)。
  5. \(312\)：\(3>1\)，\(1\) 个下降位 → \(2\) 段。计入 \(A(3,2)\)。
  6. \(321\)：\(3>2\) 且 \(2>1\)，\(2\) 个下降位 → \(3\) 段。计入 \(A(3,3)\)。
于是 \(A(3,1)=1,\;A(3,2)=4,\;A(3,3)=1\)，三者之和 \(1+4+1=6=3!\)，恰为全部 3-排列数。
例 4.7 对所有 \(n\)，恰有一个排列（即递增排列）只有一个上升段，也恰有一个排列（即递减排列）有 \(n\) 个上升段。因此 \(A(n,1)=A(n,n)=1\)。

我们可以把 \(A(n,k)\) 的定义推广到其他非负整数：令 \(A(n,0)=0\)，并对 \(k>n\) 令 \(A(n,k)=0\)。

欧拉数的显式公式自十九世纪末以来就已为人所知。然而，我们在这里给出一个相对较新、且异常简洁的证明，它是由 Richard Stanley 于 2003 年传达给本书作者的。

定理 4.8 对所有满足 \(k\le n\) 的非负整数 \(n\) 与 \(k\)，欧拉数由下面的显式公式给出： \[\tag{4.1}A(n,k)=\sum_{i=0}^{k}(-1)^i\binom{n+1}{i}(k-i)^n.\]

在开始证明之前，我们先看 \(k=1\) 与 \(k=2\) 这两个特殊情形热身。若 \(k=1\)，则排列必须有零个下降位，于是它必为递增排列，从而 \(A(n,1)=1\)；读者可验证 (4.1) 在此特例下成立。若 \(k=2\)，则我们的排列有两个上升段。这意味着，为得到这些排列，我们需要把 \([n]\) 拆成两个非空集合 \(X\) 与 \(Y\)（即将来的两个上升段），共有 \(2^n-2\) 种拆法，然后把这两个集合各自按递增排好，最后把得到的两个字符串拼接起来。不过我们必须小心：如果 \(X\) 中最大的元素小于 \(Y\) 中最小的元素（换言之，当 \(X=[j]\) 而 \(Y=\{j+1,j+2,\cdots,n\}\) 时），那么得到的排列将是 \(12\cdots n\)，它只有一个上升段。这种情况发生 \(n-1\) 次，从而 \[A(n,2)=2^n-2-(n-1)=2^n-n-1,\] 这与 (4.1) 一致，也与例 4.6 一致。

例：用 \(A(n,2)=2^n-n-1\) 验证例 4.6取 \(n=3\)：\(2^3-3-1=8-3-1=4=A(3,2)\)。再核对“拆分”过程：把 \(\{1,2,3\}\) 拆成两个非空子集，有序地“左段 \(X\)、右段 \(Y\)”共 \(2^3-2=6\) 种；其中使拼出来是 \(123\)（只有一段）的有 \(X=\{1\},Y=\{2,3\}\) 和 \(X=\{1,2\},Y=\{3\}\) 这 \(n-1=2\) 种。\(6-2=4\)，与直接列举一致。

现在我们开始看到为什么证明 (4.1) 并不容易。随着 \(k\) 增大，会出现越来越多这样的情形：在某些情况下，本应组成两个上升段的两个子串实际上只组成了一个，就像上面的 \(X\) 与 \(Y\) 那样。这是个严重的问题，因为一方面我们得到的上升段比想要的少，另一方面有些排列会被多次得到。所幸，我们的新朋友容斥原理（inclusion-exclusion principle），再加上一个巧妙的论证，会帮我们解决问题。

证明思路预告把“\(n\) 个游客自由选 \(k\) 个窗口”的全部方案数 \(k^n\) 当作起点；其中有些方案会出现“空窗口”或“拼接处前大后小”这类毛病，导致段数不足 \(k\)。我们用容斥原理把有毛病的方案数算出来，再从 \(k^n\) 里减掉，剩下的就是恰好 \(k\) 段的 \(A(n,k)\)。关键技巧是引入“可移除的栅栏”，把两种毛病合并成一种来统一计数。
证明（定理 4.8）. 我们设这 \(k\) 个窗口由 \(k-1\) 道栅栏（fence）隔开，游客们就填进栅栏之间的空档，例如 \[\tag{4.2}p=245\,|\,136\,|\,|\,79\,|\,8.\] 每位游客都可以自由前往 \(k\) 个窗口中的任何一个，这就产生了 \(k^n\) 种可能。然而其中许多对我们的目的并不合用，因为它们会导致段数少于 \(k\) 的排列。出现这种情况有两个原因：
  1. （a）可能存在空窗口（两道栅栏之间没有任何元素），以及
  2. （b）可能出现紧挨栅栏之前的元素小于其后元素的情况。
请读者验证下面这些容易的命题：如果 (a)、(b) 都不发生，那么我们恰好得到一个有 \(k\) 个上升段的 \(n\)-排列，并且——这一点至关重要——每个这样的排列恰好被得到一次。
读 (4.2) 这个例子排列是 \(p=245136798\)，\(k=5\)，故有 \(4\) 道栅栏。注意第二、三道栅栏之间是空的（毛病 a，空窗口）；又看 \(136\) 与 \(79\) 拼接处：\(6<7\)（毛病 b，栅栏前的 \(6\) 小于栅栏后的 \(7\)，本该连成一段却被栅栏强行分开）。正因有这些毛病，这个“安排”并不对应一个恰好 \(5\) 段的排列。
证明（续）. 现在我们来计数那些“出了毛病”（即 (a)、(b) 至少发生其一）的排列。这看起来像个艰巨的任务，因为我们要同时盯住两条性质而不止一条。所幸，借助下面的定义，我们能把它们同时处理。

设 \(p\) 是一个在其各项之间（也可能在开头或结尾）插入了 \(k-1\) 道栅栏的 \(n\)-排列。我们把这个结构——排列连同栅栏一起——称为一个安排（arrangement）。我们称一道栅栏 \(f\) 是可移除的（removable），如果它同时满足以下两个条件：

  1. 移除 \(f\) 后，我们仍得到一个排列，其各项在任意两道相邻栅栏之间仍然递增；以及
  2. 栅栏 \(f\) 的紧后面不是另一道栅栏。

注意，举例来说，位于排列最末端的栅栏总是可移除的。例如在 (4.2) 中，第三道栅栏是可移除的，其余的都不是。

如果一个安排没有可移除栅栏，那么对应的排列就有 \(k\) 个上升段，这正是我们想要的。如果一个安排确有至少一道可移除栅栏，那么对应的排列上升段数就少于 \(k\)。下面我们用容斥原理来枚举这些排列。

我们把排列中两个相邻元素之间的 \(n-1\) 个空档，以及开头和结尾处的空档，统称为位置（positions）。于是共有 \(n+1\) 个位置，我们从左到右给它们编号。设 \(S\subseteq[n+1]\)，令 \(A_S\) 为这样一些安排构成的集合：在属于 \(S\) 的每个位置上都有一道可移除栅栏。注意，虽然任一给定位置上可能有不止一道栅栏，但其中只有一道（即最后一道）能是可移除的。

所幸 \(A_S\) 的大小很容易确定。

命题 4.9 设 \(S\subseteq[n+1]\) 且 \(|S|=i\le k-1\)。则 \[|A_S|=(k-i)^n.\]
证明（命题 4.9）. 首先放下 \(k-i-1\) 道栅栏，并把 \(n\) 个元素排成一行，得到一个至多有 \(k-i\) 个上升段的安排；这可以用 \((k-i)^n\) 种方式完成。然后把剩下的 \(i\) 道栅栏插入属于 \(S\) 的那些位置。（如果那里已经有栅栏，就把新栅栏放在同一位置已有栅栏的右侧。）这就保证了我们在属于 \(S\) 的位置上得到可移除栅栏。而且，我们将恰好一次地得到每个具有所需性质的安排。事实上，若 \(a\) 是一个具有所需性质的安排，那么只要把 \(a\) 中属于 \(S\) 的每个位置上的最后一道栅栏移除，我们就得到那个唯一能导出 \(a\) 的原始安排。♦
为什么是 \((k-i)^n\)：拆开看
  1. “把 \(n\) 个元素分配到 \(k-i\) 个空档里”等价于“每个元素独立地选 \(k-i\) 个去处之一”，所以是 \((k-i)^n\)。这一步固定了 \(k-i-1\) 道栅栏。
  2. 剩下的 \(i\) 道栅栏被强制塞进 \(S\) 指定的 \(i\) 个位置——没有选择自由，所以不再乘任何因子。
  3. “可逆”保证不重不漏：给定结果，把 \(S\) 处的最后一道栅栏各撤一道，就唯一还原出第 1 步的安排。
  4. 关键观察：结果 \((k-i)^n\) 只依赖 \(|S|=i\)，与 \(S\) 具体是哪些位置无关。
证明（定理 4.8，收尾）. 注意，除了 \(S\) 的大小之外，我们并不需要 \(S\) 的任何特定性质，这意味着（把所有大小为 \(i\) 的 \(S\) 加起来，共 \(\binom{n+1}{i}\) 个） \[\tag{4.3}R_i=\sum_{\substack{S\subseteq[n+1]\\|S|=i}}|A_S|=\binom{n+1}{i}(k-i)^n.\] 现在我们可以使用容斥原理了。在记号上稍作通融，我们用 \(A_i\) 表示在位置 \(i\) 上有一道可移除栅栏的安排所构成的集合。那么由定理 2.38（容斥原理）， \[\begin{aligned}|A_1\cup A_2\cup\cdots\cup A_{n+1}|&=R_1-R_2+R_3-\cdots+(-1)^{k}R_{k-1}\\&=\sum_{i=1}^{k-1}(-1)^{i+1}\binom{n+1}{i}(k-i)^n.\end{aligned}\] 注意，当 \(i\ge k\) 时 \(R_i=0\)，因为总共只有 \(k-1\) 道栅栏，所以可移除栅栏不可能多于 \(k-1\) 道。

回忆起我们可能拥有的安排总数是 \(k^n\)，由减法原理，没有可移除栅栏的安排数为 \[\tag{4.4}A(n,k)=\sum_{i=0}^{k-1}(-1)^i\binom{n+1}{i}(k-i)^n,\] 这正是要证明的。♦

(4.1) 与 (4.4) 上标不同为何等价(4.1) 的求和上限是 \(k\)，(4.4) 是 \(k-1\)。差别仅在 \(i=k\) 那一项：它含因子 \((k-k)^n=0^n=0\)（\(n\ge1\)），加不加都一样。所以两式给出的 \(A(n,k)\) 相同。

欧拉数在许多方面表现得与二项式系数（binomial coefficients）相似，而在另外许多方面又与第二类斯特林数密切相关。

前者的一个例子是对称性：对任意固定的 \(n\) 与任意 \(k\le n\)，等式 \(A(n,k)=A(n,n+1-k)\) 成立。读者应先尝试自己证明这个恒等式，然后再看习题 1 中我们给出的两种解法。

对称性的数字检验取 \(n=3\)：\(A(3,1)=A(3,3)=1\)，\(A(3,2)=A(3,2)=4\)，对称成立。直观地说，把一个排列“整体翻转”（首尾颠倒）会把每个上升位变成下降位、下降位变成上升位，于是 \(k-1\) 个下降位变成 \((n-1)-(k-1)=n-k\) 个下降位，即段数从 \(k\) 变成 \(n+1-k\)。这是一个双射，故两类排列一样多。

正如二项式系数与第二类斯特林数那样，欧拉数也满足一个三角递推（triangular recurrence）。

定理 4.10 设 \(k\) 与 \(n\) 为满足 \(k\le n\) 的非负整数。则 \[A(n,k)=k\,A(n-1,k)+(n-k+1)\,A(n-1,k-1).\]
证明（定理 4.10）. 左边显然在计数有 \(k-1\) 个下降位的 \(n\)-排列；我们只需证明右边计数的是同一批对象。

设 \(p\) 是被 \(A(n,k)\) 计数的一个排列。设 \(\bar p\) 是从 \(p\) 中删去元素 \(n\) 后得到的排列。那么有两种情形：要么 \(\bar p\) 与 \(p\) 的下降位个数相同，要么少了一个。我们将证明右边的两项分别计数落入这两种情形的排列。

情形 1. 删去元素 \(n\) 后，\(p\) 的下降位个数不变。

这发生在 \(n\) 处于 \(p\) 的末尾时，或当 \(n\) 被插入到 \(\bar p\) 的第 \(i\) 项紧后面、而 \(i\) 是 \(\bar p\) 的一个下降位时。（试想 \(\ldots3n1\ldots\)。）两种情况下，我们都剩下一个长度为 \(n-1\)、有 \(k-1\) 个下降位的排列 \(\bar p\)。由定义，这样的排列有 \(A(n-1,k)\) 个。它们中的每一个都以这种方式从 \(k\) 个不同的排列 \(p\) 得到。事实上，要得到这些排列，我们可以把 \(n\) 插入 \(\bar p\) 的 \(k-1\) 个下降位中的任何一个，也可以把它放到 \(\bar p\) 的末尾。因此，有 \(k\,A(n-1,k)\) 个排列落入此情形。

情形 2. 删去元素 \(n\) 后，\(p\) 的下降位个数减少 1。

这发生在 \(n\) 是 \(p\) 的首项时，或当 \(n\) 被插入到 \(\bar p\) 的第 \(i\) 项紧后面、而 \(i\) 是 \(\bar p\) 的一个上升位时。（试想 \(\ldots1n3\ldots\)。）两种情况下，我们都剩下一个长度为 \(n-1\)、有 \(k-2\) 个下降位的排列 \(\bar p\)。这样的排列有 \(A(n-1,k-1)\) 个。它们中的每一个都以这种方式从 \(n-k+1\) 个不同的排列 \(p\) 得到。事实上，要得到这些排列，我们可以把 \(n\) 插入 \(\bar p\) 的 \(n-k\) 个上升位中的任何一个，也可以把它放到 \(\bar p\) 的最前面。由乘法原理，这解释了右边的第二项。

我们已证明两边在计数同一个集合的元素；因此它们必定相等。♦

例：用递推算 \(A(4,2)\)已知 \(A(3,2)=4,\;A(3,1)=1\)。代入 \(n=4,k=2\)： \[A(4,2)=2\cdot A(3,2)+(4-2+1)\cdot A(3,1)=2\cdot4+3\cdot1=11.\] 用显式公式 (4.1) 核对：\(A(4,2)=2^4-4-1=16-5=11\)。两者一致。
  1. “情形 1（插入 \(4\) 不增下降位）”：在每个有 \(1\) 个下降位的 3-排列（\(132,213,231,312\)）里，把 \(4\) 放到末尾或放到那个下降位处，每个生出 \(k=2\) 个 4-排列，共 \(2\times4=8\) 个。
  2. “情形 2（插入 \(4\) 使下降位减 1）”：在递增 3-排列 \(123\)（\(0\) 个下降位，对应 \(A(3,1)\)）里，把 \(4\) 放到最前或放到某个上升位处，共 \(n-k+1=3\) 个 4-排列。
  3. 合计 \(8+3=11\)。每个 4-排列都恰好被这两条途径之一生成一次，不重不漏。

定理 4.10 使我们能够证明欧拉数会出现在许多其他情境中。我们在这里给出一个例子，其余留作习题。

例 4.11 一座城市有 \(n\) 家不同的旅馆，编号从 \(1\) 到 \(n\)，其中 \(1\) 表示最便宜的旅馆，\(n\) 表示最贵的旅馆。在连续的 \(n\) 天里，每天有一位新的、热爱数学的游客抵达该城。这些游客按消费能力递增的顺序到来。也就是说，第 \(i\) 天到达的游客负担得起入住任何编号属于 \([i]\) 的旅馆。

设 \(H(n,k)\) 为游客们做出选择、使得最终恰好有 \(k\) 家旅馆各接待了至少一位游客的方式数。那么 \(H(n,k)=A(n,k)\)。

例如，若 \(n=2\)，则要么两位游客都去旅馆 \(1\)，要么第一位去 \(1\)、第二位去 \(2\)，于是 \(H(2,1)=H(2,2)=1\)，这与 \(A(2,1)=A(2,2)=1\) 一致。读者不妨验证 \(n=3\) 的结果。注意，总的可能数为 \(\sum_{k=1}^{n}A(n,k)=n!\) 并不奇怪，因为第 \(k\) 位游客有 \(k\) 种选择（\(1\cdot2\cdots n=n!\)）。

验证 \(n=3\) 的旅馆例子第 \(1\) 位只能选旅馆 \(1\)；第 \(2\) 位选 \(\{1,2\}\)；第 \(3\) 位选 \(\{1,2,3\}\)。共 \(1\cdot2\cdot3=6\) 种。按“最终被入住的旅馆数 \(k\)”分类：恰用 \(1\) 家（都挤旅馆 \(1\)）有 \(1\) 种，恰用 \(3\) 家有 \(1\) 种，其余 \(4\) 种恰用 \(2\) 家。即 \(H(3,1)=1,\,H(3,2)=4,\,H(3,3)=1\)，与 \(A(3,k)\) 完全相同。
解（例 4.11）. 我们对 \(n\) 用归纳法证明此命题，初始情形 \(n=1\) 是平凡的。假设我们对 \(n-1\) 已知该命题，来对 \(n\) 证明它。我们断言 \[\tag{4.5}H(n,k)=k\,H(n-1,k)+(n-k+1)\,H(n-1,k-1).\] 左边按定义是游客们所做的、使恰好 \(k\) 家旅馆各得到至少一位本组顾客的全部选择方案数。我们断言右边计数的是同样的对象。事实上，被左边计数的情形可由两种不同方式产生，即最后一位游客要么去了一家已经有本组某人入住的旅馆，要么没有。第一种情况下，前 \(n-1\) 位游客以 \(H(n-1,k)\) 种方式分入 \(k\) 家旅馆，然后最后一位游客在这 \(k\) 家旅馆中选一家入住；这解释了右边的第一项。第二种情况下，前 \(n-1\) 位游客以 \(H(n-1,k-1)\) 种方式分入 \(k-1\) 家旅馆，然后最后一位游客在其余 \(n-k+1\) 家旅馆中选一家；这解释了右边的第二项，从而证明了 (4.5)。

由归纳假设，我们知道 \(A(n-1,k)=H(n-1,k)\)，也知道 \(A(n-1,k-1)=H(n-1,k-1)\)。对照定理 4.10，我们看到这意味着 \(A(n,k)\) 与 \(H(n,k)\) 是由相同的数、经相同的运算得到的。因此它们必定相等。♦

请注意，我们是用一种特殊的归纳法证明定理 4.10（以及上面这个例子）的，即：我们证明两个数阵必定相同，因为它们以相同的方式起步，并满足相同的递推关系。我们很快会看到这一证明技巧的更多应用。

“同初值 + 同递推 ⇒ 同数列”这条技巧第三位游客那个细节（\(n-k+1\)）与定理 4.10 第二项里的 \(n-k+1\) 一模一样并非巧合：两个量 \(A(n,k)\) 和 \(H(n,k)\) 满足同一个递推，又有同样的初始值，于是它们逐项相等。这就把“为什么旅馆问题的答案恰是欧拉数”讲清楚了——不需要再造一个双射。

下面这个概念把下降位与另一个有趣的排列统计量联系起来，后者将在下一节讨论。一个错列（desarrangement，此处采用作者新造词，详见下文说明）是指其第一个上升位出现在偶数位置的排列。我们对这条规则作一个例外：若 \(n\) 是偶数，则我们也把递减排列 \(n(n-1)\cdots21\) 视为一个错列，仿佛它在末尾位置 \(n\) 处有一个上升位。于是 \(213\)、\(43215\) 与 \(4321\) 都是错列，但 \(12\)、\(321\) 与 \(52134\) 都不是。我们在此关心的是长度为 \(n\) 的错列的个数。

逐个核对“是不是错列”“第一个上升位”指从左数第一个满足 \(p_i<p_{i+1}\) 的位置 \(i\)。
  1. \(213\)：\(p_1=2>p_2=1\)（位置 1 是下降），\(p_2=1<p_3=3\)（位置 2 是上升）。第一个上升位在 \(i=2\)（偶数）→ 是错列。
  2. \(43215\)：\(4>3>2>1\) 都下降，到 \(p_4=1<p_5=5\)，第一个上升位 \(i=4\)（偶数）→ 是错列。
  3. \(4321\)：\(n=4\) 为偶数的递减排列，按例外规定视作错列。
  4. \(12\)：\(p_1=1<p_2=2\)，第一个上升位 \(i=1\)（奇数）→ 不是错列。
  5. \(321\)：\(n=3\) 为奇数的递减排列，无上升位，不享受例外 → 不是错列。
  6. \(52134\)：\(5>2>1\)（位置 1、2 下降），\(p_3=1<p_4=3\)，第一个上升位 \(i=3\)（奇数）→ 不是错列。

“desarrangement”一词由 Michelle Wachs 创造，意在以一种诙谐的方式向她的合作者 Jacques Désarmenien 致敬。最初首次使用该词的那本期刊的编辑们本想把它改成 “disarrangements”（这是一个真正的英文词），但当他们领会了其中的玩笑后，就保留了 “desarrangements” 不动。

引理 4.12 长度为 \(n\) 的错列的个数为 \[J(n)=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}.\]
证明（引理 4.12）. 固定 \(n\)，设 \(b_i\) 为第一个上升位出现在位置 \(2i\) 的 \(n\)-排列的个数。在这样一个排列中，前 \(2i+1\) 个元素的相对顺序有 \(2i\) 种不同的可能。事实上，位于位置 \(2i+1\) 的元素可以是这 \(2i+1\) 个元素中除最小者以外的任何一个，但一旦该元素选定，其余 \(2i\) 个元素就必须全部按递减顺序排列。因此，当 \(i<n/2\) 时，被 \(b_i\) 枚举的排列占全部 \(n\)-排列的比例为 \(\dfrac{2i}{(2i+1)!}\)；从而 \[b_i=\frac{2i}{(2i+1)!}\,n!=\left(\frac{1}{(2i)!}-\frac{1}{(2i+1)!}\right)n!.\] 把所有可能的 \(b_i\) 求和，我们得到 \[J(n)=\sum_{i=1}^{\lfloor(n-1)/2\rfloor}n!\left(\frac{1}{(2i)!}-\frac{1}{(2i+1)!}\right)=n!\left(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\cdots\right).\] 这与我们的论断等价，因为我们的论断是 \[J(n)=n!\left(1-1+\frac{1}{2}-\frac{1}{6}+\cdots\right).\] 我们所证明的与之相同，只是少了开头那两项 \(1-1\)，而这两项本就互相抵消。♦
例：算 \(J(4)\) 并与列举对照 \[J(4)=4!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right)=24\left(1-1+\tfrac12-\tfrac16+\tfrac1{24}\right)=24\cdot\tfrac{9}{24}=9.\] 所以长度为 \(4\) 的错列有 \(9\) 个。（这与“第一个上升位在偶数位”这一条件相符：\(b_1\) 对应第一个上升位在第 \(2\) 位的排列，再加上 \(n=4\) 偶数时把递减排列 \(4321\) 计入的那 \(1\) 个例外。读者可逐个枚举核对。）

最后，我们指出：除了简单地计数具有给定下降位个数的排列之外，我们还可以计数其下降位集合恰为给定集合 \(S\) 的排列，或者其下降位集合包含于给定集合 \(S\) 的排列。读者可参看习题 2–6 中此类结果。

返回 全书目录