上文：组合数学初步
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是小写)
前面一半很好理解，后一半其实就是之前的n-1个门已经排好了，现在的门可以插在任意一个门的后面。
有下面的式子：
还有母函数：
是二项反演得到的。