《洛谷深入浅出》斯特林数

斯特林数被分为三种，但我们这只介绍两种。即第一类斯特林数，和第二类斯特拉数。

第一类斯特林数指的是：

将n个不同元素，变成m个圆排列的方案数量。第一类斯特林数，分为有符号和无符号。通常我们只研究无符号斯特林数：

1，递推求第一类斯特林数：

我们用dp的思路来研究第n个元素，对于第n个元素而言，要变成m个圆排列，有两种情况。

第一种：第n个元素自己成为一个圆排列，那么也就是前n-1个元素组成m-1个圆排列。

方案数为：

第二种情况：第n个元素没有新开一个圆排列，而是加入了前面的数的圆排列。也就是前面n-1个数字，构成了m个圆排列。.

又由于，对于任意一个圆排列而言，一个数插入进去，有多少种插法？

假如一个圆排列有k个元素，那么插法就是k种（插在每两个数字之间）

假如现在有2个圆排列，分别有k，t个元素，现在要插入一个新元素，那么请问，会产生多少种不同的圆排列？

如果插入第一个圆排列中，那么有k种圆排列。

如果插入第二个圆排列中，有t种圆排列。

由加法原则：会产生k+t种圆排列。

推广到多个圆排列，我们可以发现，有多少个元素组成，就有多少个不同的圆排列。

所以第二种情况，第n个元素插入到前面的圆排列中，会产生n-1种圆排列。

所以答案数为：

所以递推式子就是：

第二类斯特林数：

记作

表示将n个元素拆分到m个有序集合中的方案数。

还是想递推的方法：

先假设集合都是相同的。

对于第n个元素：它可以有两种拆分方法。第一种是单独放入一个集合中。

也就是说，前面n-1个元素要被放在m-1个盒子中。即

第二种情况是和前面的数放在一起，也就是说，前n-1个数，要被放在m个集合里。即,

又因为，第n个数可以放m个盒子，所以由乘法原理：

那么有递推式：

最后别忘记了集合是有序的，所以对集合进行排列有: m!

答案就是：