CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== Stirling 数——理论 ======

==== 定义 1 ====

对于正整数 $n$，$k$，定义 $c(n,k)$ 为 $n$ 元对称群 $S_n$ 中恰含 $k$ 个轮换（即恰可写成 $k$ 个不交轮换的乘积）的置换个数（注意，不动点也看做一个轮换）。称 $s(n,k)=(-1)^{n-k}c(n,k)$ 为 **第一类 Stirling 数**，也常常称 $c(n,k)$ 为 **无符号的第一类 Stirling 数**。

置 $c(0,0)=1$，以及当 $n\ge 1$ 时，$c(n,0)=c(0,n)=0$，这显然是合理的。

==== 引理 2 ====

对任意 $n\geq 1$，$k\ge 1$，$c(n,k)$ 满足递推关系 $$
c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1).
$$ $\Box$

=== 证明 ===

设置换 $\sigma$ 是 $S_n$ 中恰有 $k$ 个轮换的置换。若 $\sigma(n)=n$，则 $n$ 在 $\sigma$ 中为一个单独的轮换，从而这样的 $\sigma$ 的个数等于 $S_{n-1}$ 中恰有 $k-1$ 个轮换的置换个数，即 $c(n-1,k-1)$。若 $\sigma(n)\neq n$，则将轮换 $\sigma$ 中的 $n$ 去掉就得到 $S_{n-1}$ 中含 $k$ 个轮换的置换，从而这样的 $\sigma$ 的个数等于 $S_{n-1}$ 中恰有 $k$ 个轮换的置换个数的 $n-1$ 倍，即 $(n-1)c(n-1,k)$。因此 $$
c(n,k)=(n-1)c(n-1,k)+c(n-1,k).
$$ $\Box$

==== 定理 3 ====

$\{c(n,k)\}_{n=1}^{\infty}$ 满足如下的函数方程： $$
\sum_{k=1}^{n}c(n,k)x^k=x^{\overline{n}}
$$ 其中 $x^{\overline n}=x(x+1)\cdots(x+n-1)$，为 $x$ 的 $n$ 次上升幂。

=== 证明 ===

对 $n$ 用归纳法证明命题。当 $n=1$ 时，命题即 $x=x$，显然成立。

设 $n\ge 2$，且命题对 $n-1$ 成立，则对 $n$，由归纳假设及 $c(n,k)$ 的递推性质知，对任意 $1\le k\le n$，有 $$
\begin{align}
&[x^k]x(x+1)\cdots(x+n-1)\\
&=[x^{k}]x(x+1)\cdots(x+n-2)x+(n-1)([x^k]x(x+1)\cdots(x+n-2))\\
&=[x^{k-1}]x(x+1)\cdots(x+n-2)+(n-1)([x^k]x(x+1)\cdots(x+n-2))\\
&=c(n-1,k-1)+(n-1)c(n-1,k)\\
&=c(n,k),
\end{align}
$$ 从而 $$
\sum_{k=1}^nc(n,k)x^k=x^{\overline n},
$$ 即命题对 $n$ 成立。

由归纳原理知，命题对一切正整数 $n$ 成立，即 $\{c(n,k)\}_{n=1}^{\infty}$ 满足定理中所述的函数方程。

很多情况下，第一类 Stirling 数 $s(n,k)$ 往往比无符号的第一类数 $c(n,k)$ 更容易处理。针对 $\{s(n,k)\}_{n=1}^\infty$，定理 3 相应的等价形式是下面的定理。

==== 定理 4 ====

$\{s(n,k)\}_{n=1}^{\infty}$ 满足如下的函数方程： $$
\sum_{k=1}^{n}s(n,k)x^k=x^{\underline n},
$$ 其中 $x^{\underline n}=x(x-1)\cdots(x-n+1)$.

=== 证明 ===

在定理 3 中，用 $-x$ 代替 $x$，得 $$
\sum_{k=1}^{n}c(n,k)(-x)^k=(-x)(-x+1)\cdots(-x+n-1).
$$ 上式两边同时乘以 $(-1)^n$，得 $$
\sum_{k=1}^n(-1)^nc(n,k)(-x)^k=x(x-1)\cdots(x-n+1),
$$ 即 $$
\sum_{k=1}^ns(n,k)x^k=x^{\underline n}.
$$

==== 定义 5 ====

对于正整数 $n,k$，定义 $S(n,k)$ 为把 $[n]$ 分成 $k$ 个非空子集的划分个数，称之为 **第二类 Stirling 数**。

置 $S(n,0)=S(0,n)=0 (n\ge 1)$ 及 $S(0,0)=1$。

第二类 Stirling 数有着与第一类 Stirling 数对偶的递推关系。

==== 引理 6 ====

对任意 $n\ge 1,k\ge 1$，第二类 Stirling 数 $S(n,k)$ 满足如下递推关系： $$
S(n,k)=kS(n-1,k)+S(n-1,k-1).
$$

=== 证明 ===

把 $[n]$ 分成 $k$ 个非空子集的划分简称为 $[n]$ 的一个 k-划分。设 $P$ 是 $[n]$ 的一个 k-划分。若 $n$ 在 $P$ 中为一个单独的子集，则这样的 $P$ 的个数等于 $[n-1]$ 的 (k–1)-划分个数，即 $S(n-1,k-1)$。若 $n$ 在 $P$ 中不是一个单独的子集，则从 $P$ 中去掉 $n$ 可以得到一个 $[n-1]$ 的 k-划分，而把 $n$ 插入任意一个 $[n-1]$ 的 k-划分可得到 $k$ 个不同的 $[n]$ 的 k-划分，从而这样的 $P$ 的个数等于 $[n-1]$ 的 k-划分个数的 $k$ 倍，即 $kS(n-1,k)$。因此 $$
S(n,k)=kS(n-1,k)+S(n-1,k-1)
$$

==== 定理 7 ====

$\{S(n,k)\}_{n=1}^{\infty}$ 满足如下的函数方程： $$
\sum_{k=1}^nS(n,k)x^{\underline k}=x^n,
$$ 这里 $x^{\underline k}=x(x-1)\cdots(x-k+1)$。

=== 证明 ===

对 $n$ 用归纳法证明命题。当 $n=1$ 时，命题即 $x=x$，显然成立。

设 $n\ge 2$，且命题对 $n-1$ 成立，则对 $n$，由归纳假设及 $S(n,k)$ 的递推性质知 $$
\begin{align}
x^n=x^{n-1}x&=\sum_{k=1}^{n-1}S(n-1,k)x^{\underline k}x\\
&=\sum_{k=1}^{n-1}S(n-1,k)x^{\underline k}(x-k+k)\\
&=\sum_{k=1}^{n-1}S(n-1,k)x^{\underline {k+1}}+\sum_{k=1}^{n-1}kS(n-1,k)x^{\underline k}\\
&=\sum_{k=2}^{n}S(n-1,k-1)x^{\underline k}+\sum_{k=1}^{n-1}kS(n-1,k)x^{\underline k}\\
&=\sum_{k=1}^nS(n-1,k-1)x^{\underline k}+\sum_{k=1}^nkS(n-1,k)x^{\underline k}\\
&=\sum_{k=1}^nS(n,k)x^{\underline k}.
\end{align}
$$ 即命题对 $n$ 成立。

由归纳原理知，命题对一切正整数 $n$ 成立，即 $\{S(n,k)\}_{n=1}^{\infty}$ 满足定理中所述的函数方程。

=== 注 ===

设 $x$ 为一个正整数，则有 $x^n$ 个从 $[n]$ 到 $[x]$ 的映射；对 $[x]$ 的每个 k-子集 $Y$，有 $k!S(n,k)$ 个从 $[n]$ 到 $Y$ 的满射。所以 $$
x^n=\sum_{k=1}^{n}\binom{x}{k}k!S(n,k)=\sum_{k=1}^nS(n,k)x^{\underline k}.
$$

==== 定理 8 ====

由两类 Stirling 数，定义 $n$ 阶矩阵 $A=(a_{ij})_{n\times n}:=(s(i,j))_{n\times n}$ 及 $B=(b_{ij})_{n\times n}:=(S(i,j))_{n\times n}$，则 $$
AB=BA=I.
$$

==== 推论 9 ====

两类 Stirling 数满足如下关系式： $$
\sum_{l=1}^ns(i,l)S(l,j)=\delta(i,j),\\
\sum_{l=1}^nS(i,l)s(l,j)=\delta(i,j).
$$ 其中 $\delta(i,j)=[i==j]$

==== 定理 10 ====

对任意正整数 $n,k$，有 $$
S(n,k)=\frac{1}{k!}\sum_{j=0}^k\binom{k}{j}j^n(-1)^{k-j}.
$$

==== 定理 11 ====

$\{S(n,k)\}_{n=0}^{\infty}$ 的指数型生成函数为 $$
\sum_{n=0}^{\infty}\frac{S(n,k)}{n!}x^n=\frac{(e^x-1)^k}{k!}.
$$

==== 定理 12 ====

令 $A(x),B(x)$ 分别表示数列 $\{a_n\}_{n=0}^{\infty},\{b_n\}_{n=0}^{\infty}$ 的指数型生成函数，则下列三个命题等价：

  * 对任意 $n\ge0$，有 $\displaystyle b_n=\sum_{i=0}^{n}S(n,i)a_i$;
  * 对任意 $n\ge 0$，有 $\displaystyle a_n=\sum_{i=0}^{n}s(n,i)b_i$;
  * $B(x)=A(e^x-1)$，也即 $A(x)=B(\ln(1+x))$.

==== 推论 13 ====

$\{s(n,k)\}_{n=0}^{\infty}$ 的指数型生成函数为 $$
\sum_{n=0}^{\infty}\frac{s(n,k)}{n!}x^n=\frac{(\ln(1+x))^k}{k!}.
$$
CVBB ACM Team

用户工具

站点工具

页面工具
