JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

有放回與無放回的抽樣

幾乎每個計數問題，骨子裡都是一個換了裝的抽樣問題。兩個「是／否」的問題——順序重不重要、元素能不能重複——就把它們全部分進一張整齊的 2x2 表格，每一格各對應一條公式。

兩個能歸類所有計數問題的問題

想像一個甕，裡面裝著 n 顆相異的球，你伸手進去抽出 k 顆。光是這一幅畫面——從 n 個的池子中抽出 k 個——就是你日後會遇到的大多數計數問題背後那副隱藏的骨架。前面幾篇給了你零件：乘法原理、排列與組合。抽樣就是把它們扣在一起的框架，而它靠的不過是對「你怎麼抽」問兩個「是／否」的問題。

第一個問題是順序重不重要。如果「先抽 3 號球、再抽 7 號球」和「先抽 7 號、再抽 3 號」算成不同的結果，那順序就重要，你身處排列的領域；如果這兩次抽法算成同一把，那順序就不重要，你數的是子集。這正是你已經見過的有序與無序之分。第二個問題是，每次抽完、下一次抽之前你會不會把球放回去。放回去，同一顆球就能再被抽到——這叫有放回抽樣；不放回，每抽一次池子就縮小一點——這叫無放回抽樣。這兩個彼此獨立的「是／否」回答給出四種組合，而這四種就是本篇的全部主題。

抽樣公式的 2x2 表格

我們一格一格地把四個格子填滿，每一格都從一幅畫面出發，而非死背符號。有序、有放回最簡單：k 次抽取中的每一次都獨立地擁有全部 n 個選擇，所以依乘法原理，總數是 n^k。想想用 10 個數字組成的 3 位數密碼：10 * 10 * 10 = 10^3 = 1000。有序、無放回則每抽一次就少一個選項：n 個選擇，接著 n - 1，再來 n - 2，往下走 k 步。這個遞降乘積就是上一篇的排列數 P(n, k) = n! / (n - k)!。

無序、無放回就是組合：你選出一組 k 個相異的元素，不在意抓取的順序，也就是 C(n, k) = n! / (k! (n - k)!)。它正是把有序無放回的計數除掉內部那 k! 種排序——就是你上一篇做過的那一步。第四格——無序、有放回——是唯一真正全新的一格，也是最微妙的一格，所以下面會給它自己的章節。現在只要記住，它數的是「從 n 種類型中抽出大小為 k 的多重集」，公式是 C(n + k - 1, k)。

Draw k items from n distinct items:

                      |  WITH replacement   |  WITHOUT replacement
  --------------------+---------------------+----------------------
  ORDER matters       |       n^k           |   n! / (n - k)!   = P(n,k)
  ORDER ignored       |   C(n+k-1, k)       |   n! / (k!(n-k)!) = C(n,k)

With n = 5, k = 3:
  ordered, with    : 5^3                 = 125
  ordered, without : 5*4*3               = 60
  unordered, w/o   : C(5,3)              = 10
  unordered, with  : C(5+3-1, 3) = C(7,3)= 35
抽樣的四個格子，各附一個 n = 5、k = 3 的計算實例。

棘手的那一格：無序有放回，與隔板法

為什麼無序有放回需要一條特別的公式，而且偏偏是 C(n + k - 1, k)，而不是更整齊的某個式子？陷阱在於：你可能以為，可以像組合除掉排序那樣，直接拿 n^k 去除以 k!。這行不通，因為 k! 這個修正只有在抽出的 k 個全部相異時才成立。一旦容許重複，像「（紅、紅、藍）」這樣的一抽，其相異的排序就少於 3! 種，而「（紅、藍、綠）」卻有完整的 3! 種——於是不同的選取被重複計算的倍數各不相同，單一個乾淨的除法無法把它抹平。

誠實的解法是直接去數對的物件。一個無序有放回的樣本，其實只是一張計次表：第 1 種抽到幾個、第 2 種幾個，一路到第 n 種，而這些次數加起來等於 k。要漂亮地數出這些計次表，靠的是隔板法。先擺下 k 顆相同的星星代表你抽到的元素，再擺 n - 1 根隔板，把它們切成 n 個格子（每種類型一格）。舉例來說，n = 3 種類型 {A, B, C}、k = 4 次抽取時，圖樣「* * | | * *」讀作 2 個 A、0 個 B、2 個 C。k 顆星星與 n - 1 根隔板的每一種排列，恰好對應一張合法的計次表，反之亦然。

現在計數就容易了，因為我們又回到了單純的組合。我們有一排 k + (n - 1) 個符號，必須選出其中哪 k 個位置是星星（其餘是隔板）：那就是 C(n + k - 1, k)。這個隔板法論證是計數裡最可重複套用的技巧之一——它回答了「把 k 寫成 n 個非負整數的有序和，共有幾種寫法」，這跟前面那個問題其實是同一題，只是換上代數的外衣、脫掉了甕的外衣。以我們 n = 3、k = 4 的例子，它給出 C(6, 4) = 15 張相異的計次表。

從計數到機率，以及為何放回與否改變一切

抽樣不只是計數練習；「放回／不放回」這個選擇，是兩整類機率模型之間的分水嶺，所以值得親身體會其差異。有放回抽樣使各次抽取彼此獨立且同分配：每次抽取前甕看起來都一樣，所以抽到紅的機率每次相同，且過去的抽取不帶任何資訊。無放回抽樣則使各次抽取彼此相依：抽到一顆紅球，會降低下一顆是紅的機率，因為甕已經變了。光是這個區別，就是日後你會遇到的二項分配（有放回）對上超幾何分配（無放回）的種子。

一個生動的提醒，說明「有放回」的直覺如何誤導人，就是生日問題。把生日指派給一群人，是對 365 天做*有放回*的抽樣（兩個人可以同一天生日），而令人驚訝的是重複出現得有多快：只要 23 個人，某一對人同一天生日的機率就已經超過二分之一。最乾淨的算法是補數計數——先算出 23 個生日全都相異的機率，也就是*無放回*的計數 P(365, 23) 除以*有放回*的總數 365^23，再用 1 去減它。光這一道題就同時用上了我們四格中的三格，這正是 2x2 框架值得內化的原因。

一個完整範例：選對格子

假設一家霜淇淋店有 6 種口味，而你用 3 球裝滿一個杯子。可能的杯子有幾種不同的組合？整個答案的關鍵就在那兩個問題——而題目的措辭逼出了明確的答案。杯子不會記錄你加球的順序，所以順序*不*重要；而你被允許重複同一種口味（三球都是芒果也行），所以這是*有放回*。這就把我們牢牢地落在「無序、有放回」那一格。

  1. 回答第一個問題：順序重要嗎？不重要——一杯 {香草、芒果、芒果} 不論你怎麼舀，都是同一杯。
  2. 回答第二個問題：口味能重複嗎？能——你可以重複拿同一種口味。所以是：無序、有放回。
  3. 套用對應的公式，n = 6 種類型、k = 3 球：C(n + k - 1, k) = C(6 + 3 - 1, 3) = C(8, 3) = 56 種可能的杯子。

現在感受一下，若措辭改變，答案會如何隨之改變，因為這正是前面那份紀律回本的地方。假如球是疊在甜筒上、由上到下的順序很重要、但仍允許重複，你就要切換到「有序、有放回」那一格：6^3 = 216。假如店家反而禁止口味重複、而順序仍不重要，你就要用「無序、無放回」那一格：C(6, 3) = 20。同樣六種口味、同樣三球——但四種不同的現實規則，給出四種不同的計數。公式是簡單的部分；正確讀出你身處哪一格才是真本事，而這正是下一篇在計數變得真正困難時所倚靠的工具箱。