隔板法

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

隔板法组合数学的方法,用来处理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]

逐项求和法[编辑]

a_1x_1+x_2+...+x_k=n,其中x_i为正整数

变换成x_2+...+x_k=n-a_1x_1,可行解数为\sum_{r=1}^{\frac{n-k+1}{a_1}} \binom{n-a_1r-1}{k-2}[4]

多项式模拟[编辑]

母函数(\sum_{n=0}^{\infty} x^n)^k=\frac{1}{(1-x)^k}=\sum_{n=0}^{\infty} \binom {n+k-1}{k-1} x^n模拟空盒子的情况。

n个骰子的点数之和为m的事件数为(x^1+x^2+x^3+x^4+x^5+x^6)^nx^m的系数。

如切换骰子的点数为4,3,3,2,2,1也可以用(x^4+x^3+x^3+x^2+x^2+x^1)^n模拟。[5]

参见[编辑]

参考资料[编辑]