本菜鸡尚未学会第二类斯特林数，请各位dalao不要相信本文的任何一个字

什么是第二类斯特林数

在组合数学，Stirling数可指两类数，第一类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。
Stirling数有两种，第一类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根（Copenhagen）大学的尼尔森（Niels Nielsen，1865-1931）提出了"Stirlingschen Zahlen erster Art" [第一类Stirling数]和"Stirlingschen Zahlen zweiter Art" [第二类Stirling数]，首次把这两类数冠以「Stirling数」之名 。因为苏格兰数学家斯特林（J. Stirling, 1692-1770）首次发现这些数并说明了它们的重要性。 ——百度百科

用人话来说，第二类斯特林数$S(i,j)$用来表示i个不一样的球放入j个相同盒子里的方案数。

怎么算第二类斯特林数

我们可以假设当前这个球是单独放一个盒子还是放入有别的球的盒子中，如果单独放一个盒子，显然答案为$S(i-1,j-1)$,如果放入别的盒子中，因为它放在不同的盒子后能与盒子中原本有的球组成不同的方案，因此我们要在$S(i-1,j)$前面乘以盒子总数$j$

因此，我们可以得到以下递推式：

$S(i,j)=S(i-1,j-1)+j*S(i-1,j)$

还有一个我并不会证的通项公式，会证之后再补（咕咕咕）

$S(n,m)={\frac 1 {m!}}\sum_{k=0}^m (-1)^k C(m,k)(m-k)^n$

第二类斯特林数有啥性质

有且只有一个，而且我也不会证，会证后补（咕咕咕）

$n^k=\sum_ { i=0}^n S(k,i)×i!×C(n,i)$

这个式子主要用于算一些蜜汁幂次方的时候可以用得到，例如这道题