排列组合逐渐进入正轨，这节介绍两类特殊排列组合数，变个角度也可以称为三类，再变一个角度又可以称为两类。看完看完这篇blog学了之后就会明白👍。
Stirling数
Stirling 数是一类特殊的排列组合数，它分为两类，第一类Stirting数和第二类Stirting数，这两种数联系不大，但是证明上却有相似之处，且慢慢看来...🙏
第一类Stirting数
第一类Stirling数讨论的是把N个元素放入K个环排列的方法数。其中S(n,0) =0 ; S(1,1) = 1 ; S(n,k) = S(n-1 , k-1) +(n-1)*S(n-1,k)
环排列，n个数字的环排列可以理解为把n个数字围成一个环形，没有起点终点，也就是说判定这个环的异同只能根据数字之间的相对位置来看，所以 1，2，3，4 与4，1，2，3，以及3，4，1，2其实是同一个环排列，而1，2，3，4与4，3，2，1，就不是同一个环排列.读到这里你应该能直到环排列的意思了。
而第一类Stirting数就是解决这个问题，递推公式我已给出，至于为什么这样递推，下面我给出证明：
证明
设n个元素 a[1]~a[n] 放入k个环排列中的方法数是S(n,k),在放的过程中，其实有如下两种互不相容的情况：
☝ 如果a[n]这个元素是k个环排列中单独的一个环排列（也就是说这一个数字单独成一个环排列），那么其余的n-1个数字只能放入剩下的k-1个环排列中，方法数就是S(n-1,k-1)
✌ 如果a[n]不单独形成一个环排列（也就是说a[n]在其它环排列里面），那么剩 下n-1个元素就可以放入k个环排列中去，方法数是S(n-1,k),而这个时候重点来了：a[n]这个元素该怎么放，他要放到k个环排列中的方法数是多少？答案是n-1中，而不是k种（因为环排列考虑的相对位置，这个不懂可以问我）所以这种情况就是S(n-1,k)*(n-1)咯
所以综合以上两种情况，根据加法原理n个元素放入k个环排列种的方法数是S(n-1,k-1)+S(n-1,k)*(n-1)
第二类Stirting数
第二类Stirting数是求解将n个元素划分为k个不为空的子集的方法数，容易想到S(n,n) = S(n,1) = 1 （因为将n个元素化为一个集合只能是所有元素都在一块方法是1种，将n个元素划分为n个集合只能是每个元素各自一个集合，所以方法数也是1） 其递推公式为S(n,k) = S(n-1,k-1) + S(n-1,k) * k
证明
证明过程与第一类Stirting类似，分为两种情况
☝ ：如果a[n]自己一个集合的话，剩下n-1个元素的方法数是S(n-1，k-1)
✌ ：如果a[n]跟在k个集合种的某一个的时候，我们先排剩下的n-1个元素，方法数是S[n-1][k]然后把a[n]加入进来有k种方式，即k*S[n-1][k]
👏综上，根据加法原理，S[n][k] = S[n-1][k-1] + S[n-1][k] *k
第二类Stirting数代码如下：
void GetStirting()
{
for (int i = 1; i <= 20; i++)
S[i][1] = 1;
for (int i = 2; i <= 20; i++)
for (int j = 2; j <= 20; j++)
S[i][j] = S[i - 1][j - 1] + S[i - 1][j] * j;
}
Bell数
Bell数就是集合的划分数，就是n个元素的集合的划分方法数，仔细想想这里与第二类Stirting有什么异同，第二类Stirting数也是关于集合的划分，只不过Stirting是求解n个元素化为k个集合的方法数，而Bell数没有这个k，那么我们就能联想到，其实Bell数就是第二类Stirting数的和，对于每个n(n=1,2,3...)对应一个k(1<=k<=n),令Bell数为B[n],Stirting数为S[n][k]那么B[n]= S[n][1]+S[n][2]+...+S[n][n]。
那么这里你应该可以知道，Bell数可以通过求解出第二类Stirting数来，然后对Stirting数求和就能解出。其实Bell数还有其它两种种求解方法
😜 递推式：B[n+1] = C[n][0]B[0] + C[n][1]B[1] +...+C[n][n]*B[n]（不常用）
😊 构建Bell三角形
Bell三角形的构建与杨辉三角类似，有如下构建方法：
a[1][1] =1
对于n > 1，第n行第一项等于第n-1行最后一项，即a[n] = a[n-1][n-1]
对于m,n>1，第n行第m项等于它左边和左上方的两个数之和，即a[n][m] = a[n][m-1]+a[n-1][m-1] 三角形构建完成之后，每行首项即Bell[i][1]就是Bell数
int Bell[100][100];
void GetBell()
{
Bell[1][1] = 1;
for (int i = 2; i < 50; i++)
{
Bell[i][1] = Bell[i - 1][i - 1];
for (int j = 2; j <= i; j++)
Bell[i][j] = Bell[i][j - 1] + Bell[i - 1][j - 1];
}
}
读到这里你应该就能明白这三种组合数的各自的含义了吧...
码到这里又累了，估计你看到这里也累了，打个广告？😂
有没有对机器学习，物联网，大数据，云计算感兴趣的童鞋，我有个交流群，想把它建设起来，大家来助力哇，有想法的私聊我，咱们大二大三的时候一块做项目😊
🆗来几道题吧：
题目一
小 J 有 N 块大小不同的积木，他要在海滩上搭建城市，一座城市由一组建筑物组成，在海滩上的一块积木就可以被视为一栋建筑，小J也可以将一块积木放在另一块积木之上，这样他就能搭建更高的建筑。他只能把小积木放在比大积木之上。一块积木用一个自然数表示其大小。
本题要求使用N块积木可以构建的不同的城市的数目。比如N=2时只有可能搭建两种不同的城市:
City1 两个木块1和2各自成为一个建筑，这座城市就有两栋建筑。
City2 两个木块种小的放在大的之上，1放在2的上面，即这座城市有一栋建筑
所以N=2时，我们可以构造出两个不同的城市
😋下面由你来解答，对于输入的N，输出它的结果。
这就是以上讲的三类数的应用，先不码题解了，有想法或者有迷惑的私聊我。
题目二
等会再更....
网友评论