求一道排列组合题的通用解法
20个相同的球放入5个不同的盒子 每个盒子里至少放一个球 且每个盒子里放入球的数量均不相同 问有多少种放法我想来想去还是用枚举法做出来的 想问下这类型题目有没有更简便的方法？请大家不吝赐教
拆数，学而思一年级教过的 本帖最后由 勒布朗江 于 2022-6-17 20:48 编辑
应该是7*120？。。。。 是3875吗？
小学数学已经这么难了？https://app.qianfanedu.cn/public/emotion/face_013.png 把20拆成5个不同的数的和：1,2,3,4,10;12359,12458,12368,13457,12467，23456，应该是7种（不知道漏没漏），然后7*A55=840。 fgrfgdfgh
本帖最后由 最爱怪味豆 于 2022-6-17 09:28 编辑
先枚举出7种数字组合方式。如果盒子一样要每盒数量不同，意味着每一个后面的数必须大于它前面的数，不然就重复了。现在5个盒子不同，那么这七组数字再排列组合
1,2,3,4,10/ 1,2,3,5,9/ 1,2,3,6,8/1,2,4,5,8/1,2,4,6,7/1,3,4,5,7/2,3,4,5,6 先用挡板法（C19，4），不知道怎么输入，结果是19*18*17*16/2*3*4 = 3876
然后把有相同的个数排除掉（用枚举法把5个都相同，4个相同，3个相同，2个相同的再排除掉） 如果没有每个盒子的数量不相同这个条件，挡板法最好，这个题目里面有这个条件，还是8楼的算法好些感觉 这题拆数应该是最简单的方法了！ 学家一年级教的拆数 插板法
20个球
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19个空，插4个板
C19,4 = 19*18*17*16/4/3/2 = 3876 这个是一年级的题目？惊呆了https://app.qianfanedu.cn/public/emotion/face_013.png hearts 发表于 2022-06-17 13:08
插板法
20个球
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19个空，插4个板
C19,4 = 19*18*17*16/4/3/2 = 3876
你这插板法没学好https://app.qianfanedu.cn/public/emotion/face_018.png，人家有要求：每个盘子里的数量不能一样 这个题就是要列举的，为什么呢？
随便写几组数试试：
12345总和是15，离20就差5个球了
23456总和就是20。
这样敏锐一点的人就发现，最少的盒子里只能1个球或者2个球。而且两个球只有23456这一种可能。
下面再对第一个盒子已经是1进行分类：
12xxx
13xxx
14xxx是不可能的，因为4567>20
继续分第三个盒子：
123xx
124xx
125xx不可能了，因为12567>20
134xx
135xx同样不可能。
后面同理。 水库不水 发表于 2022-06-17 10:07
如果没有每个盒子的数量不相同这个条件，挡板法最好，这个题目里面有这个条件，还是8楼的算法好些感觉
是的 球的数量均不相同这个条件 会让插板法不太好用 水库不水 发表于 2022-06-17 10:04
先用挡板法（C19，4），不知道怎么输入，结果是19*18*17*16/2*3*4 = 3876
然后把有相同的个数排除掉（用枚举法把5个都相同，4个相同，3个相同，2个相同的再排除掉）
还要排除两个盒子数量相同 另两个盒子数量也相同的情况 太麻烦了 还不如枚举… 刚刚在app上回复了这个帖子，不知道为什么没有显示。在电脑上再写一次好了。
这个题肯定是要列举法的，为什么呢？写几组试试就知道了。
12345，和是15，离20就差5了
23456，和是20，正好。
所以只有两种可能（从小到大排序，这个排序是个关键）：
1xxxx
2xxxx
（为什么3xxxx不行？因为34567和>20）
对1xxxx再往下分：
1xxxx有：
12xxx
13xxx
（14xxx就不行）
最后我们可以形成一个树状图，这样数是不会有遗漏的，共7种：
这题是要会举一反三的，如果题目改成4个盒子或者6个盒子，有多少个球这个题的枚举数量会比较好呢？家长要先自己搞清楚
本帖最后由 hearts 于 2022-6-17 15:49 编辑
潜水专家001 发表于 2022-6-17 13:40
你这插板法没学好，人家有要求：每个盘子里的数量不能一样
没看见。
那就首先假设盒子都相同，然后再乘以P(5,5)就好。
20个数很容易数吧。
20=
1+2+3+4+10
1+2+3+5+9
1+2+3+6+8
1+2+4+5+8
1+2+4+6+7
1+3+4+5+7
2+3+4+5+6
就7个，7*P(5,5)
要是非要找通用公式，我刚才搜了一下，其实研究还是很充分的，没有通用公式，只能提供generating function。
但有一点能简化。
https://www.mathpages.com/home/kmath556/kmath556.htm
指出，把(n+k(k+1)/2)分成k个不同的数相加，和 把n分成小于等于k个数相加是相同的。
例如n=5,k=5,把(5+5*6/2)=20，分成k=5个不同的数相加，（就是本题）
和把n=5分成小于等于k=5个数相加，是一样的。
就是5=
5
1+4
2+3
1+1+3
1+2+2
1+1+1+2
1+1+1+1+1
7个相同。
注意把n个数分成k数相加的（k<=n)，也一样是没有通用解的。
https://www.whitman.edu/mathemat ... k/section03.03.html
但有一个递归解
把n分成几个整数相加（所有的可能），
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-17)-...........
所以对于这个题一个一个数其实是唯一解法。
或者，先把本题 20个数分成5个不同的数， 转化为 把 5个数分成不同的数，然后通过递归算（这个比较特殊，因为本题正好能转，不是所有的都能转）
p(0)=1 0=0
p(1)=1 1=1
p(2)=p(0)+p(1)=2 2=2、1+1
p(3)=p(2)+p(1)=3 3=3、1+2、1+1+1
p(4)=p(3)+p(2)=5 4=4、1+3 、2+2 、1+1+2、1+1+1+1
p(5)=p(4)+p(3)-p(0)=7
当然如果就想通过公式算，只能通过generating function，然后再算，n不大的时候，计算量比一个一个数应该是大不少。
hearts 发表于 2022-6-17 15:26
没看见。
那就首先假设盒子都相同，然后再乘以P(5,5)就好。
收获一个宝藏网站！ 母函数很强大。 cloudcloud 发表于 2022-06-17 14:41
还要排除两个盒子数量相同 另两个盒子数量也相同的情况 太麻烦了 还不如枚举…
先枚举再排列，比较快。其他反而麻烦。 hearts 发表于 2022-06-17 15:26
本帖最后由 hearts 于 2022-6-17 15:49 编辑
没看见。
那就首先假设盒子都相同，然后再乘以P(5,5)就好。
20个数很容易数吧。
20=
1+2+3+4+10
1+2+3+5+9
1+2+3+6+8
1+2+4+5+8
1+2+4+6+7
1+3+4+5+7
2+3+4+5+6
就7个，7*P(5,5)
要是非要找通用公式，我刚才搜了一下，其实研究还是很充分的，没有通用公式，只能提供generating function。
但有一点能简化。
https://www.mathpages.com/home/kmath556/kmath556.htm
指出，把(n+k(k+1)/2)分成k个不同的数相加，和 把n分成小于等于k个数相加是相同的。
例如n=5,k=5,把(5+5*6/2)=20，分成k=5个不同的数相加，（就是本题）
和把n=5分成小于等于k=5个数相加，是一样的。
就是5=
5
1+4
2+3
1+1+3
1+2+2
1+1+1+2
1+1+1+1+1
7个相同。
注意把n个数分成k数相加的（k<=n)，也一样是没有通用解的。
https://www.whitman.edu/mathemat ... k/section03.03.html
但有一个递归解
把n分成几个整数相加（所有的可能），
p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-17)-...........
所以对于这个题一个一个数其实是唯一解法。
或者，先把本题 20个数分成5个不同的数， 转化为 把 5个数分成不同的数，然后通过递归算（这个比较特殊，因为本题正好能转，不是所有的都能转）
p(0)=1 0=0
p(1)=1 1=1
p(2)=p(0)+p(1)=2 2=2、1+1
p(3)=p(2)+p(1)=3 3=3、1+2、1+1+1
p(4)=p(3)+p(2)=5 4=4、1+3 、2+2 、1+1+2、1+1+1+1
p(5)=p(4)+p(3)-p(0)=7
当然如果就想通过公式算，只能通过generating function，然后再算，n不大的时候，计算量比一个一个数应该是大不少。
谢谢分享 很有帮助 太感谢了！ 有点对小学数学产生恐惧了……
页:
[1]