置换

**排列**（英語：Permutation）是將相異物件或符號根據確定的順序重排。每個順序都稱作一個**置換**或**排列**。例如，從一到六的數字有 720 種排列，對應於由這些數字組成的所有不重複亦不闕漏的序列，例如 "4, 5, 6, 1, 2, 3" 與 _1, 3, 5, 2, 4, 6_。

置換（排列）的廣義概念在不同語境下有不同的形式定義：

* 在集合論中，一個集合的置換是從該集合映至自身的對射；在有限集的情況，便與上述定義一致。
* 在組合數學中，置換一詞的傳統意義是一個有序序列，其中元素不重複，但可能有闕漏。例如 _1,2,4,3_ 可以稱為 _1,2,3,4,5,6_ 的一個置換，但是其中不含 _5,6_。此時通常會標明為「從 n 個對象取 r 個對象的置換」。

## 置換數的計算

此節使用置換的傳統定義。從 $n$ 個相異元素中取出 $k$ 個元素， $k$ 個元素的排列數量為：

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

其中 **P** 意為 Permutation（排列），**!**表示階乘運算。

以賽馬為例，有 8 匹馬參加比賽，玩家需要在彩票上填入前三勝出的馬匹的號碼，從 8 匹馬中取出 3 匹馬來排前 3 名，排列數量為：

　
: $P_{3}^{8}={\frac {8!}{(8-3)!}}=336$

因為一共存在 336 種可能性，因此玩家在一次填入中中獎的機率應該是：

　
: $P={\frac {1}{336}}=0.00298$

不過，中國大陸的教科書則是把從 n 取 k 的情況記作 $P_{n}^{k}$ 或 $A_{n}^{k}$ （A 代表 Arrangement，即排列）。

## 重複置換

上面的例子是建立在取出元素不重複出現狀況。

從 $n$ 個元素中取出 $k$ 個元素， $k$ 個元素可以重複出現，這排列數量為：

　
: $U_{k}^{n}=n^{k}$

以四星彩為例，10 個數字取 4 個數字，因可能重複所以排列數量為：

　
: $U_{4}^{10}=10^{4}=10000$

這時的一次性添入中獎的機率就應該是：

　
: $P={\frac {1}{10000}}=0.0001$

## 抽象代數

在集合論與抽象代數等領域中，「置換」一詞被保留為集合（通常是有限集）到自身的對射的一個稱呼。例如對於從一到十的數字構成的集合，其置換將是從集合 $\{1,\ldots ,10\}$ 到自身的對射。因此，置換是擁有相同定義域與對應域的函數，且其為對射的。一個集合上的置換在函數合成運算下構成一個群，稱為對稱群或置換群。

## 符號

以下僅考慮有限集上的置換（視為對射），由於 $n$ 個元素的有限集可以一一對應到集合 $\{1,\ldots ,n\}$ ，有限集的置換可以化約到形如 {1, ..., n} 的集合之置換。此時有兩種表示法。

第一，利用矩陣符號將_自然_排序寫在第一列，而將置換後的排序寫在第二列。例如：

　
: ${\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}$

表示集合 {1,2,3,4,5} 上的置換 $s:s(1)=2,s(2)=5,s(3)=4,s(4)=3,s(5)=1$ 。

第二，藉由置換的相繼作用描述，這被稱為「輪換分解」。分解方式如下：固定置換 $s$ 。對任一元素 $x$ ，由於集合有限而 $s$ 是對射，必存在正整數 $N$ 使得 $s^{N}(x)=x$ ，故可將置換 $s$ 對 $x$ 的相繼作用表成 $(x\;s(x)\;s^{2}(x)\cdots s^{m-1}(x))$ ，其中 $m$ 是滿足 $s^{m}(x)=x$ 的最小正整數。

稱上述表法為 $x$ 在 $s$ 下的**輪換**， $m$ 稱為輪換的**長度**。我們在此將輪換視作環狀排列，例如

　
: $(a_{1}\;a_{2}\;a_{3}\cdots a_{m})$ 與

　
: $(a_{m}\;a_{1}\;a_{2}\cdots a_{m-1})$

是同一個輪換。由此可知 $x$ 在 $s$ 下的**輪換**只決定於 $x$ 在 $s$ 作用下的軌道，於是，任兩個元素 $x,y$ 或給出同一個輪換，或給出不交的輪換。

我們將輪換 $(x_{1}\;\cdots x_{m})$ 理解為一類特殊的置換：僅須定義置換 $s$ 為 $s:x_{1}\mapsto x_{2},\ldots ,x_{m-1}\mapsto x_{m},x_{m}\mapsto x_{1}$ ，而在其它元素上定義為恆等映射。不交的輪換在函數合成的意義下可相交換。

因此我們可以將集合 {1, ..., n} 對一置換分解成不交輪換的合成，此分解若不計順序則是唯一的。例如前一個例子的 $s$ 就對應到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。

## 輪換

輪換一是種特殊的置換。

如果給定 $f:X\rightarrow X$ 是 $X$ 上的一個置換， $A$ 為 $X$ 上的一個子集。

若有

$$
\exists A\subset X,A=\{x_{1},x_{2},\cdots ,x_{l}\}
$$

$$
{\begin{cases}f(x_{1})=x_{2},f(x_{2})=x_{3},\cdots ,f(x_{l})=x_{1}\\f(x)=x,x\not \in A\end{cases}}
$$

則稱 $f$ 為一個輪換。 $l$ 為輪換的長度。

## 特殊置換

在上節的置換表法中，長度等於二的環狀置換稱為**換位**，這種環狀置換 $(x\;y)$ 不外是將元素 $x,y$ 交換，並保持其它元素不變。對稱群可以由換位生成。

由於環狀置換長度為 $l$ 的置換 $C$ 可分解為最少 $k=l-1$ 個換位，若 $k$ 為偶數，則 $C$ 為**偶換位**，否則 $C$ 為**奇換位**。即環狀置換的長度為奇數，該置換為**偶換位**；環狀置換的長度為偶數，該置換為**奇換位**。

由此可定義任一置換的奇偶性，並可證明：一個置換是偶換位的充要條件是它可以由偶數個換位生成。偶換位在置換群中構成一個正規子群，稱為交錯群。

## 計算理論中的置換

某些舊課本將置換視為變數值的_賦值_。在計算機科學中，這就是將值

　
: 1, 2, ..., _n_

賦予變數

　
: _x_1, _x_2, ..., _x_n

的賦值運算子，並要求每個值只能賦予一個變數。

賦值 / 代入的差別表明函數式編程與指令式編程之差異。純粹的函數式編程並不提供賦值機制。現今數學的慣例是將置換看作函數，其間運算看作函數合成，函數式編程也類似。就賦值語言的觀點，一個代入是將給定的值「同時」重排，這是個有名的問題。

## 置換圖

取一個無向圖 _G_，將圖 _G_ 的 _n_ 個頂點標記 _v_1,...,_v_n，對應一個置換 (s (1) s (2) ... s (_n_) )，若且唯若 s (_i_) < s(_j_) 而 _i_ > _j_，則圖的 _v_i 和 _v_j 相連，這樣的圖稱為置換圖。

置換圖的補圖必是置換圖。

## 使用計算器

多數計算器都有個計算置換數的 _nPr_ 鍵。然而此鍵在一些最先進的桌上型機種中卻被隱藏了。例如：在 TI-83 中，按 MATH、三次右鍵、再按二。在卡西歐的圖形計算機中，按 OPTN，一次右鍵（F6）、PROB（F3）、nPr（F2）。

## 試算表語法

多數試算表軟體都有函式 PERMUT (_Number_，_Number chosen_)，用以計算置換。_Number_ 是描述物件數量的一個整數，_Number chosen_ 是描述每個置換中所取物件數的整數。

## C++ 演算範例

### 迴圈法

### 遞迴法

## python 演算範例

## 注釋

## 參考文獻

* Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 978-1-58488-434-7.
* Donald Knuth. _The Art of Computer Programming_, Volume 4: _Generating All Tuples and Permutations_, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 978-0-201-85393-3.
* Donald Knuth. _The Art of Computer Programming_, Volume 3: _Sorting and Searching_, Second Edition. Addison-Wesley, 1998. ISBN 978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.

## 外部連結

* 許多排列組合問題，附詳解。 （頁面存檔備份，存於網際網路檔案館）（英文）
* 置換及圖論問題 （頁面存檔備份，存於網際網路檔案館）（英文）