上文：组合数学初步

Stirling 简述

Stirling formula

这是斯特林公式，我们可以利用它算出阶。比如卡特兰数）。

下面是正式的详细介绍：

第一类stirling数

把n个不同的人分成K个圆排列的方案数。

有两个重点：

1.不用平均分。
2.K个圆排列内部有序。
3.每组不能为空

记法：

第二类stirling数

n个不同的人分成k组的方案数。

重点：

1.还是不用平均分
2.每组内没有排序
3.每组不能为空

记法：

第二类stirling数

我们先研究第二类stirling数。
首先一个规定：
$S(n,0)=0$
不难得出：
$S(n,1)=S(n,n)=1$
请先尝试证明：

第一个式子：

首先n个元素自由选择,方案数是$2^{n}$,取消顺序除以2。因为已经确定顺序，减掉1种全在第一组的情况就行。

第二个式子：

不难想出只可能有一组是两个人，其他都是一个人，没有区别。那从n个人里挑两个就行。

发现：

先暂缓证明后两个式子。我们发现当k接近n的时候，式子多是组合数，接近0时则幂较多，大胆猜想通项与这两者混合有关。

$S(n,k)$的通项

先看看递推

首先给出一个递推：

我们发现与n-1个人和n个人只差了一个人。考虑分类。

要么是新来的人自成一组（从S(n-1,k-1)来），要么是加入k组之中(从S(n-1,k)来)。那么上式不难得出。

但我们发现递推不好推通项，换个思路。

考虑容斥

我们允许有的组可以为空，那么方案数是$k^{n}$，写成$C_{k}^{0}* k^{n}$。

我们考虑一个集合空的方案数（不考虑其他的空不空），那么方案数是$C_{k}^{1}* (k-1)^{n} $

同样的两个集合空的方案数：$C_{k}^{2}* (k-2)^{n} $

直到全空（显然不可能）：$C_{k}^{k}* (k-k)^{n} $

根据容斥可以得到通项:

~~当然你可以二项式反演的，但我觉得这样好理解。~~

这个公式就可以解释当k接近n的时候，式子多是组合数，接近0时则幂较多。因为当k大的时候，$\sum (k-i)^{n}$接近n,基本只剩组合数。而k很小时$\sum$ $C_{k}^{i}$很小，只剩下幂的形式。

一些式子：

通项推完了，看看我们能得到哪些东西。我们知道:$S(n,n) = 1$,把$S(n,n)$带进这个式子，可以得出：

如果允许空的话，可以得出下式（其实是把容斥的过程中移项）：

还记得之前的规定，$S(n,0)=0$吗?
现在我们可以给出一种理解。数学上有个Bell数，B(n)表示n个数的划分（随便几组），显然B(n)就是S(n,0)一直加到S(n,n),而B(0,0)=S(0,0),0个数显然没有划分方案，所以S(0,0)=0.

第一类stirling数

为什么要圆排列，给个背景。
有n个门，每个门对应一把钥匙。如果按正常的思路，要带n把钥匙就能把所有的门都打开，可能不能少带几把钥匙？其实只带一把就够了，把二号门的钥匙放在一号门内，以此类推。现在的问题相当于有n个门，k把钥匙，构成k组。k个组之间不能串联，也就是说不会出现拿着第一组的钥匙开了第二组的门。

于是又下面的公式(s是小写)