隔板法

维基百科,自由的百科全书
跳转至: 导航搜索

隔板法组合数学的方法,用来处理n个球放进k个盒子的问题,并可推广到整数分拆不定方程的可行解数问题。

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

例子[编辑]

现在有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个球的情况:

●|●|●●●●●●●●●●●

从3个盒子里各拿走一个,得到一种情况,如此类推:

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

n个球放进k个盒子的方法总数(允许空盒子)为\binom {n+k-1}{k-1}[2]

问题等价于求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[3]

参见[编辑]

参考资料[编辑]