隔板法

现在有${\displaystyle 10}$ 个球，要放进${\displaystyle 3}$ 个盒子里

●●●●●●●●●●

隔${\displaystyle 2}$ 个板子，把${\displaystyle 10}$ 个球被隔开成${\displaystyle 3}$ 个部分

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、......

如此类推，${\displaystyle 10}$ 个球放进${\displaystyle 3}$ 个盒子的方法总数为${\displaystyle {\binom {10-1}{3-1}}={\binom {9}{2}}=36}$ 

${\displaystyle n}$ 个球放进${\displaystyle k}$ 个盒子的方法总数为${\displaystyle {\binom {n-1}{k-1}}}$ 

问题等价于求${\displaystyle x_{1}+x_{2}+...+x_{k}=n}$ 的可行解数，其中${\displaystyle x_{1},x_{2},...,x_{k}}$ 为正整数。

现在有${\displaystyle 10}$ 个球，要放进${\displaystyle 3}$ 个盒子里，并允许空盒子。考虑${\displaystyle 10+3}$ 个球的情况：

●|●|●●●●●●●●●●●、●|●●|●●●●●●●●●●、●|●●●|●●●●●●●●●、●|●●●●|●●●●●●●●、●|●●●●●|●●●●●●●、......

每个盒子的球都被拿走一个，得到一种情况，如此类推：

||●●●●●●●●●●、|●|●●●●●●●●●、|●●|●●●●●●●●、|●●●|●●●●●●●、|●●●●|●●●●●●、......

${\displaystyle n}$ 个球放进${\displaystyle k}$ 个盒子的方法总数（允许空盒子），等同于${\displaystyle n+k}$ 个球放进${\displaystyle k}$ 个盒子的方法总数（不允许空盒子），即${\displaystyle {\binom {n+k-1}{k-1}}}$ ^[2]

问题等价于求${\displaystyle x_{1}+x_{2}+...+x_{k}=n}$ 的可行解数，其中${\displaystyle x_{1},x_{2},...,x_{k}}$ 为非负整数。

${\displaystyle {\binom {n+k-1}{k-1}}}$ 也是${\displaystyle (a_{1}+a_{2}+...+a_{k})^{n}}$ 展开式的项数${\displaystyle \sum _{n_{1}+n_{2}+...+n_{k}=n}1}$ ^[3]

• 组合数
• 多项式定理
• 整数分拆