隔板法

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

隔板法与插空法的原理一样。^[1]

例子

现在有${\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]

参见

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

参考资料

1. 樊友年. “插空法”应用系列. 数学通报. 1995, (1) [2014-05-06]. （原始内容存档于2019-01-09）.
2. 徐浩全. “隔板法”在解不定方程方面的应用及其推广. 中学教学参考. 2010, (5) [2014-04-28]. （原始内容存档于2018-10-08）.
3. 徐国文. 多项式(a1+a2+a3+…+am)~n展开式的项数. 高中数学教与学. 2002, (7) [2014-07-15]. （原始内容存档于2016-03-04）.