第2章組合學 - 第1節排列

第 2 章組合學

087

1 排列

1.1 重複排列

只用 1, 2 這兩個數字可以構成多少個 3 位數呢？當然，此時可以像 111, 222 那樣重複使用相同的數字。這類問題如果隨意嘗試，很容易重複計算或有所遺漏，因此最好採用系統性的方法來解決。

如圖 2-1 所示的圖稱為樹狀圖 (tree)，在思考這類問題時非常方便。

樹狀圖從左向右分枝展開，每次的分枝數都是 2。因為這樣的分枝發生了 3 次，所以最後的枝枒數量為

$$ 2 \cdot 2 \cdot 2 = 2^3 = 8 $$

在 $2^3$ 這個數中，從圖 2-1 可以看出，3 是空格子的數量，而 2 是放入格子中的物品——在此情況下是數字——的個數。

如果不是只用 1, 2 這兩個數字，而是可以使用 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 這全部 10 個數字的話，那麼 3 位數

088

圖 2-1

的總數為

$$ 10^3 = 1000 $$

となる。ただし、2桁の35も電話番号式に035 と書くことにとなります。ただし、2 桁の数 35 も電話番号のように 035 と書くこととします。

例題 1

從 26 個英文字母中取出 3 個字母來排列，總共有多少種排列方式（順序）？

解：

這相當於將 26 個字母放入 3 個箱子中，因此

$$ 26^3 = 17576 $$

一般而言，當箱子的數量為 $m$，而要放入箱中的物品數量為 $n$ 時，排列的總數為

$$ n^m $$

089

這種允許重複使用放入物品的排列，稱為重複排列。

例題 2

由奇數數字構成的 3 位數有多少個？

解：

因為是 3 位數，所以箱子的數量為 3 個。奇數數字有 1, 3, 5, 7, 9，共 5 個，因此

$$ 5^3 = 125 $$

個。

重複排列發生在像活字印刷那樣，同一個物件可以無限制地重複使用的情況。

例題 3

一個包含 $n$ 個元素的集合，其所有子集合的個數為 $2^n$。

解：

取一個子集合 A，對於全體集合中的任一元素 $a$，它要嘛屬於子集合 A，要嘛不屬於。當它屬於時，我們在該元素上標記 ○；不屬於時則標記 ×。這樣一來，為全體集合的所有元素標上 ○ 或 × 的方式，與子集合 A 之間就存在一對一的對應關係。

○ × ○ ○ ⋯ ○

1, 2, 3, 4, ⋯, n

如此一來，問題就轉變為求在 $1, 2, 3, \dots, n$ 這些箱子中，放入 ○ 或 × 這兩種物品的所有可能方式的數量。

090

圖 2-2

這個樹狀圖，如圖 2-2 所示，在每個節點都分岔為 2 支，因此，放入 ○× 的方法數，也就是子集合的個數為 $2^n$ 個。

1.2 排列

接下來，讓我們對允許任意重複的重複排列，加上更嚴格的條件，即「不允許重複」，看看會發生什麼情況。

例如，有 5 張標有 1, 2, 3, 4, 5 的椅子，現在有 2 位背號分別為 1 和 2 的人要入座。請問總共有多少種坐法？

我們可以把問題想成是分發座位指定券 1 2 3 4 5 。這時，把 2 個人看作是空箱子，然後將指定券放入其中，問題的本質是相同的。

第 1 個箱子可以自由地放入從 ① 到 ⑤ 的任一張指定券。對於第 2 個箱子，由於有「不允許重複」的條件...

091

圖 2-3

092

...放入第 1 個箱子的號碼就不能再放入了，所以只剩下 4 張可選。

畫出樹狀圖，就會如圖 2-3 所示。觀察圖 2-3，最左邊的券數有 5 種選擇，接下來有 4 種，因此

$$ 5 \times 4 = 20 $$

種。

例題 4

4 個人坐 10 張椅子，有多少種坐法？

解：

$$ 10 \times 9 \times 8 \times 7 = 5040 $$

一般而言，將 $n$ 個相異物不重複地分配到 $m$ 個位置的方法數為

$$ n(n-1)\cdots(n-m+1) $$

這個數記為 $_nP_m$。

$$ _nP_m = n(n-1)\cdots(n-m+1) $$

特別地，當 $n=m$ 時，這是將 $n$ 個物品排成一列的方法數，為

$$ _nP_n = n(n-1)\cdots2\cdot1 $$

這個數用 $n!$ 表示，稱為 $n$ 的階乘。

使用階乘的符號，排列數 $_nP_m$ 可以在分子和分母同乘以 $(n-m)!$

093

$$ _nP_m = \frac{n(n-1)\cdots(n-m+1)(n-m)!}{(n-m)!} = \frac{n!}{(n-m)!} $$

可以改寫成這樣。

1.3 $n!$ 的意義

$n$ 的階乘，也就是將從 1 到 $n$ 的所有整數相乘：

$$ 1 \cdot 2 \cdot 3 \cdots n = n! $$

這個數是數學中各種場合都會出現的重要符號。當 $n$ 確定時，$n!$ 也隨之確定，因此也可以說這是 $n$ 的一個函數。我們現在將其表示為

$$ f(n) = n! $$

因為 $n! = n \cdot (n-1) \cdots 2 \cdot 1 = n \cdot (n-1)!$，所以這個函數 $f$ 滿足以下關係：

$$ f(n) = nf(n-1) \quad (n \ge 2) \quad \cdots(1) $$

像這樣，將整數 $n$ 的函數值用比 $n$ 小的 $n-1, n-2, \dots$ 的值來表示的式子，稱為該函數的遞迴式。

如果存在一個滿足遞迴式 (1) 的函數 $f$，我們可以依序使用它：

$$ \begin{align*} f(n) &= nf(n-1) \\ &= n(n-1)f(n-2) \\ \end{align*} $$

094

$$ \cdots\cdots\cdots\cdots \\ = n(n-1)\cdots2 \cdot f(1) $$

因此，只要確定了初始值

$$ f(1) = 1 \quad \cdots(2) $$

就能得到 $f(n) = n(n-1)\cdots2 \cdot 1 = n!$。這個最初的值稱為初始值。

換句話說，階乘函數完全由遞迴式 (1) 和初始值 (2) 所確定。

此外，如果我們假設遞迴式 (1) 在 $n=1$ 時也成立，則

$$ 1 = f(1) = 1 \cdot f(0) $$

要使此式成立，必須有

$$ f(0) = 0! = 1 $$

如此一來，遞迴式 (1) 對於 $n \ge 1$ 均有效，而初始值也可以從 $n=0$ 開始。

例題 5

證明以下等式。

$$ n! = (n-1)((n-1)! + (n-2)!) $$

解：

$$ \begin{align*} (n-1)((n-1)! + (n-2)!) &= (n-1)(n-1)! + (n-1)(n-2)! \\ &= (n-1)(n-1)! + (n-1)! \\ &= ((n-1)+1)(n-1)! \\ &= n \cdot (n-1)! = n! \end{align*} $$

這個式子是從 $(n-1)!$ 和 $(n-2)!$ 計算出 $n!$ 的公式，因此也算是一種遞迴式。

095

1.4 含有相同物的排列

現在，假設有 2 個字母 $a_1$，1 個 $a_3$，3 個 $a_4$，和 2 個 $a_6$。將這些字母排成一列的排列方式有多少種呢？這樣的排列方式稱為含有相同物的排列。

為了求出這種排列的數量，我們先假設所有相同的字母都是不同的。我們將它們命名為：$a_1, a_1$ 變成 $a_1', a_1''$；$a_4, a_4, a_4$ 變成 $a_4', a_4'', a_4'''$；$a_6, a_6$ 變成 $a_6', a_6''$。如此一來，這個排列就變成了

$$ 2+1+3+2 = 8 \text{ (個)} $$

相異字母的排列，其總數為 $8!$。

然而，實際上因為有相同的字母存在，在這些排列中會出現相同的排列方式。我們要求的排列數會比 $8!$ 少。讓我們將所求的排列數設為 $k$。

直接計算會產生多少相同的排列是很麻煩的。因此，我們反過來思考：需要將所求的排列數 $k$「膨脹」多少倍，才會得到總數 $8!$？

對於這 $k$ 個排列中的每一個，首先將 2 個 $a_1$ 區分為 $a_1', a_1''$，會產生 $2!$ 種不同的排列。接著，對於其中的每一種排列，再將 3 個 $a_4$ 區分為 $a_4', a_4'', a_4'''$，其排列數會變為 $3!$ 倍。更進一步，對於每一種結果，再將 2 個 $a_6$ 區分為 $a_6', a_6''$，會產生 $2!$ 種不同的排列。例如：

096

$a_1 a_1 a_3 a_4 a_4 a_4 a_6 a_6$

$a_1' a_1'' a_3 a_4' a_4'' a_4''' a_6' a_6''$

$a_1' a_1'' a_3 a_4' a_4'' a_4''' a_6'' a_6'$

..................

$a_1'' a_1' a_3 a_4''' a_4' a_4'' a_6'' a_6'$

..................

如此一來，從 $k$ 個所求排列的每一個，可以產生

$$ 2! \times 1! \times 3! \times 2! $$

種不同的排列。將這些全部加總起來，就能得到 8 個相異字母的所有排列。因此，

$$ k \times 2! \times 1! \times 3! \times 2! = 8! $$

所以

$$ k = \frac{8!}{2! \times 1! \times 3! \times 2!} $$

在上例中，雖然沒有包含字母 $a_2, a_5$，但我們可以將它們視為各有 0 個，並將此概念推廣如下。

一般而言，在 $n$ 個文字中，若有 $k_1$ 個、$k_2$ 個、...、$k_m$ 個分別為相同的文字，則這些文字的排列數為

$$ k = \frac{n!}{k_1! k_2! \cdots k_m!} $$

其中，$k_1 + k_2 + \cdots + k_m = n$，且 $k_1, k_2, \dots, k_m$ 中可以包含 0。

宇宙數學教室