从零开始的斯特林数问题

全力施工中。

第一类斯特林数

定义

轮换斯特林数\(s(n,m)=\begin{bmatrix}n\\m\end{bmatrix}\)表示将n个元素分成为m个环的方案数。

递推式 \(s(n,m)=s(n-1,m-1)+(n-1)s(n-1,m)\)，边界\(s(0,0)=1\)。

性质

\[ \begin{aligned} &\sum_{i=0}^ns(n,i)=n!\&\sum_{i=0}^ns(n,i)(-1)^i=0(n\ge2)\&\sum_{i=0}^ns(n,i)x^i=x^{\overline{n}}\&\sum_{i=0}^ns(n,i)(-1)^{n-i}x^i=x^{\underline{n}} \end{aligned} \]

证明自行操作。

母函数

设它的母函数为\(G_n(x)\)，易知
\[ G_n(x)=x^\overline{n}=\prod_{i=0}^{n-1}(x+i) \]
然后是分治FFT的过程。

第二类斯特林数

定义

子集斯特林数\(S(n,m)=\begin{Bmatrix}n\\m\end{Bmatrix}\)表示将n个元素分成m个组的方案数。

递推式 \(S(n,m)=S(n-1,m-1)+mS(n-1,m)\)，边界\(S(0,0)=1\)。

性质

\[ \begin{aligned} &\sum_{i=0}^mS(n,i)\times i!\times C(m,i)=m^n\&S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^iC(m,i)(m-i)^n\&\sum_{i=0}^ni^m=\sum_{i=0}^m\frac{(n+1)^{\underline{i+1}}S(m,i)}{i+1} \end{aligned} \]

前两点自行脑补，下面用前两点推导第三点
\[ \sum_{i=0}^ni^m =\sum_{i=0}^n\sum_{j=0}^iS(m,j)\times j!\times C(i,j) =\sum_{i=0}^n\sum_{j=0}^mS(m,j)\times j!\times C(i,j)\=\sum_{j=0}^mS(m,j)\times j!\sum_{i=0}^nC(i,j) =\sum_{j=0}^mS(m,j)\times j!\times C(n+1,j+1)\=\sum_{j=0}^m\frac{S(m,j)\times j!\times (n+1)!}{(j+1)!\times (n-j)!} =\sum_{i=0}^m\frac{(n+1)^{\underline{i+1}}S(m,i)}{i+1} \]

母函数

设它的母函数为\(G_n(x)\)，易知
\[ \begin{aligned} G_n(x)&=\sum_i S(n,i)x^i\&=\sum_i\frac{1}{i!}\sum_{j=0}^i(-1)^jC(i,j)(i-j)^nx^i\&=\sum_i\sum_j\frac{(-1)^j(i-j)^n}{j!(i-j)!}x^i\&=(\sum_{i=0}\frac{(-1)^i}{i!}x^i)(\sum_{i=0}\frac{i^n}{i!}x^i) \end{aligned} \]
就很好做了似乎。

斯特林反演

定义

\[ f(n)=\sum_{i=0}^n S(n,i)g(i) \Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}s(n,i)f(i) \]

推导

结合幂、阶乘幂的变换
\[ \begin{aligned} m^\underline n &=\sum_{i=0}^ns(n,i)(-1)^{n-i}m^i\&=\sum_{i=0}^ns(n,i)(-1)^{n-i}\sum_{j=0}^m S(i,j)\times j!\times C(m,j)\&=\sum_{i=0}^ns(n,i)(-1)^{n-i}\sum_{j=0}^m S(i,j)\times m^\underline j\&=\sum_{i=0}^ns(n,i)(-1)^{n-i}\sum_{j=0}^n S(i,j)\times m^\underline j\&=\sum_{j=0}^nm^\underline j\sum_{i=0}^n(-1)^{n-i}s(n,i)S(i,j)\\end{aligned} \]
可知等式

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

类似地也能得等式
\[ \sum_{i=m}^n(-1)^{n-i}S(n,i)s(i,m)=\sum_{i=0}^n(-1)^{n-i}S(n,i)s(i,m)=[n=m] \]
于是先证从左到右
\[ \begin{aligned} g(n)&=\sum_{i=0}^n(-1)^{n-i}s(n,i)\sum_{j=0}^i S(i,j)g(j)\&=\sum_{i=0}^n(-1)^{n-i}s(n,i)\sum_{j=0}^n S(i,j)g(j)\&=\sum_{j=0}^n g(j)\sum_{i=0}^n(-1)^{n-i}s(n,i)S(i,j)\&=g(n) \end{aligned} \]
类似地也能证明从右到左。

递推式的边界参考 https://ja.wikipedia.org/wiki/スターリング数

上升阶乘幂\(x^{\overline{n}}=\frac{(x+n-1)!}{(x-1)!}\)，下降阶乘幂\(x^{\underline{x}}=\frac{x!}{(x-n)!}\)，两者的关系是\(x^{\overline{n}}=(-1)^nx^{\underline{n}}\)，\(x^{\underline{n}}=(-1)^nx^{\overline{n}}\)。

从零开始的斯特林数问题

原文：https://www.cnblogs.com/nosta/p/10970388.html