从零开始的斯特林数问题

全力施工中。

update：基础部分已完成，缺少例题。

第一类斯特林数

定义

轮换斯特林数\(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)\\ g_{2n}(x)=\prod_{i=0}^{n-1}(x+i)\prod_{i=0}^{n-1}(n+x+i)=g_n(x)g_n(x+n)\\ g_{2n}(x+1)=\prod_{i=0}^{n-1}(x+i)\prod_{i=0}^{n-1}(n+x+i)=(x+n-1)g_n(x)g_n(x+n)\\ \]
其中
\[ \begin{aligned} g_n(x+n)&=\sum_{i=0}^n s(n,i)(x+n)^i\\ &=\sum_{i=0}^ns(n,i)\sum_{j=0}^ic(i,j)n^{i-j}x^j\\ &=\sum_{i=0}^ns(n,i)\sum_{j=0}^n\frac{i!}{j!\times (i-j)!}n^{i-j}x^j\\ &=\sum_{j=0}^n\frac{x^j}{j!}\sum_{i=0}^ns(n,i)\times i!\times\frac{n^{i-j}}{(i-j)!} \end{aligned} \]
于是快速地从\(g_n(x)\)得到\(g_n(x+n)\)。（参考附录）

因此采取分治策略计算\(g_n(x)\)，复杂度与多项式求逆相近，为\(o(n\log n)\)。

第二类斯特林数

定义

子集斯特林数\(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} \]
类似地也能证明从右到左。

附录

上升阶乘幂\(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}}\)。

递推式的参考

母函数的参考

一类卷积的处理

问题：已知\(a(x)=\sum_{i=0}^n a_ix^i\), \(b(x)=\sum_{i=0}^n b_ix^i\)，求解\(c(x)=\sum_{i=0}^nx^i(\sum_{j=i}^na_jb_{j-i})\)。

做法：设对于\(p(x)=\sum_{i=0}^np_ix^i\)，\(p_r(x)=\sum_{i=0}^np_{n-i}x^i\)，则
\[ \begin{aligned} c_r(x)&=\sum_{i=0}^nx^i(\sum_{j=n-i}^na_jb_{j-(n-i)})\\ &=\sum_{i=0}^nx^i(\sum_{j=0}^ia_{j+(n-i)}b_j)\\ &=\sum_{i=0}^nx^i(\sum_{j=0}^ia(x)_{j+(n-i)}b(x)_j)\\ &=\sum_{i=0}^nx^i(\sum_{j=0}^ia_r(x)_{i-j}b(x)_j)\\ &=a_r(x)b(x) \end{aligned} \]

习题

[cf960g] bandit blues - 求第一类斯特林数