问题引出

用矩阵来表示样本属于哪类划分类别的过程中，老师提出的一个问题：从\(N\)个样本中分出\(C\)类，不同的分法一共有多少种？

抽象：\(N\)个数划分为\(C\)个集合，要求集合不能为空，方案数为？

就是第二类斯特林数。

解答

递推

其实是个数学的问题，和组合数的公式有些类似，所以我们尝试求其递推式，从\(N\)个数划分为\(C\)个非空集合，如果前面各数都已经划分好到所属集合，剩下最后一个数未划分，考虑最后一个数，则有以下两种情况：

1. 前面\(N-1\)个数划分的集合数为\(C-1\)，则最后一个数必须单独属于一个新集合。
2. 前面\(N-1\)个数划分的集合数为\(C\)，则最后一个数可以属于先前\(C\)个集合中的任意一个。

用更数学的方式表达，\(S(n,c)\)表示我们所求，则有以下转移方程。

\[S(n,c) = S(n-1,c-1)+n*S(n-1,c)\]

容斥原理（通项公式）

考虑容斥的话思路尝尝是从一个大数减起，对于这个计算直觉应该是从这个大数：\(c^n\)（把\(n\)个球放进\(c\)个可空的不同集合的总方案数，另一个角度就是\(n\)位\(c\)进制数可表达的数的范围）

那我们应该如何计算得到我们想要的\(S(n,c)\)呢？（容斥思想）

考虑\(c^n\)中包含着可空的情况，又考虑到直接求恰有\(x\)个集合满的情况，我们采取曲线救国的方式（也是容斥原理中常用的），我们可以求出至少\(x\)个集合满的情况，实际上就是\((c-k)^{n}\)。

那我们就可以容斥了，枚举空集的情况数然后求个 Sum 就行，给出公式：

\[S(n,c) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^kC(m,k)(m-k)^n\]

再一言以蔽之：就是枚举空集合的数目，剩下的随意放置，容斥以下就可以得到最终的答案了。