隔板法

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

隔板法與插空法的原理一樣。

例子

現在有$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$個球的情況：

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

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

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

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

問題等價於求$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$

參見

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