可重复排列与组合

可重复排列与组合的差别是“是否区分顺序”，同时都允许同一种对象被取多次。设有 $n \geq 1$ 种类型，取 $r \geq 0$ 次。若每次选取占一个有编号的位置，共有 $n^{r}$ 个长度为 $r$ 的序列；若只记录每种类型取了几个，共有 $(\binom{n + r - 1}{r})$ 种多重集。前者是有序可重复，后者是无序可重复，不能把普通无重复组合数 $(\binom{n}{r})$ 直接套入。

四球三味的例子

四个有位置的格子各选香草、草莓、巧克力之一，有 $3^{4} = 81$ 种填写方法。若只问买了哪几种、每种几个，令数量为 $x_{1}, x_{2}, x_{3} \geq 0$ ，满足 $x_{1} + x_{2} + x_{3} = 4$ ；答案是 $(\binom{3 + 4 - 1}{4}) = (\binom{6}{4}) = 15$ 。序列“香草—草莓—香草—巧克力”和“巧克力—香草—草莓—香草”在无序问题中是同一种选择。

隔板法的双向对应

把 $r$ 个相同圆点排成一行，再放 $n - 1$ 块隔板。第一块板前圆点数是 $x_{1}$ ，相邻板之间依次是 $x_{2}, \dots$ ，最后一块板后是 $x_{n}$ 。每个非负整数解恰好产生一种圆点—隔板串，反之亦然。总位置有 $r + n - 1$ 个，选出 $r$ 个圆点位置，就得 $(\binom{r + n - 1}{r})$ 。若每类至少一个，先给各类一个，剩下 $r - n$ 个按同法分配， $r \geq n$ 时答案变为 $(\binom{r - 1}{n - 1})$ 。

当 $r = 0$ ，两种计数都为 1：唯一结果是空序列或各类数量全零。若某类型有上限，例如每味最多两个，普通隔板法会把超限的结果也数进去，需用容斥原理、生成函数或动态规划修正。题目里的“相同物品”和“不同位置”应在列公式前先画清楚。

参考资料与相关词条

MIT 6.042J：计数与组合课程讲义。
相关：排列与组合、容斥原理、动态规划。