隔板法

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

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

例子

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

●●●●●●●●●●

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

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

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

$n$个球放进$k$个盒子的方法总数为$(\genfrac{}{}{0ex}{}{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$个盒子的方法总数（不允许空盒子），即$(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$

问题等价于求$x_1+x_2+...+x_k=n$的可行解数，其中$x_1,x_2,...,x_k$为非负整数。

$(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$也是$(a_1+a_2+...+a_k{)}^n$展开式的项数$\sum _{n_1+n_2+...+n_k=n}1$

参见

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