第一类 Stirling 数

对自然数 $1\le k\le n$, 第一类 Stirling 数分为有符号 $s(n,k)$ 与无符号 $\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ 两类, 分别是降阶乘和升阶乘$$\begin{gathered} x^{\underline{n}}=x(x-1)\cdots (x-n+1), \\ {x}^{\overline{n}}=x(x+1)\cdots (x+n-1) \end{gathered}$$中 $x^k$ 的系数.

无符号第一类 Stirling 数是计数组合中的计数结果, 是将 $n$ 元置换写成 $k$ 个不相交循环置换的方案数.

所有有符号第一类 Stirling 数可以排成一个三角形:$$\begin{array}{c}\text{1}\\ \text{−1}\text{1}\\ \text{2}\text{−3}\text{1}\\ \text{−6}\text{11}\text{−6}\text{1}\\ \text{24}\text{−50}\text{35}\text{−10}\text{1}\\ \text{…}\text{…}\text{…}\text{…}\text{…}\text{…}\end{array}$$其中, 第 $n$ 行的数字是 $s(n,1),$ $\dots ,$ $s(n,n)$. 第 $n$ 行的每个数都是其左上方的数减去其右上方的数的 $n$ 倍.

1定义

定义 1.1 (有符号第一类 Stirling 数). 对自然数 $1\le k\le n$, 有符号第一类 Stirling 数 $s(n,k)$ 是降阶乘$$x^{\underline{n}}=x(x-1)\cdots (x-n+1)$$中 $x^k$ 的系数.

定义 1.2 (无符号第一类 Stirling 数). 对自然数 $1\le k\le n$, 无符号第一类 Stirling 数 $\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ 是升阶乘$$x^{\overline{n}}=x(x+1)\cdots (x+n-1)$$中 $x^k$ 的系数.

2性质

以下设 $1\le k\le n$.

•	$s(n,k)=(-1{)}^{n-k}[\genfrac{}{}{0ex}{}{n}{k}]$.

•

有 $s(n,1)=(-1{)}^{n-1}(n-1)!$, $s(n,n)=1$, 且有递推关系$$s(n,k)=s(n-1,k-1)-ns(n-1,k).$$类似地有 $\left[\genfrac{}{}{0ex}{}{n}{1}\right]=(n-1)!$, $\left[\genfrac{}{}{0ex}{}{n}{n}\right]=1$, 且有递推关系$$\left[\genfrac{}{}{0ex}{}{n}{k}\right]=\left[\genfrac{}{}{0ex}{}{n-1}{k-1}\right]+n\left[\genfrac{}{}{0ex}{}{n-1}{k}\right].$$

•	${\sum }_{k=1}^n\left[\genfrac{}{}{0ex}{}{n}{k}\right]=n!$, 组合意义为任意一个 $n$ 元置换总能写成 $1$ 到 $n$ 个不相交循环置换的并.

•	第一类与第二类 Stirling 数可以视为彼此的逆矩阵: $$\begin{array}{rl}\sum _{j=k}^{n}s(n,j)S(j,k)& ={\delta }_{n,k},\\ \sum _{j=k}^{n}S(n,j)s(j,k)& ={\delta }_{n,k},\end{array}$$其中 ${\delta }_{n,k}$ 为 Kronecker $\delta$ 记号.

术语翻译

第一类 Stirling 数 • 英文 Stirling number of the first kind • 德文 Stirling-Zahl erster Art (f) • 法文 nombre de Stirling de première espèce (m) • 日文 第 1 種 Stirling 数 • 韩文 제1종 Stirling 수