小球装盒的问题

zuijianqiugen

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

补充内容 (2018-2-2 13:51):
此问题能进行具体计算，但问题的关键：是否有计算公式？

kastin

问题的本质是正整数 `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`.

kastin

上面的结论有个前提条件：`m-n \leqslant n`，即 `m\leqslant 2n`，否则会计算多。

kastin

根据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}]

复制代码

kastin

从上述母函数形式可以看出，这个拆分数同时也等于整数 `m-n` 拆分为每部分不超过 `n` （注意，可以都小于）的拆分数。再根据Ferrers图共轭性质，这有等价为整数 `m-n` 拆分为至多 `n` 个部分的拆分数.
验证：

1. IntegerPartitions[50 - 13, All, Range[13]] // Length
   
2. IntegerPartitions[50 - 13, {1, 13}] // Length

复制代码

lsr314

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

kastin

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

kastin

上面的符号不太统一，这里我们约定 `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` 的各种倍数的余数情况，得到不同情形下取整函数表达。

kastin

上述通项公式的怎么来？笔算的话，有两种方法：
第一种是将对应的母函数裂项未低次分式之和，然后分别展开为泰勒级数形式，取系数得到通项公式；
第二种是利用柯西积分公式-留数法，见 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

复制代码

kastin

`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` 的情况自己自己动手算吧，方法都说清楚了。