m 个无区别的小球，放入 n 个无区别的盒子（可以有空盒），有几种不同的放法？

luyuanhong

这是网友 王守恩 发表在《数学中国》论坛上的一个帖子：

放松一下，有兴趣的朋友，我们一起做一做下面的题目。

请看

1，1个“+”号，有2个算式。
    1+1
    1+2
2，2个“+”号，有3个算式。
    1+1+1
    1+1+2
    1+2+3
3，3个“+”号，有5个算式。
    1+1+1+1
    1+1+1+2
    1+1+2+2
    1+1+2+3
    1+2+3+4
4，4个“+”号，有7个算式。
    1+1+1+1+1
    1+1+1+1+2
    1+1+1+2+2
    1+1+1+2+3
    1+1+2+2+3
    1+1+2+3+4
    1+2+3+4+5
5，5个“+”号，有11个算式。
    1+1+1+1+1+1
    1+1+1+1+1+2
    1+1+1+1+2+2
    1+1+1+1+2+3
    1+1+1+2+2+2
    1+1+1+2+2+3
    1+1+1+2+3+4
    1+1+2+2+3+3
    1+1+2+2+3+4
    1+1+2+3+4+5
    1+2+3+4+5+6
     ............

我们对每个算式约定如下：

1，第1个加数是“1”；

2，后面的加数比前面的加数要大；

3，相邻两个加数的差只能是“1”或“0”；

4，相同加数的个数：后面的个数不能比前面的多。

问：20个“+”号，有多少个算式？

luyuanhong

楼上提出的问题，其实与下面的问题是有关系的：

m 个无区别的小球，放入 n 个无区别的盒子（可以有空盒），有几种不同的放法？

上面的加法算式中，有几个“1”，对应于在第 1 个盒子中放几个球，有几个“2”，

对应于在第 2 个盒子中放几个球，有几个“3”，对应于在第 3 个盒子中放几个球，

………… ，

加法算式中有 m-1 个“+”号，有 m 个加数，相当于在放球问题中有 m 个球。

例如，3 个“+”号，4 个加数，相当于有 4 个球，要放入 4 个盒子（可以有空盒）。

  1+1+1+1 对应于 （●●●●）（ ）（ ）（ ） 。

  1+1+1+2 对应于  （●●●）（●）（ ）（ ） 。

  1+1+2+2 对应于  （●●）（●●）（ ）（ ） 。

  1+1+2+3 对应于   （●●）（●）（●）（ ） 。

  1+2+3+4 对应于    （●）（●）（●）（●） 。

共有 5 个不同的加法算式，对应于 5 种不同的小球放法。


下面表格中给出了：

m 个无区别的小球，放入 n 个无区别的盒子（可以有空盒）的不同的放法数 R(m,n) 。

其中对角线上红色的数字 R(m,m) ，就是 m 个球放入 m 个盒子（可有空盒）的放法数，

也就是楼上帖子中要计算的加法算式数。

11111qqqq

斯特灵数？

11111qqqq

斯特灵数？

luyuanhong

11111qqqq 发表于 2017-6-5 15:25
斯特灵数？

本帖子中的 R(m,n) 不是 Stirling（斯特林）数。

第二类 Stirlings 数 S(n,k) ，是将 n 个可区别的物体分成 k 个子集的不同方法数。

相当于将 n 个可区别的小球放入 k 个无区别的盒子（不能有空盒）的不同方法数。

显然与本帖子中所求的 R(m,n) 不是一回事。

王守恩

王守恩 发表于 2017-6-5 20:43
谢谢陆老师!
2，3，5，7，11，15，22，30，42，56，77，101，135，176，231，297，385，490，627，792， ...

谢谢陆老师!
2，3，5，7，11，15，22，30，42，56，77，101，135，176，231，297，385，490，627，792，1002，1255，1575，1958，2436，3010，3718，...............太漂亮了！
谢谢陆老师!
2，3，5，7，11，15，22，30，42，56，77，101，135，176，231，297，385，490，627，792，1002，1255，1575，1958，2436，3010，3718，...............可以有通项公式吗？

luyuanhong