数论学习——Stirling数

问题引出

用矩阵来表示样本属于哪类划分类别的过程中,老师提出的一个问题:从$N$个样本中分出$C$类,不同的分法一共有多少种?

抽象:$N$个数划分为$C$个集合,要求集合不能为空,方案数为?

就是第二类斯特林数

解答

递推

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

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

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

容斥原理(通项公式)

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

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

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

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

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