关键词：第二类Stirling数，集合划分，连续对， 反号对合，容斥原理
1. 引言
集合的一个划分是指一组非空的两两不相交的子集(称为块)，它们的并集是该集合。定义 S(n, k ) 为 将 n 元集合划分为 k 个块的划分数。 S (n, k ) 被称为第二类 Stirling 数。众所周知， 第二类 Stirling 数满足 递归关系。
S (n + 1, k) = kS (n, k ) + S (n, k -1) , 0 < k < n. (1. 1)
初始条件为 S(n, n ) = 1, n ≥ 0 ， S (n, 0) = S (0, n ) = 0, n > 0 。
对于固定的整数 k，第二类 Stirling 数{S (n, k )}n≥0 有一个指数型生成函数，由下式给出
(1.2)其他关于 S(n, k ) 的基本性质可以参看文献[1]
第二类 Stirling 数出现在计数组合学的多类问题中。关于第二类 Stirling 数的多个恒等式已通过各种 方法建立，包括组合方法、生成函数、微分方程、特殊函数等。本文的目的是进一步研究 Sheila Sundaram 在文献[2]中得到的一个关于第二类 Stirling 数的恒等式。
我们首先回顾一些相关定义。设 A* 表示在字母表 A 上的具有有限长度的词所构成的自由幺半群。在 A* 上定义子词序 ≤ 如下：若 u 是 v 的子词则定义 u ≤ v 。显然(A* , ≤ ) 是一个分次的偏序集，其秩函数由 词 w 的长度
w
给出，即 w 中包含的字母数。最近，Sheila Sundaram ([2])在研究对称群上关于子词序的具 有特定秩的子偏序集的同调表示时， 建立了以下关于第二类 Stirling 数的恒等式：定理 1. 1 ([2])给定一个固定的正整数 d ≥ 2 ，以下恒等式
对所有 k ≥ d 成立。
Sheila Sundaram 通过证明这个恒等式的两边都是齐次对称函数 h1d hn-d 在 An,k 的顶层同调的 Frobenius特征中的系数推导出了恒等式(1.3)，其中 An,k 表示 A* 的由具有前 k 个非零秩的词和空词组成的子偏序集。她的方法涉及到 Whitney 同调技术。她还提出了两个问题：一是对于固定的 k，能否给出恒等式(1.3)左侧 和式的组合解释？二是能否给出恒等式(1.3)的一个组合证明？本文旨在回答这两个问题，并给出恒等式 (1.3)的另外两个新的证明方法。本文结构如下：在第 2 节中，我们首先给出恒等式(1.3)的归纳证明。在第 3 节中，根据 Mansour 和 Munagi 在文献[3]中的结果，我们指出恒等式(1.3)的左侧计数了具有 d 个块且避 免循环连续对的 [k ]上的集合划分的个数，因此给出了这个恒等式左侧和式的一个组合解释。进而我们给 出了恒等式(1.3)的一个容斥原理证明。在第 4 节中，我们重新构造了Mark Shattuck 在文献[4]中使用的用来证明其他恒等式的一个反号对合给出了恒等式(1.3)的反号对合证明，这可以看作恒等式(1.3)的一个组 合证明。
............ 略 ............
4. 恒等式的第三种证明
在本节中，为了回答 Sheila Sundaram 提出的第二个问题(文献[2]，问题 8.5)，我们将给出恒等式(1.3) 的一个组合证明。具体来说，我们将重新构造一个反号的对合， 这一反号对合曾被 Mark Shattuck 在文献 [4]中用于证明关于第二类 Stirling 数的其他恒等式。为了完整性我们重新给出文献[4]中出现的这一对合。
假设 k 和 d 是给定的满足 2 ≤ d ≤ k 的正整数。对于 d ≤ j ≤ k ，设 Bk ,j 是所有有序对 (S, π ) 的集合，其中 S 是 [k ] 的子集，大小为 k -j ， π 是集合 [k ]\ S 的具有 d 个块的划分。定义 Bk = uj =d Bk ,j 。设 Bk ,j的元素具有符号 (-1)k-j 。则恒等式(1.3)的右侧和式给出了 Bk 的所有元素的符号之和。我们定义一个 Bk 上 的反号对合 φ 如下：
给定 (S, π ) ∈ Bk ，设 r 是 [k ]\ S 中的最小元素，设 s 是 [r +1, k] 中的最小元素，满足以下条件之一：(a) s ∈ S 或者(b) s ∈[k ]\ S 且 s 与 r 位于 π 中同一块。
情形 1：如果 s 存在，我们可以通过以下方式得到一个新的有序对 (S ′, π ′ )：如果(a)发生，则将 s 从 S 移动到 π 中包含 r 的块；如果(b)发生，则将 s 从 π 移动到 S 中。定义 φ (S, π )= (S ′, π ′ )。注意这一运算改 变了符号但保持 r 和 s 不动，且 φ (S ′, π ′ )= (S, π )。例如，若 k = 12 ， j = 8 ， d = 4 ， S = {2, 3, 7,10}，π = 1,5,8,11 / 4 / 6,12 / 9 ，则 r = 1 ， s = 2 ，并且 (S, π ) 对应到 (S ′, π ′ ) ，其中 S ′ = {3, 7,10}， π ′ = 1, 2, 5,8,11/ 4 / 6,12 / 9 。
情形 2：如果 s 不存在，则 S 一定是某个 [l ]的形式，其中 0 ≤ l ≤ k -d (按照惯例设 [0]= ∅ )，并且[k ]\ S 中的最小元素 l +1 在 π 中是一个单元素块。定义 φ (S, π )= (S, π )。也就是说， (S, π ) 是一个不动点。 显然， π 是 [k ]\ [l ] 的具有 d 个块且 l +1 是一个单元素块的划分。如果我们从 π 中删除单元素块 l +1，可 得另一个具有 d -1 个块的 [k ]\ [l +1] 的划分。
容易验证 φ 是 Bk 上的一个反号的对合。因此，恒等式(1.3)的右侧和式简化为
这完成了证明。
注 4.1. 在文献[4]中，Mark Shattuck 通过构造不同的反号对合分别给出了四个恒等式的双射证明。结 合 Shattuck 的恒等式(2)与恒等式(4)，也可以推导出本文的恒等式(1.3)。
参考文献：略
