前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >浅谈"n个球"和"m个盒子"之间的乱伦关系

浅谈"n个球"和"m个盒子"之间的乱伦关系

作者头像
attack
发布2018-09-30 10:01:29
1.7K0
发布2018-09-30 10:01:29
举报
文章被收录于专栏:数据结构与算法

无视标题,从我做起

球异,盒同

不空

该情况为经典的第二类斯特灵数

设$fn$表示答案。

$fn = fn - 1 + m \times fn - 1$

边界条件:$f0 = 1$

答案 = 第$n$个数单独占一个盒子 + 第$n$个数和之前的数共占一个盒子,同时考虑不同位置的贡献

注意最后要乘$m$,因为第$n$个数放置的位置对答案是有影响的

例如{1}{2 4}{3}与{1}{2}{3 4}是不同的方案

题目中的应用

可空

直接枚举用了多少个盒子

设$gn$表示答案

则$gn = \sum_{i = 0}^m gn$

球异,盒异

可空

每一个球都有$m$种放法,故答案为$m^n$

不空

设$gn$表示答案,$sn$为第二类斯特灵数

则$gn = sn \times m!$

相当于是考虑$m$个盒子的顺序

球同,盒异

不空

插板法的经典例题

$n$个球之间形成$n - 1$个空位,把$m$个盒子塞到里面

方案为$C_{n - 1}^{m - 1}$

可空

注意这里不能直接套用“插板法”得到$C_{n+1}^{m - 1}$

因为使用插板法的前提条件之一就是“分成的方案不能为空”

考虑先在每个盒子中放一个小球,那么剩下的小球再往里放的时候就可以无视“非空的条件了”

故方案为$C_{n+m-1}^{m - 1}$

这里再补充一下为什么不能直接套用插板法

比如$n = 2, m = 3$时,方案为$6$,而直接套用插板法得到的答案为$3$。

究其原因,是因为没有考虑到两个板同时占了一个空位的情况。

球同,盒同

可空

这种情况下,不同方案之间与具体用了哪个球以及放到了哪个盒子里都没有必然的联系

区分不同方案的方法是:把每个盒子的球的个数从小到大排序,比较最终的情况是否相同

例如:$1  7  1$与$1  1  7  $实际是一种方案

对于$n = 8, m = 3$而言一共有$10$种不同的放法

0

0

8

0

1

7

0

2

6

0

3

5

1

1

6

1

2

5

1

3

4

2

3

4

3

3

3

从上面的分析我们也不难得出结论

$n$个相同的小球放到$m$个相同的盒子里的,盒子可以为空的方案数 与一个整数$n$拆成$m$段非递减序列的方案数相

设$fn$表示$n$个小球放到$m$个相同的盒子里,盒子可以为空的方案数

边界条件为$f0 = 1, f1 = 1, fk = 1$

递推方程$fn =

\begin{cases}

fn - m + fn &n >= m

\

fn &n < m

\end{cases}$

解释一下:

我们考虑这$m$个位置中是否有空盒子

显然:答案 = $m$个位置中至少有$1$个位置为空的方案 + $m$个位置中全不为空的方案

不空

我们可以先在所有盒子里都放了一个,然后对剩下的球讨论

同样可以得到一个结论:

$n$个相同的球,放到$m$个相同的盒子里,盒子不能为空的方案数 与把整数$n$拆成$m$段,每段不能为$0$的方案数相同

设$gn$表示$n$个小球放到$m$个相同的盒子里,盒子不能为空的方案数

则$gn = fn - m$,

题目链接

参考资料

“n个球放到m个盒子”问题整理

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-09-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 球异,盒同
    • 不空
      • 可空
      • 球异,盒异
        • 可空
          • 不空
          • 球同,盒异
            • 不空
              • 可空
              • 球同,盒同
                • 可空
                  • 不空
                  • 参考资料
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档