标签：第二类 begin end dbinom 斯特林 sum 自然数 Bmatrix

引言

然而并没有什么内容
之所以是第二类斯特林数的原因是今天比赛写的拉插被卡了。。。
第xxx次被卡常

第二类 \(\text{Stirling}\) 数

将 \(n\) 个两两不同的元素划分为 \(k\) 个互不区分的非空子集的方案数

\[\begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix}n-1\\k-1 \end{Bmatrix}+k\begin{Bmatrix}n-1\\k \end{Bmatrix} \]

边界条件：\(\begin{Bmatrix}n\\0 \end{Bmatrix}=[n=0]\)

一些公式

\[n^k=\sum_{i=1}^k\begin{Bmatrix}k\\i \end{Bmatrix}i!\dbinom n i \]

\[\sum_{i=1}^n\dbinom i k = \dbinom{n+1}{k+1} \]

（把右边按递推式展开即可证明）

自然数幂和

\[\begin{aligned} \sum_{i=1}^n i^k &= \sum_{i=1}^n \sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom i j \\ &=\sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}j! \sum_{i=1}^n \dbinom i j \\ &=\sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n+1}{j+1} \end{aligned} \]

单次就可以 \(O(k)\) 啦

标签：第二类,begin,end,dbinom,斯特林,sum,自然数,Bmatrix
From： https://www.cnblogs.com/leiyuanze/p/16819428.html