形式陈述

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

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

的整数解数为

$$ \binom{n+k-1}{k-1}. $$$$(\genfrac{}{}{0ex}{}{n+k-1}{k-1}).$$

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

$$ \binom{n-1}{k-1} $$$$(\genfrac{}{}{0ex}{}{n-1}{k-1})$$

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

直觉

隔板把一串不可区分物品切成有标签的盒子。每种星号与隔板排列对应且只对应一组非负整数解。

例子与边界

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

推论与应用

隔板法用于多重组合、单项式计数、整数格点、概率分布和生成函数系数解释。

参考资料

• 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。