本文主要是介绍《洛谷深入浅出》斯特林数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
斯特林数被分为三种，但我们这只介绍两种。即第一类斯特林数，和第二类斯特拉数。
第一类斯特林数指的是：
将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!
答案就是：
这篇关于《洛谷深入浅出》斯特林数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
