n个球放入m个盒子定理

~

n个球放入m个盒子定理分为以下八种情况：

1、球同，盒不同，不允许空箱子：

这种情况很好解释，就是把球排成一行，有m-1个空位置，我从中选择n-1个，就把球分给了不同的盒子。

C(m-1,n-1)if n>=m

0,n<m

2、球同，盒不同，允许空箱子：

在1的基础上，可以假设每个盒子都已经有一个球了，这时候就和1情况一样了，就是说，有n+m个球，盒子不变。

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

3、球不同，盒同，不允许空箱子：

dp[n][m]表示n个球放在m个盒子，有多少种情况记作S[n][m]

递推式：当第n个来时，分两种情况，1：n-1个球放在了m个盒子里，那么第n个球可以放在m个盒子里的任何一个，所以是m*dp[n-1][m]2：n-1个球放在了m-1个盒子里，那么第m个球只能放在第m个盒子里了。

dp[n][m]=m*dp[n-1][m]+dp[n-1][m-1]

初始化：

dp[i][i]=1 i>=1

dp[i][1]=1 i>=1

dp[i][j]=0 i<j

4、球不同，盒同，允许空箱子：

dp[n][m]表示n个球放在m个盒子，有多少种情况记作M[n][m]

递推式：允许空箱子的情况在不允许空箱子的基础上去做,容易找到思路。

dp[n][m]=S[n][1]+S[n][2]+S[n][3]+...+S[n][m]

初始化：

dp[n][1]=1

5、球不同，盒不同，不允许空箱子：

dp[m][n]表示m个盒子装n个球，比较符合我的习惯L[m][n]

递推式：在情况3的情况下，加上盒子不同的条件，也就是将m个盒子排列。

dp[m][n]=S[m][n]*m！

6、球不同，盒不同，允许空箱子：

dp[m][n]表示m个盒子装n个球的情况数，记作T[m][n]

递推式：参考不允许空箱子5的情况

dp[m][n]=L[1][n]+L[2][n]+....+L[m][n]

但是：

这种情况可以简化，每个球都有m种选择，一共n个球，那么就有mn种结果。

7、球同，盒同，不允许空箱子：

dp[m][n]记作F[m][n]

递推式：先把m个盒子各自放一个球，还剩n-m个球，这些球可以放在m个盒子里，因为允许为空，所以可以是dp[1][n-m]+dp[2][n-m]+...+dp[m][n-m]

dp[m][n]=dp[1][n-m]+dp[2][n-m]+...+dp[m][n-m]

8：球同，盒同，允许空箱子。

dp[m][n]记作G[m][n]

递推式：参考不允许为空的情况7

dp[m][n]=F[1][n]+F[2][n]+...+F[m][n]

初始化：略

另外：可以假设有n+m个球，m个球已经在m个盒子各自放了一个，所以=F[m][n+m]

F[m][n+m]=F[1][n]+F[2][n]+...+F[m][n]证明和递推式一样。

---

茂名市13190815386： 将n只球放入m只盒中,n - ？
陟荷娃娃：[答案] 球落入盒中的概率是1/m 最后,所有的球都会落入盒中,球可以落入1、2、3…n个盒子当中 期望E=(1/m)^n*(1+2*Cn-1取1+3*Cn-1取2+…+(n-1)*Cn-1取(n-1)) 在这不好表达,不做计算

茂名市13190815386： 将n个球放入m个盒子中,某指定的一个盒子是空的概率______. - ？
陟荷娃娃：[答案] 根据题意,将n个球放入m个盒子中,某指定的一个盒子是空,即将这n个球放入其他(m-1)个盒子中, 每个小球放入其他(m-1)个盒子中的概率为m-1m=1-1m; 则这n个球放入其他(m-1)个盒子中的概率为(1-1m)n; 故答案为(1-1m)n.

茂名市13190815386： n个同样的球放入m个不同的盒子里,有多少种方法?(可以有空盒子).分n>m和n - ？
陟荷娃娃：[答案] C(m+n-1,n). 解 设A={a1,a2,…,am}代表m个不同的盒子构成的集合, n个同样的球放入这m个的盒子里,相当从m个元素中任取n个元素的可重复组合,即从A中可重复选取(A中的任意元素选取的个数不受限制,即可选0-n个)n个元素构成的组合. 如...

茂名市13190815386： n个同样的球放入m个不同的盒子里,有多少种方法?(可以有空盒子).分n>m和n<m两种讨论.给出公式就行了 - ？
陟荷娃娃： C(m+n-1,n).解 设A={a1,a2,…,am}代表m个不同的盒子构成的集合, n个同样的球放入这m个的盒子里,相当从m个元素中任取n个元素的可重复组合,即从A中可重复选取(A中的任意元素选取的个数不受限制,即可选0-n个)n个元...

茂名市13190815386： 将n只球随机地放在m个盒子中 - ？
陟荷娃娃： 设X表示有球的盒子数. 引入随机变量X(i) X(i)=1 (第i只盒子中有球) X(i)=0 (第i只盒子中无球) P(X(i)=1)=1-((m-1)/m)^n P(X(i)=0)=((m-1)/m)^n EX(i)=1*P(X(i))+0*P(X(i))=1-((m-1)/m)^n EX=E(X(1)+X(2)+...+X(m)=EX(1)+EX(2)+...EX(m)=m*(1-((m-1)/m)^n) 所以EX=m*(1-((m-1)/m)^n)

茂名市13190815386： N个皮球【全部】放到M个箱子里,【至少】有一个箱子里有皮球;有多少种装法?N》M的时候怎样,反过来怎样?具体的装法有公式吗? - ？
陟荷娃娃：[答案] 这个是个挡板问题 那个条件:,【至少】有一个箱子里有皮球是多余的,因为这个是必然的 共有N个小球,M-1个挡板,共N+M-1个元素 所以,装法有C (N+M-1,N)种 跟 N与M 的大小也无关

茂名市13190815386： n个球放到m个盒子中(n>m),每个盒子都有球的概率????? - ？
陟荷娃娃： 反过来看啊,盒子中有球有可能是1个球,2个球~~情况很多,那就可以考虑盒子中无球的情况,再用1去减.若是考虑盒子中无球,以球为对象考虑,有(M-1)/M的概率不在这个盒子中,而要每个球都不在的话就是它的n次方了,所以答案是1-((M-1)/M)^n

茂名市13190815386： N个一样的球,放到M个有编号的箱子里,有多少种放法?举例N=3,M=2,有4种方法:3,0,;2,1;1,2;0,3我已经解出了递推公式,1. f(n,m)=f(n,m - 1)+f(n - 1,m - 1)+f... - ？
陟荷娃娃：[答案] 把n个球摆成一排.把m-1个箱子往中间插,巷子左边的球都放进箱子里,没球就表示0个,最后一波放进剩下的箱子里. 所以就是n个球和m-1个箱子排序. C(m+n-1) n 括号里表示下脚标,括号外表示上角标. 【这就是传说的挡板法】 N=3,M=2 就是C(4) ...

茂名市13190815386： 将n个相同小球放到m个不同的盒子中,若允许某些盒子不放球,相当于在m+m - 1个空位中插m - 1块板.共有C(n+m - 1)(m - 1 )种方法,那个n+m - 1怎么来的? - ？
陟荷娃娃：[答案] 相当于在n+m-1个空位中插m-1块板,意思是2个之间有一个空位,3个有两个空,n+m个物体有n+m-1个空,这里是把球与和盒子看成同种东西,隔开之后就是在隔板之间的只有一个盒子剩下的小球都放进处在同一隔断中的盒子中

茂名市13190815386： 将n只球随机地放在m个盒子中将n只球随机地放在m个盒子中,每个盒子可装任意多个球,每个球以同样的概率落入每个盒子中,求 有球盒子数X的数学期望. - ？
陟荷娃娃：[答案] 设X表示有球的盒子数.引入随机变量X(i) X(i)=1 (第i只盒子中有球)X(i)=0 (第i只盒子中无球)P(X(i)=1)=1-((m-1)/m)^n P(X(i)=0)=((m-1)/m)^n EX(i)=1*P(X(i))+0*P(X(i))=1-((m-1)/m)^n EX=E(X(1)+X(2)+...+X(m)=EX(1)...