重複組合計算機

重複組合計算機

領先 AI Skill PRO

輸入計算

數學公式

CR(n,r)=(n+r−1)!r!(n−1)!C^{R}(n,r) = \frac{(\text{n} + \text{r} - 1)!}{\text{r}!\,(\text{n} - 1)!}
使用統計

廣告

結果

重複組合的數量
70
物品種類總數(n) 5
要挑選的物品數量(r) 4

回報本頁錯誤

這個計算機的用途

重複組合計算機可以算出:當允許重複選取、且不考慮選取順序時,從 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)!\)——再依公式相除。由於採用精確階乘與整數運算,所得結果是精確的整數計數,而非近似值。

廣告
表示可重複組合的星與隔板排列
隔板法解釋了為何計數等於 \(C(n+r-1, r)\)。

範例演算

假設一家冰淇淋店提供 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}\),只有兩個分子因子存活。用星條法術語,你正在放置 5 個星星(勺子)和 \(n - 1 = 2\) 個條(風味分隔符)在 7 個位置——例如 \(\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\)。相同的邏輯使得 \(C^{R}(n,0) = 1\) 對於任何 \(n\):選擇什麼都不是一個有效的(空)選擇,這就是為什麼 \(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\) 行是常數序列 1s,第 \(n = 2\) 行是自然數 \(2, 3, 4, \dots\),第 \(n = 3\) 行是三角數 \(3, 6, 10, 15, 21, 28\),第 \(n = 4\) 行是四面體數 \(4, 10, 20, 35, 56, 84\)。這只是 \(\binom{n+r-1}{r}\) 沿著固定 \(n\) 追跡。
  • 表在移位下是對稱的。 因為 \(\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\) 個群組,用 \(n-1\) 個條(連續物品類型之間的分隔符)分隔。第 \(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 個位置,表示 1 個 A 類型,0 個 B 類型,3 個 C 類型,1 個 D 類型。

分步程序

  1. 檢查輸入。 確認 \(n\) 和 \(r\) 是整數,且 \(n \ge 1\) 和 \(r \ge 0\)。與不允許替換的組合不同,\(r\) 可能超過 \(n\) ——允許重複,所以 \(r\) 沒有上界。
  2. 計算上方指數。 計算 \(N = n + r - 1\)。這是星條位置的總數。
  3. 寫二項式。 \(C^{R}(n,r) = \dbinom{N}{r} = \dfrac{N!}{r!\,(n-1)!}\)。絕不要完全展開這些階乘——\(N!\) 爆炸式增長,大數字都會取消。
  4. 將 \((n-1)!\) 抵消 \(N!\)。 由於 \(N - r = n - 1\),商 \(N!/(n-1)!\) 在分子中留下恰好 \(r\) 個遞減因子:
$$C^{R}(n,r) = \frac{(n+r-1)(n+r-2)\cdots(n)}{r!}$$
  1. 將 \(r\) 個分子項相乘,然後除以 \(r!\)。 如果 \(r\) 大於 \(n-1\),首先使用對稱性 \(\binom{N}{r} = \binom{N}{n-1}\),以便你改為相乘較小數量的因子。
  2. 進行合理性檢查,確保結果是整數。 二項式係數總是整數,所以任何剩餘分數或餘數意味著算術錯誤。還有兩個快速檢查:\(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!\),留下 \(r = 4\) 個從 8 到 \(n = 5\) 的遞減因子:\(\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 視為相同的選取。如果順序有差別,那就要改用排列(permutation)了。

r 可以大於 n 嗎?可以。由於允許重複,你挑選的物品數量可以多於類型的種類數——例如從 3 種口味中挑 5 球完全沒問題,而且會得到更大的計數結果。

最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器