Warning: session_start(): open(/tmp/sess_6aa9f9ed661bcf8f89415b2ffa5f47dd, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 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!}. $$