关于第二类Stirling数的一个恒等式的三种证明

Three Proofs of an Identity Involving Stirling Numbers of the Second Kind

摘要: Sheila Sundaram在研究对称群上关于子词序的具有特定秩的子偏序集的同调表示时，得到了一个关于第二类Stirling数的恒等式，并提出如何给出此恒等式的一个组合证明这样一个公开问题。本文旨在给出此恒等式的两个新的证明以及重新构造前人使用的一个反号对合以给出一个对合证明，从而回答了Sundaram提出的问题。此外，我们还给出了此恒等式左侧和式的一个组合解释，这一组合解释源自于Mansour和Munagi的结果。

Abstract: Sheila Sundaram obtained an identity between Stirling numbers of the second kind while studying representations of the symmetric group on the homology of rank-selected subposets of subword order. She posed an open question that how to give a combinatorial proof of this identity. The aim of the paper is to present two new proofs as well as reproduce a sign-reversing involution proof of this curious identity, thereby answering the question posed by Sundaram. Moreover, we also provide a combinatorial interpretation of the left-hand side of this identity which is originally due to Mansour and Munagi.

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成立，即我们有恒等式

${\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\\ j\end{array}\right)S\left(j,d\right).$

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

$\begin{array}{c}R.H.S.={\displaystyle \sum }_{j=d}^{k+1}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k+1\\ j\end{array}\right)S\left(j,d\right)\\ ={\displaystyle \sum }_{j=d}^{k+1}{\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)\\ ={\displaystyle \sum }_{j=d}^{k+1}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k\\ j-1\end{array}\right)S\left(j,d\right)+{\displaystyle \sum }_{j=d}^{k+1}{\left(-1\right)}^{k-j+1}\left(\begin{array}{c}k\\ j\end{array}\right)S\left(j,d\right)\\ ={\displaystyle \sum }_{j=d}^k{\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)-{\displaystyle \sum }_{j=d}^k{\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)-{\displaystyle \sum }_{j=d}^k{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)\\ =S\left(k,d-1\right)-{\displaystyle \sum }_{j=d}^k{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)\\ ={\displaystyle \sum }_{j=d}^{k+1}{\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)={\displaystyle \sum }_{j=0}^{n-1}{\left(-1\right)}^{j}S\left(n-1-j,k-1\right).$

因此

$\begin{array}{c}{c}_0\left(k,d\right)={\displaystyle \sum }_{j=0}^{k-1}{\left(-1\right)}^{j}S\left(k-1-j,d-1\right)\\ ={\displaystyle \sum }_{j=1}^k{\left(-1\right)}^{k-j}S\left(j-1,d-1\right)\\ ={\displaystyle \sum }_{j=d}^k{\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){\displaystyle \sum }_{j=k}^{n-r}{\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)={\displaystyle \sum }_{j=d}^k{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ j\end{array}\right)S\left(j,d\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)的右侧，恒等式(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)={\displaystyle \sum }_{j=d}^k{\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}{\displaystyle \sum }_{j=d}^k{\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)+{\displaystyle \sum }_{j=1}^k{\left(-1\right)}^j{\displaystyle \sum }_{1\le i_1<i_2<\cdots <i_j\le k}\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_j}\right|\\ ={\displaystyle \sum }_{j=0}^k{\left(-1\right)}^j\left(\begin{array}{c}k\\ j\end{array}\right)S\left(k-j,d\right)={\displaystyle \sum }_{j=0}^k{\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)的右侧和式简化为

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

这完成了证明。

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

NOTES

^*通讯作者。