排列組合逐漸進(jìn)入正軌，這節(jié)介紹兩類(lèi)特殊排列組合數(shù)冰抢，變個(gè)角度也可以稱(chēng)為三類(lèi)松嘶，再變一個(gè)角度又可以稱(chēng)為兩類(lèi)】嫒牛看完看完這篇blog學(xué)了之后就會(huì)明白??翠订。
Stirling數(shù)
Stirling 數(shù)是一類(lèi)特殊的排列組合數(shù)，它分為兩類(lèi)遵倦，第一類(lèi)Stirting數(shù)和第二類(lèi)Stirting數(shù)尽超，這兩種數(shù)聯(lián)系不大，但是證明上卻有相似之處梧躺，且慢慢看來(lái)...??
第一類(lèi)Stirting數(shù)
第一類(lèi)Stirling數(shù)討論的是把N個(gè)元素放入K個(gè)環(huán)排列的方法數(shù)似谁。其中S(n,0) =0 ; S(1,1) = 1 ; S(n,k) = S(n-1 , k-1) +(n-1)*S(n-1,k)
環(huán)排列，n個(gè)數(shù)字的環(huán)排列可以理解為把n個(gè)數(shù)字圍成一個(gè)環(huán)形掠哥，沒(méi)有起點(diǎn)終點(diǎn)巩踏，也就是說(shuō)判定這個(gè)環(huán)的異同只能根據(jù)數(shù)字之間的相對(duì)位置來(lái)看，所以 1龙致，2蛀缝，3，4 與4目代，1屈梁，2，3榛了，以及3在讶，4，1霜大，2其實(shí)是同一個(gè)環(huán)排列构哺，而1，2战坤，3曙强，4與4，3途茫，2碟嘴，1，就不是同一個(gè)環(huán)排列.讀到這里你應(yīng)該能直到環(huán)排列的意思了囊卜。
而第一類(lèi)Stirting數(shù)就是解決這個(gè)問(wèn)題娜扇，遞推公式我已給出错沃，至于為什么這樣遞推，下面我給出證明：
證明
設(shè)n個(gè)元素 a[1]~a[n] 放入k個(gè)環(huán)排列中的方法數(shù)是S(n,k),在放的過(guò)程中雀瓢，其實(shí)有如下兩種互不相容的情況：
? 如果a[n]這個(gè)元素是k個(gè)環(huán)排列中單獨(dú)的一個(gè)環(huán)排列（也就是說(shuō)這一個(gè)數(shù)字單獨(dú)成一個(gè)環(huán)排列）枢析，那么其余的n-1個(gè)數(shù)字只能放入剩下的k-1個(gè)環(huán)排列中，方法數(shù)就是S(n-1,k-1)
? 如果a[n]不單獨(dú)形成一個(gè)環(huán)排列（也就是說(shuō)a[n]在其它環(huán)排列里面）刃麸，那么剩 下n-1個(gè)元素就可以放入k個(gè)環(huán)排列中去醒叁，方法數(shù)是S(n-1,k),而這個(gè)時(shí)候重點(diǎn)來(lái)了：a[n]這個(gè)元素該怎么放，他要放到k個(gè)環(huán)排列中的方法數(shù)是多少嫌蚤？答案是n-1中辐益，而不是k種（因?yàn)榄h(huán)排列考慮的相對(duì)位置，這個(gè)不懂可以問(wèn)我）所以這種情況就是S(n-1,k)*(n-1)咯
所以綜合以上兩種情況脱吱，根據(jù)加法原理n個(gè)元素放入k個(gè)環(huán)排列種的方法數(shù)是S(n-1,k-1)+S(n-1,k)*(n-1)
第二類(lèi)Stirting數(shù)
第二類(lèi)Stirting數(shù)是求解將n個(gè)元素劃分為k個(gè)不為空的子集的方法數(shù)，容易想到S(n,n) = S(n,1) = 1 （因?yàn)閷個(gè)元素化為一個(gè)集合只能是所有元素都在一塊方法是1種认罩，將n個(gè)元素劃分為n個(gè)集合只能是每個(gè)元素各自一個(gè)集合箱蝠，所以方法數(shù)也是1） 其遞推公式為S(n,k) = S(n-1,k-1) + S(n-1,k) * k
證明
證明過(guò)程與第一類(lèi)Stirting類(lèi)似，分為兩種情況
? ：如果a[n]自己一個(gè)集合的話(huà)垦垂，剩下n-1個(gè)元素的方法數(shù)是S(n-1宦搬，k-1)
? ：如果a[n]跟在k個(gè)集合種的某一個(gè)的時(shí)候，我們先排剩下的n-1個(gè)元素劫拗，方法數(shù)是S[n-1][k]然后把a(bǔ)[n]加入進(jìn)來(lái)有k種方式间校，即k*S[n-1][k]
??綜上，根據(jù)加法原理页慷，S[n][k] = S[n-1][k-1] + S[n-1][k] *k
第二類(lèi)Stirting數(shù)代碼如下：
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數(shù)
Bell數(shù)就是集合的劃分?jǐn)?shù)憔足，就是n個(gè)元素的集合的劃分方法數(shù)，仔細(xì)想想這里與第二類(lèi)Stirting有什么異同酒繁，第二類(lèi)Stirting數(shù)也是關(guān)于集合的劃分滓彰，只不過(guò)Stirting是求解n個(gè)元素化為k個(gè)集合的方法數(shù)，而B(niǎo)ell數(shù)沒(méi)有這個(gè)k州袒，那么我們就能聯(lián)想到揭绑，其實(shí)Bell數(shù)就是第二類(lèi)Stirting數(shù)的和，對(duì)于每個(gè)n(n=1,2,3...)對(duì)應(yīng)一個(gè)k(1<=k<=n),令Bell數(shù)為B[n],Stirting數(shù)為S[n][k]那么B[n]= S[n][1]+S[n][2]+...+S[n][n]郎哭。
那么這里你應(yīng)該可以知道他匪，Bell數(shù)可以通過(guò)求解出第二類(lèi)Stirting數(shù)來(lái)，然后對(duì)Stirting數(shù)求和就能解出夸研。其實(shí)Bell數(shù)還有其它兩種種求解方法
?? 遞推式：B[n+1] = C[n][0]B[0] + C[n][1]B[1] +...+C[n][n]*B[n]（不常用）
?? 構(gòu)建Bell三角形
Bell三角形的構(gòu)建與楊輝三角類(lèi)似邦蜜，有如下構(gòu)建方法：
a[1][1] =1
對(duì)于n > 1，第n行第一項(xiàng)等于第n-1行最后一項(xiàng)陈惰，即a[n] = a[n-1][n-1]
對(duì)于m,n>1畦徘，第n行第m項(xiàng)等于它左邊和左上方的兩個(gè)數(shù)之和毕籽，即a[n][m] = a[n][m-1]+a[n-1][m-1] 三角形構(gòu)建完成之后，每行首項(xiàng)即Bell[i][1]就是Bell數(shù)
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];
}
}
讀到這里你應(yīng)該就能明白這三種組合數(shù)的各自的含義了吧...
碼到這里又累了井辆，估計(jì)你看到這里也累了关筒，打個(gè)廣告？??
有沒(méi)有對(duì)機(jī)器學(xué)習(xí)杯缺，物聯(lián)網(wǎng)蒸播，大數(shù)據(jù)，云計(jì)算感興趣的童鞋萍肆，我有個(gè)交流群袍榆，想把它建設(shè)起來(lái)，大家來(lái)助力哇塘揣，有想法的私聊我包雀，咱們大二大三的時(shí)候一塊做項(xiàng)目??
??來(lái)幾道題吧：
題目一
小 J 有 N 塊大小不同的積木，他要在海灘上搭建城市亲铡，一座城市由一組建筑物組成才写，在海灘上的一塊積木就可以被視為一棟建筑，小J也可以將一塊積木放在另一塊積木之上奖蔓，這樣他就能搭建更高的建筑赞草。他只能把小積木放在比大積木之上。一塊積木用一個(gè)自然數(shù)表示其大小吆鹤。
本題要求使用N塊積木可以構(gòu)建的不同的城市的數(shù)目厨疙。比如N=2時(shí)只有可能搭建兩種不同的城市:
City1 兩個(gè)木塊1和2各自成為一個(gè)建筑，這座城市就有兩棟建筑疑务。
City2 兩個(gè)木塊種小的放在大的之上沾凄，1放在2的上面，即這座城市有一棟建筑
所以N=2時(shí)暑始，我們可以構(gòu)造出兩個(gè)不同的城市
??下面由你來(lái)解答搭独，對(duì)于輸入的N，輸出它的結(jié)果廊镜。
這就是以上講的三類(lèi)數(shù)的應(yīng)用牙肝，先不碼題解了，有想法或者有迷惑的私聊我嗤朴。
題目二
等會(huì)再更....
