aiwiki.page
中文
数学 / 离散数学与逻辑 / stirling-numbers

斯特林数

斯特林数是两类整数,分别按循环个数计数置换、按块数计数集合划分,并联系普通幂与阶乘幂。

25 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
组合数学整数置换集合划分概率空集阶乘递推关系斯特林数

斯特林数是组合数学中两类密切相关的整数。第一类斯特林数按循环个数对置换进行计数,第二类斯特林数则计算将一个集合分成指定数量的非空块的集合划分数。从代数角度看,它们是普通幂与阶乘幂相互转换时的系数。它们广泛应用于计数、有限差分、概率论以及多项式运算。

斯特林数得名于苏格兰数学家詹姆斯·斯特林,他在1730年的著作《差分法》(Methodus Differentialis)中研究了这些数。虽然它们与用于估计阶乘的斯特林近似公式都以斯特林命名,但两者是不同的数学对象。

定义与记号

对于非负整数 nn 和 kk,无符号第一类斯特林数

[nk]\left[{n\atop k}\right]

表示一个含 nn 个元素的集合上,不相交循环分解中恰有 kk 个循环的置换个数。它也常记作 c(n,k)c(n,k)。

第二类斯特林数

{nk}\left\{{n\atop k}\right\}

表示将一个含 nn 个元素的集合划分为恰好 kk 个非空、无序块的方法数。它也常记作 S(n,k)S(n,k)。

有符号第一类斯特林数定义为

s(n,k)=(−1)n−k[nk].s(n,k)=(-1)^{n-k}\left[{n\atop k}\right].

不同文献采用的记号不尽相同:尤其是“第一类斯特林数”既可能指有符号形式,也可能指无符号形式,因此必须明确所采用的约定。

边界值为

[00]={00}=1,\left[{0\atop0}\right] = \left\{{0\atop0}\right\} =1,

且当 n>0n>0 时,

[n0]={n0}=0.\left[{n\atop0}\right] = \left\{{n\atop0}\right\} =0.

当 k>nk>n 时,两类数均为零。在 (0,0)(0,0) 处取值为一,对应于唯一的空置换,以及将空集划分为零个块的唯一方式。

组合解释

第一类:按循环个数计数置换

一个循环描述了若干不同元素的一种环形排列。循环移位表示同一个循环:例如,(1 2 3)(1\,2\,3)、(2 3 1)(2\,3\,1) 和 (3 1 2)(3\,1\,2) 表示相同的置换。列出各个不相交循环时,它们的先后顺序也不影响结果。

对于一个三元素集合,其置换按循环个数分布如下:

  • 有两个置换含一个循环:(1 2 3)(1\,2\,3) 和 (1 3 2)(1\,3\,2)。
  • 有三个置换含两个循环:(1 2)(3)(1\,2)(3)、(1 3)(2)(1\,3)(2) 和 (2 3)(1)(2\,3)(1)。
  • 有一个置换含三个循环:(1)(2)(3)(1)(2)(3)。

因此,

[31]=2,[32]=3,[33]=1.\left[{3\atop1}\right]=2,\qquad \left[{3\atop2}\right]=3,\qquad \left[{3\atop3}\right]=1.

对所有可能的循环个数求和,就得到置换的总数:

∑k=0n[nk]=n!,\sum_{k=0}^{n}\left[{n\atop k}\right]=n!,

其中 n!n! 表示阶乘。

第二类:划分为块

集合划分是将一个集合分成若干两两不相交的非空子集,且这些子集的并集为原集合。块之间的顺序以及块内元素的顺序都不影响划分。

例如,

{32}=3,\left\{{3\atop2}\right\}=3,

因为将 {1,2,3}\{1,2,3\} 划分为两个块的方式为

{{1},{2,3}},{{2},{1,3}},{{3},{1,2}}.\{\{1\},\{2,3\}\},\qquad \{\{2\},\{1,3\}\},\qquad \{\{3\},\{1,2\}\}.

两类斯特林数之间有如下关系:

[nk]=∑π∏B∈π(∣B∣−1)!,\left[{n\atop k}\right] = \sum_{\pi}\prod_{B\in\pi}(|B|-1)!,

其中求和遍历所有分成 kk 个块的划分 π\pi。每个块 BB 都有 (∣B∣−1)!(|B|-1)! 种排列成循环的方式。因此,第一类斯特林数所计数的,是每个块都带有循环次序的集合划分。

递推关系

两类斯特林数都满足三角形形式的递推关系。

对于无符号第一类斯特林数,

[nk]=[n−1k−1]+(n−1)[n−1k],n≥1.\left[{n\atop k}\right] = \left[{n-1\atop k-1}\right] +(n-1)\left[{n-1\atop k}\right], \qquad n\ge1.

为说明这一点,选定标号为 nn 的元素。它要么单独构成一个循环,其余元素构成 k−1k-1 个循环;要么插入已有循环中,紧接在其余 n−1n-1 个元素中的某一个之后。

对于有符号第一类斯特林数,相应的关系为

s(n,k)=s(n−1,k−1)−(n−1)s(n−1,k).s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k).

对于第二类斯特林数,

{nk}={n−1k−1}+k{n−1k},n≥1.\left\{{n\atop k}\right\} = \left\{{n-1\atop k-1}\right\} +k\left\{{n-1\atop k}\right\}, \qquad n\ge1.

这里,选定的元素要么单独构成一个块,要么加入已有的 kk 个块之一。

最初几行的数值如下:

nn 无符号第一类,k=0,…,nk=0,\ldots,n 第二类,k=0,…,nk=0,\ldots,n
0 1 1
1 0, 1 0, 1
2 0, 1, 1 0, 1, 1
3 0, 2, 3, 1 0, 1, 3, 1
4 0, 6, 11, 6, 1 0, 1, 7, 6, 1
5 0, 24, 50, 35, 10, 1 0, 1, 15, 25, 10, 1

一些有用的特殊值包括

[n1]=(n−1)!,{n1}=1(n≥1),\left[{n\atop1}\right]=(n-1)!, \qquad \left\{{n\atop1}\right\}=1 \quad(n\ge1),

以及

[nn]={nn}=1.\left[{n\atop n}\right] = \left\{{n\atop n}\right\}=1.

在紧邻主对角线下方的位置,两类数都等于一个二项式系数:

[nn−1]={nn−1}=(n2)(n≥2).\left[{n\atop n-1}\right] = \left\{{n\atop n-1}\right\} = \binom n2 \quad(n\ge2).

阶乘幂与基变换

下降阶乘幂和上升阶乘幂分别定义为

xn‾=x(x−1)⋯(x−n+1),x^{\underline n}=x(x-1)\cdots(x-n+1),
xn‾=x(x+1)⋯(x+n−1),x^{\overline n}=x(x+1)\cdots(x+n-1),

其中,当 n=0n=0 时,两式均等于 11。

斯特林数可由以下多项式恒等式刻画:

xn‾=∑k=0ns(n,k)xk,x^{\underline n} = \sum_{k=0}^{n}s(n,k)x^k,
xn‾=∑k=0n[nk]xk,x^{\overline n} = \sum_{k=0}^{n}\left[{n\atop k}\right]x^k,

以及

xn=∑k=0n{nk}xk‾.x^n = \sum_{k=0}^{n} \left\{{n\atop k}\right\}x^{\underline k}.

例如,

x3‾=x3−3x2+2x,x^{\underline3}=x^3-3x^2+2x,

而

x3=x3‾+3x2‾+x1‾.x^3=x^{\underline3}+3x^{\underline2}+x^{\underline1}.

因此,普通幂和下降阶乘幂分别构成多项式向量空间的两组基,而有符号第一类斯特林数和第二类斯特林数则给出了互逆的基变换系数。

对于任意固定的次数上界 NN,下三角矩阵

A=(s(n,k))0≤n,k≤N,B=({nk})0≤n,k≤NA=(s(n,k))_{0\le n,k\le N}, \qquad B=\left(\left\{{n\atop k}\right\}\right)_{0\le n,k\le N}

满足 AB=BA=IAB=BA=I。等价地,

∑j=kns(n,j){jk}=δn,k,\sum_{j=k}^{n}s(n,j)\left\{{j\atop k}\right\} =\delta_{n,k},
∑j=kn{nj}s(j,k)=δn,k,\sum_{j=k}^{n}\left\{{n\atop j}\right\}s(j,k) =\delta_{n,k},

其中,当 n=kn=k 时,δn,k\delta_{n,k} 为 11,否则为 00。

由此得到斯特林反演:若两个数列满足

bn=∑k=0n{nk}ak,b_n=\sum_{k=0}^{n}\left\{{n\atop k}\right\}a_k,

则可通过

an=∑k=0ns(n,k)bk.a_n=\sum_{k=0}^{n}s(n,k)b_k.

恢复原数列。

显式公式与生成函数

第二类斯特林数的显式公式

由容斥原理可得

{nk}=1k!∑j=0k(−1)k−j(kj)jn.\left\{{n\atop k}\right\} = \frac1{k!} \sum_{j=0}^{k} (-1)^{k-j}\binom kj j^n.

事实上,k!{nk}k!\left\{{n\atop k}\right\} 计算的是从一个 nn 元素集合到一个元素带标号的 kk 元素集合的满射函数数。容斥原理剔除了遗漏一个或多个目标元素的函数;再除以 k!k!,便去除了所得各块的标号。对于边界情形 n=k=0n=k=0,该公式采用组合数学中的约定 00=10^0=1。

指数生成函数

对于固定的 kk,指数生成函数为

∑n=k∞{nk}znn!=(ez−1)kk!,\sum_{n=k}^{\infty} \left\{{n\atop k}\right\}\frac{z^n}{n!} = \frac{(e^z-1)^k}{k!},
∑n=k∞[nk]znn!=[−log⁡(1−z)]kk!,\sum_{n=k}^{\infty} \left[{n\atop k}\right]\frac{z^n}{n!} = \frac{[-\log(1-z)]^k}{k!},

以及

∑n=k∞s(n,k)znn!=[log⁡(1+z)]kk!.\sum_{n=k}^{\infty}s(n,k)\frac{z^n}{n!} = \frac{[\log(1+z)]^k}{k!}.

这些恒等式在形式幂级数的意义下成立;其中的对数表达式在 z=0z=0 附近也具有通常的解析意义。

二元形式包括

∑n=0∞∑k=0n{nk}ukznn!=exp⁡ ⁣(u(ez−1)),\sum_{n=0}^{\infty}\sum_{k=0}^{n} \left\{{n\atop k}\right\}u^k\frac{z^n}{n!} = \exp\!\bigl(u(e^z-1)\bigr),

以及

∑n=0∞∑k=0n[nk]ukznn!=(1−z)−u.\sum_{n=0}^{\infty}\sum_{k=0}^{n} \left[{n\atop k}\right]u^k\frac{z^n}{n!} = (1-z)^{-u}.

对于固定的 kk,第二类斯特林数还有如下普通生成函数:

∑n=k∞{nk}zn=zk(1−z)(1−2z)⋯(1−kz).\sum_{n=k}^{\infty} \left\{{n\atop k}\right\}z^n = \frac{z^k}{(1-z)(1-2z)\cdots(1-kz)}.

应用

贝尔数与函数计数

一个 nn 元素集合的划分总数为贝尔数

Bn=∑k=0n{nk}.B_n=\sum_{k=0}^{n}\left\{{n\atop k}\right\}.

其指数生成函数为

∑n=0∞Bnznn!=exp⁡(ez−1).\sum_{n=0}^{\infty}B_n\frac{z^n}{n!} = \exp(e^z-1).

更一般地,

mn=∑k=0n{nk}mk‾m^n = \sum_{k=0}^{n} \left\{{n\atop k}\right\}m^{\underline k}

按照实际取到的值的个数 kk,对从一个 nn 元素集合到一个 mm 元素集合的函数进行计数。具体而言,先将定义域划分为非空的原像集,再给这些原像集分配互不相同的目标值。

概率论中的矩

对于随机变量 XX,普通矩与阶乘矩之间有如下关系:

E[Xn]=∑k=0n{nk}E[Xk‾],\mathbb E[X^n] = \sum_{k=0}^{n} \left\{{n\atop k}\right\} \mathbb E[X^{\underline k}],

以及

E[Xn‾]=∑k=0ns(n,k)E[Xk],\mathbb E[X^{\underline n}] = \sum_{k=0}^{n}s(n,k)\mathbb E[X^k],

前提是相关的期望值存在。

若 XX 服从参数为 λ\lambda 的泊松分布,则

E[Xk‾]=λk,\mathbb E[X^{\underline k}]=\lambda^k,

因此

E[Xn]=∑k=0n{nk}λk.\mathbb E[X^n] = \sum_{k=0}^{n}\left\{{n\atop k}\right\}\lambda^k.

当 λ=1\lambda=1 时,nn 阶普通矩为 BnB_n。

若等概率地选取一个 nn 元素置换,则其循环个数 CnC_n 的分布为

Pr⁡(Cn=k)=[nk]n!.\Pr(C_n=k)=\frac{\left[{n\atop k}\right]}{n!}.

对于 n≥1n\ge1,其概率生成函数为

E[tCn]=t(t+1)⋯(t+n−1)n!,\mathbb E[t^{C_n}] = \frac{t(t+1)\cdots(t+n-1)}{n!},

由此可得

E[Cn]=∑j=1n1j\mathbb E[C_n]=\sum_{j=1}^{n}\frac1j

。

有限差分

对于前向差分算子

Δf(x)=f(x+1)−f(x),\Delta f(x)=f(x+1)-f(x),

下降阶乘幂满足

Δxk‾=kxk−1‾.\Delta x^{\underline k} = k x^{\underline{k-1}}.

这与导数作用于普通幂的规律相对应。因此,

Δk(xn)∣x=0=k!{nk}.\left.\Delta^k(x^n)\right|_{x=0} = k!\left\{{n\atop k}\right\}.

由此,斯特林数将幂基下的计算与有限差分方法及多项式插值联系起来。

计算与数值问题

三角形递推关系提供了直接进行精确计算的方法。计算到第 nn 行为止的所有条目,需要 O(n2)O(n^2) 次算术运算。如果只需要其中一行,可以通过从右向左更新同一个数组,将存储空间减少到 O(n)O(n) 个整数。

这些界限衡量的是算术运算次数,而非位复杂度:由于各条目的数值增长很快,整数运算的成本也会随 nn 的增大而增加。

第二类斯特林数的交错求和显式公式适合符号运算,但在浮点运算中,数值很大的中间项可能发生严重的相消。当需要精确值时,采用精确整数运算的递推计算可以避免这一问题。近似公式还必须说明 nn 与 kk 之间的关系:kk 固定的情形与 kk 随 nn 增长的情形有很大差别。