斯特林数学习笔记

斯特林数入门资料。

第一类斯特林数：

定义：n个不同元素排成m个圆排列的方案数。

无符号:$S_u(n,m)$

有符号:$S_s(n,m)=(-1)^{n+m}S_u(n,m)$

表示法：

$${[x]_{n}}=x(x-1)(x-2)...(x-n+1)=\sum^{n}_{k=0}{s}_{s}(n,k)x^k$$ $${[x]^{n}}=x(x+1)(x+2)...(x+n-1)=\sum^{n}_{k=0}{s}_{u}(n,k)x^k$$ $${s}_{u}(n,m)=\begin{bmatrix}n\\m \end{bmatrix}$$

递推式：

$$\begin{bmatrix}n\\m \end{bmatrix}=\begin{bmatrix}n-1\\m-1 \end{bmatrix}+(n-1)\cdot \begin{bmatrix}n-1\\m \end{bmatrix}$$

一些性质：

$$\begin{bmatrix}0\\0 \end{bmatrix}=1,\begin{bmatrix}n\\0 \end{bmatrix}=0,\begin{bmatrix}n\\n \end{bmatrix}=1,\begin{bmatrix}n\\1 \end{bmatrix}=(n-1)!,\begin{bmatrix}n\\n-1 \end{bmatrix}=C_{n}^{2}$$ $$\begin{bmatrix}n\\2 \end{bmatrix}=(n-1)! \cdot \sum_{i=1}^{n-1} \frac{1}{i}$$ $$\begin{bmatrix}n\\n-2 \end{bmatrix}=2 \cdot C_n^3+3\cdot C_n^4$$

第二类斯特林数:记作$S(n,m)$或$\begin{Bmatrix}n\\m \end{Bmatrix}$

$$\begin{Bmatrix}n\\m \end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m \cdot \begin{Bmatrix}n-1\\m \end{Bmatrix}$$

含义：将n个不同元素拆成m个集合的方案数。

$$\begin{Bmatrix}n\\m \end{Bmatrix}=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k C_m^k (m-k)^n$$

性质：暂坑（抄百科抄累了）

$$\begin{Bmatrix}n\\m\end{Bmatrix}=0 (n<m)$$ $$\begin{Bmatrix}n\\1\end{Bmatrix}=1,\begin{Bmatrix}n\\2\end{Bmatrix}=2^{n-1}-1,\begin{Bmatrix}n\\n\end{Bmatrix}=1,\begin{Bmatrix}n\\n-1\end{Bmatrix}=C_n^2$$ $$m!=\sum_{k=0}^m (-1)^k C_m^k (m-k)^m$$

转换关系：

待补充内容

$$\sum_{n=0}^n(-1)^{n+k}S(n,k)s(k,m)=\sum_{k=0}^n (-1)^{n+k}s(n,k)S(k,m)=[n=m]$$

因为有符号第一类斯特林数的矩阵与第二类斯特林数的矩阵互为逆矩阵。

这部分的证明见待补充部分。

$$\sum_{n=0}^n S(n,k)s(k,m)=\sum_{k=0}^n s(n,k)S(k,m)$$

额外的：

$$n^m=\sum_{k=0}^m \begin{Bmatrix}m\\k \end{Bmatrix}C_n^k k!=\sum_{k=0}^m \begin{Bmatrix}m\\k \end{Bmatrix}\begin{bmatrix}n \end{bmatrix}_k$$ $$k!\begin{Bmatrix}n\\m \end{Bmatrix}=\sum_{i=0}^k(-1)^{k-i}C_k^i i^m$$ $$\begin {Bmatrix}m\\k \end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^{i}C_k^i (k-i)^m=\sum_{i=0}^k\frac{(k-i)^m}{(k-i)!}\frac{(-1)^i}{i!}$$

可以利用上面最右的式子$O(nlogn)$快速求一行。

$$\begin{bmatrix}x\end{bmatrix}^n=\sum_{k=0}^{n}\begin{bmatrix}n\\k \end{bmatrix}x^k$$

斯特林反演公式：

$$f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n+k}\begin {bmatrix} n\\k \end{bmatrix}f(k)$$

第一类斯特林数的生成函数：

$$S_{1,n}=\prod_{k=0}^{n}(x+k)$$

可以利用这个生成函数快速求一行。