技巧

普通隔板法

问题1: 有$n$个相同的球,放到$m(m \leqslant n)$个不同的盒子里,每个盒子至少是$1$个球,问有多少种放法

本质是求 $x_1+x_2 + \cdots + x_m = n,\forall x_i \geqslant 1$的解的个数

方案为为$C_{n-1}^m-1$

进阶隔板法

有$n$个相同的球,放到$m(m\leqslant n)$个不同的盒子里,盒子可以为空,问有多少种放法.

问题2: 有$n$种球,每种球都有无限个,现在要取$m$个球有多少种取法?

方案为$C_{n+m-1}^m-1$

解法1:等效法

• 第一步: 从这$n$个球里,随机放到这个$m$盒子里.
• 第二步: 然后另外拿$m$个球,分别放一个球放到$m$个盒子里,这样就保证每个盒子里都至少有一个球.

可以想到按这两步来做达到的效果等价于普通隔板法:$n+m$个球放到$m$个盒子里的效果是一样的.也就是说这两步合在一起 做为一个整体来看,可能的方案数就等于有$C_(n+m-1)^{m-1}$

设第二步可能方案为$x$,第二步只有一种可能方案,根据分步乘法原理,

那么这样放的方案为$x times 1 = C_{n+m-1}^{m-1}$

• 等效于: 从$n+m$个球里放盒子,每个盒子至少一个的方案数,所以$x = C_{n+m-1} ^ {m-1}

解法2: 一一对应技术

有n个球,放到m个(m<=n)个不同的盒子里,盒子不可以为空,设为$f(n,m)$

有n个球,放到m个(m<=n)个不同的盒子里,盒子可以为空,设为$g(n,m)$

证明$f(n,m) = g(n-m,m)$

$f(n,m)$所形成的集合的元素序列的每个值为>=1,现在把所有的元素都减1,那总数量为n-m

可以想到:减去一之后,每个元素都对应一个新的元素(可以为0)

所以:$f(n,m) = g(n-m,m)$

| 
| |
| | |

所有减去一之后.

| 
| |