跳至內容

隔板法

維基百科,自由的百科全書

隔板法組合數學的方法,用來處理個無差別的球放進個不同的盒子的問題。可一般化為求不定方程的解數,並利用母函數解決問題。

隔板法插空法的原理一樣。[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).