隔板法

隔板法是组合数学的方法，用来处理$n$个无差别的球放进$k$个不同的盒子的问题。可一般化为求不定方程的解数，并利用母函数解决问题。

隔板法与插空法的原理一样。

例子

现在有$10$个球，要放进$3$个盒子里

●●●●●●●●●●

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

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

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

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

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

空盒子推广

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

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

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

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

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

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

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

参见

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