斯特林数
第一类
将\(n\)个有标号数放入\(m\)个非空环排列的方案数
\[\begin{bmatrix}n\\m\end{bmatrix}= \begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix} \]
考虑成为新环或者接在某个数字之后
性质
性质一： \(\begin{bmatrix}n\\1\end{bmatrix}=(n-1)!\)
证明：一个环的环排列计数，为\(n\)个点的总排列数除以\(n\)
性质二： \(\begin{bmatrix}n\\2\end{bmatrix}=(n-1)!\sum\limits_{i=1}^{n-1}\frac{1}{i}\)
证明：显然
\[\begin{bmatrix}2\\2\end{bmatrix}=1=1!\sum\limits_{i=1}^{1}\frac{1}{1} \]
考虑数学归纳法
\[\begin{bmatrix}n+1\\2\end{bmatrix}=\begin{bmatrix}n\\1\end{bmatrix}+n\begin{bmatrix}n\\2\end{bmatrix} \]
\[=(n-1)!+n(n-1)!\sum\limits_{i=1}^{n-1}\frac{1}{i} \]
\[=\frac{n!}{n}+n!\sum\limits_{i=1}^{n-1}\frac{1}{i} \]
\[=n!\sum\limits_{i=1}^{n}\frac{1}{i} \]
性质三：\(\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}=n!\)
证明：环排列是排列的不交并，即每种排列可以唯一对应一种\(n\)个点的环排列，所以
\[n!=\sum\limits_{i=1}^{n}\begin{bmatrix}n\\i\end{bmatrix} \]
同时规定\(\begin{bmatrix}n\\0\end{bmatrix}=0\)，所以
\[\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}=n! \]
求法
第一类斯特林数·行
即给定\(n\)，求\(\begin{bmatrix}n\\0\end{bmatrix},\begin{bmatrix}n\\1\end{bmatrix}\begin{bmatrix}n\\2\end{bmatrix}…\begin{bmatrix}n\\n\end{bmatrix}\)
如果您不会上升幂转通常幂，请先阅读下面的介绍
根据
\[x^{\overline{n}}=\sum\limits_{i}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \]
得到\(x^{\overline{n}}\)的\(i\)次项系数即为\(\begin{bmatrix}n\\i\end{bmatrix}\)
考虑倍增，我们有
\[x^{\overline{2n}}=x^{\overline{n}}(x+n)^{\overline{n}} \]
我们将\(x^{\overline{n}}\)看作\(f(x)\)，那么\((x+n)^{\overline{n}}\)即为\(f(x+n)\)
假设我们已经得到了\(f(x)\)，其中\(i\)次项系数为\(a_i\)，那么
\[f(x+n)=\sum\limits_{i=0}^{n}a_i(x+k)^i \]
将右边二项式展开
\[=\sum\limits_{i=0}^{n}a_i\sum\limits_{j=0}^{i}\dbinom{i}{j}x^jn^{i-j} \]
\[=\sum\limits_{i=0}^{n}x^i\sum\limits_{j=i}^{n}\dbinom{j}{i}n^{j-i}a_j \]
\[=\sum\limits_{i=0}^{n}\frac{x^i}{i!}\sum\limits_{j=i}^{n}\frac{n^{j-i}}{(j-i)!}j!a_j \]
最右明显是个卷积式了，不会卷可以看我这里的最后一步
第一类斯特林数·列
给定\(n,k\)求
求\(\begin{bmatrix}0\\k\end{bmatrix},\begin{bmatrix}1\\k\end{bmatrix},\begin{bmatrix}2\\k\end{bmatrix}…\begin{bmatrix}0\\k\end{bmatrix}\)
令\(F(x)\)是一个环的\(EGF\)
那么有
\[F(x)=\sum\limits_{i=1}^{n}\frac{(i-1)!}{i!}x^i=\sum\limits_{i=1}^{n}\frac{1}{i} \]
那么
\[\begin{bmatrix}i\\k\end{bmatrix}=\frac{F(x)^k}{k!}i! \]
注意这里常数项不为\(1\)，要用加强版的多项式幂函数
第二类
将\(n\)个有标号的数放入\(m\)个非空集合中的方案数
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n\\m\end{Bmatrix} \]
考虑占用新集合或加入之前的集合
通项
对非空集合这个条件进行容斥,先对集合进行标号，再除以\(m!\)
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{i=0}^{m}(-1)^{i}\dbinom{m}{i}(m-i)^n \]
拆开组合数
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^{m}\frac{(-1)^{i}}{i!}\frac{(m-i)^n}{(m-i)!} \]
求法
第二类斯特林数·行
给定\(n\)
求\(\begin{Bmatrix}n\\0\end{Bmatrix},\begin{Bmatrix}n\\1\end{Bmatrix},\begin{Bmatrix}n\\2\end{Bmatrix}…\begin{Bmatrix}n\\n\end{Bmatrix}\)
有通项
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^{m}\frac{(-1)^{i}}{i!}\frac{(m-i)^n}{(m-i)!} \]
设\(f_i\frac{(-1)^{i}}{i!},g_i=\frac{i^m}{i!}\)
\[\begin{Bmatrix}n\\i\end{Bmatrix}=[x^i]\sum\limits_{i=0}^{n}f_ig_i \]
第二类斯特林数·列
给定\(n,k\)
求\(\begin{Bmatrix}0\\k\end{Bmatrix},\begin{Bmatrix}1\\k\end{Bmatrix},\begin{Bmatrix}2\\k\end{Bmatrix}…\begin{Bmatrix}n\\k\end{Bmatrix}\)
考虑先把相同的集合换成不同的集合，最后令每一项乘上\(\frac{1}{k!}\)
假设相同集合换成不同集合的\(EGF\)为\(F\),单个盒子的\(EGF\)为\(G\)，那么\(F=G^k\)
由于每个盒子不能为空，所以
\[G=\sum\limits_{i=1}^{n}\frac{1}{i!}x^i \]
\[=e^x-1 \]
所以
\[F=(e^x-1)^k \]
所以
\[\begin{Bmatrix}i\\k\end{Bmatrix}=\frac{(e^x-1)^k}{k!}i! \]
我们会惊喜地发现只要把第一类斯特林数·列的代码的初始多项式由\(\sum\frac{1}{i}\)换成\(\sum\frac{1}{i!}\)就\(AC\)了
上升幂与下降幂
下降幂
\[n^{\underline{m}}=n(n-1)…(n-m+1) \]
排列\(A_{n}^{m}=n^{\underline{m}}\)
通常幂转下降幂
\[n^m=\sum\limits_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}n^{\underline{i}} \]
\(n^m\)是选\(m\)个\(1-n\)的方案数
枚举选择了多少个数字，然后把\(m\)个数放入\(i\)个集合中，再从\(1-n\)中选
上升幂
\(n^{\overline{m}}=n(n+1)…(n+m-1)\)
上升幂转通常幂
\[x^{\overline{m}}=\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \]
考虑数学归纳法
\(n=1\)时显然成立
\[x^{\overline{n}}=x^{\overline{n-1}}(x+n-1) \]
\[=(x+n-1)\sum\limits_{i=0}^{n-1}\begin{bmatrix}n-1\\i\end{bmatrix}x^i \]
\[=\sum\limits_{i=0}^{n-1}\begin{bmatrix}n-1\\i\end{bmatrix}x^{i+1}+\sum\limits_{i=0}^{n-1}(n-1)\begin{bmatrix}n-1\\i\end{bmatrix}x^i \]
令第一个求和的\(i=i+1\)
\[=\sum\limits_({i=0}^{n-1}\begin{bmatrix}n-1\\i-1\end{bmatrix}x^i+\sum\limits_{i=0}^{n-1}(n-1)\begin{bmatrix}n-1\\i\end{bmatrix}x^i \]
\[=\sum\limits_{i=1}^{n-1}\begin{bmatrix}n-1\\i-1\end{bmatrix}+\sum\limits_{i=0}^{n-1}(n-1)\begin{bmatrix}n-1\\i\end{bmatrix})x^i \]
\[=\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \]
上升幂下降幂互转
\[x^{\overline{n}}=(-1)^{n}(-x)^{\underline{n}} \]
\[x^{\underline{n}}=(-1)^{n}(-x)^{\overline{n}} \]
显然
反转公式
\[\sum\limits_{k=m}^{n}(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}=[m=n] \]
\[\sum\limits_{k=m}^{n}(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}=[m=n] \]
第二个式子证明
通常幂转下降幂转上升幂再转通常幂
\[n^m=\sum\limits_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix} \]
\[=\sum\limits_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}(-1)^{i}(-n)^{\overline{i}} \]
\[=\sum\limits_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}(-1)^{i}\sum\limits_{j=0}^{i}\begin{bmatrix}i\\j\end{bmatrix}(-n)^j \]
\[=\sum\limits_{j=0}^{m}(-n)^j\sum\limits_{i=j}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^i \]
\[n^m=\sum\limits_{j=0}^{m}n^j\sum\limits_{i=j}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j} \]
当\(j=m\)时
\[\sum\limits_{j=0}^{m}n^j\sum\limits_{i=j}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j}=n^m \]
同时
\[\sum\limits_{i=j}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j}=1 \]
所以
\[\sum\limits_{j=0}^{m-1}n^j\sum\limits_{i=j}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j}=0 \]
又因为
\[\sum\limits_{j=0}^{m-1}n^j>0 \]
所以当\(j\neq m\)
\[\sum\limits_{i=j}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j}=0 \]
我们可以得知负数与正数部分绝对值相等，只要保证\((-1)\)的幂次奇偶性不断变化，所以
\[\sum\limits_{k=m}^{n}(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}=[m=n] \]
斯特林反演
\[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}f_i \]
证明
\[f_n=\sum\limits_{i=0}^{n}[i=n]f_i \]
\[=\sum\limits_{i=0}^{n}\sum\limits_{j=i}^{n}(-1)^{n-j}\begin{Bmatrix}n\\j\end{Bmatrix}\begin{bmatrix}j\\i\end{bmatrix}f_i \]
\[=\sum\limits_{j=0}^{n}\begin{Bmatrix}n\\j\end{Bmatrix}\sum\limits_{i=0}^{j}(-1)^{j-i}\begin{bmatrix}j\\i\end{bmatrix}f_i \]
因为
\[f_n=\sum\limits_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}g_i \]
所以
\[g_n=\sum\limits_{i=0}^{n}(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f_i \]