勵志

勵志人生知識庫

機率隔板法

隔板法組合數學中的一種方法,主要用於解決將n個無差別的小球放入k個不同的盒子中的問題。這種方法可以一般化為求解不定方程的解數,並利用母函式來解決問題。隔板法與插空法的原理相同。

套用隔板法必須滿足以下三個條件:

這n個元素必須互不相異;

所分成的每一組至少分得1個元素;

分成的組別彼此相異。

基本例子:

將10個相同的小球放入3個不同的箱子,每個箱子至少一個。這種情況下,10個小球中間有9個空格可以插入板,插入兩塊板就分成3部分,所以是C(9, 2)種情況。

添加元素隔板法:

求方程 x+y+z=10的非負整數解的個數。注意到x、y、z可以為零,因此需要添加三個球,給x、y、z各添加一個球,這樣原問題就轉化為求 x+y+z=13的正整數解的個數了。這樣問題就等價於把13個相同小球放入3個不同箱子,每個箱子至少一個,有幾種情況?易得解的個數為C(n+m-1,m-1)=C(12,2)=66種情況。

具體例子:

把10個相同小球放入3個不同箱子,第一個箱子至少1個,第二個箱子至少3個,第三個箱子可以放空球。我們可以在第二個箱子先放入10個小球中的2個,小球剩8個放3個箱子,然後在第三個箱子放入8個小球之外的1個小球,則問題轉化為把9個相同小球放3不同箱子,每箱至少1個,幾種方法?C(8,2)=28種情況。

將20個相同的小球放入編號分別為1,2,3,4的四個盒子中,要求每個盒子中的球數不少於它的編號數。先將第二個盒子放1個,第三個盒子放2個,第四個盒子放3個,就變成將14個相同的小球放入這四個盒子的問題。