隔板法

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

隔板法與插空法的原理一樣。^[1]

例子

現在有${\displaystyle 10}$個球，要放進${\displaystyle 3}$個盒子裏

●●●●●●●●●●

隔${\displaystyle 2}$個板子，把${\displaystyle 10}$個球被隔開成${\displaystyle 3}$個部份

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

如此類推，${\displaystyle 10}$個球放進${\displaystyle 3}$個盒子的方法總數為${\displaystyle {\binom {10-1}{3-1}}={\binom {9}{2}}=36}$

${\displaystyle n}$個球放進${\displaystyle k}$個盒子的方法總數為${\displaystyle {\binom {n-1}{k-1}}}$

問題等價於求${\displaystyle x_{1}+x_{2}+...+x_{k}=n}$的可行解數，其中${\displaystyle x_{1},x_{2},...,x_{k}}$為正整數。

空盒子推廣

現在有${\displaystyle 10}$個球，要放進${\displaystyle 3}$個盒子裏，並允許空盒子。考慮${\displaystyle 10+3}$個球的情況：

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

每個盒子的球都被拿走一個，得到一種情況，如此類推：

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

${\displaystyle n}$個球放進${\displaystyle k}$個盒子的方法總數（允許空盒子），等同於${\displaystyle n+k}$個球放進${\displaystyle k}$個盒子的方法總數（不允許空盒子），即${\displaystyle {\binom {n+k-1}{k-1}}}$^[2]

問題等價於求${\displaystyle x_{1}+x_{2}+...+x_{k}=n}$的可行解數，其中${\displaystyle x_{1},x_{2},...,x_{k}}$為非負整數。

${\displaystyle {\binom {n+k-1}{k-1}}}$也是${\displaystyle (a_{1}+a_{2}+...+a_{k})^{n}}$展開式的項數${\displaystyle \sum _{n_{1}+n_{2}+...+n_{k}=n}1}$^[3]

參見

• 組合數
• 多項式定理
• 整數分拆