計數原理

此頁面文字抄襲自劍橋大學出版社出版的《IB 文憑數學高階水平》一書。此處文字應刪除。

學習目標

能夠將複雜的計數問題分解成更容易計數的步驟，然後將它們組合在一起，
能夠計算排列一組物件的排列方式數量，
能夠使用稱為階乘函式的有用新工具的代數性質，
知道從一組物件中選擇物件的多少種方法，以及
知道將這些工具應用於更難問題的各種策略。

簡介

計數是數學中最早學習的內容之一，乍一看似乎非常簡單。如果有人被要求計算學校裡有多少人，這將不是一項非常棘手的任務。如果有人被要求計算如果每個人都要與其他人比賽，需要進行多少場比賽，這會稍微複雜一些。如果有人被要求計算可以選出多少支不同的足球隊，可能會發現數量太大而無法計算，因此需要想出一些巧妙的技巧。本章旨在幫助發展在如此困難的情況下進行計數的策略。

乘積原理和加法原理

選單

主菜

披薩
漢堡
西班牙海鮮飯

甜點

冰淇淋
水果沙拉

對非常小的群體進行計數很容易。因此，需要將更復雜的問題分解成對小群體進行計數。但如何將這些計數組合在一起才能得出整體問題的答案呢？答案在於使用乘積原理和加法原理，可以使用以下選單來進行說明。

安娜想點一道主菜和一道甜點。她可以選擇三種主菜中的一種和兩種甜點中的一種。她可以做出多少種不同的選擇？鮑勃想點一道主菜或一道甜點。他可以選擇三種主菜中的一種或兩種甜點中的一種；他可以做出多少種不同的訂單？

我們可以使用符號 $n(A)$ 表示對 $A$ 進行選擇的種數。

乘積原理 允許從 $A$ 中選擇一個選項並從 $B$ 中選擇一個選項，那麼需要將各個可能性相乘。

乘積原理（AND 規則）進行選擇 $A$ 和選擇 $B$ 的種數是選擇 $A$ 的種數與選擇 $B$ 的種數的乘積。

$n(A{\text{ AND }}B)=n(A)\times n(B)$

加法原理 如果要從 $A$ 中選擇一個選項或從 $B$ 中選擇一個選項，那麼結果就是將可能性相加。

加法原理有一個重要的限制。只有當選擇 $A$ 和選擇 $B$ 之間沒有重疊時，才能使用它。例如，不能用加法原理來計算骰子上出現奇數或素數的次數。如果選擇 $A$ 和選擇 $B$ 之間沒有重疊，這兩個事件是互斥的。

加法原理（或規則）選擇 $A$ 或選擇 $B$ 的方法數量是 $A$ 選項數量與 $B$ 選項數量的總和。

如果 $A$ 和 $B$ 是互斥的，那麼

$n(A{\text{ OR }}B)=n(A)+n(B)$

應用加法原理或乘法原理最難的部分是分解問題，並決定使用哪個原理。人們必須自查確保所有情況都被檢查過，並確保它們是互斥的。通常，將方程式改寫以強調需要什麼，'AND' 或 'OR'，會有所幫助。

從 $n$ 個物件中選擇某個東西 $r$ 次的方法數量是 $n^{r}$ 。

排列的計數

單詞 'ARTS' 和單詞 'STAR' 都包含相同的字母，但排列順序不同。它們都是字母 R、A、T 和 S 的排列（也稱為排列）。可以計算出不同排列的數量。

第一個字母有四種可能性，然後對於每個第一個字母的選擇，第二個字母有三種選擇（因為一個字母已經被使用過了）。這給第三個字母留下了兩種選擇，然後最後一個字母就被固定了。使用 'AND 規則'，可能的排列數量是 $4\times 3\times 2\times 1=24$ 。

$n$ 個不同物件的排列數量等於小於或等於 $n$ 的所有正整數的乘積。這個'表示式縮寫為 $n!$ （讀作 'n 階乘'）。

排列指將一組物件按特定順序排列的方式。排列 $n$ 個物件的方法數量為 $n!$

$n!=n(n-1)(n-2)...\times 2\times 1$

階乘的代數

要解決更復雜的計數問題，通常需要簡化涉及階乘的表示式。這可以透過使用階乘公式來完成，

$n!=n(n-1)(n-2)...\times 2\times 1$

然後繼續尋找各項的公因數。理解一個階乘與下一個階乘之間的聯絡很重要

$(n+1)!=(n+1)\times n!$

能夠簡化涉及 $n!$ 的表示式很有用，因為 $n!$ 很快就會變得非常大。通常，即使使用計算器也無法計算階乘。例如，標準科學計算器只能計算到 $69!=1.71\times 10^{98}$ （保留三位有效數字）。

選擇計數

假設從一個有 11 名學生的班級中選出 3 名學生參加與校長會面。可以選出多少種不同的三個人小組？

在這個例子中，需要從 11 名學生中選擇 3 名學生，但他們不必按照任何指定的順序排列。順序不重要；例如，選擇阿斯帕西亞、弗裡妮，然後拉哈布與選擇弗裡妮、拉哈布，然後弗裡妮是一樣的。這種選擇被稱為組合。一般來說，從 $n$ 個物件中選擇 $r$ 個物件的方法數量用符號 ${n \choose r}$ 或 $^{n}C_{r}$ （讀作“n C r”或“從 n 箇中選 r 個”）表示。

組合指選擇一組物件的方式，其中順序無關緊要。從 $n$ 個物件中選擇 $r$ 個物件的方法數量為

${n \choose r}={\frac {n!}{r!(n-r)!}}$

排除原則

排除原則是一種透過先計算不感興趣的事物來計算感興趣的事物的方法。這通常用於計算某些屬性被禁止（不允許）的情況。

排除原則透過先計算所有不滿足條件的結果，然後從總結果數中減去它，來計算滿足給定條件的結果數。

想象一下，使用數字 1-5 中的每一個數字恰好一次來形成一個五位數的程式碼。如果要計算有多少個此類程式碼不以“25”結尾，可以算出所有不以“25”結尾的可能選項。這個方法有效，但很長很複雜。更簡單的方法是使用排除原則。

計算有序選擇

有時，需要從一個更大的組中選擇一些物件，但選擇的順序很重要。例如，找到比賽中前三名選手的可能性，或從一組固定的數字中形成數字。處理這些情況的策略是，首先從更大的組中選擇，然後排列所選物件。

假設整個集合的大小為 $n$ ，並且要選擇和排序大小為 $r$ 的子集。執行此操作的方法數量用符號 $^{n}P_{r}$ 表示，並被描述為“從 $n$ 個物件中排列 $r$ 個物件的方法數”。可以使用公式 ${n \choose r}$ 推匯出 $^{n}P_{r}$ 的公式：有 ${n \choose r}$ 種方法可以從主題中選擇物件，並且這些物件可以以 $r!$ 種方法排列。因此，

$^{n}P_{r}={n \choose r}\times r!$

或者，類似地

$^{n}P_{r}={\frac {n!}{(n-r)!}}$

這可以使用階乘代數寫成

$^{n}P_{r}=n(n-1)(n-2)\ldots (n-r+1)$

以這種形式寫出來，我們可以看到公式 $^{n}P_{r}$ ，是“與規則”的應用。例如，假設一場比賽有五個人，你想計算前三名的可能性數量。我們可以這樣推理：如果獲勝者有五種選擇，那麼對於每個獲勝者，第二名有四種選擇，第三名有三種選擇。這給了我們 $5\times 4\times 3=^{5}P_{3}$ 。

保持物體在一起或分開

單詞“SQUARE”有多少種字母排列方式可以使Q和U相鄰？有多少種方式可以使母音字母全部分開？當一個問題有像這種約束條件時，我們需要一些巧妙的技巧來處理它們。

我們將要觀察的第一類問題是，物體被強迫保持在一起。訣竅是想象單詞“SQUARE”中的字母是寫在瓷磚上的。如果Q和U需要在一起，我們實際上就是在處理五塊瓷磚，其中一塊包含QU。

S	QU	A	R	E

我們還必須記住，如果Q和U的順序相反，也滿足條件。

S	UQ	A	R	E

另一種約束條件是，物體必須保持分開。除非我們只分開兩個物體，否則這不是物體保持在一起的反面。例如，三個物體保持在一起的反面包括兩個在一起，第三個分開。所以，當處理“保持物體分開”時，我們需要關注關鍵物體可以放入的空隙。

考慮單詞“SQUARE”有多少種排列方式，其中母音字母都不在一起。我們首先要排列所有子音字母。其中一種排列方式是

*	S	*	Q	*	R	*

其中* 是可以放置母音字母的空隙。我們只有三個母音字母，所以只需要選擇三個空隙，然後決定以什麼順序插入母音字母。