- 把“相同对象分配”问题（分甜甜圈、名额分配、各组人数组成）翻译为不定方程的整数解计数问题；
- 叙述并用隔板法证明非负整数解个数公式 \(\binom{n+r-1}{r-1}\)，说明解与“星–板”排列之间的一一对应；
- 用换元（平移）技巧求正整数解个数以及带下界约束 \(x_i\ge a_i\) 的解数；
- 区分“相同对象”与“不同对象”两类分组计数模型，对给定情境正确选用 1.5 节或本节的公式。
1. 从“分东西”到数方程的解
1.5 节的多项式系数解决了“把 \(n\) 个互不相同的对象分组”的计数问题。本节处理与之对偶的情形：对象完全相同。设想把 12 个同一款式的甜甜圈分给 5 个孩子——由于甜甜圈彼此无从区分，“哪一只甜甜圈进了谁的盘子”不再有意义，有意义的只是每个孩子分得的数量。数量层面的分配问题可以翻译成代数语言：设第 \(i\) 个孩子得到 \(x_i\) 只，则 \(x_1+x_2+\cdots+x_5=12\)，且每个 \(x_i\) 都是非负整数；反过来，方程的每一个这样的解都给出一种分法。于是“分法数”就等于“方程的解数”。只要求整数解的方程称为不定方程(indeterminate equation)，在数论中也叫丢番图方程(Diophantine equation)。
方程 \(x_1+x_2+\cdots+x_r=n\) 的一个非负整数解(nonnegative integer solution)是满足方程且每个分量 \(x_i\ge 0\) 都取整数的 \(r\) 元组 \((x_1,\dots,x_r)\)；若进一步要求 \(x_i\ge 1\)，则称为正整数解(positive integer solution)。
把 \(n\) 个相同的（不可区分的，indistinguishable）球分入 \(r\) 个编号盒子的每一种分法，与上述方程的一个非负整数解一一对应：\(x_i\) 就是第 \(i\) 个盒子里的球数。
使用这个模型时要注意两个前提：其一，盒子必须可区分（有编号），否则连“哪一堆算哪个盒子”都无法约定；其二，允许空盒对应允许 \(x_i=0\)。这两个前提在建模时最容易被忽略，是常见的出错根源（见第 4 小节的注记）。
2. 隔板法与基本定理
怎样数出方程的解？逐个枚举显然不现实。本节的主角——隔板法(stars and bars)——提供了漂亮的办法：不解方程，而是把每个解“画”出来，让解变成一种一眼就能数清的排列对象。这是组合数学中“用一一对应计数”思想的典范。
设 \(n,r\) 为正整数。方程 \[ x_1+x_2+\cdots+x_r=n \] 的非负整数解个数为 \(\displaystyle\binom{n+r-1}{r-1}\)（按 1.4 节的记号即 \(C(n+r-1,\,r-1)\)）。
求方程 \(x_1+x_2+x_3=10\) 的非负整数解个数。
面包店只剩 12 个同款甜甜圈，要全部分给 5 个孩子，每人分得的数量不限（可以为 0）。共有多少种分法？
3. 正整数解与下界约束：平移技巧
如果要求每盒不空，星板串中任何两块隔板便不得相邻，而且隔板不能落在两端。直接数这种“带间隔限制”的排法并不方便，下面的定理给出两条殊途同归的路线。
设 \(n\ge r\ge 1\)。方程 \(x_1+x_2+\cdots+x_r=n\) 的正整数解个数为 \(\displaystyle\binom{n-1}{r-1}\)。
换一个角度同样能得到它：令 \(y_i=x_i-1\ge 0\)，则 \(y_1+\cdots+y_r=n-r\)，由定理 1 得 \(\binom{(n-r)+r-1}{r-1}=\binom{n-1}{r-1}\)。两种证法答案一致并非巧合：“每个间隙至多一块板”与“每盒先垫一个球”是同一约束的两种说法。这个平移（换元）技巧的价值在于它可以处理任意下界：
设 \(a_1,\dots,a_r\) 为非负整数且 \(\sum_{i=1}^{r}a_i\le n\)。方程 \(x_1+\cdots+x_r=n\) 满足 \(x_i\ge a_i\)（\(i=1,\dots,r\)）的整数解个数为 \[ \binom{n-\sum_{i=1}^{r}a_i+r-1}{r-1}. \]
求方程 \(x_1+x_2+x_3=10\) 的正整数解个数。
某实验室要把 30 位员工编入 A、B、C 三个项目组，人数不限（允许出现空组）。只关心各组人数时，三个组的人数组成共有多少种可能？若要求每个项目组至少 1 人呢？
4. 相同对象与不同对象：与 1.5 节的对照
至此，第 1 章的两类“分组”计数工具都已就绪：
- 不同对象（1.5 节，多项式系数）：把 \(n\) 个互不相同的对象分成大小为 \(n_1,\dots,n_r\) 的 \(r\) 组，共 \(\dfrac{n!}{n_1!\,n_2!\cdots n_r!}\) 种；
- 相同对象（本节，隔板法）：把 \(n\) 个相同的对象分入 \(r\) 个编号盒、各盒数量不限，共 \(\binom{n+r-1}{r-1}\) 种。
判别的第一步永远是：对象可区分吗？图 2 用最小的对照实验把差别摆上台面——同样是“3 个球放入 2 个编号盒”，相同的球只有 4 种数量分布，不同的球却有 8 种放法。
| 比较维度 | 相同对象（本节，隔板法） | 不同对象（1.5 节，多项式系数） |
|---|---|---|
| 数学模型 | \(x_1+\cdots+x_r=n\) 的非负整数解 | 把 \(n\) 个对象分成大小为 \(n_1,\dots,n_r\) 的 \(r\) 组 |
| 计数公式 | \(\binom{n+r-1}{r-1}\) | \(\dfrac{n!}{n_1!\,n_2!\cdots n_r!}\) |
| 附加约束 | 下界 \(x_i\ge a_i\)：平移后仍用本节公式（推论 1） | 各组大小 \(n_1,\dots,n_r\) 事先指定 |
| 每盒恰 1 球（\(n=r\)） | \(1\) 种 | \(n!\) 种（即全排列，1.3 节） |
| 典型情境 | 同款甜甜圈、名额与预算分配、各组人数组成 | 字母重排（MISSISSIPPI）、发牌、按名单分组 |
| 判别关键 | 对象不可区分，只看各盒数量 | 对象可区分，“谁在哪组”有意义 |
来历与思想：星与条(stars and bars)这一论证在现代教科书中的流行通常归功于费勒(W. Feller)的经典著作。它把代数问题化为排列问题，是“构造一一对应”这一计数思想的典范：不直接数解，而去数更容易数的对象。
常见误区一：忘记盒子必须编号。若盒子也不可区分，问题变成把 \(n\) 写成无序和的整数分拆(integer partition)问题——例如 \(4=4=3+1=2+2=2+1+1=1+1+1+1\) 共 5 种——难度完全不同，不在本教程范围内。误区二：混用两类模型，例如把例 4 中 30 位互不相同员工的分组直接数成 \(\binom{32}{2}\)。动手之前先问一句“对象可区分吗”。
延伸：上界约束（如 \(x_i\le b\)）无法仅靠隔板法处理，通常需要容斥原理(inclusion–exclusion principle，见第 2 章)或生成函数，练习 4 给了一个可以下手的小例子。此外，当第 2 章的样本空间由“球入盒”型等可能结果构成时，有利结果的计数正是本节的问题。
5. 本节小结
- 相同对象分盒 ↔ 不定方程的非负整数解：解数为 \(\binom{n+r-1}{r-1}\)（定理 1）。
- 核心是解与“\(n\) 颗星、\(r-1\) 块板排列”的一一对应：\(n+r-1\) 个位置中任选 \(r-1\) 个放板。
- 正整数解数为 \(\binom{n-1}{r-1}\)；下界 \(x_i\ge a_i\) 用平移 \(y_i=x_i-a_i\) 化归定理 1（推论 1）。
- 与 1.5 节对照：不同对象用多项式系数，相同对象用隔板法；判别的第一步是问对象是否可区分。
- 第 1 章至此完成：乘法原理、排列、组合、多项式系数、整数解计数五件武器，将在第 2 章计算等可能模型中的概率时逐一登场。
练习
练习 1-6-1
求方程 \(x_1+x_2+x_3+x_4=15\) 的正整数解个数。
答案与提示由定理 2，个数为 \(\binom{15-1}{4-1}=\binom{14}{3}=\frac{14\cdot 13\cdot 12}{6}=364\)。
练习 1-6-2
求方程 \(x_1+x_2+x_3=20\) 满足每个 \(x_i\ge 2\) 的整数解个数。
答案与提示令 \(y_i=x_i-2\ge 0\)，则 \(y_1+y_2+y_3=14\)，由推论 1（\(\sum a_i=6\)）得 \(\binom{20-6+3-1}{2}=\binom{16}{2}=120\)。
练习 1-6-3
用隔板法证明恒等式 \[ \sum_{k=0}^{n}\binom{r+k-1}{k}=\binom{r+n}{n}. \]
答案与提示引入松弛变量(slack variable) \(x_{r+1}=n-(x_1+\cdots+x_r)\ge 0\)。不等式 \(x_1+\cdots+x_r\le n\) 的非负整数解，与方程 \(x_1+\cdots+x_r+x_{r+1}=n\) 的非负整数解一一对应。一方面，先令 \(\sum_{i=1}^{r}x_i=k\)（\(k=0,1,\dots,n\)），各 \(k\) 层的解数为 \(\binom{r+k-1}{r-1}=\binom{r+k-1}{k}\)，求和即得左端；另一方面，\(r+1\) 个变量的方程由定理 1 直接有 \(\binom{n+(r+1)-1}{(r+1)-1}=\binom{r+n}{n}\) 个解。两边数的是同一批对象，故相等。
练习 1-6-4
掷 3 颗骰子，求点数之和等于 10 的有序结果 \((x_1,x_2,x_3)\) 的个数（每个 \(1\le x_i\le 6\)）。
答案与提示令 \(y_i=x_i-1\)，则 \(0\le y_i\le 5\) 且 \(\sum y_i=7\)。先不管上界，非负解共 \(\binom{9}{2}=36\) 个；其中某个 \(y_i\ge 6\) 的，令 \(z_i=y_i-6\)，则 \(z_i\) 与其余两个变量之和为 \(1\)，各 \(\binom{3}{2}=3\) 个，共 \(3\times 3=9\) 个；两个变量同时 \(\ge 6\) 不可能（\(6+6>7\)）。故所求个数为 \(36-9=27\)。