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

高中數學擴充套件

---

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

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

矩陣 — 更多模運算 — 數學規劃 — 馬爾可夫鏈

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

有序選擇（排列）

假設您的音樂庫中有 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 首不同的歌曲中選擇一首作為第一個位置（或第一首播放的歌曲），從剩下的 9 首中選擇一首作為第二個位置（因為已經選了一首歌曲），從剩下的 8 首中選擇一首作為第三個位置（因為已經選了 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$

種方法可以安排 4 個人坐在圓桌旁。

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!}}$

我們使用了 m 個專案從 n 個專案中排列的公式，然後除以 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 喬伊仍然很餓，想再吃一份三明治。他可以用火腿、乳酪、薩拉米香腸、番茄和生菜（無需全部使用）。他不想在同一個三明治中放火腿和薩拉米香腸。喬伊可以製作多少種不同的三明治（三明治裡配料的順序無關緊要）？