1. 引言

集合的一个划分是指一组非空的两两不相交的子集(称为块)，它们的并集是该集合。定义 $S\left(n,k\right)$ 为将n元集合划分为k个块的划分数。 $S\left(n,k\right)$ 被称为第二类Stirling数。众所周知，第二类Stirling数满足递归关系

$S\left(n+1,k\right)=kS\left(n,k\right)+S\left(n,k-1\right),0<k<n.$ (1.1)

初始条件为 $S\left(n,n\right)=1,n\ge 0$ ， $S\left(n,0\right)=S\left(0,n\right)=0,n>0$ 。

对于固定的整数k，第二类Stirling数 ${\left\{S\left(n,k\right)\right\}}_{n\ge 0}$ 有一个指数型生成函数，由下式给出

${\displaystyle {\sum }_{n=k}^{\infty }S\left(n,k\right)\frac{x^n}{n!}}=\frac{{\left(E^x-1\right)}^k}{k!}.$ (1.2)

其他关于 $S\left(n,k\right)$ 的基本性质可以参看文献[1]。

第二类Stirling数出现在计数组合学的多类问题中。关于第二类Stirling数的多个恒等式已通过各种方法建立，包括组合方法、生成函数、微分方程、特殊函数等。本文的目的是进一步研究Sheila Sundaram在文献[2]中得到的一个关于第二类Stirling数的恒等式。

我们首先回顾一些相关定义。设 $A^{\text{*}}$ 表示在字母表A上的具有有限长度的词所构成的自由幺半群。在 $A^{\text{*}}$ 上定义子词序 ≤ 如下：若u是v的子词则定义 $u\le v$ 。显然 $\left(A^{\text{*}},\le \right)$ 是一个分次的偏序集，其秩函数由词w的长度 $\left|w\right|$ 给出，即w中包含的字母数。最近，Sheila Sundaram ([2])在研究对称群上关于子词序的具有特定秩的子偏序集的同调表示时，建立了以下关于第二类Stirling数的恒等式：

定理1.1 ([2])给定一个固定的正整数 $d\ge 2$ ，以下恒等式

${\displaystyle {\sum }_{j=d}^k{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)}={\displaystyle {\sum }_{j=d}^k{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ k-j\end{array}\right)S\left(j,d\right)}$ (1.3)

对所有 $k\ge d$ 成立。

Sheila Sundaram通过证明这个恒等式的两边都是齐次对称函数 $h_1^d{h}_{n-d}$ 在 $A_{n,k}^{*}$ 的顶层同调的Frobenius特征中的系数推导出了恒等式(1.3)，其中 $A_{n,k}^{*}$ 表示 $A^{\text{*}}$ 的由具有前k个非零秩的词和空词组成的子偏序集。她的方法涉及到Whitney同调技术。她还提出了两个问题：一是对于固定的k，能否给出恒等式(1.3)左侧和式的组合解释？二是能否给出恒等式(1.3)的一个组合证明？本文旨在回答这两个问题，并给出恒等式(1.3)的另外两个新的证明方法。本文结构如下：在第2节中，我们首先给出恒等式(1.3)的归纳证明。在第3节中，根据Mansour和Munagi在文献[3]中的结果，我们指出恒等式(1.3)的左侧计数了具有d个块且避免循环连续对的 $\left[k\right]$ 上的集合划分的个数，因此给出了这个恒等式左侧和式的一个组合解释。进而我们给出了恒等式(1.3)的一个容斥原理证明。在第4节中，我们重新构造了Mark Shattuck在文献[4]中使用的用来证明其他恒等式的一个反号对合给出了恒等式(1.3)的反号对合证明，这可以看作恒等式(1.3)的一个组合证明。

2. 恒等式的第一种证明

为了给出恒等式(1.3)的归纳证明，我们逆向分析发现下面的一个恒等式起着关键作用。下面先以引理的形式给出此恒等式：

引理2.1 ([5])

$dS\left(k,d\right)={\displaystyle {\sum }_{j=d}^k{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ j-1\end{array}\right)S\left(j,d\right)}$ .

为了完整性，我们重新给出Ira Gessel在文献[5]中给出的关于此式的简短证明。

证明：正如Ira Gessel在[5]中指出的，我们可以利用恒等式(1.2)，并从以下恒等式的两边提取 $x^k/k!$ 的系数：

$d\frac{{\left({\text{e}}^x-1\right)}^d}{d!}=\left(1-{\text{e}}^{-x}\right)\frac{\text{d}}{\text{d}x}\frac{{\left({\text{e}}^x-1\right)}^d}{d!}.$

上式立即得证。

现在我们给出恒等式(1.3)的第一种证明。我们对k进行归纳。当 $k=d$ 时，因为 $S\left(d-\text{1},d-\text{1}\right)=S\left(d,d\right)=\text{1}$ ，显然左右两边都等于1。对于 $k\ge d$ ，假设等式对k成立，即我们有恒等式

$\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)=\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ j\end{array}\right)S\left(j,d\right).$

我们需要证明等式对 $k+1$ 也成立。为了证明这一点，注意

$\begin{array}{c}R.H.S.=\underset{j=d}{\overset{k+1}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k+1\\ j\end{array}\right)S\left(j,d\right)\\ =\underset{j=d}{\overset{k+1}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j+1}\left[\left(\begin{array}{c}k\\ j-1\end{array}\right)+\left(\begin{array}{c}k\\ j\end{array}\right)\right]S\left(j,d\right)\\ =\underset{j=d}{\overset{k+1}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k\\ j-1\end{array}\right)S\left(j,d\right)+\underset{j=d}{\overset{k+1}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k\\ j\end{array}\right)S\left(j,d\right)\\ =\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k\\ j-1\end{array}\right)S\left(j,d\right)+S\left(k+1,d\right)-\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ j\end{array}\right)S\left(j,d\right).\end{array}$

根据引理2.1，我们可以将上述的第一个和式替换为 $-dS\left(k,d\right)$ 。根据归纳假设，我们可以将上述的第二个和式替换为 $-{\displaystyle {\sum }_{j=d}^k{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)}$ 。因此

$\begin{array}{c}R.H.S.=-dS\left(k,d\right)+S\left(k+1,d\right)-\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)\\ =S\left(k,d-1\right)-\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)\\ =\underset{j=d}{\overset{k+1}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j+1}S\left(j-1,d-1\right)=L.H.S.\end{array}$

其中我们使用了递归关系(1.1)从第一行的式子推导到第二行的式子。根据数学归纳法，证明完成。

3. 恒等式的第二种证明

在本节中，我们首先给出恒等式(1.3)左侧和式的一个组合解释，这一组合解释源自于Mansour和Munagi在文献[3]中的结果。进而使用容斥原理，我们给出恒等式(1.3)的第二种证明。

回顾一下在文献[3]中， $\left[n\right]$ 上的一个集合划分的循环连续对被定义为一个有序对 $\left(a,b\right)$ ，它位于该集合划分的同一个块中，且满足 $b-a\equiv 1\left(\mathrm{mod}n\right)$ 。换句话说，循环连续对指一对相邻的整数对或者整数对 $\left(n,1\right)$ 。如果 $\left[n\right]$ 的集合划分的任何一个块包含循环连续对，则称该划分包含循环连续对。否则，称该划分避免循环连续对。设 $c_r\left(n,k\right)$ 表示有k个块且包含r个循环连续对的 $\left[n\right]$ 的集合划分数，因此 $c_0\left(n,k\right)$ 表示有k个块且避免循环连续对的 $\left[n\right]$ 的划分数。在[3]中，Mansour和Munagi使用生成函数(文献[3]，推论11)得到了 $c_0\left(n,k\right)$ 的具体表达式，即

$c_0\left(n,k\right)=\underset{j=0}{\overset{n-1}{{\displaystyle \sum }}}{\left(-1\right)}^{j}S\left(n-1-j,k-1\right).$

因此

$\begin{array}{c}{c}_0\left(k,d\right)=\underset{j=0}{\overset{k-1}{{\displaystyle \sum }}}{\left(-1\right)}^{j}S\left(k-1-j,d-1\right)\\ =\underset{j=1}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)\\ =\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right).\end{array}$

由此我们立即看出恒等式(1.3)的左侧和式恰好计数了 $\left[k\right]$ 的包含d个块且避免循环连续对的集合划分的个数，从而回答了Sheila Sundaram提出的第一个问题(文献[2]，问题8.6)。

值得一提的是，根据Mansour和Munagi在文献[3]中的结果，也可以推导出恒等式(1.3)。事实上，Mansour和Munagi通过指数型生成函数得到了 $c_r\left(n,k\right)$ 的一个具体表达式(文献[3]，推论14)，即

$c_r\left(n,k\right)=\left(\begin{array}{c}n\\ r\end{array}\right)\underset{j=k}{\overset{n-r}{{\displaystyle \sum }}}{\left(-1\right)}^{n-r-j}\left(\begin{array}{c}n-r\\ j\end{array}\right)S\left(j,k\right).$

设 $r=0$ 得到

$c_0\left(k,d\right)=\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ j\end{array}\right)S\left(j,d\right)=\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ k-j\end{array}\right)S\left(j,d\right),$

这恰好是恒等式(1.3)的右侧，恒等式(1.3)立即得证。

接下来我们给出恒等式(1.3)的容斥原理证明。设 $A_i\left(1\le i\le k\right)$ 表示 $\left[k\right]$ 的具有d个块且包含循环连续对 $\left(i,i+1\right)$ 的划分的集合，(当 $i=k$ 时， $i+1$ 表示 $i+1\mathrm{mod}k$ )。显然，这k个集合的补集的交集 $\overline{A_1}\cap \overline{A_2}\cdots \cap \overline{A_k}$ 表示 $\left[k\right]$ 的具有d个块且避免循环连续对的划分的集合，从而

$\left|\overline{A_1}\cap \overline{A_2}\cdots \cap \overline{A_k}\right|=c_0\left(k,d\right)=\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right).$

容易看出 $\left[k\right]$ 的具有d个块且包含循环连续对 $\left(1,2\right)$ 的划分与集合 $\left\{2,3,\cdots ,k\right\}$ 的具有d个块的划分一一对应，因此 $\left|A_1\right|=S\left(k-1,d\right)$ 。同理 $\left|A_i\right|=S\left(k-1,d\right)$ 对任意 $2\le i\le k$ 均成立。进一步地， $\left[k\right]$ 的具有d个块且同时包含循环连续对 $\left(1,2\right),\left(2,3\right)$ 的划分与集合 $\left\{3,\cdots ,k\right\}$ 的具有d个块的划分一一对应，因此 $\left|A_1\cap A_2\right|=S\left(k-2,d\right)$ 。同理 $\left|A_i\cap A_j\right|=S\left(k-2,d\right)$ 对任意 $1\le i<j\le k$ 均成立。一般地，不难得到对于任何满足 $1\le i_1<i_2<\cdots <i_j\le k$ 的 $\left(i_1,i_2,\cdots ,i_j\right)\left(j\ge 1\right)$ ，有 $\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_j}\right|=S\left(k-j,d\right)$ 。因此根据容斥原理我们得到

$\begin{array}{l}\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)=c_0\left(k,d\right)\\ =\left|\overline{A_1}\cap \overline{A_2}\cdots \cap \overline{A_k}\right|\\ =S\left(k,d\right)+\underset{j=1}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^j\underset{1\le i_1<i_2<\cdots <i_j\le k}{{\displaystyle \sum }}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_j}\right|\\ =\underset{j=0}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^j\left(\begin{array}{c}k\\ j\end{array}\right)S\left(k-j,d\right)=\underset{j=0}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ k-j\end{array}\right)S\left(j,d\right).\end{array}$

4. 恒等式的第三种证明

在本节中，为了回答Sheila Sundaram提出的第二个问题(文献[2]，问题8.5)，我们将给出恒等式(1.3)的一个组合证明。具体来说，我们将重新构造一个反号的对合，这一反号对合曾被Mark Shattuck在文献[4]中用于证明关于第二类Stirling数的其他恒等式。为了完整性我们重新给出文献[4]中出现的这一对合。

假设k和d是给定的满足 $2\le d\le k$ 的正整数。对于 $d\le j\le k$ ，设 $B_{k,j}$ 是所有有序对 $\left(S,\pi \right)$ 的集合，其中S是 $\left[k\right]$ 的子集，大小为 $k-j$ ， $\pi$ 是集合 $\left[k\right]\backslash S$ 的具有d个块的划分。定义 $B_k={\displaystyle {\cup }_{j=d}^k{B}_{k,j}}$ 。设 $B_{k,j}$ 的元素具有符号 ${\left(-1\right)}^{k-j}$ 。则恒等式(1.3)的右侧和式给出了 $B_k$ 的所有元素的符号之和。我们定义一个 $B_k$ 上的反号对合 $\varphi$ 如下：

给定 $\left(S,\pi \right)\in B_k$ ，设r是 $\left[k\right]\backslash S$ 中的最小元素，设s是 $\left[r+1,k\right]$ 中的最小元素，满足以下条件之一：(a) $s\in S$ 或者(b) $s\in \left[k\right]\backslash S$ 且s与r位于 $\pi$ 中同一块。

情形1：如果s存在，我们可以通过以下方式得到一个新的有序对 $\left(S^{\prime },{\pi }^{\prime }\right)$ ：如果(a)发生，则将s从S移动到 $\pi$ 中包含r的块；如果(b)发生，则将s从 $\pi$ 移动到S中。定义 $\varphi \left(S,\pi \right)=\left(S^{\prime },{\pi }^{\prime }\right)$ 。注意这一运算改变了符号但保持r和s不动，且 $\varphi \left(S^{\prime },{\pi }^{\prime }\right)=\left(S,\pi \right)$ 。例如，若 $k=12$ ， $j=8$ ， $d=4$ ， $S=\left\{2,3,7,10\right\}$ ， $\pi =1,5,8,11/4/6,12/9$ ，则 $r=1$ ， $s=2$ ，并且 $\left(S,\pi \right)$ 对应到 $\left(S^{\prime },{\pi }^{\prime }\right)$ ，其中 $S^{\prime }=\left\{3,7,10\right\}$ ， ${\pi }^{\prime }=1,2,5,8,11/4/6,12/9$ 。

情形2：如果s不存在，则S一定是某个 $\left[l\right]$ 的形式，其中 $0\le l\le k-d$ (按照惯例设 $\left[0\right]=\varnothing$ )，并且 $\left[k\right]\backslash S$ 中的最小元素 $l+1$ 在 $\pi$ 中是一个单元素块。定义 $\varphi \left(S,\pi \right)=\left(S,\pi \right)$ 。也就是说， $\left(S,\pi \right)$ 是一个不动点。显然， $\pi$ 是 $\left[k\right]\backslash \left[l\right]$ 的具有d个块且 $l+1$ 是一个单元素块的划分。如果我们从 $\pi$ 中删除单元素块 $l+1$ ，可得另一个具有 $d-1$ 个块的 $\left[k\right]\backslash \left[l+1\right]$ 的划分。

容易验证 $\varphi$ 是 $B_k$ 上的一个反号的对合。因此，恒等式(1.3)的右侧和式简化为

$\underset{\left(S,\pi \right)是一�不��}{{\displaystyle \sum }}{\left(-1\right)}^{\left|S\right|}=\underset{j=0}{\overset{k-d}{{\displaystyle \sum }}}{\left(-1\right)}^{j}S\left(k-j-1,d-1\right)=\underset{j=d}{\overset{k}{{\displaystyle \sum }}}{\left(-1\right)}^{k-j}S\left(j-1,d-1\right).$

这完成了证明。

注4.1. 在文献[4]中，Mark Shattuck通过构造不同的反号对合分别给出了四个恒等式的双射证明。结合Shattuck的恒等式(2)与恒等式(4)，也可以推导出本文的恒等式(1.3)。

NOTES

^*通讯作者。

参考文献