[总结] 第二类Stirling数
2024-10-11 14:48:52
上一道例题
我们来介绍第二类Stirling数
定义
第二类Stirling数实际上是集合的一个拆分,表示将n个不同的元素拆分成m个集合的方案数,记为
或者
。和第一类Stirling数不同的是,集合内是不考虑次序的,而圆排列是有序的。常常用于解决组合数学中几类放球模型。描述为:将n个不同的球放入m个无差别的盒子中,要求盒子非空,有几种方案?
第二类Stirling数要求盒子是无区别的,所以可以得到其方案数公式:
递推式
第二类Stirling数的推导和第一类Stirling数类似,可以从定义出发考虑第n+1个元素的情况,假设要把n+1个元素分成m个集合则分析如下:
(1)如果n个元素构成了m-1个集合,那么第n+1个元素单独构成一个集合。方案数
。
(2)如果n个元素已经构成了m个集合,将第n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。
综合两种情况得:
应用举例
第二类Stirling数主要是用于解决组合数学中的几类放球模型。主要是针对于球之前有区别的放球模型:
(1)n个不同的球,放入m个无区别的盒子,不允许盒子为空。
方案数:
。这个跟第二类Stirling数的定义一致。
(2)n个不同的球,放入m个有区别的盒子,不允许盒子为空。
方案数:
。因盒子有区别,乘上盒子的排列即可。
(3)n个不同的球,放入m个无区别的盒子,允许盒子为空。
方案数:
。枚举非空盒的数目便可。
(4)n个不同的球,放入m个有区别的盒子,允许盒子为空。
①方案数:
。同样可以枚举非空盒的数目,注意到盒子有区别,乘上一个排列系数。
②既然允许盒子为空,且盒子间有区别,那么对于每个球有m中选择,每个球相互独立。有方案数:
。
上述式子可以应用于第二类Stirling数通项的求解。
通项公式
最新文章
- 设计模式C#实现(十四)——责任链模式
- 第一章.C语言简介
- oracle 报警日志详解
- mvc路由,mvc区域
- java提高篇---HashSet
- Android应用增量更新
- Filter登录验证过滤器(全局)
- java新手笔记7 找最小、最大、排序
- eclipse python开发环境搭建
- 仓储Repository
- (Matlab)GPU计算所需的配置
- kubeadm的安装步骤(HA)
- Android第四次作业
- docker介绍
- 5.sql2008分组与嵌套
- 20155205 2016-2017-2 《Java程序设计》第10周学习总结
- Vue购物车
- thinkphp自学笔记
- HDU 3709 Balanced Number(数位DP)题解
- JS实现图的创建和遍历
热门文章
- Wireshark理解TCP乱序重组和HTTP解析渲染
- pc浏览器css和js计算浏览器宽度的差异以及和滚动条的关系
- Qemu,KVM,Virsh傻傻的分不清
- Meet Python
- JXL组件生成报表报错(一)
- Caused by: java.sql.SQLException: Incorrect integer value: '' for column 'clientId' at row 41
- java的System.getProperty()获取的值
- C# Coding Conventions(译)
- SpringBean基础装配
- CentOS 7.x 防火墙开放端口相关用法记录