分组、分配与隔板法

分配题先区分球与盒子是否可辨，再检查空盒是否允许。隔板法只处理特定的同类对象分配模型。

相同对象放入不同盒子：隔板法

设 $m\ge0,n\ge1$ 为整数。将 $m$ 个相同对象分给 $n$ 个有区别的盒子，记第 $i$ 个盒中的数量为 $x_i$ 。允许空盒时，分配结果与方程

x_1+\cdots+x_n=m,\qquad x_i\in\mathbb Z_{\ge0}

的解一一对应，解数为

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

证明。 把 $m$ 个相同圆点与 $n-1$ 块相同隔板排成一行。第一块板前的圆点数为 $x_1$ ，相邻板之间的数量为对应的 $x_i$ ，最后一块板后的数量为 $x_n$ 。允许隔板相邻或在两端，恰好对应空盒。反过来，每组解也唯一确定这一行排列，因此只须在 $m+n-1$ 个位置中选择 $n-1$ 个隔板位置。

要求每盒非空时，令 $y_i=x_i-1\ge0$ ，得到 $\sum y_i=m-n$ 。因此当 $m\ge n$ 时有

\binom{m-1}{n-1}

种分配；当 $m<n$ 时为 $0$ 。

更一般地，若要求 $x_i\ge a_i$ ，其中 $a_i$ 为给定非负整数，令 $y_i=x_i-a_i$ 。当 $M=m-\sum_i a_i\ge0$ 时，解数为 $\binom{M+n-1}{n-1}$ ，否则为 $0$ 。上界限制不能通过同样的一次平移消去，需结合容斥或递推。

可重组合。 从 $n$ 种对象中取 $m$ 个，不计顺序而允许同种重复，等价于记录各类使用次数 $x_1,\ldots,x_n$ ，故也有 $\binom{m+n-1}{m}$ 种。该公式要求供给足够；若某类库存少于 $m$ ，必须检查上界，不能直接套用无限供给模型。

例：上下界

求 $x+y+z=7$ ， $0\le x,y,z\le3$ 的整数解数。无上界时有 $\binom92=36$ 种。 $x\ge4$ 时令 $u=x-4$ ，则 $u+y+z=3$ ，有 $\binom52=10$ 种；三个变量各有这样的坏情形。两个变量同时至少 $4$ 不可能，所以答案为 $36-3\cdot10=6$ 。

不同对象的分配与分组

把 $m$ 个不同对象放进 $n\ge1$ 个有标号的盒子，允许空盒，每个对象各有 $n$ 个去处，因此有 $n^m$ 种。这与隔板法的“对象相同”条件不同。

若规定第 $i$ 组恰有 $r_i$ 个对象，其中 $r_i\ge0$ 、 $\sum r_i=m$ ，并且各组有标号，则数量为

\binom m{r_1}\binom{m-r_1}{r_2}\cdots\binom{r_n}{r_n} =\frac{m!}{r_1!\cdots r_n!}.

这是依次选择各组成员的乘法原理。

若各组无标号、只规定正的组大小多重集，设大小为 $s$ 的组有 $c_s$ 个，则数量为

\frac{m!}{\left(\prod_i r_i!\right)\left(\prod_s c_s!\right)}.

理由： 临时给同样大小的组编号，每个无标号分组恰好被这类组的 $c_s!$ 种编号排列重复计算；不同大小的组已经可以按大小辨别，无须互相交换后再除一次。

例如六人分为两个无标号三人组，数量为 $\binom63/2!=10$ ；分为一个二人组和一个四人组，则为 $\binom62=15$ ，两组大小已不同，不能再除以 $2$ 。若两组三人分别承担两项不同任务，则有标号，数量恢复为 $\binom63=20$ 。

易错点

不同球分盒不能直接使用隔板法。原条件中的下界可先逐项减去，但上界需要另外处理。

连续整数的固定项数子集和：每个中间值都能取到

从连续整数 $b,b+1,\ldots,b+N-1$ 中选 $r$ 个不同数， $1\le r\le N$ 。最小和为 $L=rb+r(r-1)/2$ ，最大和为 $U=L+r(N-r)$ 。不仅 $L\le S\le U$ ，而且每个整数 $S\in[L,U]$ 都能取到。

证明可达性：写 $S-L=qr+s$ ，其中 $0\le s<r$ 。先选最小的 $r$ 个数，把前 $r-s$ 个各增加 $q$ ，后 $s$ 个各增加 $q+1$ 。增量总和为 $qr+s$ ；增量非递减，原来相邻至少差1，所以不会重合。

如果 $s=0$ ， $S-L\le r(N-r)$ 保证 $q\le N-r$ ；如果 $s>0$ ，则 $q+1\le N-r$ 。所以最大选中数也没有越过 $b+N-1$ 。这给出明确构造，不能只从最小和、最大和就推定所有整数中间值都存在。

连续整数等和分拆：奇偶只是必要条件

把 $X=\{1990,1991,\ldots,1990+k\}$ 分成两个互不相交且并为 $X$ 的子集，要求元素和相等， $k$ 为正整数。

总和为 $(k+1)(3980+k)/2$ ，须为偶数。逐个检查 $k$ 除以4的余数，得到必要条件 $k\equiv0$ 或 $3\pmod4$ 。

$k=4m+3$ 。 元素个数为 $4m+4$ 。把连续数按每四个分一组；对 $t,t+1,t+2,t+3$ ，有 $t+(t+3)=(t+1)+(t+2)$ ，每组分为两份等和，再合并即可。因此所有正的这类 $k$ 都成立。

$k=4m$ ，其中 $m\ge1$ 。 一共有 $4m+1$ 个数，分拆时至少一份不超过 $2m$ 个。因各数均正，该份的和不超过最大的 $2m$ 个数之和

U=6m^2+3981m.

目标半和为

T=(4m+1)(995+m)=4m^2+3981m+995.

因此必须 $2m^2\ge995$ ，即 $m\ge23$ 。

反过来， $m\ge23$ 时，最小的 $2m$ 项之和为 $L=2m^2+3979m$ ，有 $L<T\le U$ 。前一节已证明固定选取 $2m$ 个连续整数时，每个介于 $L,U$ 的整数和均可达到，所以能选一份和为 $T$ ，补集自然也为 $T$ 。

因此全部解是

k\equiv3\pmod4\quad\text{或}\quad k\equiv0\pmod4\text{ 且 }k\ge92.

这道题的可复用内容是“先看总和奇偶，再看项数与极端和，最后证明中间和可达”；只写总和为偶数，会多算许多无法分拆的小 $k$ 。

关联阅读

先修：排列、组合与圆排列。

同主题：受限排列：捆绑、插空与补集 · 容斥、递推计数与错排。