隔板法
问题
-
n
n
n 个相同的小球，放到
m
m
m个不同的盒子里，盒子不能为空的方案数
-
n
n
n 个相同的小球，放到
m
m
m个不同的盒子里，盒子可以为空的方案数
解决
问题
1
1
1
我们考虑下面这种做法：
因为每个小球是相同的，所以我们不需要一个一个去考虑他们具体安排，我们只需要从左往右依次将他们分成
m
m
m 块，这样就放进了
m
m
m 个盒子里。
m
m
m 个块（盒子）意味着我们需要划分
m
−
1
m-1
m−1 次（我们形象化的把这个划分的过程想象成放入一个个的隔板，因此叫做隔板法）。
而
n
n
n 个小球有
n
−
1
n-1
n−1 个空隙，因为不能为空，因此不能有两个隔板放在同一个空隙。
所以我们要在
n
−
1
n-1
n−1 个空隙中选出
m
−
1
m-1
m−1 个，方案数
(
n
−
1
m
−
1
)
\begin{pmatrix}n-1\\m-1\end{pmatrix}
(n−1m−1)
问题
2
2
2
我们不妨按照问题
1
1
1 的做法继续思考。
但是如果可以为空，那么每个空隙中就可能回放多个小球，这怎么办呢？
其实我们不妨将这个问题转换为问题
1
1
1, 如果我们先人为的给每个格子一个小球，那么这个问题不就和问题
1
1
1 相同了吗？
因此，我们现在有
n
+
m
n+m
n+m 个小球，
n
+
m
−
1
n+m-1
n+m−1 个空隙，
m
−
1
m-1
m−1个隔板。
在
n
+
m
−
1
n+m-1
n+m−1 个空隙种选出
m
−
1
m-1
m−1 个的方案数
(
n
+
m
−
1
m
−
1
)
\begin{pmatrix}n+m-1\\m-1\end{pmatrix}
(n+m−1m−1)
拓展
那么两个问题又和那些问题等价呢？
问：
x
1
+
x
2
+
x
3
+
.
.
.
x
m
=
n
x_1+x_2+x_3+...x_m=n
x1+x2+x3+...xm=n 的正整数解（或非负整数解）有多少组？
