数学研发论坛

 找回密码
 欢迎注册
查看: 523|回复: 27

[悬赏] 小球装盒的问题

[复制链接]
发表于 2018-2-1 20:21:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
将m个完全相同的小球,分别装入n个完全相同的盒子里。要求每个盒子里至少装一个小球(m>n),问有几种不同的装法?

补充内容 (2018-2-2 13:51):
此问题能进行具体计算,但问题的关键:是否有计算公式?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-1 21:33:19 | 显示全部楼层
问题的本质是正整数 `m` 的(无序) `n`- 拆分.
考虑到至少每个盒子里放一个,故剩余 `m-n` 个可自由分配,即 `m-n` 的拆分数 `p(m-n)`.
生成函数为 `G(x)=\D\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots(1-x^{m-n})}=\sum_{i\geqslant 0} p(i)x^i`.

点评

这位老师的方法很不错。但只能进行具体计算,推不出计算公式。  发表于 2018-2-2 13:53
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 10:35:56 | 显示全部楼层
上面的结论有个前提条件:`m-n \leqslant n`,即 `m\leqslant 2n`,否则会计算多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 11:27:30 | 显示全部楼层
根据Ferrers图的共轭性质可推知:一个整数 `m` 拆分成恰好为 `n` 部分的拆分数,等于这个整数 `m` 拆分成最大部分为 `n` 的拆分数。
因此,生成函数应该是 `G(x)=\D\frac{x^n}{(1-x)(1-x^2)(1-x^3)\cdots(1-x^{n})}=\sum_{i\geqslant 0} p(i)x^i`,其结果应该对应于 `p(m)`.

例如,将50恰好拆分为13个正整数之和的拆分数为15988,验证:
  1. IntegerPartitions[50, {13}] // Length
  2. SeriesCoefficient[x^13/Product[1 - x^k, {k, 1, 13}], {x, 0, 50}]
复制代码

点评

p(m)的计算公式是啥?  发表于 2018-2-2 13:54
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 11:54:21 | 显示全部楼层
从上述母函数形式可以看出,这个拆分数同时也等于整数 `m-n` 拆分为每部分不超过 `n` (注意,可以都小于)的拆分数。再根据Ferrers图共轭性质,这有等价为整数 `m-n` 拆分为至多 `n` 个部分的拆分数.
验证:
  1. IntegerPartitions[50 - 13, All, Range[13]] // Length
  2. IntegerPartitions[50 - 13, {1, 13}] // Length
复制代码

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 11:54:58 | 显示全部楼层
本帖最后由 lsr314 于 2018-2-2 11:57 编辑

和方程$x_1+x_2+……+x_n=m$的正整数解的个数是不是等价的?还是说轮换视为同一个解?

点评

有计算公式吗?  发表于 2018-2-2 13:55
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 12:01:57 | 显示全部楼层
本帖最后由 kastin 于 2018-2-2 12:18 编辑
lsr314 发表于 2018-2-2 11:54
和方程$x_1+x_2+……+x_n=m$的正整数解的个数是不是等价的?还是说轮换视为同一个解?


这个不定方程解的个数是有序拆分,若加上一个约束 `x_1\geqslant x_2\geqslant \cdots\geqslant x_n`,才等价为无序拆分,见 https://bbs.emath.ac.cn/forum.ph ... 65&fromuid=8865

点评

是否有计算公式?  发表于 2018-2-2 13:56
因此楼主的问题等价为不定方程 `x_1+2x_2+3x_3+\cdots_nx_n=m-n` 的非负整数解的个数。  发表于 2018-2-2 12:25
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 14:58:53 | 显示全部楼层
本帖最后由 kastin 于 2018-2-2 17:05 编辑

上面的符号不太统一,这里我们约定 `p_{a}^{b}(m)` 表示整数 `m` 在约束条件 `a,b` 下的拆分数,其中 `a` 表示拆分成的部分的个数约束,`b` 表示拆分成的每部分的约束。考虑到拆分部分最小为1,最大为被拆分的整数(相应地,拆分的部分的个数最多为m,最小为1),故若约束条件任何之一省略掉(无特殊约束),便等价为默认 `\leqslant m`.
比如,`p_{\leqslant n}(m)` 表示 `m` 拆分为至多 `n` 个部分的拆分数。又等价为 `p_{\leqslant n}^{\leqslant m}(m)`的值。又如,`p_{=n}^{\geqslant 4}(m)` 表示 `m` 恰好拆分为 `n` 个部分,且每个部分不小于 `4` 的拆分数。 再如,`p^{\max= n}(m)` 表示 `m` 进行拆分,使得拆分的最大部分等于 `n` 的拆分数。

楼主的问题的结果就是 `p_{=n}(m)`,根据前面提到的等价关系,有 `p_{=n}(m)=p^{\max=n}(m)=p^{\leqslant n}(m-n)=p_{\leqslant n}(m-n)`.
整数拆分的一般情况,即没有特殊约束 `p(m)` 是没有通式表达的,只有通过母函数或递推关系计算。
但楼主的问题 `p_{=n}(m)` 对于 `n` 取具体值是有通式的:
`n=2`,即 `m` 个同样的球放到 `2` 个相同的的盒子里,每个盒子至少一个球,共有 `p_{=2}(m)=\D\frac{2m+(-1)^m-1}{4}=\lfloor \frac m2 \rfloor` 种方法。
`n=3`,即 `m` 个同样的球放到 `3` 个相同的的盒子里,每个盒子至少一个球,共有 `p_{=3}(m)=\D\frac{m^2}{12}-\frac{(-1)^m}{8}-\frac{7}{72}+\frac 29\cos\frac{2m\pi}{3}=\lfloor \frac {m^2+3}{12} \rfloor` 种方法。
剩下则公式更为复杂,里面包含各种三角函数。想要化简为取整函数的简单表达,需要分析 `m` 除以 `n` 的各种倍数的余数情况,得到不同情形下取整函数表达。

点评

@zuijianqiugen,对于m、n的具体数值计算,能把你的升序排列解法透露一下吗?。  发表于 2018-2-14 13:17
@zuijianqiugen,我只是个数学爱好者,水平并不高,远不及论坛中其他资深前辈。请以后不要用 “大师”,“老师”一类的词,也不用夸赞,论坛中平等交流即可。  发表于 2018-2-2 15:35
希望这位老师找出当n=4、5时,并不多复杂的计算公式。  发表于 2018-2-2 15:25
这位老师的水平是大大的高,值得点赞。找出当n=2、3时,有简单的计算公式。估计当n=4、5时,也不会多复杂,关键在于计算方式和技巧。  发表于 2018-2-2 15:23

评分

参与人数 1金币 +2 贡献 +1 鲜花 +1 收起 理由
zuijianqiugen + 2 + 1 + 1 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 15:30:03 | 显示全部楼层
上述通项公式的怎么来?笔算的话,有两种方法:
第一种是将对应的母函数裂项未低次分式之和,然后分别展开为泰勒级数形式,取系数得到通项公式;
第二种是利用柯西积分公式-留数法,见 https://bbs.emath.ac.cn/thread-15213-1-1.html,不过要注意,链接中给的是正整数解的个数,根据7楼评论可知,楼主问题结果应该是链接中非负整数解的个数的情况,即链接中6楼推导的情形。

其实二者本质是一样的,泰勒级数是 Laurent 级数的特殊情形,后者则与柯西积分公式的推广形式相关。

偷懒的话,直接用MMA计算(我怀疑MMA内部是用第二种方法计算的),当然也只适用于 `n` 取具体指的情况,而且给出的结果含有复数,需要自己进一步整理化简。比如 `n=3` 的例子:
  1. SeriesCoefficient[x^3/Product[1 - x^k, {k, 1, 3}], {x, 0, m},
  2.   Assumptions -> m > 3 && m \[Element] Integers] // ExpToTrig
复制代码

点评

@zuijianqiugen,对于m、n的具体数值计算,能把你的升序排列解法透露一下吗?。  发表于 2018-2-17 10:57
@zuijianqiugen,并非任何数列都存在有限的初等表达的通项公式的。  发表于 2018-2-2 17:12
对于m、n的具体数值计算,我找到一种升序排列的方法。问题在于难以找到通项公式。  发表于 2018-2-2 15:51
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-2 17:04:02 | 显示全部楼层
本帖最后由 kastin 于 2018-2-2 17:06 编辑

`n=4`,`p_{=4}(m)=\D \frac{m^3+3m^2}{144}-\frac{m}{32}-\frac {13}{288}+\frac{(-1)^m}{32}(m+1)+\frac 18\cos\frac{m\pi}{2}-\frac{2}{9\sqrt{3}}\sin \frac{2(m+1)\pi}{3}`.
`n=5` 的情况自己自己动手算吧,方法都说清楚了。

评分

参与人数 1金币 +2 贡献 +1 经验 +1 鲜花 +1 收起 理由
zuijianqiugen + 2 + 1 + 1 + 1 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-5-27 21:36 , Processed in 0.070386 second(s), 26 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表