求一道排列组合题的通用解法

cloudcloud

20个相同的球放入5个不同的盒子 每个盒子里至少放一个球 且每个盒子里放入球的数量均不相同 问有多少种放法

我想来想去还是用枚举法做出来的 想问下这类型题目有没有更简便的方法？请大家不吝赐教

来自苹果APP客户端

dujshao

拆数，学而思一年级教过的

来自苹果APP客户端

勒布朗江

应该是7*120？。。。。

来自安卓APP客户端

177018508

是3875吗？
   

来自苹果APP客户端

随遇er安

小学数学已经这么难了？

来自苹果APP客户端

潜水专家001

把20拆成5个不同的数的和：1,2,3,4,10;12359,12458,12368,13457,12467，23456，应该是7种（不知道漏没漏），然后7*A55=840。

来自安卓APP客户端

Bud

fgrfgdfgh

最爱怪味豆

先枚举出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个相同的再排除掉）

来自苹果APP客户端

水库不水

如果没有每个盒子的数量不相同这个条件，挡板法最好，这个题目里面有这个条件，还是8楼的算法好些感觉

来自苹果APP客户端

kaka2000

这题拆数应该是最简单的方法了！

dujshao

学家一年级教的拆数

来自苹果APP客户端

hearts

插板法

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

wangwww

这个是一年级的题目？惊呆了

来自苹果APP客户端

潜水专家001

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

你这插板法没学好，人家有要求：每个盘子里的数量不能一样

来自安卓APP客户端

sjsj

这个题就是要列举的，为什么呢？
随便写几组数试试：
12345总和是15，离20就差5个球了
23456总和就是20。
这样敏锐一点的人就发现，最少的盒子里只能1个球或者2个球。而且两个球只有23456这一种可能。

下面再对第一个盒子已经是1进行分类：
12xxx
13xxx
14xxx是不可能的，因为4567>20

继续分第三个盒子：
123xx
124xx
125xx不可能了，因为12567>20
134xx
135xx同样不可能。

后面同理。

来自苹果APP客户端

cloudcloud

水库不水 发表于 2022-06-17 10:07
如果没有每个盒子的数量不相同这个条件，挡板法最好，这个题目里面有这个条件，还是8楼的算法好些感觉

是的 球的数量均不相同这个条件 会让插板法不太好用

来自苹果APP客户端

cloudcloud

水库不水 发表于 2022-06-17 10:04
先用挡板法（C19，4），不知道怎么输入，结果是19*18*17*16/2*3*4 = 3876
然后把有相同的个数排除掉（用枚举法把5个都相同，4个相同，3个相同，2个相同的再排除掉）

还要排除两个盒子数量相同 另两个盒子数量也相同的情况 太麻烦了 还不如枚举…

来自苹果APP客户端

sjsj

刚刚在app上回复了这个帖子，不知道为什么没有显示。在电脑上再写一次好了。
这个题肯定是要列举法的，为什么呢？写几组试试就知道了。
12345，和是15，离20就差5了
23456，和是20，正好。

所以只有两种可能（从小到大排序，这个排序是个关键）：
1xxxx
2xxxx
（为什么3xxxx不行？因为34567和>20）

对1xxxx再往下分：
1xxxx有：
  12xxx
  13xxx
  （14xxx就不行）

最后我们可以形成一个树状图，这样数是不会有遗漏的，共7种：



这题是要会举一反三的，如果题目改成4个盒子或者6个盒子，有多少个球这个题的枚举数量会比较好呢？家长要先自己搞清楚

hearts

潜水专家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不大的时候，计算量比一个一个数应该是大不少。

xjyxiao

hearts 发表于 2022-6-17 15:26
没看见。

那就首先假设盒子都相同，然后再乘以P(5,5)就好。

收获一个宝藏网站！

Bud

母函数很强大。

来自苹果APP客户端

cfa2000

cloudcloud 发表于 2022-06-17 14:41
还要排除两个盒子数量相同 另两个盒子数量也相同的情况 太麻烦了 还不如枚举…

先枚举再排列，比较快。其他反而麻烦。

来自苹果APP客户端

cloudcloud

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&lt;=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)-...........


所以对于这个题一个一个数其实是唯一解法。

或者，先把本题&nbsp; &nbsp;20个数分成5个不同的数， 转化为 把 5个数分成不同的数，然后通过递归算（这个比较特殊，因为本题正好能转，不是所有的都能转）
p(0)=1&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp; 0=0
p(1)=1&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp; 1=1
p(2)=p(0)+p(1)=2&nbsp; &nbsp; 2=2、1+1
p(3)=p(2)+p(1)=3&nbsp; &nbsp; 3=3、1+2、1+1+1
p(4)=p(3)+p(2)=5&nbsp; &nbsp; 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不大的时候，计算量比一个一个数应该是大不少。

谢谢分享 很有帮助 太感谢了！

来自苹果APP客户端

bluemona

有点对小学数学产生恐惧了……

来自苹果APP客户端