组合数学

第一类斯特灵数

$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)!}$$