隔板法（又稱插板法）是组合数学中一種基礎計數方法，主要用於解決將 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
参见
*组合数
*多项式定理
*整数分拆
参考资料
评论 (0)