皮纳塔糖果分配的组合计数问题求解
嘿，这个问题正好是组合数学里经典的「整数分拆与分配」问题，我来一步步给你掰扯清楚～
首先先纠正你一个小笔误：你提到的第一个无约束分配（允许客人拿0颗糖）的公式，正确的写法应该是组合数 $\binom{m+n-1}{n-1}$，也就是你写的最后那个表达式 $\frac{(m+n-1)!}{m!(n-1)!}$，前面的 $\binom{n-1}{m+n-1}$ 是写反啦，组合数的下标必须大于等于上标才行哦。
这个公式的核心思路是隔板法：把m颗完全相同的糖果排成一排，要分成n份分给n个客人，就需要放n-1个“隔板”。因为允许有人拿0颗，所以隔板可以放在糖果的两端或者多个隔板挨在一起，这样总共有 $m + n - 1$ 个位置（m颗糖占m个位置，加上n-1个隔板的位置），选n-1个位置放隔板，对应的就是 $\binom{m+n-1}{n-1}$ 种分配方式。
接下来重点讲带约束的情况，我用你提到的两个典型约束来举例：
约束1：每个客人至少拿1颗糖果
这种情况我们可以先给每个客人预分1颗糖，这样就剩下 $m - n$ 颗糖，问题就转化成了把这 $m - n$ 颗糖分给n个客人（允许拿0颗），直接套用无约束的公式就行：
$$\binom{(m-n)+n-1}{n-1} = \binom{m-1}{n-1}$$
本质还是隔板法，只不过这时候隔板不能放在两端或者挨在一起，只能放在m颗糖之间的 $m-1$ 个空隙里，选n-1个空隙放隔板，对应就是 $\binom{m-1}{n-1}$ 种方式。
约束2：每个客人至少1颗，且最多3颗
这种带上限的约束，我们需要用容斥原理来解决，步骤如下：
- 先处理下限：每个客人至少1颗，所以先给每人分1颗，剩下 $m' = m - n$ 颗糖，现在问题变成：把 $m'$ 颗糖分给n个客人，每人最多再拿2颗（因为总共不能超过3颗），即每个客人的额外糖果数 $x_i' \geq 0$，$x_i' \leq 2$，且 $\sum_{i=1}^n x_i' = m'$。
- 先算无上限约束的总方式：$\binom{m' + n -1}{n-1} = \binom{m-1}{n-1}$
- 减去有客人拿超过2颗的情况：假设某一个客人拿了≥3颗额外糖果，我们先给这个客人分3颗，剩下的 $m' - 3$ 颗随意分配，这样的情况有 $\binom{n}{1} \times \binom{(m'-3)+n-1}{n-1} = n \times \binom{m-4}{n-1}$
- 加回重复减去的情况：如果有两个客人都拿了≥3颗，刚才的步骤里被减了两次，所以要加回来一次，对应的是 $\binom{n}{2} \times \binom{(m'-6)+n-1}{n-1} = \binom{n}{2} \times \binom{m-7}{n-1}$
- 以此类推，直到 $m' - 3k < 0$ 时停止（k是拿超量糖果的客人数量）
最终的计算公式就是：
$$\sum_{k=0}^{k_{max}} (-1)^k \binom{n}{k} \binom{m-1-3k}{n-1}$$
其中 $k_{max}$ 是满足 $m-1-3k \geq n-1$（也就是 $m-3k \geq n$）的最大整数，或者简单说 $k_{max} = \lfloor \frac{m-n}{3} \rfloor$
举个实际例子验证下：比如m=10颗糖，n=4个客人，每人至少1最多3颗。
- $m-n=6$，$k_{max}=2$
- 计算：
- k=0：$\binom{9}{3}=84$
- k=1：$-4 \times \binom{6}{3} = -4 \times 20 = -80$
- k=2：$6 \times \binom{3}{3}=6 \times 1=6$
- 总和：$84-80+6=10$，手动数的话确实是10种合法分配方式～
总的来说，带约束的糖果分配问题，核心是先把约束转化为可以用隔板法处理的基础问题，再用容斥原理来修正上限类的约束，灵活组合这两个方法就能解决大多数类似问题啦。
备注：内容来源于stack exchange，提问作者stats_noob
