斯特林数小结

· · 个人记录

1. 第一类斯特林数

第一类斯特林数 \begin{bmatrix} n \\ m \end{bmatrix} 表示将 n 个两两不同的元素划分为 m 个圆排列的方案数。

有递推式 \begin{bmatrix} n \\ m \end{bmatrix}=\begin{bmatrix} n-1 \\ m-1 \end{bmatrix}+\begin{bmatrix} n-1 \\ m \end{bmatrix}*(n-1)。

第一类斯特林数·行

给定 n，对于 i \in [0,n] ，求出 \begin{bmatrix} n \\ i \end{bmatrix} 。

设第 n 行第一类斯特林数的 OGF 为 f_n 。 有 f_n=f_{n-1}*(x+n-1)=x^{\overline{n}} 。倍增 或者 分治NTT 求解即可。

第一类斯特林数·列

给定 n , m，对于 i \in [0,n] ，求出 \begin{bmatrix}i\\m\end{bmatrix} 。

设第一列第一类斯特林数的 EGF 为 f，则 f=\sum\limits_{i=1}\dfrac{(i-1)!}{i!}x^i=\sum\limits_{i=1}\dfrac{x^i}{i} 。

由于 f_m 可以看做 m 个圆排列组合在一起，故有 f_m=f^m 。多项式快速幂即可。

2. 第二类斯特林数

第二类斯特林数 \begin{Bmatrix}n\\m\end{Bmatrix} 表示将 n 个两两不同的元素划分为 m 个集合的方案数。

有递推式 \begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+\begin{Bmatrix}n-1\\m\end{Bmatrix}*m。

同时，第二类斯特林数有另外的性质：

由二项式反演得到 $\begin{Bmatrix}n\\m\end{Bmatrix}=\dfrac{1}{m!}\sum\limits_{i=0}^{m}(-1)^{m-i}\begin{pmatrix}m\\i\end{pmatrix}i^n=\sum\limits_{i=0}^{m}\dfrac{(-1)^{m-i}i^n}{(m-i)!i!}$ 。 ### 第二类斯特林数·行 给定 $n$，对于 $i \in [0,n]$ ，求出 $\begin{Bmatrix} n \\ i \end{Bmatrix}$ 。 设第 $n$ 行第一类斯特林数的 OGF 为 $F_n$ ，$f=\sum\limits_{i=0}\dfrac{(-1)^i}{i!}x^i$ ， $g=\sum\limits_{i=0}\dfrac{i^n}{i!}x^i$ 。 由上述性质可知 $F_n=f*g$ 。 ### 第二类斯特林数·列 给定 $n , m$，对于 $i \in [0,n]$ ，求出 $\begin{Bmatrix}i\\m\end{Bmatrix}$ 。 设第一列第一类斯特林数的 EGF 为 $f$，则 $f=\sum\limits_{i=1}\dfrac{x^i}{i!}$ 。 由于 $f_m$ 可以看做 $m$ 个集合组合在一起，故有 $f_m=f^m$ 。多项式快速幂即可。 # 3. 斯特林反演 $f(n)=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}g(i) \iff g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}g(i) \\ f(n)=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i) \iff g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}g(i) \\ f(n)=\sum\limits_{i=n}\begin{bmatrix}i\\n\end{bmatrix}g(i) \iff g(n)=\sum\limits_{i=n}(-1)^{i-n}\begin{Bmatrix}i\\n\end{Bmatrix}g(i) \\ f(n)=\sum\limits_{i=n}\begin{Bmatrix}i\\n\end{Bmatrix}g(i) \iff g(n)=\sum\limits_{i=n}(-1)^{i-n}\begin{bmatrix}i\\n\end{bmatrix}g(i)

4. 普通幂与上升幂下降幂的转化

\\x^{\overline{n}}=\sum\limits^{n}_{i=0}\begin{bmatrix}n\\i\end{bmatrix}x^i\iff x^i=\sum\limits^{n}_{i=0}(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\overline{n}}

5. 例题

有 m 张牌，其中一张是王牌。现在你执行 n 次如下操作：洗牌后查看第一张牌是什么。 令 x 为洗牌后第一张牌为王牌的次数，现在假设洗牌时 m! 种牌的排列出现的概率均相等，求 x^k 在模 998244353 意义下的期望值。

1 \le n, m < 998244353 , 1 \le k \le 5000

直接上式子：

\\ &= \sum\limits^n_{i=0} \begin{pmatrix}n\\i\end{pmatrix} \dfrac{(m-1)^{n-i}}{m^n} \sum\limits^k_{j=1} \begin{pmatrix}i\\j\end{pmatrix} \begin{Bmatrix}k\\j\end{Bmatrix}j! \\ &= \dfrac{1}{m^n} \sum\limits^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}\sum\limits^n_{i=0}\dfrac{n!}{(n-i)!(i-j)!}(m-1)^{n-i} \\ &= \dfrac{1}{m^n} \sum\limits^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}\sum\limits^n_{i=0}\begin{pmatrix}n-j\\n-i\end{pmatrix}n^{\underline{j}}(m-1)^{n-i} \\ &= \dfrac{1}{m^n} \sum\limits^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}\sum\limits^{n-j}_{i=0}\begin{pmatrix}n-j\\i\end{pmatrix}(m-1)^{i} \\ &= \dfrac{1}{m^n} \sum\limits^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}m^{n-j} \end{aligned}

在 O(k^2) 的时间内预处理出第二类斯特林数，再 O(k) 计算答案。