Stirling 数"/>
Stirling 数
第一类stirling数:将n个不同的元素构成m个圆排列的方法数(每一种情况都是n个元素全部参与所构成m个圆排列);
递推关系式:1.s(n,0)=s(0,n)=0;
2.s(n,n)=1;
3.s(n,m)=s(n-1,m-1)+(n-1)*s(n-1,m);
递推关系的说明:1.甲物体独自占一个圆排列,此时为s(n-1,m-1);
2.甲物体没有独自占一个圆排列,先把 n-1 个元素构成 m 个圆排列,为 s(n-1,m);再将甲元素插入到每个元素的左边(或是右边),为 (n-1)*s(n-1,m);
第二类stirling数:将n个不同的元素分成m个非空的集合的方案数
递推关系式:1.S(n,0)=S(0,n)=0;
2.S(n,1)=S(n,n)=1;
3.S(n,m)=S(n-1,m-1)+m*S(n-1,m);
递推关系式的说明:1.甲元素独自占一个集合,此时为S(n-1,m-1);
2.先将除甲之外的n-1个元素进行分割,为S(n-1,m),最后将甲插入,为m*S(n-1,m);
如果为m个不同的容器,为m!*S(n,m);
例:将n个不同的球放入m个不同的容器中所有的方案数(容器不能为空);
或者是:
n场比赛,m张牌(n>=m)每场比赛用一张牌,
#include#include#includeusing namespace std;
int stirling(int n,int m);
int fac(int m);
int sum[110][110];
int n,m;
int main()
{while(scanf("%d%d",&n,&m)!=EOF){printf("%d\n",stirling(n,m));}return 0;
}
int stirling(int n,int m)
{for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){if(ij) sum[i][j]=sum[i-1][j-1]+j*sum[i-1][j];}return sum[n][m]*fac(m);
}
int fac(int m)
{int num=1;for(int i=1;i<=m;i++)num*=i;return num;
}
每张牌至少用一次,问有几种方案数。
分析:n场比赛划分成m个集合,每个集合里的比赛只用同一张牌,
没有空的集合。也就是说把包含n个元素的集合划分为正好m个非空子集的方法的数目,
再乘m的全排列。
圆排列:
一.n个元素的圆排列
定义:n个不同元素按一定的相对顺序排成一圈,叫做n个元素的一个圆排列;
例如:将n个学生线性排列为n!,圆排列为(n-1)!;
证明:将一个元素个固定,将剩下的n-1元素线性排列为(n-1)!,所以圆排列为(n-1)!;
特点:1.元素无首尾之分
2.元素按同一方向转换后仍为同一圆排列
3.两个不同的圆排列,或元素不尽相同,或元素虽同但元素之间的相互顺序不同
二.n个元素中取m个元素的圆排列(每一种方案中有m个元素参与排列)
从n个不同的元素中取出m个元素的总数为
证明:对于线性排列中的一个排列,元素按同一方向转换,仍为同一圆排列,因此每m个线性排列对应于一个圆排列
更多推荐
Stirling 数
发布评论