作业帮现有n个完全相同的小球.把它们分成m堆.每一堆至少有一个球.问有几种分法?例如n=7 m=4 有{1,1,1,4} {1,2,2,2} {1,1,2,3} 这3种分法.注:{1,1,1,4} {1,1,4,1} {1,4,1,1} {4,1,1,1} 是完全一样的分法,算一种提供资料
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 06:32:07
现有n个完全相同的小球.把它们分成m堆.每一堆至少有一个球.问有几种分法?例如n=7 m=4 有{1,1,1,4} {1,2,2,2} {1,1,2,3} 这3种分法.注:{1,1,1,4} {1,1,4,1} {1,4,1,1} {4,1,1,1} 是完全一样的分法,算一种提供资料
现有n个完全相同的小球.把它们分成m堆.每一堆至少有一个球.
问有几种分法?
例如n=7 m=4 有{1,1,1,4} {1,2,2,2} {1,1,2,3} 这3种分法.
注:{1,1,1,4} {1,1,4,1} {1,4,1,1} {4,1,1,1} 是完全一样的分法,算一种
提供资料也可
那篇东西说的什么?我英语烂看不懂啊
一楼的是错的吧?
我再等等...
现有n个完全相同的小球.把它们分成m堆.每一堆至少有一个球.问有几种分法?例如n=7 m=4 有{1,1,1,4} {1,2,2,2} {1,1,2,3} 这3种分法.注:{1,1,1,4} {1,1,4,1} {1,4,1,1} {4,1,1,1} 是完全一样的分法,算一种提供资料
这就是“整数划分”问题：
将自然数n写为m个自然数的和,不计顺序,共有多少种方法.
用递推来计算（没有简单的公式）：
设A(n,m)为自然数n写为m个自然数和的方法.则：
A(n,m) = A(n-1,m-1) + A(n-m,m)
这个递推式的意思是这样的：
我们要把n写为m个数的和.有两种情形：(1)和式中的最小数为1；(2)和式中的最小数至少是2.
对第一种情形,我们把和式中的一个1去掉,剩下的和式就是将n-1写为m-1个数的和了,于是就是A(n-1,m-1)种.
对第二种情形,我们把和式中每个元素都减去1,变成了将n-m写为m个数的和式,于是就是A(n-m,m)种.
剩下的就是初始值了：
对任意n,A(n,1)=A(n,n)=1；
按照递推的计算方法,一步一步算下去,就可以了.
其实,就是填A(i,j)的表格,一列一列的填.