【排列组合】排列组合 "n个球放入m个盒子m"问题

港控/mmm° 2022-06-01 04:55 228阅读 0赞

[【转载博文地址，感谢博主分享】][Link 1]

求，盒子都可以分成是否不能区分，和能区分，还能分成是否能有空箱子，所以一共是8种情况，我们现在来一一讨论。

1.球同，盒不同，无空箱

C(n-1,m-1), n>=m  
0, n < m

使用插板法：n个球中间有n-1个间隙，现在要分成m个盒子，而且不能有空箱子，所以只要在n-1个间隙选出m-1个间隙即可

2.球同，盒不同，允许空箱

C(n+m-1,m-1)

我们在第1类情况下继续讨论，我们可以先假设m个盒子里都放好了1个球，所以说白了就是，现在有m+n个相同的球，要放入m个不同的箱子，没有空箱。也就是第1种情况

3.球不同，盒相同，无空箱

第二类斯特林数dp\[n\]\[m\]  
dp\[n\]\[m\]=m\*dp\[n-1\]\[m\]+dp\[n-1\]\[m-1\],1 <= m < n  
dp\[k\]\[k\]=1,k>=0  
dp\[k\]\[0\]=0,k>=1  
0,n < m

这种情况就是第二类斯特林数，我们来理解一下这个转移方程。

对于第n个球，如果前面的n-1个球已经放在了m个箱子里，那么现在第n个球放在哪个箱子都是可以的，所以m\*dp\[n-1\]\[m\];

如果前n-1个球已经放在了m-1个箱子里，那么现在第n个球必须要新开一个箱子来存放，所以dp\[n-1\]\[m-1\]

其他的都没法转移过来

4.球不同，盒相同，允许空箱

sigma dp\[n\]\[i\],0<=i<=m,dp\[n\]\[m\]为情况3的第二类斯特林数

这种情况就是在第3种情况的前提下，去枚举使用的箱子的个数

5.球不同，盒不同，无空箱

dp\[n\]\[m\]\*fact\[m\],dp\[n\]\[m\]为情况3的第二类斯特林数,fact\[m\]为m的阶乘

因为球是不同的，所以dp\[n\]\[m\]得到的盒子相同的情况，只要再给盒子定义顺序，就等于现在的答案了

6.球不同，盒不同，允许空箱

power(m,n) 表示m的n次方

每个球都有m种选择，所以就等于m^n

7.球同，盒同，允许空箱

dp\[n\]\[m\]=dp\[n\]\[m-1\]+dp\[n-m\]\[m\], n >= m  
dp\[n\]\[m\]=dp\[n\]\[m-1\], n < m  
边界dp\[k\]\[1\]=1,dp\[1\]\[k\]=1,dp\[0\]\[k\]=1

现在有n个球，和m个箱子，我可以选择在所有箱子里面都放上1个球，也可以不选择这个操作。

如果选择了这个操作，那么就从dp\[n-m\]\[m\]转移过来

如果没有选择这个操作，那么就从dp\[n\]\[m-1\]转移过来

8.球同，盒同，无空箱

dp\[n-m\]\[m\],dp同第7种情况,n >= m  
0, n < m

因为要求无空箱，我们先在每个箱子里面放1个球，然后还剩下n-m个球了，再根据情况7答案就出来了

[Link 1]: http://blog.csdn.net/qwb492859377/article/details/50654627

发表评论取消回复

表情：

评论列表（有 0 条评论，228人围观）

还没有评论，来说两句吧...

相关阅读

相关 n个数组实现排列组合

命题场景：现在有一批手机，其中颜色有［‘白色’,‘黑色’,‘金色’］；内存大小有［‘16G’,‘32G’,‘64G’］，版本有［‘移动’,‘联通’,‘电信’］，要求写一个算

╰半橙微兮°/ 2023年07月16日 12:57/ 0 赞/ 61 阅读

相关今日三个排列组合练习

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

快来打我*/ 2022年12月26日 10:29/ 0 赞/ 138 阅读

相关排列组合

排列组合问题： 1. 字符串全排列(permutation) 转自：[http://www.cnblogs.com/sujz/archive/2011/06/16/20828

我不是女神ヾ/ 2022年09月17日 06:27/ 0 赞/ 291 阅读

相关 m个苹果放入n个盘子

题目描述放苹果问题：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（注：5,1,1和1,1,5是同一种分法）解题分析：

约定不等于承诺〃/ 2022年08月08日 05:23/ 0 赞/ 236 阅读

相关排列组合问题

1.排列问题：（1）递归解法：以abc为例 (1).第一个字符分别与后面的字符交换 (2).第二个字符分别与之后的字符交换，和(1)相同，进行递归。 includ

矫情吗；*/ 2022年08月04日 13:37/ 0 赞/ 246 阅读

相关求一个数组，n个元素的不同组合(排列组合问题)

array('a1','b2','c3','d4','e5','x1','y1','z1');比如以上数组我想要这个数组元素中三个元素的不同组合，例如下 array('a

偏执的太偏执、/ 2022年06月14日 00:07/ 0 赞/ 269 阅读

相关【排列组合】排列组合 "n个球放入m个盒子m"问题

[【转载博文地址，感谢博主分享】][Link 1] 求，盒子都可以分成是否不能区分，和能区分，还能分成是否能有空箱子，所以一共是8种情况，我们现在来一一讨论。 1.球同，盒

港控/mmm°/ 2022年06月01日 04:55/ 0 赞/ 229 阅读

相关 [LeetCode] java的排列与组合C(m,n)、A(m,n)

考题出处: [子集][Link 1] > 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 > 说明：解集不能包含重复的子集。 >

淩亂°似流年/ 2022年05月18日 04:13/ 0 赞/ 435 阅读

相关全排列、排列、排列组合

排列组合问题小总结：排列组合方法 1、for循环层层枚举 2、交换递归全排列 /给出

一时失言乱红尘/ 2021年12月20日 02:15/ 0 赞/ 489 阅读

相关排列组合

1.引言 pku的OJ平台1731题，就是求一个输入字符串的全排列。在STL中有两个和排列相关的算法，next\_permutation和prev\_per

以你之姓@/ 2021年10月16日 00:14/ 0 赞/ 592 阅读