隔板法 | Codeboy's Blog

形式陈述

对整数 $n\ge0$ 、 $k\ge1$ ，方程

x_1+x_2+\cdots+x_k=n, \qquad x_i\ge0

的整数解数为

\binom{n+k-1}{k-1}.

证明把 $n$ 个相同物品排成一列，并在 $n+k-1$ 个位置中选 $k-1$ 个隔板，隔板间物品数即各 $x_i$ 。若要求 $x_i\ge1$ ，令 $y_i=x_i-1$ ，解数为

\binom{n-1}{k-1}

（ $n\ge k\ge1$ ）。若下界为 $x_i\ge a_i$ ，先减去下界。

直觉

把 $n$ 个不可区分单位排成星号，再用 $k-1$ 个隔板切成 $k$ 段，每段星数就是一个非负整数解。对象不可区分、变量有标签，是公式成立的关键；交换两个变量对应移动整段而产生新解。正整数约束可先给每个变量预放一个单位，再处理剩余量。

例子与边界

把 $7$ 个相同球放入 $3$ 个有标签盒子，允许空盒，共有 $\binom92=36$ 种。若每盒至少一个，则剩余四球任意分配，共 $\binom62=15$ 种。公式要求物品不可区分、盒子可区分；若物品有标签，应使用函数计数而非隔板法。加入上界 $x_i\le u_i$ 后不能只平移，通常还需容斥或生成函数。 $k=1$ 时非负解唯一；组合数公式仍给 $\binom n0=1$ 。

考虑

x_1+x_2+x_3=5,\qquad 0\le x_i\le2.

先忽略上界有 $\binom72=21$ 个解。对固定的 $i$ ，令 $y_i=x_i-3$ 可数得 $x_i\ge3$ 的非法解有 $\binom42=6$ 个；两个变量同时至少为 $3$ 已不可能。因此合法解数为 $21-3\cdot6=3$ ，恰是 $(1,2,2)$ 的三个排列。

推论与应用

组合计数星号与隔板位置，非负整数解对应可重复选取。它处理单项式次数、整数格点、资源按类别分配、多重集合选择及一些离散概率分布；带上下界时可与容斥原理结合，带权总和则更适合普通生成函数。

参考资料

Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，§15.5, Cor. 15.5.3; Problems 15.7 and 15.19(b)–(c)。
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019，§6.5, generalized permutations and combinations。

形式陈述 ​

反向链接

形式陈述