这个计算器能做什么
可重复组合计算器用来计算:当允许重复、且不考虑选取顺序时,从 n 个不同种类中选出 r 个物品,一共有多少种取法。这是组合数学与概率论中的一个基础公式,常被称为"隔板法"(stars and bars,又称星与隔板问题)。由于每个种类都可以被多次选中,所以它的结果会比"不可重复"的普通组合数更大。
需要输入的参数
- 物品种类总数(n):你可以选择的不同类别有多少种——例如 3 种口味的冰淇淋。
- 选取的物品数量(r):你总共要选多少个,其中同一种类可以被反复选中。
两个数都填入整数后,计算器会立即给出一个结果:不同"多重集"的数量(即允许重复的无序选取方案数)。
计算公式
本工具采用标准的可重复组合公式:
$$C^{R}(n,r) = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$
它在内部会计算三个阶乘——\((n + r - 1)!\)、\(r!\) 和 \((n - 1)!\)——然后按上式相除。由于使用的是精确阶乘和整数运算,所得结果是一个精确的整数计数,而不是近似值。
实例演算
假设一家冰淇淋店提供 n = 3 种口味,你想要一杯 r = 2 球的冰淇淋,并且允许同一种口味重复。代入 n = 3、r = 2:
- \(n + r - 1 = 3 + 2 - 1 = 4\)
- $$C(4, 2) = \frac{4!}{2!\cdot 2!} = \frac{24}{2 \cdot 2} = \mathbf{6}$$
因此一共有 6 种两球搭配:AA、BB、CC、AB、AC 和 BC。计算器会立刻返回 6。
更多已详细求解的例子
下面的每个例子都使用相同的恒等式,\(C^{R}(n,r) = \binom{n+r-1}{r} = \frac{(n+r-1)!}{r!\,(n-1)!}\),其中 \(n\) 是可用的不同物品类型的数量,\(r\) 是选择的物品数量。顺序无关紧要,每种类型都可以重复使用,因此每个结果是一个多重集合。
例子 1 — 三个相同的骰子(n = 6,r = 3)
你掷三个无法区分的六面骰子,只记录显示的面集合(因此 1-3-6 和 6-3-1 算作同一结果)。有 \(n = 6\) 种面的类型和 \(r = 3\) 次选择,允许重复,因为两个骰子可以显示相同的面。
顶部索引:\(n + r - 1 = 6 + 3 - 1 = 8\)。
$$C^{R}(6,3) = \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$$所以有56种不同的无序面组合。请注意,这远少于\(6^3 = 216\)种有序掷骰子——216 种有序结果合并为 56 个多重集合,但分布不均匀(像 4-4-4 这样的三元组有一种排列方式,而 1-3-6 有六种),这正是为什么骰子和概率必须从 216 种有序掷骰子计算,而不是从 56 个多重集合计算。
例子 2 — 勺数超过风味数(n = 3,r = 5)
一家冰淇淋店提供 3 种风味,你订购一个 5 勺的盒子;允许相同风味的勺,它们被装入的顺序无关紧要。这里 \(r = 5\) 大于 \(n = 3\),这对于没有重复的组合是不可能的,但在这里完全可以。
顶部索引:\(n + r - 1 = 3 + 5 - 1 = 7\)。
$$C^{R}(3,5) = \binom{7}{5} = \frac{7!}{5!\,2!} = \frac{7 \times 6}{2 \times 1} = \frac{42}{2} = 21$$有21种可能的盒子。这里消去\(5!\)而不是\(2!\)是快捷方式:因为\(\binom{7}{5} = \binom{7}{2}\),只有两个分子因子存留。用星号和棒线术语来说,你在 7 个位置放置 5 个星号(勺)和 \(n - 1 = 2\) 根棒线(风味分隔符)——例如 \(\star\star\,|\,\star\,|\,\star\star\) 表示 2 个香草、1 个巧克力、2 个草莓。
例子 3 — 两个边界情况(r = 1 和 n = 1)
选择一个物品(n = 4,r = 1)。你从 4 种尺寸中选择一种饮料。只选一次,重复不可能发生,所以答案必须就是类型的数量:
$$C^{R}(4,1) = \binom{4+1-1}{1} = \binom{4}{1} = \frac{4!}{1!\,3!} = \frac{4}{1} = 4$$这给出4个结果——任何这样的表格的 \(r = 1\) 列总是 \(n\)。
只有一种类型(n = 1,r = 7)。一台自动贩卖机库存单一产品,你买 7 个:
$$C^{R}(1,7) = \binom{1+7-1}{7} = \binom{7}{7} = \frac{7!}{7!\,0!} = \frac{5040}{5040 \times 1} = 1$$恰好有一个多重集合——"仅有物品的七个"——因为只有一种类型时没有选择的余地。正式地说,需要 \(n - 1 = 0\) 根棒线,所有 7 个位置必须是星号,\(\binom{7}{7} = 1\)。同样的逻辑使得对任何 \(n\),\(C^{R}(n,0) = 1\):选择什么都不是一个有效的(空)选择,这就是为什么 \(0! = 1\) 是保持公式一致的约定。
有重复组合参考表
\(C^{R}(n,r) = \binom{n+r-1}{r}\) 对于 1–8 种物品类型各选择 1–6 次的精确值。向下找到你的类型数 \(n\),然后横向找到选择数 \(r\)。
| n(类型) | r = 1 | r = 2 | r = 3 | r = 4 | r = 5 | r = 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 3 | 6 | 10 | 15 | 21 | 28 |
| 4 | 4 | 10 | 20 | 35 | 56 | 84 |
| 5 | 5 | 15 | 35 | 70 | 126 | 210 |
| 6 | 6 | 21 | 56 | 126 | 252 | 462 |
| 7 | 7 | 28 | 84 | 210 | 462 | 924 |
| 8 | 8 | 36 | 120 | 330 | 792 | 1716 |
如何读懂这些模式
- 每一行都是帕斯卡三角形的一条对角线。行 \(n = 1\) 是常数序列 1,行 \(n = 2\) 是自然数 \(2, 3, 4, \dots\),行 \(n = 3\) 是三角数 \(3, 6, 10, 15, 21, 28\),行 \(n = 4\) 是四面体数 \(4, 10, 20, 35, 56, 84\)。这就是沿固定 \(n\) 追踪 \(\binom{n+r-1}{r}\)。
- 该表在移位下对称。因为 \(\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\),我们得到 \(C^{R}(n,r) = C^{R}(r+1,\,n-1)\)。例如 \(C^{R}(6,3) = 56 = C^{R}(4,5)\),和 \(C^{R}(8,3) = 120 = C^{R}(4,7)\)。以这种方式交换"类型"和"选择"的角色通常会将长乘法转变为短乘法。
- 增长在 r 中是多项式,度数为 n − 1。固定 \(n\),\(C^{R}(n,r) = \frac{(r+1)(r+2)\cdots(r+n-1)}{(n-1)!}\),一个度数为 \(n-1\) 的多项式——当 \(n = 2\) 时是线性的,当 \(n = 3\) 时是二次的,当 \(n = 4\) 时是三次的。固定 \(r\) 并增加 \(n\) 的行为相同,但角色互换(\(n\) 中的度数 \(r\))。无论如何,计数都远低于有序重复选择的 \(n^{r}\) 计数。
- 每个条目是它上面的条目和左边的条目的和(如果两者都存在):\(C^{R}(n,r) = C^{R}(n-1,r) + C^{R}(n,r-1)\)。检查 \(n = 6\)、\(r = 4\) 单元格中的 \(126 = 70 + 56\)。该递推关系是快速手工扩展表格的方法。
如何手工计算它
星号和棒线图
在进行算术之前,有助于看到为什么公式有这种形状。将选择表示为 \(r\) 个相同的星号(你取的物品),由 \(n-1\) 个棒线(相邻物品类型之间的分隔符)分成 \(n\) 组。第 \(i\) 组中星号的数量是你选择了多少个第 \(i\) 类型的副本。\(r\) 个星号和 \(n-1\) 个棒线的每一种排列都对应恰好一个有效的选择,行中有 \(r + (n-1) = n + r - 1\) 个位置。计数选择因此意味着选择这 \(n+r-1\) 个位置中的哪 \(r\) 个包含星号:
$$C^{R}(n,r) = \binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$例如,对于 \(n = 4\) 种类型和 \(r = 5\) 次选择,行 \(\star\,|\,|\,\star\star\star\,|\,\star\) 有 8 个位置,表示 A 类型 1 个,B 类型 0 个,C 类型 3 个,D 类型 1 个。
分步程序
- 检查输入。确认 \(n\) 和 \(r\) 是整数,且 \(n \ge 1\) 和 \(r \ge 0\)。与不允许重复的组合不同,\(r\) 可以超过 \(n\)——允许重复,所以 \(r\) 没有上界。
- 计算顶部索引。计算 \(N = n + r - 1\)。这是星号和棒线位置的总数。
- 写出二项式。\(C^{R}(n,r) = \dbinom{N}{r} = \dfrac{N!}{r!\,(n-1)!}\)。永远不要完全展开这些阶乘——\(N!\) 增长很快,大数字都会相消。
- 消去 \((n-1)!\) 对 \(N!\)。由于 \(N - r = n - 1\),商 \(N!/(n-1)!\) 在分子中留下恰好 \(r\) 个递降因子:
- 将 \(r\) 个分子项相乘,然后除以 \(r!\)。如果 \(r\) 大于 \(n-1\),先使用对称性 \(\binom{N}{r} = \binom{N}{n-1}\),这样你可以改为将更少数量的因子相乘。
- 检查结果是否为整数。二项系数总是整数,所以任何剩余的分数或余数意味着算术错误。两个更快的检查:\(r = 1\) 必须给出恰好 \(n\),\(n = 1\) 必须给出恰好 1。
已详细求解的示例(n = 5,r = 4)
从 5 种配菜中选择 4 勺冷冻酸奶,允许重复,顺序无关。
- 步骤 2:\(N = 5 + 4 - 1 = 8\)。
- 步骤 3:\(C^{R}(5,4) = \dfrac{8!}{4!\,4!}\)。
- 步骤 4:消去 \((n-1)! = 4!\),留下从 8 到 \(n = 5\) 的 \(r = 4\) 个递降因子:\(\dfrac{8 \times 7 \times 6 \times 5}{4!}\)。
- 步骤 5:\(\dfrac{1680}{24} = 70\)。
- 步骤 6:70 是整数,它匹配上面参考表中 \(n = 5\)、\(r = 4\) 的单元格。
答案是70种不同的配菜组合。有用的对比:如果顺序重要,相同的输入给出 \(5^4 = 625\),如果禁止重复,只有 \(\binom{5}{4} = 5\)——所以在选择公式之前总是要决定顺序和重复是否适用。
常见问题
它和普通组合有什么区别?普通组合 \(C(n, r)\) 不允许重复——每个物品最多只能被选一次。可重复组合则允许同一种类被多次选中,所以公式改为 \(C(n + r - 1, r)\)。
这里需要考虑顺序吗?不需要。AB 和 BA 算作同一种选法。如果顺序也要区分,那就应该使用排列而不是组合。
r 可以比 n 大吗?可以。由于允许重复,你选取的物品数量完全可以超过种类数——例如从 3 种口味里选 5 球是完全合理的,只是结果数会更大。