球盒模型（2）的简单求法

球盒模型（2）

问：将m个球放到n个带中,有k种方法，可空，若M=8，N=5，K=?

解：

一般情况下（m球,n盒，不可空）方法数为P(m,n)

等价于P(m,n+m)

可以列出P(m,n)=P(1,n)+p(2,n)+...+P(m,n)

也等价于P(m,n+m)=P(1,n)+p(2,n)+...+P(m,n)

通过举例子找规律可以发现:P(1,n)=P(n,n)=P(n-1,n)=1,且P(2,m)=向下取整(n/2)

则本题目：

P(5,8) = P(5,5+8) = P(1,8) + P(2,8) + P(3,8) + P(4,8) + P(5,8)

结合上述分析直接可得P(1,8)=1          P(2,8)=向下取整(8/2)=4

P(3,8)=P(3,8-3)=P(3,5)=P(1,5)+P(2,5)+P(3,5)=1+2+P(3,5-3)=3+P(3,2)=3+P(1,2)+P(2,2)=5

//P(3,5)可以继续拆下去：P(3,5-3)=P(3,2)=P(1,2)+P(2,2)这样就好算了

P(4,8)=P(4,8-4)=P(4,4)=P(1,4)+P(2,4)+P(3,4)+P(4,4)=1+2+1+1=5

//P(3,4)=P(n-1,n)=1  P(4,4)=P(n,n)=1

P(5,8)=P(5,8-5)=P(5,3)=P(1,3)+P(2,3)+P(3,3)=1+1+1=3//不多说了

因此：P(5,8) = P(5,5+8) = P(1,8) + P(2,8) + P(3,8) + P(4,8) + P(5,8) = 1+4+5+5+3=18