很有意思的一类组合题
n个球放到m个盒子里,根据球和盒子是否有区别以及是否允许有空盒有${ 2 } ^{ 3 }=8$种放球问题:求如下问题的放球方案数
- 1) n个球有区别,m个盒子有区别,允许有空盒
- ${ m }^{ n }$
- 2) n个球有区别,m个盒子有区别,不允许有空盒
- $m!S(n,m)$
- 3) n个球有区别,m个盒子无区别,允许有空盒
- $ \begin{cases} S(n,1)+S(n,2)+…+S(n,m),\quad m\le n ; \ S(n,1)+S(n,2)+…+S(n,n),\quad m>n \end{cases} $
- 4) n个球有区别,m个盒子无区别,不允许有空盒
- $S(n,m)$
- 5) n个球无区别,m个盒子有区别,允许有空盒
- $C(n+m-1,n)$
- 6) n个球无区别,m个盒子有区别,不允许有空盒
- $C(n-1,m-1)$
- 7) n个球无区别,m个盒子无区别,允许有空盒
- $G(x)=\frac { 1 }{ (1-x)(1-{ x }^{ 2 })…(1-{ x }^{ m }) } $的$x^n$项的系数
- 8) n个球无区别,m个盒子无区别,不允许有空盒
- $G(x)=\frac { x^m }{ (1-x)(1-{ x }^{ 2 })…(1-{ x }^{ m }) } $的$x^n$项的系数
注:
S(n,m)为第二类斯特林数
G(x)为母函数
C(n+m-1,n)为多重组合