Stirling数
2024-09-03 11:18:10
第一类:
定义
第一类Stirling数表示表示将 n 个不同元素构成m个圆排列的数目。又根据正负性分为无符号第一类Stirling数
和带符号第一类Stirling数
。有无符号Stirling数分别表现为其升阶函数和降阶函数的各项系数[类似于二项式系数[3] ],形式如下:
对于有无符号Stirling数之间的关系有
。组合数学中的第一类Stirling数一般指无符号的第一类Stirling数。意思是n个不同元素构成m个圆排列的方案数。
所以
f(a,b)=f(a,b-1)+f(a-b,b)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int t;//测试数据数量
int n;//苹果数
int m; //盘子数
int tot=;//最多有几种放法
int f(int a,int b)
{
if(a<=||b<=)//当只有一个苹果或一个盘时,只有一种放法
return ;
if(a<b)
return f(a,a);//苹果数<盘数,则最多只有b个盘有苹果
else
return f(a,b-)+f(a-b,b);///如果有一个不放,则有 f(a,b-1)种;如果每个都放,则相当于 f(a-b,b)
}
int main()
{ cin>>t;
for(int i=;i<=t;i++)
{
cin>>m>>n;
cout<<f(m,n)<<endl;
}
return ; }
Code
第二类:
定义
第二类Stirling数实际上是集合的一个拆分,表示将n个不同的元素拆分成m个集合的方案数,记为
或者
。和第一类Stirling数不同的是,集合内是不考虑次序的,而圆排列是有序的。常常用于解决组合数学中几类放球模型。描述为:将n个不同的球放入m个无差别的盒子中,要求盒子非空,有几种方案?
所以:
f(n,m)=f(n-1,m-1)+f(n-1,m)*m
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int t;
int n;
int m;
int tot=;
int f(int a,int b)
{
if(a<=||b<=)
return ;
if(a<b)
return f(a,a);
else
return f(a-,b-)+f(a-,b)*b;
}
int main()
{ cin>>t;
for(int i=;i<=t;i++)
{
cin>>m>>n;
cout<<f(m,n)<<endl;
}
return ;
}
最新文章
- 一个App Widget实例第一次创建时被调用
- 移除首页->;重回首页
- Eclipse中Java项目转换为Web项目
- make_head,,,pop_head,,,push_head,,,sort_head..
- Epoll模型详解
- innobackupex 备份实验
- 函数os_file_pread
- HDU 5313 Bipartite Graph (二分图着色,dp)
- 慕课linux学习笔记(八)常用命令(5)
- Xamarin+Prism开发详解八:自动化测试之NUnit实践
- 禁止Linux系统被 ping
- SQL学习入门(一) 概述
- C#基础概念总结
- 随手小代码——Python 从集合中随机抽取元素
- 通过ICE轻松部署WES7镜像
- Java上传文件FTP服务器代码
- 多线程Task
- 【转】ubuntu apt-get update 失败解决
- 善用 CSS 中的 table-layout 屬性加快 Table 的顯示速度
- POJ-1458 Common Subsequence(线性动规,最长公共子序列问题)