機率/組合學

我們都知道如何計數。然而，計數實際上可能相當複雜，並且存在許多與計數相關的複雜技術。在本章中，我們將介紹一些基本技術，這些技術是計算組合機率（在下一章中討論）的基礎。這些技術大量使用基本計數原理，在下一節中討論。

基本計數原理

就像數學中有四種基本運算：加法、減法、乘法、除法一樣，計數中也有四種相應的基本原理：加法、減法、乘法、除法計數原理。

加法和減法計數原理

命題. (加法計數原理) 如果有$n_{1}$ 種方法可以完成任務 1，以及$n_{2}$ 種方法可以完成任務 2，但是 我們不能同時完成兩個任務，那麼我們有 $n_{1}+n_{2}$ 種方法可以完成任務 1 或任務 2。

備註.

• 在集合論術語中，這意味著如果 $A$ 和 $B$ 是不相交的有限集（分別包含完成任務 1 和 2 的方法），則 $|A\cup B|=|A|+|B|$.

更一般地，我們有減法計數原理

命題。 （減法計數原理） 如果有 $n_{1}$ 種方法完成任務 1，並且有 $n_{2}$ 種方法完成任務 2，並且 有 $n_{3}$ 種方法同時完成兩個任務，那麼我們有 $n_{1}+n_{2}-n_{3}$ 種方法完成任務 1 或 任務 2。

備註.

• 解釋：由於 $n_{1}+n_{2}$ 包含 了過多的方法（一些方法被重複計算），我們需要 排除 這些重複計算的方法 ($n_{3}$ 個)。
• 令 $n_{3}=0$ ，則得到加法計數原理。
• 用集合論的術語來說，這意味著如果 $A$ 和 $B$ 是有限集（分別包含完成任務 1 和 2 的方法），那麼 $|A\cup B|=|A|+|B|-|A\cap B|$.
• 請注意，完成任務 1 或 任務 2 包含了同時完成兩個任務的可能性。也就是說，“或” 是包含的。在數學中，“或” 通常被認為是包含的。

實際上，前面提到的兩個計數原理只是更一般原理的特殊情況：包含-排除原理。

定理。 （容斥原理）設 $n$ 是一個正整數， $S_{1},S_{2},\dotsc ,S_{n}$ 是有限集。 那麼，它們的並集的基數為 $${\begin{aligned}|S_{1}\cup \dotsb \cup S_{n}|&=|S_{1}|+|S_{2}|+\dotsb +|S_{n}|\\&\quad -{\big (}|S_{1}\cap S_{2}|+|S_{1}\cap S_{3}|+\dotsb +|S_{n-1}\cap S_{n}|{\big )}\\&\quad +{\big (}|S_{1}\cap S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{4}|+\dotsb +|S_{n-2}\cap S_{n-1}\cap S_{n}|{\big )}\\&\quad -\dotsb \\&\quad +(-1)^{n+1}|S_{1}\cap S_{2}\cap \dotsb \cap S_{n}|\\\end{aligned}}$$

備註.

• “容斥原理”這個名字來源於這個原理基於 過度包含，然後進行 補償排除。 我們重複包含和排除過程，直到包含完全準確。
• 我們可以認為集合 $S_{1},S_{2},\dotsc ,S_{n}$ 包含完成任務 1,2,...,$n$ 的方法。 然後，並集 $S_{1}\cup S_{2}\cup \dotsb \cup S_{n}$ 包含完成任務 1,2,... 或 $n$ 的方法。

示例。（容斥原理的特殊情況）當 $n=2$ 時，容斥原理給出 $$|S_{1}\cup S_{2}|=|S_{1}|+|S_{2}|-|S_{1}\cap S_{2}|.$$ 當 $n=3$ 時，容斥原理給出 $$|S_{1}\cup S_{2}\cup S_{3}|=|S_{1}|+|S_{2}|+|S_{3}|-|S_{1}\cap S_{2}|-|S_{1}\cap S_{3}|-|S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{3}|.$$

示例。在 140 個人中，有 110 人至少會說英語、法語或德語。已知

• 90 人會說英語，30 人會說法語，42 人會說德語；
• 23 人會說英語和法語；
• 25 人會說英語和德語；
• 16 人會說法語和德語。

求會說英語、法語和德語的人數。

解答. 設 $E$、$F$、$G$ 分別表示會說英語、法語和德語的人的集合。那麼，根據容斥原理，$$|E\cup F\cup G|=|E|+|F|+|G|-|E\cap F|-|F\cap G|-|E\cap G|+|E\cap F\cap G|\implies 110=90+30+42-23-29-16+|E\cap F\cap G|\implies |E\cap F\cap G|=12.$$ 因此，會說英語、法語和德語的人數為 $110-90-30-42+23+25+16=12$.

韋恩圖

*----------------*
|90-13-12-11=54  | <---- E
|      *---------*--------------*
|      |25-12=13 |42-13-12-4=13 | <--- G
*------*---------*--------------*-----*
|      |   12    |16-12=4       |     |
|      *---------*--------------*     | <--- F
|  23-12=11      |  30-11-12-4=3      |
*----------------*--------------------*
  140-110=30

練習。

1 求會說（a）只有英語的人數；（b）只有法語的人數；（c）只有德語的人數。

	(a) 90; (b) 30; (c) 42
	(a) 54; (b) 13; (c) 3
	(a) 54; (b) 11; (c) 3
	(a) 54; (b) 3; (c) 11
	以上都不對。

2 假設在現在的 140 人中，有 $k$ 人學會說英語。計算 $k$ 使得其中 123 人至少會說英語、法語或德語中的一種，並且現在有 20 人會說英語、法語和德語。

	20
	21
	22
	23
	以上都不對。

3 從上一題繼續。計算現在會說英語和法語的人數。

	23
	31
	36
	44
	以上都不對。

乘法計數原理

定理. (乘法計數原理)

一個樹狀圖說明了這個概念。

設 $n$ 是一個正整數。如果做任務 $1,2,\dotsc ,n$ 分別有 $m_{1},m_{2},\dotsc ,m_{n}$ 種方法，那麼做這 $n$ 個任務有 $m_{1}\times m_{2}\times \dotsb \times m_{n}$ 種方法。

證明. 我們用數學歸納法證明。設 $P(n)$ 為命題

"如果做任務 $1,2,\dotsc ,n$ 分別有 $m_{1},m_{2},\dotsc ,m_{n}$ 種方法，那麼做這 $n$ 個任務有 $m_{1}\times m_{2}\times \dotsb \times m_{n}$ 種方法."

基礎步驟: 假設做任務 1 有 $m_{1}$ 種方法。那麼顯然做這一個任務有 $m_{1}$ 種方法。所以，$P(1)$ 顯然成立。

歸納假設: 設 $k$ 是一個任意正整數。假設 $P(k)$ 成立。也就是說，假設

如果完成任務 $1,2,\dotsc ,k$ 分別有 $m_{1},m_{2},\dotsc ,m_{k}$ 種方法，那麼完成這 $k$ 個任務有 $m_{1}\times m_{2}\times \dotsb \times m_{k}$ 種方法。

是正確的。

Inductive Step: We want to show that $P(k+1)$ is true. So, we now assume that there are $m_{1},m_{2},\dotsc ,m_{k},{\color {darkgreen}m_{k+1}}$ ways to do the task $1,2,\dotsc ,k,{\color {darkgreen}k+1}$ respectively. By the inductive hypothesis, there are $m_{1}\times m_{2}\times \dotsb \times m_{k}$ ways to do the first $k$ tasks (task $1,2,\dotsc ,k$). Now, for each of the $m_{1}\times m_{2}\times \dotsb m_{k}$ ways of doing the first $k$ tasks, there are ${\color {darkgreen}m_{k+1}}$ ways to do the task $k+1$. Expressing it using a table, we have $${\begin{array}{cc}{\text{ways of doing the first }}k{\text{ tasks}}&{\text{number of ways to do task }}k+1\\\hline {\text{way 1}}&m_{k+1}\\{\text{way 2}}&m_{k+1}\\\vdots &\vdots \\{\text{way }}m_{1}\times m_{2}\times \dotsb m_{k}&m_{k+1}\\\end{array}}$$ Hence, the number of ways of doing the $k+1$ tasks (the first $k$ tasks, and the task $k+1$) is $$\underbrace {m_{k+1}+m_{k+1}+\dotsb +m_{k+1}} _{m_{1}\times m_{2}\times \dotsb m_{k}{\text{ times}}}=(m_{1}\times m_{2}\times \dotsb \times m_{k})m_{k+1}=m_{1}\times m_{2}\times \dotsb \times m_{k+1}.$$ So, $P(k+1)$ is true.

因此，根據數學歸納法，$P(n)$ 對每個正整數 $n$ 都成立。

$\Box$

備註.

• 有時，將“完成方式”替換為“結果”可能更自然，特別是在任務具有隨機結果且無法控制結果的情況下（例如抽獎）。

• 類似地，將“任務”替換為“試驗”有時可能更自然。

當我們使用乘法計數原理來解決一些計數問題時，需要注意以下幾點

• 我們需要確保完成每個任務的方式數量是 固定的，並且不應該依賴於完成其他任務的方式。（參見以下示例）
• 在使用乘法計數原理來計算完成 $n$ 個任務的方式數量後，有可能一些方式（或“決策路徑”，即我們“走過”的樹狀圖路徑）實際上對應於問題情況下 相同的結果，因此在該上下文中，這些方式應只算作一種結果。（參見以下示例）

示例。（試驗結果數量不固定）考慮一個包含一個 紅色 球和一個 藍色 球的盒子。假設試驗 1 和 2 分別是第一次和第二次從盒子中取出一個球。我們進一步假設當取出 紅色 球時，我們將其放回盒子中。否則，我們不放回。那麼，如果我們在試驗 1 中取出 紅色 球，那麼試驗 2 有兩種結果。否則，試驗 2 只有 1 種結果。在這種情況下，乘法計數原理不適用，因為試驗 2 的結果數量不是 固定的（它在 1 和 2 之間變化，具體取決於試驗 1 的結果）。

使用圖表，這種情況如下所示

  Trial 1         Trial 2

              ---- red
             /    
   red  ----*
 /           \    
*             ---  blue
 \           
  blue  ----*--- red

我們可以看到，我們只有 3 種方法可以完成這兩個任務。（這裡，完成任務 2 的方法數量既不是 1 也不是 2。事實上，我們無法確定這個數字，因為這個數字根本不固定。）

示例。（兩個決策路徑導致相同的結果）

假設我們同時拋擲兩枚相同且不可區分的硬幣。我們還將一枚硬幣的結果視為“試驗 1”的結果，另一枚硬幣的結果視為“試驗 2”的結果。在這種情況下，我們可以使用圖表來說明情況

Trial 1              Trial 2 
                    ---- H
                   / 
   H -------------* 
 /                 \---- T
/
*                   
\                   ----- H
 \                 /
   T -------------*
                   \
                    ----- T

在這種情況下，“試驗 1 中為 H，試驗 2 中為 T”與“試驗 1 中為 T，試驗 2 中為 H”相同，因為兩者在該上下文中意味著相同的事情

我們從一枚硬幣得到“正面”，從另一枚硬幣得到“反面”。

因此，這兩個試驗實際上只有三個（不同的）結果

1. “兩個正面”
2. “一個正面，一個反面”
3. “兩個反面”，

而不是 $2\times 2=4$ 個結果，因為不可區分的試驗導致兩個決策路徑導致相同的結果。

練習。假設你有一個抽屜，裡面有 50 只相同的紅色襪子和 50 只相同的藍色襪子，假設你從抽屜裡取出兩隻襪子。這兩隻襪子有多少種不同的顏色組合？

解決方案

我們從抽屜裡取出兩次。我們將“取 1”視為任務 1，將“取 2”視為任務 2。

Task 1              Task 2 
                    ---- R
                   / 
   R -------------* 
 /                 \---- B
/
*                   
\                   ----- R
 \                 /
   B -------------*
                   \
                    ----- B
R: red sock
B: blue sock

類似地，“任務 1 中為 R，任務 2 中為 B”的顏色模式本質上與“任務 1 中為 B，任務 2 中為 R”的顏色模式相同，因為在兩種情況下，顏色組合都是“1 個紅色 1 個藍色”。在這種情況下，只有三個不同的顏色組合

1. 2 個紅色
2. 1 個紅色 1 個藍色
3. 2 個藍色

示例。

在一個國家，有三個城鎮：A 鎮、B 鎮和 C 鎮。每個城鎮之間的路線由下圖說明

  /*------*\          *------------*
 /          \        /             |
A---*\       /B ----*--------------C
      \ /*--*  \                  /
       *        \                /
                 *--------------* 

計算從 A 鎮到 C 鎮的路線數量。

解決方案. 首先，我們從 A 鎮到 B 鎮有 2 條路線，從 B 鎮到 C 鎮有 3 條路線。所以，從 A 鎮到 C 鎮有 $2\times 3=6$ 種路線。

練習。假設部分路線以以下方式斷開：（xxx 表示斷開路線）

  /*------*\          *------------*
 /          \        /             |
A---*\       /B xxx *--------------C
      \ /*--*  \                  /
       *        \                /
                 *--------------* 

現在計算從 A 鎮到 C 鎮的路線數量。

解決方案

路線數量為 $2\times 1=2$.

練習。

一位化學家有三種未知化學物質：化學物質 A、B 和 C。為了測試這三種化學物質，化學家決定進行以下所有實驗

1. 混合 A 和 B
2. 混合 B 和 C
3. 混合 A 和 C

假設已知化學物質 A 比其他兩種化學物質更具反應性，因此

• 混合不含化學物質 A 的兩種化學物質後，有兩種可能的結果：（i）無反應；（ii）弱反應；
• 混合含有化學物質 A 的兩種化學物質後，有三種可能的結果：（i）無反應；（ii）弱反應；（iii）爆炸。

這三個實驗有多少種可能的結果？

解決方案

實驗1、2、3 的可能結果數分別為 3、2、3。因此，這三個實驗的可能結果總數為 $3\times 2\times 3=18$.

示例：（冪集中的元素數）集合 $S$ 的冪集中元素的個數為 $2^{n}$，其中 $n$ 是集合 $S$ 中的元素個數。

證明：考慮集合 $S$ 中的 $n$ 個元素，逐個進行考慮。對於每個元素，我們可以選擇 包含它或 不包含它在集合 $S$ 的一個子集中。因此，構造集合 $S$ 的一個子集需要 $n$ 步，每步都有兩種可能的結果。根據乘法計數原理，這 $n$ 步有 $\underbrace {2\times 2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}$ 種可能的結果。也就是說，集合 $S$ 有 $2^{n}$ 個可能的（不同的）子集。根據定義，冪集包含集合 $S$ 的所有子集，因此冪集有 $2^{n}$ 個元素。

$\Box$

示例：假設我們擲兩個（六面）骰子，顏色分別為紅色和藍色。證明向上面的數字組合可能出現的不同對數為 $6\cdot 6=36$.

證明：由於骰子是可區分的，我們可以使用乘法計數原理。更準確地說，我們可以將紅色骰子可能出現的數字作為“試驗1”的可能結果，藍色骰子的可能結果作為“試驗2”的可能結果。由於每次試驗都有六種可能的結果，因此可能的結果（即可能出現不同的對數）為 $6\cdot 6=36$.

$\Box$

練習：假設紅色骰子變成藍色骰子，使得兩個骰子不再可區分。證明向上面的數字組合可能出現的不同對數為 21。（提示：從上面的 36 對中減去一些對。）

證明

證明。 從例子中的 36 種結果中，有些組合在改變後與其他組合相同（即，我們不能將它們識別為兩組不同的組合）。因此，我們需要從這 36 個組合中刪除一個重複的組合。使用 $(a,b)$ 表示原始紅藍骰子中朝上的數字 $a$ 和 $b$，我們有 $${\begin{aligned}&(1,2),{\cancel {(2,1)}},(1,3),{\cancel {(3,1)}},(1,4),{\cancel {(4,1)}},(1,5),{\cancel {(5,1)}},(1,6),{\cancel {(6,1)}},&\leftarrow {\text{5 pairs removed}}\\&(2,3),{\cancel {(3,2)}},(2,4),{\cancel {(4,2)}},(2,5),{\cancel {(5,2)}},(2,6),{\cancel {(6,2)}},&\leftarrow {\text{4 pairs removed}}\\&(3,4),{\cancel {(4,3)}},(3,5),{\cancel {(5,3)}},(3,6),{\cancel {(6,3)}},&\leftarrow {\text{3 pairs removed}}\\&(4,5),{\cancel {(5,4)}},(4,6),{\cancel {(6,4)}},&\leftarrow {\text{2 pairs removed}}\\&(5,6),{\cancel {(6,5)}}.&\leftarrow {\text{1 pair removed}}\end{aligned}}$$ 總共刪除了 $5+4+3+2+1=15$ 個組合，所以我們想要的數字是 $36-15=21$.

$\Box$

除法計數原理

定理. （除法計數原理）如果一個任務可以使用一個可以執行 $n$ 種方法的 過程 完成，並且對於執行任務的每種方法 $w$，在 過程 中恰好有 $d$ 種 $n$ 種方法對應於方法 $w$。（${\frac {n}{d}}$ 是一個正整數。）

從圖形上看，它就像 $${\begin{aligned}{\text{Task }}\quad &{\text{ Procedure}}\\\hline {\text{way 1}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\{\text{way 2}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\\vdots \\{\text{way }}{\frac {n}{d}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\\hline \qquad \qquad &{\text{Total}}:{\frac {n}{d}}\times d=n{\text{ ways for the procedure}}\end{aligned}}$$

例子. （數牛）假設我們要計算一個牧場裡牛的數量。我們先數出總共有 1000 條腿。由於每頭牛有四條腿，所以牛的數量是 ${\frac {1000}{4}}=250$。（這裡，“任務”可以解釋為選擇一頭牛，“過程”可以解釋為選擇一條腿。然後，選擇一條腿的 4 種方法對應於選擇一頭牛的 1 種方法。）

例子. （圓桌座位安排）

一個說明這個想法的動畫。

計算在圓桌旁為四個人安排座位的種數，其中兩個座位安排被認為是 相同 的，如果每個人都有 相同的左邊鄰居 和 相同的右邊鄰居。例如，以下兩個座位安排被認為是相同的

   1               4
4     2         3     1
   3               2

但以下兩個座位安排被認為是 不同 的

   1               4
4     2         1     3
   3               2

因為，對於第 1 個人來說，在左邊座位安排中，他的左邊和右邊鄰居分別是 2 和 4，而在右邊座位安排中，他的左邊和右邊鄰居分別是 4 和 2。

解決方案.

過程：首先，我們計算在圓桌旁為四個人安排座位的種數，不考慮座位安排是否被認為相同。我們將座位安排看作一個四步過程

1. 為第一個人分配一個座位（有 4 個空座位，所以有 4 種方法）
2. 為第二個人分配一個座位（有 3 個空座位，所以有 3 種方法）
3. 為第三個人分配一個座位（有 2 個空座位，所以有 2 種方法）
4. 為第四個人分配一個座位（有 1 個空座位，所以有 1 種方法）

方法數由以下公式給出：$$\underbrace {4} _{4{\text{ vacant seats}}}\times \underbrace {3} _{3{\text{ vacant seats}}}\times \underbrace {2} _{2{\text{ vacant seats}}}\times \underbrace {1} _{1{\text{ vacant seat}}}=24.$$ 任務：給定一個過程中的安排，我們可以將其順時針旋轉 90、180 或 270 度（旋轉 360 度與不旋轉相同），以產生另外三種不同的過程安排。然而，這四種安排在任務中被視為相同。這意味著過程中的這四種安排對應於任務中的一種安排。然後，根據除法計數原則，所需的方法數為 $${\frac {24}{4}}=6.$$

練習. 如果有五個人而不是四個人，計算方法數。

解決方案

步驟：首先，在圓桌旁坐五個人（不考慮座位是否被認為是相同的）的方法數為 $$\underbrace {5} _{5{\text{ vacant seats}}}\times \underbrace {4} _{4{\text{ vacant seats}}}\times \underbrace {3} _{3{\text{ vacant seats}}}\times \underbrace {2} _{2{\text{ vacant seats}}}\times \underbrace {1} _{1{\text{ vacant seat}}}=120.$$ 同樣。

任務：給定過程中的安排，我們可以將其順時針旋轉 72、144、216 或 288 度，以產生 四個 更多不同的過程安排。但這五種安排在任務中被視為相同。因此，過程中的 五 種安排對應於任務中的一種安排。因此，所需的方法數為 $${\frac {120}{5}}=24.$$

示例。

假設 10 個人決定一起打籃球。因此，他們需要將自己分成兩支無法區分的隊伍，每支隊伍有 5 個人。

1. 控球后衛
2. 得分後衛
3. 小前鋒
4. 大前鋒
5. 中鋒

有多少種方法可以組建這兩支隊伍？

解決方案.

步驟：首先，我們假設這兩支隊伍是可區分的，例如一支是藍隊，另一支是紅隊。在這種情況下，我們可以將隊伍組建過程視為一個 10 步過程

• 步驟 1：從 10 個人中選一個作為藍隊的控球后衛。（10 種方法）
• 步驟 2：從 9 個人中選一個作為藍隊的得分後衛。（9 種方法）
• 步驟 3：從 8 個人中選一個作為藍隊的小前鋒。（8 種方法）
• ...
• 步驟 10：從 1 個人中選一個作為紅隊的中鋒。（1 種方法）

所以，組建這兩支可區分的隊伍共有 $10\times 9\times 8\times \dotsb \times 1=3628800$ 種方法。

任務：給定一個組建兩支隊伍的過程方法，我們可以交換藍隊和紅隊的隊員，以產生另一種不同的組建兩支隊伍的過程方法。也就是說，將最初在藍隊的隊員都分配到紅隊，將最初在紅隊的隊員都分配到藍隊，我們可以建立另一種組建兩支隊伍的過程方法。但這兩種方法對應於任務中的一種方法（在這兩種方法中，兩支無法區分的隊伍包含相同的隊員，因此這兩種方法被認為是相同的）。根據除法計數原則，方法數為 $${\frac {3628800}{2}}=1814400.$$

練習. 假設每支隊伍都沒有位置。也就是說，一支隊伍的五個人都被視為僅僅是隊伍的成員，沒有特定的角色或位置。證明組建這兩支隊伍只有 126 種方法。（提示：確定將位置安排在最初隊伍中 5 個人的方法數。然後，應用除法計數原則（將 1814400 除以某個數）。

證明

證明. 步驟：假設每支隊伍仍然有位置。然後，根據上面的示例，組建這兩支隊伍有 1814400 種方法。

任務：給定步驟中的一個方法，我們可以將位置安排在兩支隊伍中 5 個人的位置。現在，讓我們考慮有多少種排列方法。對於每支隊伍，它是一個五步過程

1. 從 5 個隊員中選擇一個作為控球后衛（5 種方法）
2. 從 4 個隊員中選擇一個作為得分後衛（4 種方法）
3. 從 3 個隊員中選擇一個作為小前鋒（3 種方法）
4. 從 2 個隊員中選擇一個作為大前鋒（2 種方法）
5. 從 1 個隊員中選擇一個作為中鋒（1 種方法）

所以，每支隊伍的排列方法數為 $5\times 4\times 3\times 2\times 1=120$。然後，安排兩支隊伍是一個兩步過程

1. 安排其中一支隊伍（120 種方法）
2. 安排另一支隊伍（120 種方法）

所以，排列的總方法數為 $120\times 120=14400$，其中包括給定的方法。

因此，這意味著在程式中，我們可以生成$14400-1=14399$ 種方法。但這些 14400 種方法在沒有位置的情況下被認為是相同的（兩支隊伍都包含相同的成員）。根據除法計數原理，方法的數量為$${\frac {1814400}{14400}}=126.$$

$\Box$

我們應該意識到，如果不同的任務執行方式對應於程式中不同的數量，則除法計數原理不適用。考慮以下示例

示例。 （同一個籠子裡的雞和兔子）

假設同一個籠子裡有一些雞和兔子，但我們不知道有多少雞和兔子。假設我們知道籠子裡有 120 條腿。然後，學生 A 和 B 為計算籠子裡動物的數量做出了以下論據

• 學生 A：由於每隻兔子都有四條腿，籠子裡有${\frac {120}{4}}=30$ 只動物。
• 學生 B：由於每隻雞都有兩條腿，籠子裡有${\frac {120}{2}}=60$ 只動物。

解釋為什麼兩個學生都錯了。

解決方案。學生 A 錯了，因為籠子裡並非每隻動物都有四條腿（雞有兩條腿）。類似地，學生 B 錯了，因為籠子裡並非每隻動物都有兩條腿（兔子有四條腿）。我們可以看到除法計數原理在這裡不適用。

示例。 假設我們拋硬幣兩次。沒有任何假設，不同的結果是 HH、HT、TH 和 TT。假設我們將拋擲視為無序，即結果的順序並不重要。在這種情況下，結果 HT 和 TH 被視為相同，例如兩者都被視為“1 個正面 1 個反面”，或者簡稱為“1H1T”。但結果 HH 和 TT 仍然被視為不同。

有了這樣的考慮，結果就變成了“2H”、“1H1T”和“2T”。但我們看到“1H1T”對應於“HT”和“TH”（“程式”中的兩種方式），而“2H”對應於“HH”（“程式”中的一種方式）。所以，除法計數原理在這裡不適用，這種情況下的結果數量不是由${\frac {4}{2}}=2$ 給出。

練習。 假設我們拋硬幣兩次，我們只關心兩次拋擲是否產生相同的結果。我們可以在此處使用除法計數原理嗎？為什麼？

解決方案

在這種情況下，"HH" 和 "TT" 都對應於"相同的結果"，而 "HT" 和 "TH" 對應於"不同的結果"。因此，對於"任務"的每個結果，都有兩個對應於它的"程式"結果，因此可以使用除法計數原理獲得所需的結果數量：$${\frac {4}{2}}=2.$$

將r個球放入n個單元格中的方法數量

在本節中，我們將討論如何計算將$r$個球放入$n$個單元格中的方法數量。從這裡，人們可能會問為什麼我們考慮這種情況，而且似乎我們很少在實踐中遇到這種情況。通常，我們想要計算做其他事情的方法數量，而不是將球放入單元格中。

雖然許多遇到的情況似乎與這種情況大不相同，特別是背景通常不是關於將球放入單元格中，但我們可以認為它們好像我們在將球放入單元格中。事實上，許多情況被稱為“抽象等效”，從某種意義上說，"生成"結果的底層過程是相同的，但我們只是用不同的詞語來描述。

讓我們考慮一些與“將$r$個球放入$n$個單元格中”抽象等效的情況（對於某些$n$和$r$）

1. 10 人可能的生日數量：將 10 個“人”（球）放入 365 個“生日日期”（單元格）中。（這裡，我們假設一年只有 365 天。）請注意，我們不是將 365 個“生日日期”放入 10 個“人”中。（如果是這種情況，有些人會有不止一個生日！）還要注意，我們可以將不止一個人放入同一個“生日日期”中。（多人可以分享同一個生日！）
2. 設定 6 位數字密碼：將 6 個“密碼位置”（球）放入 10 個“數字”（單元格）中 (0,1,...,9)。（同樣，我們不是將“數字”放入“密碼位置”中。如果是這種情況，那麼某些密碼位置包含不止一個數字，這是不可能的。）
3. 將 1000 人分類為 0-10 歲、11-20 歲、...、91-100 歲、101 歲或以上：將 1000 個“人”（球）放入 11 個“年齡組”（單元格）中。
4. 電梯有 20 個乘客，停在 10 層樓：將 20 個“乘客”（球）放入 10 個“樓層”（單元格）中。
5. 3 只鴿子飛進 2 個鴿舍：將 3 只“鴿子”（球）放入 2 個“鴿舍”（單元格）中。
6. 滾動 10 個骰子：將 10 個“骰子”（球）放入 6 個“結果”（單元格）。
7. 從一副撲克牌中抽取 3 張牌：將 3 個“抽籤”（球）放入 52 個“牌”（單元格）。
8. 拋擲 2 枚硬幣：將 2 個“拋擲”（球）放入 2 個“結果”（單元格）。
9. 從 20 個人中選出 5 個人組成委員會：將 5 個“委員會職位”（球）放入 20 個“人”（單元格）。

在本節中，我們將主要針對 四種類型 從可區分物件中選擇某些物件的情況，根據選擇是否 有序 以及選擇是否 有放回 進行分類，推導一些計算選擇方法數量的公式。我們可以應用上述“抽象等價”的概念，將這種選擇轉化為將一些可區分或不可區分的球放入一些具有特定容量的可區分單元格的問題，從而使我們能夠更輕鬆、更方便地推匯出公式。（正如我們將會看到的，球的可區分性對應於選擇是否有序，而單元格的容量對應於選擇是否有放回。）

在討論這四種類型的選擇之前，我們需要先介紹一個在後續內容中將頻繁使用的數學概念。

定義。（階乘）令 $n$ 為非負整數。 $n$ 的 階乘，記為 $n!$，定義為：$$n!={\begin{cases}1,&n=0;\\n(n-1)(n-2)\dotsb (1),&n\geq 1.\end{cases}}$$

將 r 個可區分的球放入 n 個容量為 1 的可區分單元格（有序選擇，不放回）

首先讓我們討論從 $n$ 個物件中 有序 選擇 $r$ 個物件，不放回。我們可以認為這與將 $r$ 個可區分的球（選擇 1、2、…、$r$）放入 $n$ 個可區分的單元格（物件 1、2、…、$n$）抽象等價，容量為 1。

• 容量為 1 是因為 不放回，我們無法多次選擇同一個物件（無法將兩個或多個球（選擇）放入同一個單元格（物件））。

然後，我們推匯出以下公式。

定理。 將 $r$ 個可區分的球放入 $n$ 個容量為 1 的可區分單元格的方法數量是 $_{n}P_{r}={\frac {n!}{(n-r)!}}$。

證明。 我們將放置視為一個 $r$ 步過程

• 對於第一個球，有 $n$ 個空格子。因此，有 $n$ 種方法將球放入格子中。
• 對於第二個球，有 $n-1$ 個空格子。因此，有 $n-1$ 種方法將球放入格子中。
• ...
• 對於第 $r$ 個球，有 $n-(r+1)$ 個空格子。因此，有 $n-(r+1)$ 種方法將球放入格子中。

因此，根據計數的乘法原理，所需方法的數量為 $$\underbrace {n} _{\text{ball 1}}\times \underbrace {(n-1)} _{\text{ball 2}}\times \dotsb \times \underbrace {(n-r+1)} _{{\text{ball }}r}={\frac {n\times (n-1)\times \dotsb \times (n-r+1)\times {\color {darkgreen}(n-r)\times \cdots \times 1}}{\color {darkgreen}(n-r)\times \cdots \times 1}}={\frac {n!}{(n-r)!}}.$$

$\Box$

示例. 在書架的一排上，有 5 個放置書籍的位置。艾米有 11 本書，想要填滿這一排（順序很重要）。有多少種可能的方法？

解答. 我們可以將 5 個放置書籍的位置視為 5 個球，艾米擁有的 11 本書視為 11 個格子，每個格子容量為 1（因為每本書最多隻能放置一次）。因此，方法的數量為 $$_{11}P_{5}=11\times 10\times 9\times 8\times 7=55440.$$

示例。

在某個地方，有 10 根旗杆，放置在不同的位置。假設我們有 7 面不同的旗幟要放在旗杆上，並且每根旗杆最多隻能放一面旗幟。有多少種可能的排列方法？

解答. 我們可以將 10 根旗杆視為 10 個可區分的格子（因為旗杆在不同的位置），每個格子容量為 1（旗杆最多隻能放一面旗幟），並將 7 面不同的旗幟視為 7 個可區分的球。因此，排列方法的數量為 $$_{10}P_{7}=10\times 9\times 8\times 7\times 6\times 5\times 4=604800.$$

練習. 假設有 7 根旗杆和 10 面不同的旗幟。計算可能的排列方法的數量。

解決方案

我們可以將 7 根旗杆視為 7 個可區分的球，並將 10 面不同的旗幟視為 10 個可區分的格子，每個格子容量為 1（因為每面旗幟最多隻能放在一根旗杆上）。經過這樣的解釋，情況與上面相同。因此，排列方法的數量也是相同的 (604800)。

示例。

從一副撲克牌（有 52 張牌）中抽取 5 張牌，抽取的順序很重要，有多少種方法？

解答. 我們可以將 5 次有序抽取視為 5 個可區分的球，將一副撲克牌中的 52 張牌視為 52 個可區分的格子。那麼，方法的數量為 $$_{52}P_{5}={\frac {52!}{47!}}=311875200.$$

練習. 如果抽取的順序 不重要，有多少種方法？（提示: 考慮除法計數原理。為了確定對應於一個無序抽取的有序抽取的數量，考慮對 5 次抽取進行排序（或 排列）的方法數量。）

解決方案

要排列 5 次抽籤，我們可以將 5 次抽籤視為 5 個可區分的球，將 5 個有序位置視為 5 個可區分的單元格（容量為 1）。那麼，這種排序的方案數為 $_{5}P_{5}={\frac {5!}{0!}}=5!=120$.

這反過來意味著 120 種有序抽籤對應 1 種無序抽籤。也就是說，有 120 種有序抽籤，其中 5 次抽籤始終包括 5 張牌的組合。因此，根據除法計數原理，方案數為 $${\frac {311875200}{120}}=2598960.$$

示例。 （比賽）有 16 位候選人參加比賽。

(a) 有多少種方法可以頒發冠軍、第一名和第二名？

(b) 艾米和鮑勃是 16 位候選人中的兩位。假設艾米獲得了第一名，而鮑勃沒有獲得任何獎項。有多少種方法可以頒發冠軍、第一名和第二名？

(a) 方案數為 $$_{16}P_{3}=\underbrace {16} _{\text{winner}}\times \underbrace {15} _{\text{1st runner-up}}\times \underbrace {14} _{\text{2nd runner-up}}=3360.$$

(b) 方案數為 $$_{14}P_{2}\times 1=\underbrace {14} _{\text{winner}}\times \underbrace {1} _{\text{1st runner-up: Amy}}\times \underbrace {13} _{\text{2nd runner-up}}=182.$$

練習。

1 假設克里斯也是 16 位候選人中的一員。鑑於艾米、鮑勃和克里斯獲得了比賽的獎項，計算頒發冠軍、第一名和第二名的方案數。

	1
	3
	6
	32
	96

2 繼續上一個問題。鑑於艾米、鮑勃和克里斯 沒有 獲得比賽的任何獎項，計算頒發冠軍、第一名和第二名的方案數。

	1716
	2496
	3354
	3357
	3359

示例。 證明排列（或排列）$n$ 個可區分物件的方案數為 $n!$.

證明。 排列 $n$ 個可區分物件與將 $n$ 個可區分物件（球）放入 $n$ 個可區分的（且有序的）“位置”（單元格）相同。（例如，當球 1、2、3 分別放入位置 2、3、1 時，這意味著按以下順序排列三個球：3、1、2。）因此，方案數為 $_{n}P_{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$.

$\Box$

示例。 有多少種方法可以排列字串“APPLE”？(提示: 您可能需要使用除法計數原理。）

解決方案。首先，我們排列字串，就像兩個“P”是可區分的。然後，有 $5!$ 種方法可以執行“過程”。但實際上兩個“P”是不可區分的，因此 $5!$ 種方法中的一些實際上被認為是相同的。更準確地說，當我們交換兩個“P”在一個給定字串中的位置時，得到的字串在“任務”中應該與之前相同，但如果我們在“過程”中將兩個“P”視為可區分的，我們將其視為兩個不同的字串。因此，我們將方案數除以 2，以獲得執行“任務”的方案數：$${\frac {5!}{2}}=60,$$ 這就是我們想要的。

練習. 字串“PEPPER”有多少種排列方式？

解決方案

我們使用與上面例子類似的方法。首先，我們將字串排列，就好像三個“P”和兩個“E”是可以區分的一樣。因此，有 $6!$ 種“過程”排列方式。

現在，對於“任務”，給定一個字串，對 3 個“P”進行排序不會改變字串。同樣，對 2 個“E”進行排序也不會改變字串。但是，這種排序會在過程中改變字串。根據乘法計數原理和關於排序的結果，有 $3!\times 2!=12$ 種這樣的排序，因此在過程中有 12 種方式對應一個給定的字串。因此，排列方式的數量是 $${\frac {6!}{12}}=60.$$

上面例子中的情況實際上可以解釋為劃分的特例。

劃分

為了排列字串“APPLE”，我們可以將情況看作是將 5 個（可區分且有序的）字母位置劃分為 4 個組：“A”、“P”、“L”和“E”，我們要求“A”、“P”、“L”、“E”組分別包含 1、2、1、1 個字母位置。類似地，為了排列字串“PEPPER”，我們可以將情況看作是將 5 個（可區分且有序的）字母位置劃分為 3 個組：“P”、“E”和“R”，我們要求“P”、“E”、“R”組分別包含 3、2、1 個字母位置。

這種情況下實際上等效於將可區分的球放入可區分的盒子中，並對每個盒子中必須包含的球數進行一些限制。一般來說，“將$n$ 個可區分的物體劃分為$k$ 個組，其中組 1、2、…、$k$ 必須分別包含$n_{1},n_{2},\dotsc ,n_{k}$ 個物體”（僅僅改變將物體放入某個組的順序不會影響劃分，因為最終組中仍然包含相同的東西。）實際上等效於“將$n$ 個可區分的球放入盒子 1、2、…、$k$ 中，其中盒子 1、2、…、$k$ 必須分別包含$n_{1},n_{2},\dotsc ,n_{k}$ 個球”。

定理. 將$n$ 個可區分的球放入盒子 1、2、…、$k$ 中，其中盒子 1、2、…、$k$ 必須分別包含$n_{1},n_{2},\dotsc ,n_{k}$ 個球，方法的數量是 ${\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}={\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$.

證明。 首先，我們考慮一個過程，在這個過程中我們認為單元格 1、2、...、$k$ 包含 $n_{1},n_{2},\dotsc ,n_{k}$ 個 有序位置 用於放置一個球（例如，在單元格 1、2、...、$k$ 中有 $n_{1},n_{2},\dotsc ,n_{k}$ 個“子單元格”。在這種情況下，我們可以將放置視為 $n$ 個可區分球的排列，因為 $k$ 個單元格總共包含 $n$ 個“有序位置”（“子單元格”）。經過這樣的考慮，放置的方法數量為 $n!$。

但當然我們實際上沒有這樣的“子單元格”。所以，我們將使用除法計數原理。給定“任務”中的特定分割槽，有 $n_{1}!,n_{2}!,\dotsc ,n_{k}!$ 種方法來排列單元格 1、2、...、$k$ 中子單元格的可區分球，所以總共有 $n_{1}!n_{2}!\dotsc n_{k}!$ 種方法，對應於“任務”中的一種方法。因此，根據除法計數原理，分割槽的方法數量為 ${\frac {n!}{n_{1}!n_{2}!\dotsc n_{k}!}}$。

$\Box$

備註.

• ${\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}$ 被稱為 多項式係數。

練習。

計算排列字串“EXERCISE”的方法數量。

	28
	56
	3360
	6720
	20160

示例。 證明將數字 171237615 排序使得形成的數字為奇數的方法數量為 23520。

證明。 我們考慮相反情況的排列數量，即形成的數字為偶數，因為這個數字更容易計算。我們可以注意到，為了使形成的數字為偶數，該數字必須以數字 2 或數字 6 結尾。因此，我們考慮在這兩種情況下的排序方法數量。

情況 1：以 2 結尾。那麼，我們只能在頭八個數字位置對剩下的 8 個數字進行排序。排序的方法數量為 ${\frac {8!}{3!2!}}=3360$（有三個“1”和兩個“7”。所有其他數字都只出現一次。）

情況 2：以 6 結尾。那麼，我們只能在頭八個數字位置對剩下的 8 個數字進行排序。排序的方法數量為 ${\frac {8!}{3!2!}}=3360$（有三個“1”和兩個“7”。所有其他數字都只出現一次。）

我們還可以看到，一個數字不能同時以數字 2 和 6 結尾。 因此，這兩種情況下沒有共同的排序。 因此，形成偶數的排序數量是 $3360+3360=6720$.

現在，我們考慮 沒有 任何限制的排序數量。 該數字由 ${\frac {9!}{3!2!}}=30240$ 給出。 由於形成的數字是奇數或偶數，我們可以從沒有限制的排序數量中減去形成偶數的排序數量，以得到所需數量。 因此，所需數量是 $30240-6720=23520$.

$\Box$

練習。 在下面，撲克牌有 52 張，每個玩家都得到相同數量的牌（即 13 張）。 還假設四個玩家分別被稱為北、東、南、西玩家，分別坐在桌子上的北、東、南、西位置。

(a) 證明將一副撲克牌分給 4 個玩家的方法數量約為 $5.364\times 10^{28}$.

(b) 證明將一副撲克牌分給 4 個玩家的方法數量，使每個玩家都正好有一張 A，約為 $5.659\times 10^{27}$.

(c) 證明將一副撲克牌分給 4 個玩家的方法數量，使一個玩家得到所有四張 A，約為 $5.667\times 10^{26}$.

(d) 證明將一副撲克牌分給 4 個玩家的方法數量，使北玩家得到所有 13 張同花順，約為 $3.379\times 10^{17}$.

證明

一般來說，我們可以將 52 張牌視為 52 個可區分的球，將四個玩家視為四個可區分的單元格。 但對不同部分的單元格的球的數量要求不同。

(a)

證明。 以這種方式分發撲克牌可以被視為將 52 張牌分成四個（可區分的）組，每組正好包含 13 張牌。 因此，方法的數量是 ${\frac {52!}{(13!)^{4}}}\approx 5.364\times 10^{28}$.

$\Box$

(b)

證明。 我們首先考慮牌組中沒有 A 的 48 張牌。 有 ${\frac {48!}{(12!)^{4}}}$ 種方法將 48 張牌分成四個 12 張牌的組。 現在，我們考慮四張 A 的分配。 由於每個玩家都正好有一張 A，分配四張 A 就相當於對四張 A 進行排列。 因此，該數字是 $4!$。 因此，該數字是 $4!\times {\frac {48!}{(12!)^{4}}}\approx 5.659\times 10^{27}$.

$\Box$

(c)

證明。 我們首先考慮牌組中沒有 A 的 48 張牌。 有 ${\frac {48!}{(13!)^{3}\times 9!}}$ 種方法將 48 張牌分成四個組，使得其中三個組分別包含 13 張牌（沒有得到所有四張 A 的玩家），一個組包含 9 張牌（得到所有四張 A 的玩家）。 由於一個玩家得到了所有四張 A，並且沒有指定該玩家，因此根據哪個玩家得到四張 A，有四種分配四張 A 的可能性。 因此，該數字是 $4\times {\frac {48!}{(13!)^{3}\times 9!}}\approx 5.667\times 10^{26}$.

$\Box$

(d)

證明： 首先考慮牌堆中的 39 張牌，其中去掉了一種特定型別的牌。有 ${\frac {39!}{(13!)^{3}}}$ 種方法將 39 張牌分成三組，每組 13 張，分別對應東、南、西玩家。由於北玩家得到所有 13 張同類型的牌，並且型別沒有指定，因此有四種類型的可能性。因此，總數為 $4\times {\frac {39!}{(13!)^{3}}}\approx 3.379\times 10^{17}$.

$\Box$

例： （骰子結果序列）一個六面骰子擲九次。證明出現 1、3 和 5 各三次的不同結果序列的數量為 1680。

證明： 將這九次（有序）骰子結果看作分成三組，分別代表出現 1、3 和 5 的結果。每個組包含 3 個結果，因為數字 1、3、5 各出現了 三次。因此，對結果進行分組的方法數量為 ${\frac {9!}{3!3!3!}}=1680$.

對於每種結果分組方式，我們都會得到一個唯一的結果序列。（例如，如果我們將第一次、第二次和第四次結果放入代表出現 1 的組中，第五次、第七次和第九次結果放入代表出現 3 的組中，剩下的結果放入代表出現 5 的組中，那麼我們得到的序列將是： （第一次結果）1、1、5、1、3、5、3、5、3 （第九次結果），按照此順序。）因此，結果成立。

$\Box$

練習。

1 計算出現 2、4 和 6 各三次的不同序列數量。

	840
	1680
	3360
	6720
	361200

2 假設我們擲骰子 12 次。計算每個數字出現兩次的不同序列數量。

	2520
	5040
	113400
	369600
	7484400

例： （行走路徑）考慮以下圖表： $${\begin{array}{c|c|c|c|c}A&&&&B\\\hline &&E&&\\\hline C&&&&D\\\end{array}}$$ 假設我們最初位於 $A$，並且只能每一步向右走一個單元格或向下走一個單元格。證明從 $A$ 到 $D$ 的不同步數序列的數量為 15。

證明： 首先，觀察到我們需要 正好 6 步才能從 $A$ 到 $D$，包括 4 步向右走 ($\rightarrow$) 和 2 步向下走 ($\downarrow$)。（這可以從圖表中觀察出來，並且我們只能向右走一個單元格或向下走一個單元格的假設非常重要）

因此，不同步數序列的數量等效於 4 個 $\rightarrow$ 和 2 個 $\downarrow$ 的不同序列的數量。

那麼可以將其視為一個劃分問題：將 6 個步進位置劃分為 2 組，其中一組代表 $\rightarrow$ （包含 4 個步進位置），另一組代表 $\downarrow$ （包含 2 個步進位置）。

因此，所需的數字是 $$\underbrace {6!} _{\text{steps}}/(\underbrace {2!} _{\downarrow }\underbrace {4!} _{\rightarrow })=15.$$

$\Box$

練習。

1 如果每一步也可以向左走一個格，請再次計算不同序列的數目。

	15
	35
	90
	105
	以上都不對

2 如果我們還需要在從 $A$ 到 $D$ 的行走過程中經過 $E$，請計算不同序列的數目。（提示: 可以將其視為從 $A$ 到 $E$，然後從 $E$ 到 $D$ 的行走）。

	9
	10
	11
	12
	13

3 如果我們不能在行走過程中經過 $C$，請計算不同序列的數目。

	10
	11
	12
	13
	14

4 假設艾米和鮑勃最初分別位於 $A$ 和 $B$。請計算艾米步進的不同序列數量，使得艾米和鮑勃在 $E$ 處相遇，已知艾米每一步只能向右走一個格或向下走一個格，而鮑勃每一步只能向左走一個格或向下走一個格。

	3
	6
	9
	12
	15

下面我們將討論不帶放回的無序選擇，可以將其視為劃分的特例。

將 r 個不可區分的球放入 n 個可區分的單元格中，每個單元格最多容納一個球（不帶放回的無序選擇）

之前我們討論過將 $r$ 個 可區分的 球放入 $n$ 個 可區分的 容量為一的盒子中。現在，我們將考慮 $r$ 個球是 不可區分的 的情況。（可以把球想象成 相同的（比如顏色和大小相同），因此無法區分。）類似地，這種放置等同於無放回的選取（$r$ 個球代表選擇，每個盒子仍然最多隻能放一個球）。然而，在這種情況下，$r$ 個球（選擇）是不可區分的。所以，我們只知道哪些 $r$ 個盒子包含一個球（被選中），但不知道他們 以什麼順序 包含一個球，因為球是不可區分的。因此，對於哪些盒子包含一個球（被選中）的順序在這種情況下並不重要，因為我們無法識別不同選擇順序的差異。因此，我們將選擇過程視為 無序的。這種選擇過程很常見，因為我們通常更關心 什麼 被選中，而不關心 什麼順序 選擇東西。

在這種情況下，我們實際上可以將其視為劃分的一種特殊情況。

• 對於包含一個球的盒子（$r$ 個），他們被放入 “選中” 組（他們被選中放置一個球）。
• 對於包含零個球的盒子（$n-r$ 個），他們被放入 “未選中” 組（他們沒有被選中放置一個球）。

所以，這意味著這種放置等同於將 $n$ 個 可區分的 盒子分成兩組，分別包含 $r$ 個 可區分的 盒子和 $n-r$ 個 可區分的 盒子。有了這樣的考慮，以下結果是顯而易見的

定理。 將 $r$ 個不可區分的球放入 $n$ 個 可區分的 容量為一的盒子的方法數為 ${\binom {n}{r}}={\frac {n!}{r!(n-r)!}}$.

這裡，我們給出了該定理的另一種證明，它利用了之前關於可區分球的結果和除法計數原理。

證明。 從之前關於可區分球的結果可知，有 ${\frac {n!}{(n-r)!}}$ 種方法將 $r$ 個可區分球放入 $n$ 個容量為 1 的可區分單元格。但這裡我們需要的是球不可區分時的方案數。因此，我們考慮除法計數原理：每個球不可區分的放置方案對應 $r!$ 個球可區分的放置方案（透過排列 $r$ 個可區分球獲得）。因此，所需的方案數為 $${\frac {n!}{(n-r)!}}{\bigg /}r!={\frac {n!}{r!(n-r)!}}.$$

$\Box$

備註.

• ${\binom {n}{r}}$ 稱為 二項式係數。它也可以用 $_{n}C_{r}$ 表示。
• ${\binom {n}{r}}$ 讀作 “n 選 r”。

例子。 考慮一個有 10 人的小組。

(a) 從 10 人中選出 4 人組成委員會，有多少種方法？

(b) 假設這 10 人中有 6 名男性和 4 名女性，委員會需包含 2 名男性和 2 名女性。現在有多少種方法？

(c) 除了委員會需包含 2 名男性和 2 名女性的要求外，委員會中還有 4 個職位：1 名領導人和 3 名成員。現在有多少種方法？

解決方案.

(a) 委員會的選拔順序並不重要。因此，我們可以將 4 個委員會職位視為不可區分的球，放入 10 個可區分的單元格（10 人）中。因此，方案數為 ${\binom {10}{4}}=210$。

(b) 在這種情況下，要組成委員會，我們需要兩步

1. 從 6 名男性中選出 2 人組成委員會 (${\binom {6}{2}}$ 種方法)
2. 從 4 名女性中選出 2 人組成委員會 (${\binom {4}{2}}$ 種方法)

根據乘法計數原理，方案數為 ${\binom {6}{2}}\times {\binom {4}{2}}=90$。

(c) 我們考慮兩種不同的情況

情況 1：領導人是男性。那麼，3 名成員應該是一名男性和兩名女性。在這種情況下，要組成委員會，我們需要三步

1. 從 6 名男性中選出 1 人擔任領導人（6 種方法）
2. 從 5 名男性中選出 1 人擔任成員（5 種方法）（領導人不能同時擔任成員）
3. 從 4 名女性中選出 2 人擔任成員 (${\binom {4}{2}}$ 種方法)

根據乘法計數原理，有 $6\times 5\times {\binom {4}{2}}=180$ 種方法。

情況 2：領導人是女性。那麼，3 名成員應該是一名女性和兩名男性。我們也需要三步來組成委員會

1. 從 4 個女性中選 1 個作為領導（4 種方法）
2. 從 3 個女性中選 1 個作為成員（3 種方法）
3. 從 6 個男性中選 2 個作為成員（${\binom {6}{2}}$ 種方法）

然後，根據乘法計數原理，共有 $4\times 3\times {\binom {6}{2}}=180$ 種方法。

我們可以觀察到，情況 1 和情況 2 中沒有共同的方法，因為領導者要麼是男性，要麼是女性。因此，所需方法數為 $180+180=360$。

練習. 繼續從 (c) 開始。假設 Amy 是 4 個女性中的一個，Bob 是 6 個男性中的一個。進一步假設，如果領導人是男性，則必須選擇 Amy 作為成員，如果領導人是女性，則必須選擇 Bob 作為成員。證明方法數為 150。

解決方案

我們考慮兩種不同的情況

情況 1：領導人是男性。那麼，3 個成員應該是 1 個男性和 2 個女性。在這種情況下，為了組建委員會，我們需要四個步驟

1. 從 6 名男性中選出 1 人擔任領導人（6 種方法）
2. 從 5 個男性中選 1 個作為成員（5 種方法）
3. 選擇 Amy 作為成員（1 種方法）
4. 從 3 個女性中選 1 個作為成員（3 種方法）

根據乘法計數原理，共有 $6\times 5\times 1\times 3=90$ 種方法。

情況 2：領導人是女性。那麼，3 個成員應該是 1 個女性和 2 個男性。我們需要四個步驟來組建委員會

1. 從 4 個女性中選 1 個作為領導（4 種方法）
2. 從 3 個女性中選 1 個作為成員（3 種方法）
3. 選擇 Bob 作為成員（1 種方法）
4. 從 5 個男性中選 1 個作為成員（5 種方法）

然後，根據乘法計數原理，共有 $4\times 3\times 1\times 5=60$ 種方法。

我們可以觀察到，情況 1 和情況 2 中沒有共同的方法，因為領導者要麼是男性，要麼是女性。因此，所需方法數為 $90+60=150$。

示例。

虛線橢圓提醒我們，這些是集合，其中順序不重要。

考慮集合 $\{1,2,3\}$。從集合中的 3 個元素中選擇（a）零個元素；（b）一個元素；（c）兩個元素；（d）三個元素，共有多少種方法？因此，分別列出具有 0、1、2、3 個元素的子集，並證明共有 $2^{3}=8$ 個子集。

解決方案。首先，選擇元素是無序的，因為選擇元素的順序不會影響選擇的最終結果。

(a) ${\binom {3}{0}}=1$。

(b) ${\binom {3}{1}}=3$。

(c) ${\binom {3}{2}}=3$。

(d) ${\binom {3}{3}}=1$。

子集列表

• ${\binom {3}{0}}=1$ 集包含 0 個元素。它是空集：$\varnothing$。
• ${\binom {3}{1}}=3$ 個集合包含 1 個元素。它們是 $\{1\}$，$\{2\}$ 和 $\{3\}$。
• ${\binom {3}{2}}=3$ 個集合包含 2 個元素。它們是 $\{2,3\}$，$\{1,3\}$ 和 $\{1,2\}$。
• ${\binom {3}{3}}=1$ 個集合包含 3 個元素。它是集合本身：$\{1,2,3\}$。

總共有 $1+3+3=1=8$ 個子集。

示例。 (比賽) 有一場比賽有 16 名候選人，決賽只有 3 個名額。進入決賽的方法數是 ${\binom {16}{3}}={\frac {16\times 15\times 14}{3\times 2\times 1}}=560.$

練習。

1 艾米、鮑勃和克里斯是 $16$ 名候選人中的三位。計算將他們選入決賽的方法數。

	1
	3
	6
	32
	96

2 從上一題繼續。計算選擇除艾米、鮑勃和克里斯以外的候選人進入決賽的方法數。

	220
	286
	554
	557
	559

示例。 我們有 10 個相同的燈泡，其中 3 個是壞的，另外 7 個燈泡正常工作。我們要把這 10 個燈泡排成一排來照明。為了確保燈泡均勻排列，要求兩個壞燈泡不能相鄰。有多少種方法可以排列這 10 個燈泡？

解決方案。為了確保沒有兩個壞燈泡相鄰，請考慮以下圖表

        * * * * * * *
       ^ ^ ^ ^ ^ ^ ^ ^
* : normally operating bulb
^ : place for at most one defective light bulb

對於每個壞燈泡，我們需要將其放置在正常工作燈泡之間的某個間隙中。此外，為了確保沒有兩個壞燈泡相鄰，每個間隙只能包含 最多一個 壞燈泡。

由於壞燈泡是相同的，因此無法區分（在壞燈泡之間）。所以，情況與將 3 個無法區分的球放入 8 個可區分的單元格（由 "^" 表示的 8 個位置）相同。因此，數量是 $${\binom {8}{3}}=56.$$

例：（超級百萬）考慮超級百萬彩票遊戲。在該遊戲中，玩家需要從遊戲板上的上半部分白色區域（對應白球）的1到56中選擇五個號碼，並在遊戲板上的下半部分黃色區域（對應金色巨型球）的1到46中選擇一個巨型球號碼。之後，會抽出五個1到56的白色球和一個1到46的金色巨型球，這些球的號碼將決定彩票的結果。特別地，如果抽出的五個白色球的號碼和抽出的金色巨型球的號碼與玩家選擇的號碼完全匹配，則玩家贏得頭獎。

彩票有多少種不同的結果？

解。我們將結果的決策過程視為一個兩步過程

1. （五個白色球）將五個抽取視為五個不可區分的球（每個抽取的具體數字並不重要。我們只關心五個抽取的數字是什麼），並將數字1到56視為56個可區分的單元格（容量為一，因為一個白色球不能被抽取多次）。那麼，抽取五個白色球的方式數量是${\binom {56}{5}}=3819816$.
2. （一個金色巨型球）從46個金色巨型球中抽取一個有46種方法。

因此，結果的數量是$3819816\times 46=175711536$.

例：（組合證明恆等式）令$n$和$r$是非負整數，使得$n\geq r$。證明$${\binom {n}{r}}={\binom {n-1}{r-1}}+{\binom {n-1}{r}}$$

（a）組合地；

（b）解析地。

組合地證明某件事，是指我們考慮一個特定的情況，並使用兩種方法計算該情況的方式/結果/等等的數量，從而得到兩個計算相同數字的表示式。然後，我們可以將這兩個表示式相等。這種證明也稱為雙重計數證明，因為我們對同一個數字進行了兩次計數。

(a)

證明。考慮將$r$個不可區分的球放入$n$個可區分的單元格（容量為一）的情況。根據前面的定理，方式數量是${\binom {n}{r}}$.

因此，我們有了第一個計數方式數量的方法，對應於方程的左側。現在，我們使用另一種方法來計數方式數量。首先，我們關注單元格1，並將情況分成兩種情況

情況1：單元格1包含一個球。那麼，有$r-1$個球剩餘，以及$n-1$個單元格剩餘。因此，將剩餘的$r-1$個球放入剩餘的$n-1$個單元格的方式數量是${\binom {n-1}{r-1}}$。由於單元格包含一個球只有一個方法，所以根據乘法計數原理，方式數量是${\binom {n-1}{r-1}}$.

情況 2：單元格 1 包含零個球。那麼，還剩 $r$ 個球，以及 $n-1$ 個單元格。因此，方法的數量類似地為 ${\binom {n-1}{r}}$。

由於單元格 1 或者包含一個球，或者包含零個球，所以在情況 1 和 2 中沒有共同的方法。因此，放置的方法數量為 $${\binom {n-1}{r-1}}+{\binom {n-1}{r}},$$ 與 RHS 中的表示式相對應。

$\Box$

(b)

證明。 考慮 RHS。我們有 $${\begin{aligned}{\binom {n-1}{r-1}}+{\binom {n-1}{r}}&={\frac {(n-1)!}{(r-1)!(n-1-r+1)!}}+{\frac {(n-1)!}{r!(n-1-r)!}}\\&={\frac {(n-1)!}{(r-1)!(n-r)!}}+{\frac {(n-1)!}{r!(n-r-1)!}}\\&={\frac {(n-1)!}{{\color {blue}(r-1)!}(n-r){\color {blue}(n-r-1)!}}}+{\frac {(n-1)!}{r{\color {blue}(r-1)!(n-r-1)!}}}&{\big (}(n-r)!=(n-r)(n-r-1)!{\text{ and }}r!=r(r-1)!{\big )}\\&={\frac {{\color {red}r}(n-1)!+(n{\color {red}-r})(n-1)!}{r(n-r){\color {blue}(r-1)!(n-r-1)!}}}\\&={\frac {n(n-1)!}{\underbrace {r{\color {blue}(r-1)!}} _{r!}\underbrace {(n-r){\color {blue}(n-r-1)!}} _{n-r!}}}\\&={\frac {n!}{r!(n-r)!}}\\&={\binom {n}{r}},\end{aligned}}$$ 建立了所需的恆等式。

$\Box$

備註.

• 另一種組合證明是 雙射證明，但我們這裡不再討論它，因為它比較高階。

例如。 令 $n$ 和 $r$ 為非負整數，使得 $n\geq r$。證明 $${\binom {n}{r}}={\binom {n}{n-r}}$$ 的組合意義。

證明。 考慮有 $n$ 個人，從中選出 $r$ 個人參加委員會。這種選擇是無序的（順序不影響結果），並且無放回（我們不能選擇一個人多次參加委員會）。根據前面的定理，這樣做的方法數為 ${\binom {n}{r}}$。

另一方面，我們可以將這種情況視為從 $n$ 人中選出 $n-r$ 個人 不 參加委員會。同樣，這種選擇是無序的，並且無放回（一個人不能被選擇多次不參加）。因此，這樣做的方法數為 ${\binom {n}{n-r}}$。

由於這兩種解釋是在同一情況下進行的，因此這兩種方法數相同。因此，我們得到了所需的恆等式。

$\Box$

練習。 令 $m,n$ 和 $r$ 為非負整數，使得 $m\geq r$ 且 $n\geq r$。證明 範德蒙德恆等式，即 $${\binom {m+n}{r}}=\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}$$ 的組合意義。

證明

證明。 考慮將 $r$ 個不可區分的球放入 $m+n$ 個可區分的容量為 1 的盒子的情況。根據前面的定理，這樣做的方法數為 ${\binom {m+n}{r}}$。

現在，讓我們考慮另一種計算方法。我們關注前 $m$ 個單元格，在 $m+n$ 個單元格中。我們根據放入前 $m$ 個單元格的球的數量，將情況分為 $r$ 種情況。

情況 0： 0 個球被放入前 $m$ 個單元格。我們將此放置過程視為兩步操作

1. 將 0 個球放入前 $m$ 個單元格 (${\binom {m}{\color {blue}0}}$ 種方式)
2. 將 $r-{\color {blue}0}$ 個球放入剩下的 $n$ 個單元格 (${\binom {n}{r-{\color {blue}0}}}$ 種方式)

因此，這種情況下的方法數量為 ${\binom {m}{\color {blue}0}}\times {\binom {n}{r-{\color {blue}0}}}$.

情況 1： 1 個球被放入前 $m$ 個單元格。我們將此放置過程視為兩步操作

1. 將 1 個球放入前 $m$ 個單元格 (${\binom {m}{\color {blue}1}}$ 種方式)
2. 將 $r-{\color {blue}1}$ 個球放入剩下的 $n$ 個單元格 (${\binom {n}{r-{\color {blue}1}}}$ 種方式)

因此，這種情況下的方法數為 ${\binom {m}{\color {blue}1}}\times {\binom {n}{r-{\color {blue}1}}}$.

...

情況 $k$：${\color {blue}k}$ 個球被放置到 $m$ 個單元格中。我們將放置視為一個兩步過程

1. 將 ${\color {blue}k}$ 個球放置到 $m$ 個單元格中（${\binom {m}{\color {blue}k}}$ 種方法）
2. 將 $r-{\color {blue}k}$ 個球放置到其他 $n$ 個單元格中（${\binom {n}{r-{\color {blue}k}}}$ 種方法）

因此，這種情況下的方法數為 ${\binom {m}{\color {blue}k}}\times {\binom {n}{r-{\color {blue}k}}}$.

...

情況 $r$：${\color {blue}r}$ 個球被放置到 $m$ 個單元格中。我們將放置視為一個兩步過程

1. 將 ${\color {blue}r}$ 個球放入 $m$ 個盒子 (${\binom {m}{\color {blue}r}}$ 種方法)。
2. 將剩下的 $r-{\color {blue}r}$ 個球放入剩下的 $n$ 個盒子 (${\binom {n}{r-{\color {blue}r}}}$ 種方法)。

因此，在這種情況下，方法數為 ${\binom {m}{\color {blue}r}}\times {\binom {n}{r-{\color {blue}r}}}$。

我們可以觀察到，在任意兩組情況下，沒有共同的方法。因此，方法數為 $$\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}.$$

$\Box$

將 r 個可區分的球放入 n 個可區分的盒子，盒子容量無限制（帶替換的順序選擇）

到目前為止，我們只考慮了無放回的選擇，或者等價地，容量為一的單元格。從本節開始，我們將討論有放回的選擇，或者等價地，容量無限的單元格（相同的東西可以被選擇無限次）。在本節中，讓我們考慮一個更簡單的例子：將$r$個可區分的球放入$n$個可區分的單元格，每個單元格的容量無限。這等價於從$n$個可區分的物體中以有序的方式選擇$r$個物體，並有放回，透過將球 1,2,...,$r$ 視為選擇 1,2,...,$r$，單元格 1,2,...,$n$ 視為物體 1,2,...,$n$。特別地，由於每個物體都可以被選擇無限次，因此每個單元格的容量都是無限的。但是計算這種放置方法的數量實際上非常簡單，因為我們只需使用乘法計數原理。

命題。 將$r$個可區分的球放入$n$個可區分的單元格，每個單元格的容量無限的方法數是$n^{r}$。

證明。 我們將放置視為一個 $r$ 步過程

• 步驟 1：選擇$n$個單元格中的一個來放置球 1。（$n$ 種方法）
• 步驟 2：選擇$n$個單元格中的一個來放置球 2。（$n$ 種方法）
• ...
• 步驟 $r$：選擇$n$個單元格中的一個來放置球 $r$。（$n$ 種方法）

總而言之，根據乘法計數原理，方法數為 $$\underbrace {n\times n\times \dotsb \times n} _{r{\text{ times}}}=n^{r}.$$

$\Box$

備註.

• 實際上，這種情況只是乘法計數原理應用的一個特例，其中每個$r$任務的方案數相同（$n$種）。

示例. 有多少個6位數，每個數字都是奇數？

解答. 由於每個數字都是奇數，所以每位數字有五個選擇：1、3、5、7、9。因此，這樣的數字有$5^{6}=15625$個。

示例. 擲兩個不同的骰子，有多少種可能的結果？

解答. 每個骰子有六種結果。因此，可能結果的數量是$6^{2}=36$.

練習. 假設我們從一副有52張牌的撲克牌中抽取5張牌有放回，每張牌都記錄下來，記錄保持順序。有多少種可能的抽牌記錄？

(a) 五張A？

(b) 五張相同花色的A？

(c) 五張相同的牌？

(注意：計數的方法不一定是本節中提到的方法。)

解決方案

(a) 可能性數量為$4^{5}=1024$。 (每次抽取，都有四種A的選擇。)

(b) 可能性數量為$4\times 1\times 1\times 1\times 1=4$。 (第一次抽取，有四種A的選擇。 對於接下來的四次抽取，抽取的A必須與第一次抽取的A相同花色，因此這四次抽取中只有一個選擇。)

(c) 可能性數量為$52\times 1\times 1\times 1\times 1=52$。 (第一次抽取，有52種選擇，對於剩下的每次抽取，只有一個選擇，就是第一次抽取的牌。)

示例. （設定密碼） 假設我們設定一個包含6個字元的密碼，遵循以下規則

(R1) 允許使用數字

(R2) 允許使用字母，區分大小寫

(R3) 特殊字元（即所有非數字和字母的字元）不允許

證明設定此密碼的方案數為 56800235584。

證明. 密碼的6個位置，每個位置都有$\underbrace {2} _{\text{cases}}\times \underbrace {26} _{\text{alphabets}}+\underbrace {10} _{\text{numbers}}=62$ 種字元選擇。 此外，字元可以在多個位置重複出現，並且順序很重要。 因此，這是帶放回的區分物件的排序選擇。 因此，所需的數量為 $\underbrace {62} _{\text{1st position}}\times \underbrace {62} _{\text{2nd position}}\times \dotsb \times \underbrace {62} _{\text{6th position}}=62^{6}=56800235584.$

$\Box$

練習。

1 假設一臺機器每秒可以進行$3.5\times 10^{11}$次密碼猜測。 使用公式$${\text{the maximum time needed}}\approx {\frac {\text{number of ways to set the password}}{\text{guessing speed}}}.$$ 近似計算機器正確猜測六字元密碼所需的最長時間（精確到小數點後兩位）。

	0.00 秒
	0.15 秒
	0.16 秒
	6.16 秒
	369.72 秒

2 假設密碼的安全性取決於機器使用上一個問題中相同的公式在最短時間內猜出密碼所需的時長是否大於或等於 100 年（即 $100\times 365.25\times 24\times 3600=3155760000$ 秒）。為了使密碼達到安全性，密碼所需的最小字元數（遵循相同的規則）是

	11
	12
	13
	14
	15

示例。 考慮一個抽屜，裡面有一些紅襪子和藍襪子。假設你從抽屜裡抽出一隻襪子五次，每次抽完後放回。有多少種可能的襪子抽取 序列？

解答。 每次抽取都有兩種可能性：（i）抽取一隻紅襪子；（ii）抽取一隻藍襪子。因此，可能的序列數量是 $2^{5}=32$（因為我們考慮的是序列，順序很重要）。

示例。 考慮一個機率論課程，有 23 人。有多少種可能的 23 人的生日 序列？（假設一年有 365 天。）

解答。 每個人都有 365 種可能的生日。因此，可能的序列數量是 $365^{23}\approx 8.565\times 10^{58}$.

練習。 所有學生生日都不同的序列有多少種？因此，證明在所有可能序列（如上例所示）中，至少兩個人 有相同生日的序列比例約為 50.73%。 (提示：在班級中，要麼 所有人的生日都不相同，要麼 至少兩個人有相同的生日。）

解決方案

我們將這種情況視為一個 23 步過程

• 第 1 個人有 365 種可能的生日。
• 第 2 個人有 364 種可能的生日（與第 1 個人不同）。
• 第 3 個人有 363 種可能的生日（與前 2 個人不同）。
• ...
• 第 23 個人有 343 種可能的生日（與前 22 個人不同）。

因此，序列數量為 $365\times 364\times 363\times \dotsb \times 343={\frac {365!}{342!}}\approx 4.22\times 10^{58}$.

這意味著 至少兩個人 有相同生日的序列數量為 $8.565\times 10^{58}-4.22\times 10^{58}\approx 4.345\times 10^{58}$. 因此，該比例為 ${\frac {4.345\times 10^{58}}{8.565\times 10^{58}}}\approx 0.5073=50.73\%$.

將 r 個不可區分的球放入 n 個可區分的盒子中，盒子容量無限制（無序選擇，可重複）。

在上節中，球是可以區分的。現在，我們將討論一個更復雜的情況，球是不可區分的。

這種情況的難點在於，我們不能像之前關於將 $r$ 個不可區分的球放到 $n$ 個可區分的容量為 1 的盒子（“任務”）中的情況一樣，應用除法計數原理來計算方法的數量。在之前的情況下，我們知道任務中的每一種方法都對應於程式中的 $r!$ 種方法（我們將 $r$ 個可區分的球放入盒子），透過考慮排列被 一個球 佔據的 $r$ 個盒子的方法的數量。

但是，在這種情況下，每個盒子可以包含多個球。這意味著被佔據的盒子數量可以在 1（所有 $r$ 個球都在一個盒子裡）到 $r$（每個盒子一個球）之間變化，具體取決於我們在任務中如何將球放入盒子。因此，任務中的不同方法對應於程式中不同數量的方法。因此，我們不能應用除法計數原理。

由於這個原因，在這種情況下，開發方法數量的方法與之前討論的方法有很大不同，我們需要一些技巧。

定理。 將 $r$ 個不可區分的球放到 $n$ 個可區分的容量無限的盒子中的方法數量為 $_{n}H_{r}={\binom {n-1+r}{r}}$.

證明。 為了證明這一點，我們引入星號和槓桿符號，來表示球放入盒子的方式。特別是，用 $r$ 個（相同的）星號來表示 $r$ 個不可區分的球，用 $n$ 個（有序的）空格來表示 $n$ 個可區分的盒子。例如，

       *********     9 indistinguishable balls

           |
           |          placement
           v

  **|*| |***|*| |**   
   1 2 3  4  5 6  7  Cell

用來表示

• 盒子 1 中有 2 個球
• 盒子 2 中有 1 個球
• 盒子 3 中有 0 個球
• 盒子 4 中有 3 個球
• 盒子 5 中有 1 個球
• 盒子 6 中有 0 個球
• 盒子 7 中有 2 個球。

此外，在這種情況下，我們正在將 $r=9$ 個不可區分的球放入 $n=7$ 個盒子。

引入這種符號後，我們將計算排列這些星號和槓桿的方法數量，因為 每一種 星號和槓桿的排列都對應於將 $r$ 個不可區分的球放入 $n$ 個可區分的盒子中的 一種 方法。因此，排列的方法數量正好是將球放入盒子中的方法數量。

如果有 $n-1$ 根棍子和 $r$ 顆星星，它們可以任意排列，以表示不同的位置。總共有 $n-1+r$ 個（有序且可區分的）位置來放置星星或棍子。這裡，我們關注星星的放置。我們可以將此解釋為從這 $n-1+r$ 個位置中無序地選擇 $r$ 個位置來放置星星，不放回（當一顆星星被放置在一個位置時，我們不能在同一個位置放置另一個星星）。因此，放置方法的數量為 ${\binom {n-1+r}{r}}$。一旦我們放置了 $r$ 顆星星，只有一種方法可以放置棍子：將它們放置在剩餘的位置。

因此，排列 $n-1$ 根棍子和 $r$ 顆星星的方法有 ${\binom {n-1+r}{r}}$ 種，因此結果隨之而來。

$\Box$

備註.

• $r$ 可以大於 $n$。

示例. 將 10 個相同的球分配到 4 個不同的箱子（容量無限）有多少種方法？

解答. 我們可以將 10 個相同的球視為 10 個不可區分的球，將 4 個不同的箱子視為 4 個可區分的單元格（容量無限）。那麼，方法數為 $_{4}H_{10}={\binom {4-1+10}{10}}={\binom {13}{10}}=286$。

示例。

擲兩個相同的骰子有多少種結果？

解答. 我們可以將兩個相同的骰子視為 2 個不可區分的球，將擲骰子的 6 種結果視為 6 個可區分的單元格（容量無限，因為一種結果可以在兩個骰子上出現多次）。那麼，結果數為 $_{6}H_{2}={\binom {6-1+2}{2}}={\binom {7}{2}}=21$。

練習. 擲 三個 相同的骰子有多少種結果？

解決方案

這次，我們有 3 個不可區分的球，還有 6 個可區分的單元格。因此，結果數為 $_{6}H_{3}={\binom {6-1+3}{3}}={\binom {8}{3}}=56$。

示例. 有 8 種不同的食物或飲料，即漢堡、雞蛋、薯條、蛋糕、蘋果派、蘋果汁、橙汁和可樂。除非另有說明，否則套餐可以包含相同專案多次。

(a) 有多少種不同的 4 專案套餐必須包含不同的專案？

(b) 有多少種不同的 4 件組合？

(c) 有多少種不同的 3 種食物和 1 種飲料的組合？

解決方案.

我們可以將組合中的 4 種選擇視為 4 個不可區分的球（因為我們關心的是整體的 4 種選擇是什麼，而不關心這 4 種選擇中的 每一種具體是什麼，所以應該將其視為不可區分的），並將 8 種食物/飲料視為 8 個可區分的單元格。

(a) 由於組合必須包含不同的專案，這意味著我們不能在一個單元格中放置多個食物選擇。換句話說，單元格的容量為一。因此，組合的數量由 ${\binom {8}{4}}=70$ 給出。

(b) 這一次，由於組合可能包含多次相同的專案，這意味著單元格的容量變得無限。因此，組合的數量為 ${\binom {8-1+4}{4}}=330$.

(c) 由於組合需要包含 3 種食物和 1 種飲料，我們需要分兩個步驟

1. 我們需要將 4 個不可區分的球中的一個放入 3 個可區分的單元格中的一個，代表 3 種飲料（蘋果汁、橙汁和可樂）。（3 種方法）
2. 然後，我們將剩下的 3 個不可區分的球放入另外 5 個可區分的單元格中（容量無限），代表 5 種食物。（$_{5}H_{3}$ 種方法）

因此，組合的數量為 $3\times {}_{5}H_{3}=3\times {\binom {5-1+3}{3}}=3\times {\binom {7}{3}}=105$.

練習。

(a) 有多少種不同的 4 種食物組合？

(b) 艾米很喜歡吃漢堡，所以她每次選擇 4 件組合的時候都會選擇兩個漢堡。計算艾米點餐 4 件組合的不同方法的數量。

解決方案

(a) 由於組合需要包含 4 種食物，我們正在將 4 個不可區分的球放入 5 個可區分的單元格中，代表 5 種食物。因此，組合的數量為 $_{5}H_{4}={\binom {5-1+4}{4}}=70$

(b) 由於有 2 個不可區分的球必須放入代表漢堡的單元格中（只有一種方法），所以還有 2 個不可區分的球剩下，要放入其他 7 個單元格中（它們不能放入漢堡的單元格中，因為艾米選擇的是 正好 兩個漢堡）。因此，組合的數量為 $_{7}H_{2}={\binom {7-1+2}{2}}=28$.

示例。 （選 3 個）考慮一個名為 選 3 個 的彩票遊戲。在這個遊戲中，玩家從 0 到 9 中選擇三個數字，並且每天多次宣佈 3 個 中獎號碼。玩家在選擇三個數字時，有兩種方法可以使用這三個數字進行遊戲

1. 精確順序：如果玩家選擇的三個數字與他選擇後最近一次宣佈的中獎號碼 完全 相匹配（在數字和順序上），則玩家獲勝。（更高的獎金）
2. 任何順序：如果玩家選擇的三個數字與他選擇後最近一次宣佈的中獎號碼的數字相匹配（但順序不一定相同），則玩家獲勝。（更低的獎金）

因此，選擇不同遊戲方式的玩家對中獎號碼的看法不同

• 對於選擇 精確順序 的玩家，他們關心中獎號碼的順序和數字。
• 對於選擇 任何順序 的玩家，他們只關心中獎號碼的數字。

因此，不同的中獎號碼的數量可能不同，因為“不同”的含義取決於遊戲方式。（這裡，“不同”指的是不同中獎號碼所代表的結果不同。例如，1,2,3 和 1,3,2 從精確順序的角度來看是不同的，但從任何順序的角度來看是相同的（因為中獎號碼中的三個數字是相同的，因此這兩個中獎號碼的含義相同：如果玩家分別選擇了數字 1,2,3 一次，那麼他就會獲勝）。在本例中，我們將從這兩個角度計算不同的中獎號碼的數量。

(a) 從精確順序的角度來看，有多少種不同的中獎號碼？

(b) 從任何順序的角度來看，有多少種不同的中獎號碼？

解決方案.

(a) 從精確順序的角度來看，中獎號碼的順序很重要。然後，我們可以將中獎號碼的形成視為一個三步過程

1. 從十個數字 0-9 中選擇一個作為第一個中獎號碼。（10 種方法）
2. 從十個數字 0-9 中選擇一個作為第二個中獎號碼。（10 種方法）
3. 從十個數字 0-9 中選擇一個作為第三個中獎號碼。（10 種方法）

因此，有 $10^{3}=1000$ 種不同的中獎號碼。

(b) 從任意順序的角度來看，中獎號碼的順序無關緊要。我們只關心哪三個數字出現在中獎號碼中。因此，我們可以將中獎號碼的三個位置視為三個不可區分的球，並將數字 0-9 視為十個可區分的單元格（容量無限，因為 0-9 之間的數字可以被選中超過一次作為 3 箇中獎號碼）。然後，不同中獎號碼的數量為 $$_{10}H_{3}={\binom {10-1+3}{3}}=220.$$

例：（方程的整數解數）考慮方程 $$x_{1}+x_{2}+\dotsb +x_{7}=10.$$ (a) 當 $x_{1},\dotsc ,x_{7}$ 為非負整數時，方程有多少個解？

(b) 當 $x_{1},\dotsc ,x_{7}$ 為正整數時，方程有多少個解？

(c) 證明當 $x_{1},\dotsc ,x_{7}$ 為非負整數時，不等式 $x_{1}+x_{2}+\dotsb +x_{7}<10$ 有 11440 個解。

解決方案.

(a) 我們可以將數字 10 視為 10 個不可區分的球（每個球代表“1”），並將 $x_{1},x_{2},\dotsc ,x_{7}$ 視為 7 個可區分的單元格，容量無限（每個單元格可以包含 0 個或多個球，對應於 $x_{1},x_{2},\dotsc ,x_{7}$ 的非負性）。（例如，如果單元格 $x_{3}$ 包含 2 個球，則意味著 $x_{3}=2$。）因此，解的數量是將球放入單元格的方式的數量，即 $$_{7}H_{10}={\binom {7-1+10}{10}}=8008.$$

(b) 令 $x_{1}'=x_{1}-1,\dotsc ,x_{7}'=x_{7}-1$. 那麼，$x_{1}',\dotsc ,x_{7}'$ 都是非負整數。那麼，我們有 $$x_{1}+x_{2}+\dotsb +x_{7}=10\iff x_{1}'+x_{2}'+\dotsb +x_{7}'={\color {darkgreen}3}.$$ 由此可知解的個數為 $_{7}H_{\color {darkgreen}3}={\binom {7-1+3}{3}}=84$.

(c) 可以透過考慮所有 10 種可能的情況來計算解的個數：$x_{1}+\dotsb +x_{7}=0,1,\dotsc ,{\text{ or }}9$. 但這裡我們提供了一種替代的、更方便的方法，它使用了一個巧妙的技巧

證明。 為了使不等式變成等式，我們在左側新增一個額外的正整數項 $x_{8}$，這導致了一個等式：$$x_{1}+x_{2}+\dotsb +x_{8}=10$$ 其中 $x_{8}$ 是一個 正整數。這個等式與不等式等價，因為 $$x_{1}+x_{2}+\dotsb +x_{7}<10\iff x_{1}+x_{2}+\dotsb +x_{7}=10-\underbrace {x_{8}} _{\text{+ve integer}}<10\iff x_{1}+x_{2}+\dotsb +x_{8}=10.$$ 所以，為了得到這個等式的解的個數，我們將情況考慮如下

• 10 個不可區分的球
• 8 個可區分的單元格代表 $x_{1},x_{2},\dotsc ,x_{8}$，其中每個單元格 $x_{1},\dotsc ,x_{7}$ 包含零個或多個球，而單元格 $x_{8}$ 包含一個或多個球。

由於單元格 $x_{8}$ 必須包含一個或多個球，因此我們必須先將 10 個不可區分的球中的一個放入此單元格（1 種方式）。因此，還有 9 個剩餘的不可區分的球。同樣地，我們可以暫時忽略單元格 $x_{8}$ 中的球。然後，將 9 個球放入 8 個單元格的方式數量為 $_{8}H_{9}$。之後，我們可以考慮回到單元格 $x_{8}$ 中的球，以確定相應的解決方案。

因此，解的數量為 $_{8}H_{9}={\binom {8-1+9}{9}}=11440.$

$\Box$

練習。 一位投資者正在積極跟蹤 7 只不同的股票，他想以某種方式在這 7 只股票上投資 100,000 美元。假設每隻股票的每股價格為 10,000 美元。使用上述示例中的適當結果，確定

(a) 投資 7 只股票的方式數量。

(b) 投資 7 只股票並節省部分資金（非零）的方式數量。

解決方案

我們可以將 $x_{1},\dotsc ,x_{7}$ 視為分別為股票 1、...、7 購買的股票數量。

(a) 8008。 （每隻股票的股票數量為非負整數。由於總投資額為 100,000 美元，因此購買的股票總數為 10。）

(b) 11440。 （總投資額小於 100,000 美元，因此購買的股票總數小於 10。）

Example. Consider the multinomial theorem which states that $$(x_{1}+x_{2}+\dotsb +x_{r})^{n}=\sum _{(n_{1},n_{2},\dotsc ,n_{r}):n_{1}+n_{2}+\dotsb +n_{r}=n}^{}{\binom {n}{n_{1},n_{2},\dotsc ,n_{r}}}x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{r}^{n_{r}}$$ for every positive integer $k$ and nonnegative integer $n$. Also, $n_{1},\dotsc ,n_{r}$ are nonnegative. In particular, the summation notation means that the sum is taken over all nonnegative integer vectors (i.e., lists of numbers) $(n_{1},n_{2},\dotsc ,n_{r})$ such that $n_{1}+n_{2}\dotsc +n_{r}=n$. For example, $$(x_{1}+x_{2}+x_{3})^{2}={\binom {2}{2,0,0}}x_{1}^{2}x_{2}^{0}x_{3}^{0}+{\binom {2}{0,2,0}}x_{1}^{0}x_{2}^{2}x_{3}^{0}+{\binom {2}{0,0,2}}x_{1}^{0}x_{2}^{0}x_{3}^{2}+{\binom {2}{1,1,0}}x_{1}^{1}x_{2}^{1}x_{3}^{0}+{\binom {2}{1,0,1}}x_{1}^{1}x_{2}^{0}x_{3}^{1}+{\binom {2}{0,1,1}}x_{1}^{0}x_{2}^{1}x_{3}^{1}=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+2x_{1}x_{2}+2x_{1}x_{3}+2x_{2}x_{3}.$$ Show that there are $_{n}H_{r}$ terms in the expansion by the multinomial theorem.

證明。 注意到展開式中的每一項都對應於一個非負整數向量 $(n_{1},n_{2},\dotsc ,n_{r})$。因此，展開式中項的數量正好是非負整數向量 $(n_{1},n_{2}\dotsc ,n_{r})$ 的數量，滿足條件 $n_{1}+n_{2}+\dotsb +n_{r}=n$，即方程 $n_{1}+n_{2}+\dotsb +n_{r}=n$ 的解的數量，其中 $n_{1},n_{2},\dotsc ,n_{r}$ 是非負整數。

為了得到這個數字，我們將情況視為將 $n$ 個不可區分的球放入 $r$ 個可區分的單元格，這些單元格具有無限容量，分別代表 $n_{1},n_{2},\dotsc ,n_{r}$。根據之前的結果，該數字為 $_{n}H_{r}$。

$\Box$

示例。 四個漁夫一起去釣魚。假設他們今天釣到 20 條相同的魚，需要將這些魚分給彼此。有多少種分配方式呢？

解決方案。我們將 20 條魚視為 20 個不可區分的球，將 4 個漁夫視為 4 個可區分的單元格。因此，方法數為 $$_{4}H_{20}={\binom {4-1+20}{20}}=1771.$$

示例。 十個相同的機器人乘坐電梯，電梯從 1/F 到 6/F 一層一層地移動。假設他們必須在其中一層樓的左側下電梯。

(a) 有多少種不同的下電梯方式？

(b) 假設將十個相同的機器人替換為十個不同的人。有多少種不同的下電梯方式？

解決方案.

(a) 我們將十個相同的機器人視為 10 個不可區分的球，將六層樓視為六個可區分的單元格。然後，數量為 $_{6}H_{10}=3003$.

(b) 我們將 10 個人下電梯的過程視為一個 10 步的過程

• 第 1 步：第一個人可以在六層樓中任意一層下電梯。(6 種方法)
• 第 2 步：第二個人可以在六層樓中任意一層下電梯。(6 種方法)
• ...
• 第 10 步：第十個人可以在六層樓中任意一層下電梯。(6 種方法)

因此，數量為 $6^{10}=60466176$.

練習。 一家公司有 20 名員工，他們將被分成三個團隊：A 團隊、B 團隊、C 團隊。這 20 名員工中有 3 人將被選中分別擔任 A 團隊、B 團隊、C 團隊的隊長。除此之外，對每個團隊的人數沒有要求。

(a) 如果這 20 名員工是相同的機器人，請證明有 171 種劃分方法。

(b) 如果這 20 名員工是不同的人，請證明有 883318714920 種劃分方法。

證明

(a)

證明。 我們將劃分過程視為兩步過程

1. 分別從 120 個相同的機器人中選擇 A 團隊、B 團隊、C 團隊的三個隊長（一種方法）。
2. 剩下 17 個員工，我們將他們視為 17 個不可區分的球，放入 3 個可區分的單元格（代表三個團隊）中，這些單元格的容量無限制。($_{3}H_{17}$ 種方法)

因此，方法數為 $_{3}H_{17}={\binom {3-1+17}{17}}=171$.

$\Box$

(b)

證明。 我們將劃分過程視為兩步過程

1. 分別從 20 個人中選擇 A 團隊、B 團隊、C 團隊的三個隊長。($20\times 19\times 18$ 種方法)
2. 對於剩下的 17 個人中的每一個人，他們可以被分配到三個團隊中的一個。($3^{17}$ 種方法)

所以，方法數為 $20\times 19\times 18\times 3^{17}=883318714920$.

$\Box$

練習。 艾米有九個相同的戒指。假設她的每根手指都可以戴無限多個戒指。

(a) 請證明她右手戴戒指有 715 種方法。

(b) 請證明她兩隻手戴戒指有 48620 種方法。

(c) 假設她的左手要戴四個戒指，右手要戴另外五個戒指。請證明她兩隻手戴戒指有 8820 種方法。

(d) 假設她每個無名指都戴一個戒指。請證明她兩隻手戴戒指有 3432 種方法。

證明

(a)

證明。 方法數為 $_{5}H_{9}=715$。(9 個不可區分的球：9 個戒指；5 個容量無限制的可區分單元格：5 根手指)

$\Box$

(b)

證明。 方法數為 $_{10}H_{9}=48620$。(9 個不可區分的球：9 個戒指；10 個容量無限制的可區分單元格：10 根手指)

$\Box$

(c)

證明。 考慮兩步

1. 左手戴戒指。($_{5}H_{4}=70$ 種方法。4 個不可區分的球：4 個戒指；5 個容量無限制的可區分單元格：5 根手指)
2. 右手戴戒指。($_{5}H_{5}=126$ 種方法。5 個不可區分的球：5 個戒指；5 個容量無限制的可區分單元格：5 根手指

所以，方法數為 $70\times 126=8820$.

$\Box$

(d)

證明。 考慮兩步

1. 每個無名指都戴一個戒指。(1 種方法)
2. 剩下的八根手指戴著七個剩餘的戒指。 ($_{8}H_{7}=3432$ 種方式。7 個不可區分的球：7 個戒指；8 個可區分的細胞，容量無限：8 根手指)

所以，方法的數量是 3432。

$\Box$

摘要

將 $r$ 個球放入 $n$ 個可區分的細胞

	容量為一個的細胞	容量無限的細胞
可區分的球	$$n^{r}$$	$${\frac {n!}{(n-r)!}}$$
不可區分的球	$${\binom {n-1+r}{r}}$$	$${\binom {n}{r}}$$

練習。 嘗試證明上述每個公式，不參考前幾節。之後，您可以將您的證明與前幾節中的證明進行比較。

或者等效地，

從 $n$ 個可區分的物件中選擇 $r$ 個物件

	有替換	無替換
有序	$$n^{r}$$	$${\frac {n!}{(n-r)!}}$$
無序	$${\binom {n-1+r}{r}}$$	$${\binom {n}{r}}$$

不可區分的細胞

當 細胞 不可區分時，通常沒有簡單明瞭的公式來計算方法的數量。此外，在這種情況下，可能更難想象“不可區分的細胞”是什麼樣子，因為即使細胞是相同的，它們的 position 應該不同，以便球可以放置在不同的細胞中。然後，這些細胞仍然是可區分的。為了視覺化不可區分的細胞，人們可以想象在球被放入細胞後，“排序”這些細胞，根據它們包含的球的數量，球最少的細胞放在最左邊，球最多的細胞放在最右邊。（具有相同球數的細胞可以隨意放在一起。）然後，在將球“投入”細胞 並 對細胞進行排序後，我們可以觀察這些細胞來觀察結果。在這種情況下，細胞可以被視為不可區分的，因為我們只知道有多少個細胞包含 0 個、1 個等球，但不知道原始的細胞 1、2、.. 包含多少個球（我們無法在排序後判斷哪個細胞是原始的“細胞 1、2、..”）。

當我們遇到不可區分的細胞時，我們可能需要逐一考慮方法。

示例。 四個人要被分成 3 個 不可區分的 組。假設每個組可以包含零個人或多個人。證明有 14 種可能的組合。

證明。 我們將這種情況視為將四個可區分的球（代表四個人）放入三個不可區分的細胞（代表三個組）中，這些細胞具有無限容量。 然後，我們對球 1、2、3、4 放入三個不可區分的細胞（按包含的球數排序的細胞）有以下不同的排列方式。（我們使用數字 1、2、3、4 分別表示球 1、2、3、4，並將兩個豎線建立的三個空格作為不可區分的細胞（“排序”後的細胞）。請注意，空格中數字的順序無關緊要。我們只關心 哪些 數字包含在每個空格中。）

1. $||1234$
2. $|1|234$
3. $|2|134$
4. $|3|124$
5. $|4|123$
6. $|12|34$
7. $|13|24$
8. $|14|23$
9. $1|2|34$
10. $1|3|24$
11. $1|4|23$
12. $2|3|14$
13. $2|4|13$
14. $3|4|12$

因此，共有 14 種方法。

$\Box$

計數問題的強大工具：生成函式

定義。 （生成函式）一個 生成函式 是一個 冪級數，其係數給出特定數字序列。也就是說，序列 $a_{0},a_{1},a_{2},\dotsc$ 的生成函式由 $$G(x)=\sum _{n=0}^{\infty }a_{n}x^{n}=a_{\color {darkgreen}0}x^{\color {darkgreen}0}+a_{\color {darkgreen}1}x^{\color {darkgreen}1}+a_{\color {darkgreen}2}x^{\color {darkgreen}2}+\dotsb .$$

備註.

• $x^{k}$ 的係數，即 $a_{k}$，可以透過 $a_{k}={\frac {1}{k!}}G^{(k)}(0)$ 獲得，其中 $G^{(k)}(0)$ 表示函式 $G$ 在 $x=0$ 處的 $k$ 階導數。
• 在後面的章節中，我們將研究兩種重要的生成函式：矩生成函式（mgf）和機率生成函式（pgf），它們的係數在某種意義上分別給出矩序列和機率序列。可以使用與上述類似的方法獲得這些係數（表示矩/機率）。

以下定理給出了一些常見的生成函式。

定理。 （牛頓廣義二項式定理）令 $\alpha$ 為一個 實數。 那麼，$$(1+x)^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}$$ 其中 $|x|<1$，並且 ${\binom {\alpha }{k}}={\frac {\alpha (\alpha -1)(\alpha -2)\dotsb (\alpha -k+1)}{k!}}$ 是 廣義二項式係數。

備註.

• 定理中的級數也稱為 二項式級數。
• 方程中的級數實際上是 $(1+x)^{\alpha }$ 在零處的泰勒級數。也就是說，如果我們令 $f(x)=(1+x)^{\alpha }$，那麼該級數由以下給出

$$\sum _{n=0}^{\infty }{\frac {f^{(n)}(0)}{n!}}x^{n}$$

其中 $f^{(n)}(0)$ 是函式 $f$ 在 $x=0$ 處的 $n$ 階導數，條件 $|x|<1$ 是為了確保這個級數收斂。

• 然而，需要注意的是，僅僅這個泰勒級數收斂並不保證它收斂到函式的實際值（它可能收斂到其他地方）。因此，僅僅使用這個泰勒級數不足以證明該定理。

• 定理中的級數是序列 ${\binom {\alpha }{0}},{\binom {\alpha }{1}},{\binom {\alpha }{2}},\dotsc$ 的生成函式。

以下是該定理的一些特例

• (等比級數) $(1+x)^{-1}=1-x+x^{2}-x^{3}+\dotsb$: 序列 1,-1,1,-1,... 的生成函式;
• (等比級數) $(1-x)^{-1}=1+x+x^{2}+x^{3}+\dotsb$: 序列 1,1,1,1,... 的生成函式;
• (負二項式級數) $(1-x)^{-n}=\sum _{r=0}^{\infty }{\binom {n-1+r}{r}}x^{r}$: 序列 ${\binom {n-1}{0}},{\binom {n-1+1}{1}},{\binom {n-1+2}{2}},{\binom {n-1+3}{3}},\dotsc$ ;
• （二項式定理）$(1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+\dotsb +{\binom {n}{n}}x^{n}$：是序列${\binom {n}{0}},{\binom {n}{1}},{\binom {n}{2}},\dotsc ,{\binom {n}{n}}$ 的生成函式；（$n$ 是非負整數）
• （二項式定理）$(x+y)^{n}={\binom {n}{0}}x^{n}y^{0}+{\binom {n}{1}}x^{n-1}y+\dotsb +{\binom {n}{n}}x^{n-n}y^{n}$。（注意到$(x+y)^{n}=x^{n}(1+y/x)^{n}$，並將定理應用於$(1+y/x)^{n}$ 的 RHS 得出。）

示例. 使用生成函式的概念，證明將 $r$ 個不可區分的球放入 $n$ 個可區分的箱子的方法數為 ${\binom {n}{r}}$。

證明。 我們將選擇過程編碼為二項式序列，然後使用係數來確定所需的方法數量。更準確地說，考慮二項式序列：$$\underbrace {(1+x)(1+x)\dotsb (1+x)} _{n{\text{ times}}}=(1+x)^{n}=1+\cdots +{\binom {n}{r}}x^{r}+\cdots +{\binom {n}{n}}x^{n}.$$ 我們將 $n$ 個括號 $(1+x)$ 編碼為 $n$ 個單元格，如果我們在括號中選擇 "1"，則該單元格有零個球。如果我們在括號中選擇 "$x$"，則該單元格有一個球。由於有 $r$ 個球，因此 $r$ 個 $n$ 個括號中包含一個球，因此所需的方法數量是 $x^{r}$ 的係數（係數給出透過將 $x$ 乘以恰好 $r$ 個括號來 "構建" $x^{r}$ 的方法數量（"$x$" 是透過在恰好 $r$ 個單元格中放置一個球而得到的）。因此，方法數量為 ${\binom {n}{r}}$.

$\Box$

示例。 證明將 $r$ 個無法區分的球放入 $n$ 個可區分的單元格中，每個單元格容量無限的方法數量為 ${\binom {n-1+r}{r}}$.

證明。 我們將 $n$ 個括號 $(1+x+x^{2}+\dotsb )$ 編碼為 $n$ 個單元格。如果我們在括號中選擇“1”，那麼單元格中沒有球，如果我們在括號中選擇“$x$”，那麼單元格中有一個球，如果我們在括號中選擇“$x^{2}$”，那麼單元格中有兩個球，等等。然後，所需數字是 $x^{r}$ 的係數（透過在不同的括號中乘以一些 $x$ 的冪來“構建” $x^{r}$ 的方法數量（冪由一些單元格中的一些球獲得））在生成函式 $$\underbrace {(1+x+x^{2}+\dotsb )(1+x+x^{2}+\cdots )\cdots (1+x+x^{2}+\cdots )} _{n{\text{ times}}}=\underbrace {(1-x)^{-1}(1-x)^{-1}\dotsb (1-x)^{-1}} _{n{\text{ times}}}=(1-x)^{-n}.$$ 這是負二項式級數。因此，$x^{r}$ 的係數是 $${\binom {n-1+r}{r}}.$$

$\Box$

示例。 證明將 $n$ 個可區分的球放入單元格 1、2、...、$k$ 中，其中單元格 1、2、...、$k$ 必須分別包含 $n_{1},n_{2},\dotsc ,n_{k}$ 個球的方法數量是 ${\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$，使用生成函式的概念。

證明： 我們將 $n$ 個括號 $(x_{1}+x_{2}+\dotsb +x_{k})$ 編碼為 $n$ 個單元格。如果選擇 $x_{1},x_{2},\dotsc ,x_{k}$，我們就在單元格 1, 2, ..., $k$ 中放一個球。由於我們希望單元格 1, 2, ..., $k$ 中恰好包含 $n_{1},n_{2},\dotsc ,n_{k}$ 個球，我們感興趣的是 $x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$ 的係數，即，將不同的 "$x_{i}$" 在不同的括號中相乘以建立乘積 $x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$ 的方法數量，在 $$\underbrace {(x_{1}+x_{2}+\cdots +x_{k})(x_{1}+x_{2}+\cdots +x_{k})\cdots (x_{1}+x_{2}+\cdots +x_{k})} _{n{\text{ times}}}=(x_{1}+x_{2}+\cdots +x_{k})^{n},$$ 也就是 ${\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$，根據 多項式定理。

$\Box$

例如： 計算方程 $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=26$ 的解的個數，其中 $x_{1},x_{2},\dotsc ,x_{6}$ 為正數，$x_{5}>3$ 且 $3\leq x_{6}<6$.

解. 考慮生成函式 $$\underbrace {(x+x^{2}+x^{3}+\dotsb )^{4}} _{x_{1},x_{2},x_{3},x_{4}}\underbrace {(x^{4}+x^{5}+x^{6}+\dotsb )} _{x_{5}}\underbrace {(x^{3}+x^{4}+x^{5})} _{x_{6}}=x^{4}(1-x)^{-4}x^{4}(1-x)^{-1}(x^{3}+x^{4}+x^{5})=(x^{11}+x^{12}+x^{13})(1-x)^{-5}.$$ （不同括號內的 $x$ 的冪表示不同未知數 $x_{i}$ 所選的整數）。

根據牛頓廣義二項式定理， $x^{15},x^{14},x^{13}$ 在 $(1-x)^{-5}$ 中的係數分別為 ${\binom {-5}{15}}(-1)^{15}=3876,{\binom {-5}{14}}(-1)^{14}=3060,{\binom {-5}{13}}(-1)^{13}=2380$。這意味著 $x^{26}$ 在 $(x^{11}+x^{12}+x^{13})(1-x)^{-5}$ 中的係數為 $3876+3060+2380=9316$。因此，解的個數為 9316。

備註.

• 也可以注意到$(1-x)^{-5}$ 是一個負二項式級數，並繼續使用，例如，${\binom {5-1+15}{15}}$ 來獲得$x^{15}$ 在$(1-x)^{-5}$ 中的係數。

示例. 假設你去水果店購買 15 個水果。水果店裡有兩個蘋果，三個梨，六個香蕉，以及無限數量的柚子。證明你可以用 84 種不同的方式購買這 15 個水果。（假設每種水果都是相同的，因此無法區分。）

Proof. Consider the generating function $${\begin{aligned}G(x)&=\underbrace {(1+x+x^{2})} _{\text{apple}}\underbrace {(1+x+x^{2}+x^{3})} _{\text{pear}}\underbrace {(1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})} _{\text{banana}}\underbrace {(1+x+x^{2}+\dotsb )} _{\text{grapefruit}}\\&={\frac {1-x^{3}}{1-x}}\cdot {\frac {1-x^{4}}{1-x}}\cdot {\frac {1-x^{7}}{1-x}}\cdot {\frac {1}{1-x}}&({\text{geometric series formulas}})\\&=(1-x^{3})(1-x^{4})(1-x^{7})(1-x)^{-4}\\&=(1-x^{3}-x^{4}+x^{10}+x^{11}-x^{14})(1-x)^{-4}.\end{aligned}}$$ (The powers of $x$ in different brackets indicate the number of different fruits bought.) By Newton's generalized binomial theorem, the coefficients of $x^{15},x^{12},x^{11},x^{5},x^{4},x$ in $(1-x)^{-4}$ is ${\binom {-4}{15}}(-1)^{15}=816,{\binom {-4}{12}}(-1)^{12}=455,{\binom {-4}{11}}(-1)^{11}=364,{\binom {-4}{5}}(-1)^{5}=56,{\binom {-4}{4}}(-1)^{4}=35,{\binom {-4}{1}}(-1)=4$ respectively. Thus, the desired number of ways is the coefficient of $x^{15}$ in $G(x)$, which is $$816-455-364+56+35-4=84.$$

$\Box$

示例. 假設你擲了四個相同的骰子。證明有 136 種不同的結果，使得得到的數字之和能被 9 整除。

證明. 考慮生成函式$$G(x)=\underbrace {(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}} _{4{\text{ dices}}}{\overset {\text{ GS }}{=}}x^{4}(1-x^{6})^{4}(1-x)^{-4}=(x^{4}-4x^{10}+6x^{16}-4x^{22}+x^{28})(1-x)^{-4}$$（$x$ 的冪表示得到的數字）。由於擲了四個骰子，因此數字之和的範圍為 4 到 24。在這個數字範圍內，9 和 18 可以被 9 整除。因此，所需結果的數量是$x^{9},x^{18}$ 在$G(x)$ 中的係數之和。現在，讓我們逐一找到這些係數。

$x^{9}$ 的係數:

根據牛頓廣義二項式定理，$x^{5}$ 在$(1-x)^{-4}$ 中的係數為$$-{\binom {-4}{5}}=56.$$ 因此，$x^{9}$ 的係數為 56。

$x^{18}$ 的係數:

根據牛頓廣義二項式定理，$x^{14},x^{8},x^{2}$ 在 $(1-x)^{-4}$ 中的係數分別為 $${\binom {-4}{14}}=680,{\binom {-4}{8}}=165,{\binom {-4}{2}}=10$$。因此，$x^{18}$ 的係數為 $$680-4(165)+6(10)=80.$$

因此，結果數量為 $56+80=136$.

$\Box$

練習。 有 8 種不同的食物或飲料，分別是漢堡、雞蛋、薯條、蛋糕、蘋果派、蘋果汁、橙汁和可樂。除非另有說明，組合可以包含相同專案多次。

(a) 假設每種食物或飲料只有 2 個庫存。證明有 266 種不同的 4 專案組合。 (提示: 你可能會發現以下公式有用: $(1-x^{3})^{8}=1-8x^{3}+{\text{terms with order higher than }}x^{4}$ (這可以透過將 "$-x^{3}$" 看作定理中的 $x$ 來得到。)

(b) 假設每種食物價格 10 美元，每種飲料價格 5 美元。證明有 60 種不同的 20 美元組合。 (提示: 將 5 美元視為一個單位。那麼，每種食物對應兩個單位，每種飲料對應一個單位。利用這個想法，構造一個適當的生成函式，其冪為這些“單位”。之後，你可能會發現以下公式有用: $(1-x^{2})^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}(-x^{2})^{k}$ (透過將 "$x^{2}$" 看作廣義二項式定理中的 "$x$" 來得到 (條件變為 $|x^{2}|<1$).)

證明

(a)

證明： 考慮生成函式 $$G(x)=\underbrace {(1+x+x^{2})^{8}} _{\text{food/drink item}}{\overset {\text{ GS }}{=}}(1-x^{3})^{8}(1-x)^{-8}=(1-8x^{3}+{\text{terms with order higher than }}x^{4})(1-x)^{-8}$$ （不同括號中的 $x$ 的冪代表選擇的不同物品數量。）根據牛頓廣義二項式定理，$x^{4},x$ 在 $(1-x)^{-8}$ 中的係數分別為 $${\binom {-8}{4}}=330,-{\binom {-8}{1}}=8$$ 。因此，$x^{4}$ 在 $G(x)$ （即我們想要的數字）中的係數為 $$330-8(8)=266.$$

$\Box$

(b)

證明： 考慮生成函式 $$G(x)=\underbrace {(1+x^{2}+x^{4}+\dotsb )^{5}} _{\text{food}}\underbrace {(1+x+x^{2}+\dotsb )^{3}} _{\text{drink}}=(1-x^{2})^{-5}(1-x)^{-3}$$ （不同括號中的 $x$ 的冪表示用於不同食品/飲料專案的 $5 的數量。對於每種食物，需要兩個 $5，因此 $x$ 的冪每次增加 2）由於套餐總成本為 $20，即四個 $5，因此我們想要的數字由 $x^{4}$ 的係數給出。

現在，我們考慮 $x^{0},x^{2},x^{4}$ 在 $(1-x^{2})^{-5}$ 中的係數:（將 $x^{2}$ 看作廣義二項式定理中的 $x$）

• $x^{0}:{\binom {-5}{0}}={\color {red}1}$
• $x^{2}:-{\binom {-5}{1}}={\color {blue}5}$
• $x^{4}=(x^{2})^{2}:{\binom {-5}{2}}={\color {darkgreen}15}$

現在，我們考慮 $x^{0},x^{2},x^{4}$ 在 $(1-x)^{-3}$ 中的係數:（對於 $x^{1},x^{3}$，我們不能用它來構造 $x^{4}$，因為只有 $x^{0},x^{2},x^{4}$（對於階數最多為 $x^{4}$ 的項）在 $(1-x^{2})^{-5}$ 中可用）

• $x^{0}:{\binom {-3}{0}}={\color {darkgreen}1}$
• $x^{2}:{\binom {-3}{2}}={\color {blue}5}$
• $x^{4}:{\binom {-3}{4}}={\color {red}15}$

因此，$G(x)$ 中 $x^{4}$ 的係數是 $${\color {red}1(15)}+{\color {blue}5(6)}+{\color {darkgreen}15(1)}=60.$$

$\Box$

其他練習

練習。

檔案:Ryu combo.gif

考慮遊戲街頭霸王。在本練習中，我們考慮不同的“連招”。為了簡單起見，我們做以下假設

1. 只有四種類型的動作：拳（P）、腳（K）、前進（F）、跳躍（J）
2. 一個連招可以包含 2-4 個動作，這些動作可以是不同的，也可以是相同的，並且動作可以按任何順序排列（順序很重要）。例如，

• P不是連招，因為它只包含 1 個動作。
• PJJ 是一個連招。
• PPKF 是一個連招。
• KKKFJ不是連招，因為它包含 5 個動作。

(a) 有多少個不同的連招？

(b) 如果一個連招不能以跳躍開始，有多少個不同的連招？

(c) 證明如果一個連招必須包含至少一個“攻擊動作”（即拳或腳），則有 308 個不同的連招。

解決方案

(a) 我們將情況分為 3 種情況。

情況 1：連招包含 2 個動作。然後，有 $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}=16$ 個不同的連招（每個動作有 4 種選擇）。

情況 2：連招包含 3 個動作。然後，有 $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}=64$ 個不同的連招。

情況 3：連招包含 4 個動作。然後，有 $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}\times \underbrace {4} _{\text{move 4}}=256$ 個不同的連招。

由於這四種情況中沒有相同的連招，因此不同的連招總數為 $16+64+256=336$。

(b) 我們將情況分為 3 種情況。

情況 1：連招包含 2 個動作。然後，有 $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}=12$ 個不同的連招（動作 1 不能是跳躍。所以，動作 1 只有 3 種選擇）。

情況 2: 組合包含 3 個動作。然後，就有 $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}=48$ 種不同的組合。

情況 3: 組合包含 4 個動作。然後，就有 $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}\times \underbrace {4} _{\text{move 4}}=192$ 種不同的組合。

由於這四種情況下沒有相同的組合，所以不同的組合總數是 $12+48+192=252$。

(c)

證明。 我們首先考慮包含 零 個攻擊動作的不同組合。同樣地，我們將情況分為 3 種。

情況 1: 組合包含 2 個動作。然後，就有 $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}=4$ 種不同的組合（每個動作有 2 種選擇）。

情況 2: 組合包含 3 個動作。然後，就有 $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}\times \underbrace {2} _{\text{move 3}}=8$ 種不同的組合。

情況 3: 組合包含 4 個動作。然後，就有 $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}\times \underbrace {2} _{\text{move 3}}\times \underbrace {2} _{\text{move 4}}=16$ 種不同的組合。

由於這四種情況下沒有相同的組合，所以包含零個攻擊動作的不同組合總數是 $4+8+16=28$。因此，為了得到所需的組合數，我們將這個數字（28）從所有可能的不同組合數（336）中減去：$336-28=308$。

$\Box$

練習。

考慮一個與劍相關的遊戲。在這個遊戲中，有五級劍，從 1 到 5。為了獲得一把等級 $n$ 的劍，玩家需要獲得三把等級 $n-1$ 的劍，它們會自動組合成一把等級 $n$ 的劍。例如，為了獲得一把等級 2 的劍，玩家需要獲得三把等級 1 的劍。

玩家最初獲得一把1級劍，並且可以使用最高等級的劍（每次只能使用一把劍）來擊敗怪物，以賺取金幣。假設每個怪物的生命值（HP）為100，而使用等級為 $n$ 的劍，玩家每秒可以對怪物造成 $2^{n}$ 點傷害，也就是說，等級為 $n$ 的劍的 每秒傷害（DPS）為 $2^{n}$。例如，使用一把3級劍，DPS 為 8，因此需要 ${\frac {100}{8}}=12.5$ 秒來殺死一個怪物。殺死一個怪物後，玩家可以獲得1枚金幣，1級劍的價格是1枚金幣（並且只能購買1級劍，但1級劍供應無限）。

證明玩家需要 812.5 秒才能獲得一把 5 級劍。

證明

證明。 遊戲過程如下

1. 當玩家擁有等級為 $n$ 的劍並且它是他的最高等級劍時，玩家使用它來殺死一些怪物，以獲得足夠的金幣來購買 兩把 額外的等級為 $n$ 的劍。之後，玩家將擁有三把等級為 $n$ 的劍，因此可以獲得一把等級為 $n+1$ 的劍。
2. 重複步驟 1 直到玩家獲得一把 5 級劍。

我們逐步考慮獲得一把 5 級劍的過程

1. 使用 1 級劍殺死兩隻怪物，獲得 2 枚金幣，購買兩把 1 級劍，然後玩家獲得一把 2 級劍。（花費 ${\frac {200}{2}}=100$ 秒）
2. 使用 2 級劍殺死六隻怪物，獲得 6 枚金幣，購買六把 1 級劍，然後玩家獲得兩把 2 級劍，因此獲得一把 3 級劍。（花費 ${\frac {600}{2^{2}}}=150$ 秒）
3. 使用 3 級劍殺死 18 只怪物，獲得 18 枚金幣，購買 18 把 1 級劍，然後玩家獲得 6 把 2 級劍，因此獲得兩把 3 級劍。之後，玩家獲得一把 4 級劍。（花費 ${\frac {1800}{2^{3}}}=225$ 秒）
4. 使用 4 級劍殺死 54 只怪物，獲得 54 枚金幣，購買 54 把 1 級劍，然後獲得 18 把 2 級劍，然後獲得 6 把 3 級劍，然後獲得 2 把 4 級劍。之後，玩家獲得一把 5 級劍。（花費 ${\frac {5400}{2^{4}}}=337.5$ 秒）

因此，總共需要 $100+150+225+337.5=812.5$ 秒。

$\Box$

練習。 在某所大學，學生每個學期需要修五門課程，並且在 透過 八個學期後，學生畢業。另一方面，如果學生 不及格 兩個學期 連續，他將被學校開除。（這裡，透過一個學期是指透過該學期修的所有課程，不及格一個學期是指該學期至少有一門課程不及格。）我們將這種情況視為兩個結果的有序序列：透過（P）和不及格（F）。例如，PPPFPFF 表示第 1、2、3 個學期透過，第 4 個學期不及格，第 5 個學期透過，第 6、7 個學期不及格。學生在第 7 個學期被開除，因此序列停止。另一方面，PPPPPPPPP 表示連續透過八個學期，並且學生畢業，因此序列也停止。

在本練習中，我們將統計在不同情況下有多少種不同的序列。

(a) 證明有 765 種不同的序列。

(b) 證明如果學生在 12 個學期後還沒有畢業，也會被開除，那麼有 466 種不同的序列。

證明

(a)

證明。 首先，請注意學生最終要麼畢業，要麼最終不及格。也就是說，序列最終會停止。換句話說，序列的長度必須是有限的。（實際上，可以透過重複模式“FP”八次來構建一個具有最大長度的序列：FPFPFPFPFPFPFPFP。此序列的長度為 16，我們可以看到它是最大長度，因為我們不能在中間新增更多“F”（否則學生將被開除），並且有八個“P”。）

為了統計序列的數量，我們考慮兩種情況

情況 1：學生最終畢業。這意味著序列中包含八個“P”，但序列中沒有兩個連續的“F”。圖形地，

        P P P P P P P P
       ^ ^ ^ ^ ^ ^ ^ ^ ^
^: position for at most one "F"

在由“^”指示的每個位置（9 個位置），我們可以選擇 (i) 放入一個“F”；或 (ii) 不放入一個“F”。因此，每個位置都有兩種方法。總共有九步，每步都有兩種方法。因此，序列的數量為 $2^{9}=512$.

案例 2：學生最終不及格。這意味著序列中出現了連續的兩個“F”。現在我們考慮有多少種不同的序列，使得最後兩個學期是連續的兩個“F”。以下是可能性

                           number of sequences    number of "P"s before "FF"
                   FF            1                      0

                 P FF            2                      1
                ^
               P P FF           2^2                     2
              ^ ^
             P P P FF           2^3                     3
            ^ ^ ^
           P P P P FF           2^4                     4
          ^ ^ ^ ^
         P P P P P FF           2^5                     5
        ^ ^ ^ ^ ^
       P P P P P P FF           2^6                     6
      ^ ^ ^ ^ ^ ^
     P P P P P P P FF           2^7                     7
    ^ ^ ^ ^ ^ ^ ^
^: position for at most one "F"
(semester just before "FF" must be "P", otherwise the "FF" occurs earlier)

因此，此情況下的序列數量為 $$1+2+2^{2}+2^{3}+2^{4}+2^{5}+2^{6}+2^{7}=253.$$

結合兩種情況，可以得出有 $512+253=765$ 種不同的序列（兩種情況中沒有共同的序列）。

$\Box$

(b)

證明。在這種情況下，更明顯的是序列最終必須停止，序列的最大長度為 12。

為了計算序列數量，我們同樣考慮兩種情況

案例 1：學生最終畢業。這意味著序列中有八個“P”，但序列中沒有連續的兩個“F”，並且序列的長度最多為 11。圖形表示如下：

        P P P P P P P P
       ^ ^ ^ ^ ^ ^ ^ ^ ^
^: positions for placing at most 3 "F"s, with each contains at most one "F".

在由“^”表示的 9 個位置中，我們可以最多放置 3 個“F”，每個位置最多包含一個“F”。這等同於將 $k$ 個不可區分的球（“F”）放入 9 個可區分的單元格（由“^”表示）中，每個單元格容量為 1，其中 $k=0,1,2,{\text{ or }}3$。因此，序列數量為 $${\binom {9}{0}}+{\binom {9}{1}}+{\binom {9}{2}}+{\binom {9}{3}}=130.$$

案例 2：學生最終不及格。我們首先考慮序列中存在連續的兩個“F”的情況（這意味著學生透過獲得“FF”而不是在 12 個學期後沒有 8 個“P”而不及格）。這裡，我們還包括在獲得“FF”後，長度僅為 12 的情況。

現在我們考慮有多少種不同的序列，使得最後兩個學期是連續的兩個“F”（長度最多為 12，包括最後的兩個“F”）。以下是可能性

                           number of sequences    number of "P"s before "FF"
                   FF            1                      0              

                 P FF            2                      1
                ^
               P P FF           2^2                     2
              ^ ^
             P P P FF           2^3                     3
            ^ ^ ^
           P P P P FF           2^4                     4
          ^ ^ ^ ^
         P P P P P FF           2^5                     5   
        ^ ^ ^ ^ ^
       P P P P P P FF           9C4                     6   (place at most 4 "F"s)
      ^ ^ ^ ^ ^ ^
     P P P P P P P FF           9C3                     7   (place at most 3 "F"s)
    ^ ^ ^ ^ ^ ^ ^
(semester just before "FF" must be "P", otherwise the "FF" occurs earlier)

此情況下序列的數量為 $1+2+2^{2}+2^{3}+2^{4}+2^{5}+{\binom {9}{4}}+{\binom {9}{3}}=273$.

現在，我們考慮序列中不存在連續的兩個“F”，但學生在 12 個學期後沒有透過八個學期的情況（這意味著學生由於在 12 個學期後沒有 8 個“P”而不及格）。以下是可能性

No. of  "P"s
     <5                           (impossible. Reason is similar to the case for 5 "P"s)

     5          P P P P P         (impossible. Even placing exactly one "F" at each position, the length is 11 < 12.)
               ^ ^ ^ ^ ^ ^

     6        P P P P P P         (place exactly 6 "F"s where each position contains at most one "F", making the length 12, and no "FF")
             ^ ^ ^ ^ ^ ^ ^  

     7      P P P P P P P         (place exactly 5 "F"s where each position contains at most one "F", making the length 12, and no "FF")
           ^ ^ ^ ^ ^ ^ ^ ^  

對於 6 個“P”的情況，序列數量為 ${\binom {7}{6}}=7$，對於 7 個“P”的情況，序列數量為 ${\binom {8}{5}}=56$。因此，總共有 $7+56=63$ 種序列。

由於這兩種情況下沒有共同的序列（一種情況包含“FF”，另一種情況不包含），在案例 2 中，總共有 $273+63=336$ 種序列。

結合兩種情況，可以得出有 $130+336=466$ 種不同的序列（兩種情況中沒有共同的序列）。

$\Box$

練習。（注意：機率分佈的概念本身不需要用於完成此練習。）

一位機率論課程的老師想從他的題庫中建立一份課堂考試。課堂考試是關於機率分佈的概念。題庫中有 74 道與該概念相關的不同問題，它們分為以下型別

• 43 道關於離散分佈的問題，包括

• 9 道關於伯努利分佈的問題
• 5 道關於二項分佈的問題
• 7 道關於負二項分佈的問題
• 6 道關於幾何分佈的問題
• 3 道關於超幾何分佈的問題
• 13 道關於泊松分佈的問題

• 31 道關於連續分佈的問題，包括

• 10 道關於正態分佈的問題
• 11 道關於指數分佈的問題
• 3 道關於伽馬分佈的問題
• 2 道關於貝塔分佈的問題
• 5 道關於均勻分佈的問題

課堂考試將包含五道（不同的）問題。在以下內容中，當考慮方法數量時，問題的順序並不重要，因為改變順序不會影響考試的內容。

(a) 有多少種方法可以建立課堂考試？

(b) 有多少種方法可以建立包含 3 道關於離散分佈的問題和 2 道關於連續分佈的問題的課堂考試？

(c) 有多少種方法可以建立至少包含 1 道關於正態分佈的問題的課堂考試？

(d) 有多少種方法可以建立一個包含正好一個關於正態分佈的問題的課堂測試？

(e) 有多少種方法可以建立一個包含涵蓋 5 種不同連續分佈的問題的課堂測試？（即，包含關於 5 種不同連續分佈的每種分佈正好一個問題）

(f) 有多少種方法可以建立一個包含涵蓋正好一種分佈的問題的課堂測試？（即，包含關於單個分佈的五個問題）

解決方案

由於測試中的問題是不同的，並且問題的順序並不重要，因此建立課堂測試的過程等同於將 5 個不可區分的球（代表測試中的 5 個問題）放入 74 個可區分的單元格（代表題庫中的 74 個不同問題）中，每個單元格的容量為 1（因為測試中的問題不能重複）。

(a) 方法數為 ${\binom {74}{5}}=16108764$.

(b) 根據要求，我們需要將 3 個球放入 43 個離散分佈的單元格中，並將 2 個球放入 31 個連續分佈的單元格中。因此，方法數為 ${\binom {43}{3}}\times {\binom {31}{2}}=5738565$.

(c) 根據要求，我們需要將 1 個球放入 10 個正態分佈的單元格中（10 種方法），並將剩餘的 4 個球放入剩餘的 72 個單元格中（測試中包含一個關於正態分佈的問題，並且不能重複）(${\binom {72}{4}}$ 種方法）。因此，方法數為 $10\times {\binom {72}{4}}=10287900$.

(d) 根據要求，我們需要將 1 個球放入 10 個正態分佈的單元格中（10 種方法），並將剩餘的 4 個球放入剩餘的 63 個單元格中（排除所有與正態分佈相關的問題）(${\binom {63}{4}}$ 種方法）。因此，方法數為 $10\times {\binom {63}{4}}=5956650$.

(e) 我們將根據該要求建立測試視為一個 5 步過程：將一個球放入 (i) 10 個單元格；(ii) 11 個單元格；(iii) 3 個單元格；(iv) 2 個單元格；(v) 5 個單元格。那麼方法數為 $\underbrace {10} _{\text{norm}}\times \underbrace {11} _{\text{exp}}\times \underbrace {3} _{\text{gamma}}\times \underbrace {2} _{\text{beta}}\times \underbrace {5} _{\text{uniform}}=3300$.

(f) 為了使測試中的所有問題都只涵蓋單個分佈，該分佈在題庫中至少應有 5 道題。因此，對於超幾何分佈、伽馬分佈和貝塔分佈來說這是不可能的。方法數由 $$\underbrace {\binom {9}{5}} _{\text{Ber}}+\underbrace {1} _{\text{bin}}+\underbrace {\binom {7}{5}} _{\text{NB}}+\underbrace {\binom {6}{5}} _{\text{geo}}+\underbrace {\binom {13}{5}} _{\text{Pois}}+\underbrace {\binom {10}{5}} _{\text{norm}}+\underbrace {\binom {11}{5}} _{\text{exp}}+\underbrace {1} _{\text{uniform}}=2150.$$

練習。 假設你去一家餐廳吃自助午餐。餐廳有 60 種不同的食物，包括

• 7 種沙拉
• 23 種肉類
• 6 種蔬菜
• 14 種甜點
• 10 種麵包

假設每種食物都有無限份。每次拿食物時，你需要把它們放在盤子裡。假設每次要放 3-5 種食物到盤子裡。

(a) 證明有 8257997 種方法可以把食物放在盤子裡。

(b) 一名學生提出以下論點來計算如果盤子裡至少有一份肉類，那麼放食物到盤子的方法數。

因為盤子裡至少有一份肉類，所以需要將一個球放入代表 23 種肉類的 23 個單元格中（23 種方法）。之後，將剩餘的球放入代表 60 種食物的 60 個可區分單元格中。

我們現在考慮不同食物數量的情況（將 $k=2,3,{\text{ or }}4$ 個不可區分的球（“盤子位置”）放入 60 個單元格中），得到

• 3 種食物：$23\times {}_{60}H_{2}=42090$
• 4 種食物：$23\times {}_{60}H_{3}=869860$
• 5 種食物：$23\times {}_{60}H_{4}=13700295$

所以，方法總數為 $42090+869860+13700295=14612245$.

解釋為什麼答案必須是錯誤的，並解釋論點中存在哪些錯誤。(提示: 為了解釋為什麼答案必須是錯誤的，請將該數字與 (a) 中的數字進行比較。錯誤在於對乘法計數原理的使用不當。您可以閱讀討論該原理的部分以獲得一些想法。）

解決方案

(a)

證明。 我們可以將 60 種不同的食物視為 60 個可區分的單元格，它們具有無限容量，並將“盤子位置”視為不可區分的球。放入單元格中的“盤子位置”數量取決於盤子裡放了多少食物（3、4 或 5）。因此，我們將情況分為 3 種情況。

情況 1：3 種食物（球）。所以，我們將 3 個球放入 60 個單元格中。因此，方法數為 $_{60}H_{3}=37820$.

對於 4 種食物和 5 種食物的情況，情況類似，方法數分別為 $_{60}H_{4}=595665$ 和 $_{60}H_{5}=7624512$。因此，方法總數為 $37820+595665+7624512=8257997$.

$\Box$

(b) 答案一定是錯的，因為這個數字比 (a) 中的數字還要大，但 (b) 中有一個額外的條件。透過增加一個額外條件，(a) 中的一些方式不被允許，並且不會有任何額外的方案。因此，這個數字應該小於 (a) 中的數字。

該論證的錯誤在於，當學生使用乘法計數原理來獲得食物數量時，"任務"是不可區分的，這導致了多條決策路徑導致相同的結果。讓我們考慮一個包含 3 種食物的例子。

1. 第一個決策路徑：第一步，將一個球放到肉類 1 中，第二步，將兩個球分別放到肉類 2、3 中。
2. 第二個決策路徑：第一步，將一個球放到肉類 2 中，第二步，將兩個球分別放到肉類 1、3 中。

因此，結果是三個 不可區分 的球分別進入肉類 1、2、3，無論哪條決策路徑都是如此。

但是，在使用乘法計數原理時，我們假設每條決策路徑都只產生一個結果，因此學生得到的數字確實是決策路徑的數量。但有些路徑會導致相同的結果，因此這個數字不是方案總數。

練習。 假設你拋硬幣 10 次，得到一個結果序列。例如，序列 HTHHTHTTTT 表示第 1、3、4、6 次丟擲正面，第 2、5、7、8、9、10 次丟擲反面。

(a) 有多少個不同的序列？

(b) 證明由恰好五次（不是六次、七次，等等）連續 正面組成的不同序列的數量是 64。

解決方案

(a) 對於每一次拋擲，都有兩種結果：正面 (H) 或反面 (T)。因此，不同的序列數量是 $2^{10}=1024$.

(b)

證明。 為了讓正面出現 恰好 五次連續，"HHHHH" 需要被 "T" 包圍。有六種情況

情況 1：第 1、2、3、4、5 次丟擲正面 (HHHHHT????)。

情況 2：第 2、3、4、5、6 次丟擲正面 (THHHHHT???)。

情況 3：第 3、4、5、6、7 次丟擲正面 (?THHHHHT??)。

情況 4：第 4、5、6、7、8 次丟擲正面 (??THHHHHT?)

情況 5：第 5、6、7、8、9 次丟擲正面 (???THHHHHT)

情況 6：第 6、7、8、9、10 次丟擲正面 (????THHHHH)

上述情況中，只有標記為 "?" 的拋擲才有自由度。對於其他拋擲，結果是固定的。在上述兩種情況中，有四個 "?"（因此序列數量是 $2^{4}=16$），而對於剩餘的情況，有三個 "?"（因此序列數量是 $2^{3}=8$）。因此，序列數量為 $$2\cdot 16+4\cdot 8=64.$$

$\Box$

練習。 考慮一個 角色扮演遊戲 (RPG)，玩家需要在遊戲開始時建立一個角色，並分配一些 技能點 給角色。假設玩家有 10 個技能點，角色有五個屬性，如下所示

1. 生命值
2. 攻擊力
3. 防禦力
4. 速度
5. 幸運

玩家可以給每個屬性分配 1-5 個技能點，我們將分配 10 個技能點給五個屬性稱為一個 加點。

(a) 證明不同的加點數量是 121。（提示：考慮使用生成函式。）

(b) 有多少種不同的加點方式，其中分配給幸運屬性的技能點為 5 個？

(c) 假設如果分配給攻擊力和速度屬性的技能點至少為 3 個，那麼加點方式稱為 攻擊加點，如果分配給生命值和防禦力屬性的技能點至少為 3 個，那麼加點方式稱為 防禦加點。有多少種攻擊加點方式？有多少種防禦加點方式？攻擊加點方式和防禦加點方式的數量是否相等？

(d) 假設玩家可以在角色建立階段留下一些 10 個技能點不分配，並在遊戲中後期分配這些技能點。儘管如此，每個屬性仍然需要分配至少 1 個技能點。證明在角色建立階段分配技能點有 247 種方法。

解決方案

(a)

證明。 我們可以把 10 個技能點看作 10 個不可區分的球，五個屬性看作五個容量為 5 的可區分的盒子，每個盒子中必須至少包含一個球。為了方便，我們考慮以下生成函式：$$G(x)=(x+x^{2}+x^{3}+x^{4}+x^{5})^{5}=\left({\frac {x(1-x^{5})}{1-x}}\right)^{5}=x^{5}(1-x^{5})^{5}(1-x)^{-5}=x^{5}({\color {blue}1}-{\color {red}5}x^{5}+{\text{terms with order higher than }}x^{5})(1-x)^{-5}$$（不同括號中 $x$ 的冪表示分配給不同屬性的技能點數量。）（這裡，我們對 $(1-x^{5})^{5}$ 應用牛頓廣義二項式定理。）由於玩家只有 10 個技能點，因此不同的加點數量是 $x^{10}$ 在 $G(x)$ 中的係數。

根據牛頓廣義二項式定理，$x^{0},x^{5}$ 在 $(1-x)^{-5}$ 中的係數分別為 ${\binom {-5}{0}}={\color {red}1},-{\binom {-5}{5}}={\color {blue}126}$。因此，構建數量，即 $x^{10}$ 在 $G(x)$ 中的係數為 $${\color {blue}126\cdot 1}-{\color {red}5\cdot 1}=121.$$

$\Box$

(b) 我們可以再次使用生成函式方法：$$G(x)=(x+x^{2}+x^{3}+x^{4}+x^{5})^{\color {darkgreen}4}\underbrace {(x^{5})} _{\text{luck}}=x^{4}(1-x^{5})^{4}(1-x)^{-4}x^{5}=x^{9}({\color {blue}1}+{\text{terms with order higher than }}x)(1-x)^{-4}$$ （我們寫下高於 $x$ 的項，因為對於這些項，在乘以 $x^{9}$ 後，其階數至少為 $x^{11}$，因此我們對此不感興趣。）根據牛頓廣義二項式定理，$(1-x)^{-4}$ 中 $x$ 的係數為 $-{\binom {-4}{1}}=4$。因此，不同構建的數量（即 $G(x)$ 中 $x^{10}$ 的係數）為 ${\color {blue}4\cdot 1}=4$。

另一種方法：或者，我們可以使用以下更“聰明”的方法。由於要分配 5 個技能點給幸運，並且每個生命值、攻擊、防禦和速度分別必須分配 1 個技能點。因此，只剩下 1 個技能點可以自由分配，而所有其他技能點都是固定的。這個技能點要分配給生命值、攻擊、防禦和速度中的一個（不能分配給幸運，因為幸運已經有了五個（最大）技能點）。因此，有四種分配方法。所以，不同構建的數量是 4。

(c) 由於對稱性，攻擊流派的數量與防禦流派的數量相同。（每種流派基本上有相同的需求。不同的屬性除了名稱外，在本質上沒有任何實際區別。）所以，我們只需關注攻擊流派。我們再次考慮生成函式方法： $${\begin{aligned}G(x)&=\underbrace {(x^{3}+x^{4}+x^{5})^{2}} _{{\text{atk }}\&{\text{ spd}}}(x+x^{2}+x^{3}+x^{4}+x^{5})^{3}\\&=\left({\frac {x^{3}(1-x^{3})}{1-x}}\right)^{2}\left({\frac {x(1-x^{5})}{1-x}}\right)^{3}\\&=x^{9}(1-x^{3})^{2}(1-x^{5})^{3}(1-x)^{-5}\\&=x^{9}({\color {blue}1}+{\text{terms with order higher than }}x)({\color {blue}1}+{\text{terms with order higher than }}x)(1-x)^{-5}.\\\end{aligned}}$$ 根據牛頓廣義二項式定理，$x$ 在 $(1-x)^{-5}$ 中的係數是 $-{\binom {-5}{1}}=5$。因此，不同流派的數量，也就是 $x^{10}$ 在 $G(x)$ 中的係數，是 5。

(d)

證明。 我們回顧生成函式 $G(x)$ 在 (a) 部分：$$G(x)=x^{5}(1-5x^{5}+{\text{terms with order higher than }}x^{5})(1-x)^{-5}.$$ 由於並非所有十個技能點都需要分配，但每個屬性都必須分配至少一個技能點，因此至少分配了 5 個技能點（最多分配 10 個技能點）。因此，我們將考慮所有可能性中構建的數量（分配了 5、6、7、8、9、10 個技能點），並將它們加起來。該數量由生成函式中 $x^{5},x^{6},x^{7},x^{8},x^{9},x^{10}$ 的係數的 和 給出。 $G(x)$。

根據牛頓廣義二項式定理，$$(1-x)^{-5}=(1+5x+15x^{2}+35x^{3}+70x^{4}+126x^{5}+{\text{terms with order higher than }}x^{5}).$$ 因此，生成函式由 $$G(x)=x^{5}(1-5x^{5}+{\text{terms with order higher than }}x^{5})(1+5x+15x^{2}+35x^{3}+70x^{4}+126x^{5}+{\text{terms with order higher than }}x^{5})$$ 因此，係數之和為 $$\underbrace {1\cdot 1} _{x^{5}}+\underbrace {1\cdot 5} _{x^{6}}+\underbrace {1\cdot 15} _{x^{7}}+\underbrace {1\cdot 35} _{x^{8}}+\underbrace {1\cdot 70} _{x^{9}}+\underbrace {121} _{x^{10}{\text{ by (a)}}}=247.$$

$\Box$

練習。 一組 12 人一起去茶館共進午餐。他們點了一系列的 點心 菜餚（一種中國菜），包括：

• 三種不同的 餃子

• 蝦餃
• 燒賣
• 餛飩

• 三種不同的 包點

• 叉燒包
• 奶油包
• 蓮蓉包

• 四種不同的 卷

• 春捲
• 腐皮卷
• 牛肉腸粉
• 蝦腸粉

圓桌。

假設點心菜餚被放置在一個圓桌子上，以圓形排列在十個位置（見下圖），人們圍坐在桌子旁吃這些菜餚。

                                  N
        * * *  *                  ^
      *    1     *              W<+>E
    * 10       2  *               v
   *             3 *              S
   * 9              *
   *              4 *
    *  8        5  *
     *    7  6    *
       * * * *  * 
The region bounded by "*" is the circular table, the numbers indicate the ten dishes.

使用指南針方向（N、E、S、W），十個菜餚的位置和 12 個人的座位都是可區分的。

(a) 以這種方式排列十道菜有多少種不同的方法？

(b) 以這種方式排列 12 人的座位有多少種不同的方法？

(c) 假設三個餃子必須放在一起，三個包點也必須放在一起。但餃子和包點必須分開（即，餃子和包點不能彼此相鄰），用四個卷分開。證明有 25920 種方法可以根據此要求排列十道菜？ (提示: 我們將這種情況說明如下：

                                  N
        * * *  *                  ^
      *    D     *              W<+>E
    * R        D  *               v
   *             D *              S
   * B              *
   *              R *
    *  B        R  *
     *    B  R    *
       * * * *  * 
D: dumpling
B: bun
R: roll
(1 R in the gap "from B to D" (viewed clockwise). The gap "from B to D" is the upper one, and the gap "from D to B" is the lower one.)

除了上面所示的方式外，還有兩種可能的方式可以將餃子和包點分開。確定它們，並計算每種情況下的排列數量。）

解決方案

(a) 方法數為 $10!=3628800$。 (將 10 道不同的菜餚放入 10 個可區分的位置)

(b) 方法數為 $12!=479001600$。 (將 12 個不同的人放置在 12 個可區分的座位上)

(c)

證明。 提示中的圖表顯示了一種將餃子和包點分開的

                                  N
        * * *  *                  ^
      *    R     *              W<+>E
    * R        D  *               v
   *             D *              S
   * B              *
   *              D *
    *  B        R  *
     *    B  R    *
       * * * *  * 
(2 R in the gap "from B to D" (viewed clockwise))

                                  N
        * * *  *                  ^
      *    R     *              W<+>E
    * R        D  *               v
   *             D *              S
   * R              *
   *              D *
    *  B        R  *
     *    B  B    *
       * * * *  * 
(3 R in the gap "from B to D" (viewed clockwise))

這裡，我們逐一考慮三種情況。

情況 1："1 R" 情況。我們首先關注圖中所示的特殊情況。排列數量為 $$\underbrace {3!} _{D}\times \underbrace {4!} _{R}\times \underbrace {3!} _{B}=864.$$ 但我們可以旋轉圓桌，為每個這樣的排列生成 9 個更多 的排列。因此，總數為 $$10\times 864=8640.$$

對於 "2 R" 情況和 "3 R" 情況，情況類似，因此總數也是 8640。這三種情況沒有共同的排列方式。因此，總共有 $8640\times 3=25920$ 種排列。

$\Box$