斯特林数

标签：斯特林 sum brack binom brace displaystyle

\brack
\brace
\displaystyle{{n}\brack {m}}
\displaystyle{{n}\brace {m}}

斯特林数

第二类斯特林数

一般表示为 \(\displaystyle{n\brack m}\)，含义为把 \(n\) 个不同的数分成 \(m\) 个集合的方案数。
递推式：

\[{n\brack m}=m{{n-1}\brack m}+{{n-1}\brack{m-1}} \]

含义为，拎出来最后一个数，对这个数进行讨论：
如果这个数放在原来的 \(m\) 个集合里，有 \(m\) 个可以选择的集合，放在每个集合的方案数都是 \(\displaystyle{{n-1}\brack m}\)，所以总的贡献就是：\(m\displaystyle{{n-1}\brack m}\)；
如果这个数给他新开一个集合存起来，那么贡献就是：\(\displaystyle{{n-1}\brack {m-1}}\)。

第一类斯特林数

一般表示为 \(\displaystyle{n\brace m}\)，含义为 把 \(n\) 个不同的数分成 \(m\) 个轮换的方案数。
轮换就是一个环，与第二类不同的地方就在于，把每个集合的数连成了一个环，因为环的排列是有序的，所以会比第二类的方案数一般要多一些。
递推关系为：

\[{n\brace m}=(n-1){{n-1}\brace m}+{{n-1}\brace{m-1}} \]

含义为，同样考虑最后一个数字的位置：
如果放在之前的轮换里，那么每个大小为 \(siz\) 的置换都有 \(siz\) 种方案，所以对于一种轮换状态的方案就有 \(n-1\) 种，那么总的方案就有：\((n-1)\displaystyle{{n-1}\brace m}\)；
如果新开一个轮换单独放他自己，那么贡献就是：\(\displaystyle{{n-1}\brace {m-1}}\)。

斯特林数的性质

边界：
当 \(m>n\) 时，\(\displaystyle{n\brace m}=\displaystyle{n\brack m}=0\)；
当 \(n<0\) 时，\(\displaystyle{{n}\brace {m}}=\displaystyle{{n}\brack{m}}=0\)；
当 \(m=0\) 时，\(\displaystyle{{n}\brace {0}}=\displaystyle{{n}\brace {0}}=[n=0]]\)。

普通幂和下降幂的关系：

\[x^n=\sum_{k=0}^n{n\brace k} x^{\underline{k}}\\ x^{\underline{n}}=\sum_{k=0}^n{n\brace k}(-1)^{n-k}x^k\\ \]

普通幂和上升幂的关系：

\[x^{\overline{n}}=\sum_{k=0}^n{n\brack k}x^k\\ x^n=\sum_{k=0}^n{n\brack k}(-1)^{n-k}x^{\overline{k}}\\ \]

特殊值：

\[{n\brack 1}=(n-1)![n>0]\\ {n\brack 2}=(n-1)!H_{n-1}[n>0]\\ \]

反转公式：

\[\sum_{k}{n\brace k}{k\brack m}(-1)^{n=k}=[m=n]\\ \sum_{k}{n\brack k}{k\brace m}(-1)^{n=k}=[m=n]\\ \]

其他的比较常用的恒等式：

\[{n+1\brace m+1}=\sum_{k}\binom{n}{k}{k\brace m}\\ {n+1\brack m+1}=\sum_{k}{n\brack k}\binom{k}{n}\\ {n\brace m}=\sum_{k}\binom{n}{k}{k+1\brace m+1}(-1)^{n-k}\\ {n\brack m}=\sum_{k}{n+1\brack k+1}\binom{k}{m}(-1)^{m-k}\\ \]

联系：

\[{n\brack k}={-k\brace -n}\\ {n\brace k}={-k\brack -n}\\ \]

标签：斯特林,sum,brack,binom,brace,displaystyle
From： https://www.cnblogs.com/linghuabaobao/p/17061116.html