置換

维库，知识与思想的自由文库

置換或排列是將相異物件或符號根據確定的順序重排。每個順序都稱作一個置換 ^[1]。例如，從一到六的數字有 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$ 個相異元素中取出 $r$ 個元素並加以排序的可能方式。所有可能的置換數為：

$P_r^n = \frac{n!}{(n-r)!}$

其中：

r 是每個置換的長度，
n 是所置換的元素數量，而
! 表階乘運算。

例一：假設我們有 10 個元素，即整數 {1,2,...,10}，並考慮從中取出 3 個元素的所有可能性（含順序），此時須取 $n = 10, r = 3$ ，並計算

$P_r^n = \dfrac{10!}{(10-3)!} = \dfrac{10 \cdot 9 \cdot \cdots 1}{7 \cdot 6 \cdot \cdots 1} = 10 \cdot 9 \cdot 8 = 720$

例二：從 {1, ..., 6} 取出 6 個元素（含順序），也就是將數字 1 到 6 重新排序的方式共有

$P^6_6 = \dfrac{6!}{(6-6)!} = \dfrac{6!}{0!} = 720/1 = 720$

其它較舊的記法包括 ⁿP_r, P_n,r 或 _nP_r。

[编辑] 抽象觀點

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

[编辑] 符號

更多資料：對稱群

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

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

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

表示集合 {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(x))$ ，其中 $s m (x)$ 是滿足 $s^m(x) \neq 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)$ 理解為一類特殊的置換^[2]：僅須定義置換 $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)。

[编辑] 特殊置換

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

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

[编辑] 計算理論中的置換

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

1, 2, ..., n

賦予變數

x₁, x₂, ..., x_n.

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

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

[编辑] 使用計算機

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

[编辑] 試算表語法

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

[编辑] 參考資料

↑ 對於不排序的情形，請見條目組合。
↑ 可遞置換

[编辑] 參考文獻

Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 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 0-201-85393-0.
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.

[编辑] 外部連結

来自“http://www.wikilib.com/wiki/%E7%BD%AE%E6%8F%9B”

个人工具

置換