首页 > 代码库 > 斯特林数

斯特林数

一个经典的组合数学问题。求解方法:递推。

第一类斯特林数:n个数摆成m个环,有多少种方法?数各不相同。

s[i][j]表示i个数摆成j个环  的方法数目。

递推:1,摆第n+1个数时,如果前n个数摆成了m个环,那么要在环中插入一个数,总数目是s[n][m]*n;

   2,如果前n个数摆成了m-1个环,方法数目是s[n][m-1].

    综上:s[n+1][m]=s[n][m]*n+s[n][m-1].

这个过程和组合数公式:C[n][m]=C[n-1][n-1]+C[n-1][n]   类似。

第二类斯特林数:经典问题,n个不同的球放到m个相同的盒子里,每个盒子不为空。

和第一类很相似。

递推:1,放第n+1个球时,如果前n个球已经把m个盒子都填了,那么这个球有m中放法,S[n][m]*m;

   2,如果前n个球只把n-1个盒子填了,那么这个球只有一种放法,S[n][m-1]*1.

 

HDU3625问题:有n个房间和n个对应的钥匙,每个房间放着一把钥匙,侦探要侦破案件,调查所有房间,他只能破门而入,1号房间的客人比较尊贵,不能破开1号门,给定数k,要求最多只能破开k个门,求侦探成功的概率。

  开一个门就能开成环的所有门,破门次数对应环的个数,s[n][i];第一个房间不能破门进入,看作1号门自成一环,无法完成的情况就是s[n-1][i-1]种。

  能进入的总情况数目:Σi~k  s[n][i]-s[n-1][i-1]

  所有情况数目和:n!

  做除法

技术分享
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=25;
 4 typedef unsigned long long ull;
 5 ull s[maxn][maxn];
 6 void init()
 7 {
 8     s[0][0]=1;
 9     for(int i=1;i<maxn;i++)
10         s[i][0]=0;
11     for(int i=1;i<21;i++)
12         for(int j=1;j<=i;j++)
13             s[i][j]=s[i-1][j]*(i-1)+s[i-1][j-1];
14 }
15 int main()
16 {
17     init();
18     int t,k,n;
19     cin>>t;
20     while(t--)
21     {
22         cin>>n>>k;
23         double fin=0;
24         for(int i=1;i<=k;i++)
25             fin=fin+s[n][i]-s[n-1][i-1];
26         for(int i=1;i<=n;i++)
27             fin/=i;
28         printf("%.4f\n",fin);
29     }
30     return 0;
31 }
View Code

 

斯特林数