第一类斯特灵数
$S_1(n,k)$表示把一个包含$n$个元素的集合分成$k$个环排列的方法数。
初始值:
$$S_1(n,0)=0 \\\ S_1(1,1)=1$$
递推式:
$$S_1(n+1,k)=S_1(n,k-1)+nS_1(n,k)$$
递推式说明：考虑第$n+1$个物品，$n+1$可以单独构成一个非空循环排列，这样前$n$种物品构成$k-1$个非空循环排列，有 $S_1(n-1,k-1)$种方法；也可以前$n$种物品构成$k$个非空循环排列，而第$n+1$个物品插入第$i$个物品的左边，这有 $ nS_1(n,k)$种方法。
第二类斯特灵数
$S_2(n,k)$表示把一个包含$n$个元素的集合分成$k$个非空子集的方法数。
初始值:
$$S_2(n,0)=0 \\\ S_2(n,k)=0 (n < k) \\\ S_2(n,1)=S_2(n,n)=1$$
递推式:
$$S_2(n,k)=S_2(n-1,k-1)+kS_2(n-1,k)$$
递推式说明：考虑第$n$个物品，$n$可以单独构成一个非空集合，此时前$n-1$个物品构成$k-1$个非空的集合，有$S(n-1,k-1)$种方法；也可以前$n-1$种物品构成$k$个非空集合，第$n$个物品放入任意一个中，这样有$k*S(n-1,k)$种方法。
两类斯特灵数的关系
$$\sum\limits_{n=0}^{max(j,k)}S_1(n,j)S_2(k,n)=\sum\limits_{n=0}^{max(j,k)}S_2(n,j)S_1(k,n)=\delta_{jk}$$
其中$\delta_{jk}$为克罗内克函数
分拆数
$P(n,k)$表示把正整数$n$拆分成$k$个的正整数之和的方案数。
初始值:
$$P(0,0)=1 \\\ P(n,0)=0$$
递推式:
$$
P(n,m)=
\begin{cases}
P(n,n) & n < m \\\\
P(n,m-1)+P(n-m,m) & n \ge m
\end{cases}
$$
母函数等更多内容详见wiki
球盒分配问题总结
有了上面的内容，我们便可以解决所有情况的球盒分配问题。
将$n$个球放入到$m$个盒子中的方案数可见下表。
| 球可分辨 | 盒子可分辨 | 盒可空 | 方案数 |
|---|---|---|---|
| 是 | 是 | 是 | $m^n$ |
| 是 | 是 | 否 | $m!S_2(n,m)$ |
| 是 | 否 | 是 | $\sum\limits_{i=1}^mS_2(n,i)$ |
| 是 | 否 | 否 | $S_2(n,m)$ |
| 否 | 是 | 是 | $C_{n+m-1}^{m-1}$ |
| 否 | 是 | 否 | $C_{n-1}^{m-1}$ |
| 否 | 否 | 是 | $P(n+m,m)$ |
| 否 | 否 | 否 | $P(n,m)$ |
卡特兰数
卡特兰数应用很广泛，它有非常多的解释，如：
一个无穷大的栈的进栈序列为$1,2,3, \cdots ,n$，问有多少种出栈序列。
一个括号序列由$n$个左括号和$n$个右括号组成，问有多少种合法括号序列。
把一个正$n$多边形用$n-3$条不相交的对角线划分成$n-2$个三角形的方案数。
一棵体积为$n$的有根二叉树有多少种形态。
…
初始值:$$h(0)=1$$
递推式:
$$h(n)=\sum\limits_{i=0}^{n-1}h(i)h(n-1-i)$$
$$h(n)=\frac{4n-2}{n+1}h(n-1)$$
$$h(n)=\frac{C_{2n}^n}{n+1}=\frac{2n!}{n!(n+1)!}$$
