隔板法

维基百科,自由的百科全书

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

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

例子[编辑]

现在有个球,要放进个盒子里

●●●●●●●●●●

个板子,把个球被隔开成个部份

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

如此类推,个球放进个盒子的方法总数为

个球放进个盒子的方法总数为

问题等价于求的可行解数,其中正整数

空盒子推广[编辑]

现在有个球,要放进个盒子里,并允许空盒子。考虑个球的情况:

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

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

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

个球放进个盒子的方法总数(允许空盒子),等同于个球放进个盒子的方法总数(不允许空盒子),即[2]

问题等价于求的可行解数,其中非负整数

也是展开式的项数[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).