高中數學擴充套件/補充/基本計數

高中數學擴充套件

---

補充章節 — 質數和模算術 — 邏輯

數學證明 — 集合論和無限過程 — 計數和生成函式 — 離散機率

矩陣 — 進一步模算術 — 數學規劃 — 馬爾可夫鏈

補充章節
內容
基本計數
多項式除法
部分分數
求和符號
複數
微分
問題與專案
問題集
解答
練習解答
問題集解答

有序選擇 (排列)

假設你的音樂庫中有 10 首歌曲，你想要隨機播放所有歌曲（即這 10 首歌曲會以隨機順序播放）。你的音樂庫可以有多少種不同的播放方式？

這種型別的題被稱為有序選擇（排列），因為我們是在選取音樂庫中的歌曲並以特定順序進行播放。例如，以下這些選擇被認為是不同的：

${\begin{array}{l}1,2,3,4,5,6,7,8,9,10\\7,3,10,4,9,5,1,8,2,6\\2,1,3,4,5,6,7,8,9,10\end{array}}$

這些明顯地定義了不同的播放順序，或實際上，不同的播放列表。

讓我們逐步思考。我們可以從 10 首不同的歌曲中選擇 1 首放在第一個位置（或播放的第一首歌曲），從剩下的 9 首歌曲中選擇 1 首放在第二個位置（因為已經選了 1 首），從剩下的 8 首歌曲中選擇 1 首放在第三個位置（因為已經固定了 2 首），以此類推。總的播放方式可以計算如下：

$10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1$

將近 400 萬種不同的播放列表！

現在我們將介紹階乘函式，它是一種表達以下內容的簡便方法：

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

正式定義為：

${\begin{array}{l}0!=1\\n!=n\times (n-1)!\end{array}}$

因此，在我們的例子中：

${\begin{array}{l}10!=10\times 9!=10\times 9\times 8!...\\10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\end{array}}$

如果我們有 30 首歌曲，但仍然只想要隨機播放其中的 10 首呢？類似的推理得出以下結論：

$30\times 29\times 28\times 27\times 26\times 25\times 24\times 23\times 22\times 21$

種不同的方式。這等同於：

${\frac {30!}{20!}}={\frac {30!}{(30-10)!}}$

     注意！階乘函式不對加法或乘法進行分配。

一般來說，從n個專案中選取m個專案的排列數量（例如，從 30 首歌曲中選取 10 首）為：

${\frac {n!}{(n-m)!}}$

其背後的原理是我們取消了n!乘積中除前m個因子以外的所有因子：

$30!=\underbrace {30\times 29\times ...\times 22\times 21} _{\text{First 10 factors}}\times \underbrace {20\times ...\times 2\times 1} _{(30-10)!=20!}$

當m等於n時，我們說我們是在計算n個專案的排列數量。

${\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$

在解決計數問題時，我們通常會使用“專案”或“元素”（在本例中為歌曲）以及“集合”（在本例中為集合或播放列表）這些詞。

1. In how many ways can I arrange my bookshelf (7 books) if I own a trilogy and the 3 books have to be always together, in the same order?

2. In how many ways can I arrange my family (6 members) in a line, with the only rule that my parents have to be in adjacent positions?

排列（有重複）

用奇素數（即3、5或7）可以組成多少個不同的兩位數？75、37、77、33都是可能的解。

這是一個排列的特殊情況，專案可以選擇多次。透過計數，我們發現每個位置有3種可能性，因為數字可以重複。

$\underbrace {3\times 3} _{\text{2 positions}}=3^{2}$

9個不同的數字。

如果我們要從n個專案中選擇m個，並且可能重複，那麼會有

$\underbrace {n\times n\times n...\times n} _{\text{m times}}=n^{m}$

排列。

1. How many three-digit numbers can be formed with only prime digits, and odd digits may only be repeated twice?

環形排列

我們可以用多少種方法讓4個人（愛麗絲、鮑勃、查爾斯和唐納德）圍坐在一張圓桌旁？

這也是排列的另一種特殊情況，4個元素以環形順序排列，排列的起點和終點是未定義的。

如果我們簡單地計算

$4!$

將會有一些重複。我們將重複計算每個獨特的排列，因為像

${\begin{array}{l}{\text{A, B, C, D}}\\{\text{D, A, B, C}}\\{\text{C, D, A, B}}\\{\text{B, C, D, A}}\end{array}}$

被認為是等價的。請記住，圓桌沒有起點。

     有4個人椅子和4組等價排列，這並非巧合。

如果我們任意給椅子編號，我們可以透過迴圈整個佈局來獲得所有等價的排列。我們會迴圈多少次？有多少個椅子/位置？4個。

將我們的第一個意圖除以4（即將4個等價佈置分組）

${\frac {4!}{4}}=3!$

6個唯一的佈置。

另一種方法是強制定義佈局的任意起點，換句話說，固定一個元素並排列剩下的3個元素

$(4-1)!=3!=6$

方法讓四個人圍坐在一張圓桌旁。

1. What if there are 7 people, but the table only has 5 chairs?

無序選擇（組合）

在數學課的15名學生中，將選出5名學生代表班級參加全校數學競賽。有多少種方法可以選擇這5名學生？

這種型別的問題稱為無序選擇（組合），因為選擇學生的順序並不重要。例如，以下選擇被認為是等價的

${\begin{array}{l}{\text{Joe, Lee, Sue, Violet, Justin}}\\{\text{Lee, Joe, Sue, Justin, Violet}}\end{array}}$

如前所述，有

${\frac {15!}{10!}}$

種方法以有序選擇方式選擇5名候選人，但對於每個不同的組合，有5！種有序選擇（即相同的5名學生）。這意味著我們為每個組合都計算了5！次。因此，有

${\frac {15!}{10!\times 5!}}$

種方法選擇5名學生代表班級。

一般來說，從n個專案中選擇m個專案的種數為

${\frac {n!}{(n-m)!\times m!}}$

我們拿出了從 *n* 個專案中選出 *m* 個專案的排列公式，然後除以 *m*!，因為每個組合都被計算了 *m*! 個有序的選擇（*m*! 次）。

這個公式用以下符號表示：

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

注意，${n \choose m}$ 通常讀作 *從 n 中選 m*。

1. Try not to use a calculator and think of the problem with groups of 1 student.

2. Again, no calculator and this time there are 1 million students in the class and we want to form groups of 999,999 students.

重複組合

在這種特殊的組合問題情況下，元素可以被選擇多次。也就是說，組可以包含同一個元素的多個樣本。

知道哪些元素被取樣不足以定義一個選擇，我們需要知道 **每個元素被選擇的次數** （即該元素被選擇的樣本數量）。本質上，這兩種方法是相同的，因為說一個元素被選擇了 0 次等同於說它沒有被取樣。

現在假設我們要從 *n* 個元素中選出 *m* 個元素。我們不應該把這個問題看成是 "從 *n* 個元素中選擇 *m* 次"，而應該把它看成是 "將 *m* 個可用位置分配給 *n* 個不同的元素"（表示將 *m* 個元素放入 *n* 個集合中）。同樣，這兩種解釋是等效的，因為元素被選擇的次數由其對應集合中元素的數量表示。

為了定義一個選擇，我們把每個集合中放入了與我們從該集合所代表的元素中選擇的樣本一樣多的物件。我們可以建立一個字串來標識選擇，例如用一個方塊來表示每個物件（樣本），用一個短橫線來表示集合邊界

$-\underbrace {{\blacksquare }{\blacksquare }{\blacksquare }} _{\text{First set/element}}-\underbrace {{\blacksquare }{\blacksquare }} _{\text{Second set/element}}-\underbrace {{\blacksquare }{\blacksquare }} _{\text{Third set/element}}-$

這意味著三個位置被分配給第一個元素，兩個位置被分配給第二個元素，兩個位置被分配給第三個元素。換句話說，該選擇包含三個第一類元素，兩個第二類元素，兩個第三類元素。該字串可以代表一個隨機的五個字母組成的字母組，僅包含字母 A，B，C

${\text{A, A, A, B, B, C, C}}$

連線的字串由 *m* 個方塊和 *n + 1* 個短橫線組成。例如，以下代表從五個元素中選出的三個元素

$-\underbrace {{\blacksquare }{\blacksquare }} _{\text{First set/element}}-\underbrace {} _{\text{Second set/element}}-\underbrace {\blacksquare } _{\text{Third set/element}}-\underbrace {} _{\text{Forth set/element}}-\underbrace {} _{\text{Fifth set/element}}-$

注意，除了固定在字串開頭和結尾的兩個短橫線外，其他 *n - 1* 個短橫線和 *m* 個方塊可以移動，而不會使字串無效。因此，在 *n - 1 + m* 個位置中，有 *n - 1 + m* 個可移動字元。可能的字串數量等於將 *m* 個方塊放在 *n - 1 + m* 個字元中的方法數量，換句話說，是從 *n - 1 + m* 個位置中選出 *m* 個位置的方法數量

${{n-1+m} \choose {m}}$

等效地，我們可以談論將 *n - 1* 個短橫線放在 *n - 1 + m* 個字元中的位置

${{n-1+m} \choose {n-1}}$

由於每個字串都獨一無二地確定一個選擇或組，因此字串的數量顯然等同於可能的組或選擇的數量。

如果我們要為長途旅行打包三種水果，而你只有香蕉、蘋果、橙子、桃子和奇異果，那麼會有

${{5-1+3} \choose {3}}={{5-1+3} \choose {5-1}}=35$

可能的打包組。

二項式係數

二項式係數

${n \choose m}$

表示從包含n個元素的集合中選擇m個元素可以形成的無序組的數量。

以下是一些基本且有用的屬性

• 從n個元素中選擇m個元素的方式數量等於從n個元素中選擇n-m個元素的方式數量，因為每個選定元素組都有一個相應的未選定元素組。選定元素組定義了另一個未選定元素組。

${n \choose m}={n \choose {n-m}}$

• 只有一種方法可以選擇所有元素或不選擇任何元素。

${n \choose 0}={n \choose n-0}=1$

• 有n種方法可以選擇1或n-1個元素。

${n \choose 1}={n \choose {n-1}}=n$

• 之間的差異

${n \choose m}$

和

${{n+1} \choose m}$

在於第一個公式沒有計算包含在第二個公式中新增的元素的組。包含來自包含n+1個元素的集合中的特定元素的m大小的組的數量是

${{(n+1)-1} \choose {m-1}}={n \choose {m-1}}$

因此

${{n+1} \choose m}={n \choose m}+{n \choose {m-1}}$

• 之間的差異

${n \choose {m+1}}$

和

${n \choose m}$

在於第一個公式計算的組比第二個公式計算的組多一個元素。每個m大小的組需要n-m中剩餘的“缺失”元素中的一個才能增長到m+1大小。

${n \choose m}\times (n-m)$

但是，我們必須觀察到我們多次計算每個m+1大小的組，實際上是m+1次。這是因為“缺失”的元素可以是結果組中的m+1個元素中的任何一個，換句話說，m+1個m大小的組（當與正確的元素關聯時）將形成同一個m+1大小的組。從m+1大小的組中移除一個元素可以形成多少個m大小的組？

${{m+1} \choose 1}=m+1$

這表明

${n \choose {m+1}}={n \choose m}\times {\frac {n-m}{m+1}}$

二項式展開

二項式定理描述了以下表達式的代數展開

$(a+b)^{n}$

例如，取 *n* = 2，我們將嘗試手動展開表示式，得到

$(a+b)^{2}=(a+b)(a+b)=aa+ab+ba+bb$

取 *n* = 3

$(a+b)^{3}=(a+b)(a+b)(a+b)=aaa+aab+aba+abb+baa+bab+bba+bbb$

在展開過程中，我們故意沒有對錶達式進行簡化。正如你所看到的，最終展開的形式分別有四項和八項。這些項都是 *a* 和 *b* 在兩個和三個因子的乘積中所有可能的組合。

因子的數量等於第一個乘積中二項式 *(a + b)* 的數量，而這反過來又等於 *n*。

在

$(a+b)^{n}$

中，每一項都有 *n* 個因子。有多少項只有一個 *b*？換句話說，我可以在 *n* 個不同位置中放置一個 *b* 有多少種方法？或者更好的是，我可以在 *n* 個位置中選擇一個位置（放置一個 *b*）有多少種方法？

${n \choose 1}$

類似地，我們可以計算出其他所有項的係數

$(a+b)^{3}={3 \choose 0}a^{3}+{3 \choose 1}a^{2}b+{3 \choose 2}ab^{2}+{3 \choose 3}b^{3}$

更一般地說

$(a+b)^{n}={n \choose 0}a^{n}+{n \choose 1}a^{n-1}b+{n \choose 2}a^{n-2}b^{2}+...{n \choose n-1}ab^{n-1}+{n \choose n}b^{n}$

或者更簡潔地使用求和運算子

$(a+b)^{n}=\sum _{i=0}^{n}{n \choose i}a^{n-i}b^{i}$

練習

1 用單詞“BOOK”的字母可以排列出多少種不同的方式？

2 從一副牌中選出五張方塊牌有多少種方法？

3 喬伊想給自己做三明治。他將使用火腿、乳酪、薩拉米香腸、番茄和生菜，但他不喜歡火腿和薩拉米香腸互相接觸。他總是把生菜放在最上面。喬伊可以用多少種方法排列他三明治的配料？

4 瑞秋想買一杯冰淇淋。她從十種不同的口味中選擇了三種，但她不喜歡將巧克力與香草混合。瑞秋可以點多少種不同的冰淇淋？

5 喬伊仍然很餓，想吃另一個三明治。他可以使用火腿、乳酪、薩拉米香腸、番茄和生菜（不必全部使用）。他不想在同一個三明治中放火腿和薩拉米香腸。喬伊可以做多少種不同的三明治（三明治中配料的順序無關緊要）？