置換和排列

置換

一個有限集合 \(S\) 到自身的雙射（即一一對應）稱為 \(S\) 的一個置換。集合 \(S=\{a_1,a_2,\dots,a_n\}\) 上的置換可以表示為

\[ f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix} \]

意為將 \(a_i\) 映射為 \(a_{p_i}\)，其中 \(p_1,p_2,\dots,p_n\) 是 \(1,2,\dots,n\) 的一個排列。顯然 \(S\) 上所有置換的數量為 \(n!\)。

乘法

對於兩個置換 \(f=\begin{pmatrix}a_1,a_2,\dots,a_n\\a_{p_1},a_{p_2},\dots,a_{p_n}\end{pmatrix}\) 和 \(g=\begin{pmatrix}a_{p_1},a_{p_2},\dots,a_{p_n}\\a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix}\)，\(f\) 和 \(g\) 的乘積記為 \(g\circ f\)，其值為

\[ g\circ f=\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_{q_1},a_{q_2},\dots,a_{q_n}\end{pmatrix} \]

簡單來説就是先經過 \(f\) 的映射，再經過 \(g\) 的映射。

排列

設 \(I=\{1,2,\cdots,n\}\) 是前 \(n\) 個正整數構成的集合，\(\sigma\) 是 \(I\) 的一個置換。記：

\[ \sigma(1)=i_1\quad\sigma(2)=i_2\quad\cdots\quad\sigma(n)=i_n \]

於是 \(i_1,i_2,\cdots,i_n\) 仍然為 \(1,2,\cdots,n\) 這 \(n\) 個數，只是順序有所不同。

由 \(1,2,\cdots,n\) 組成的一個有序組，稱為 \(1,2,\cdots,n\) 的一個排列。例如把前文 \(i_1,i_2,\cdots,i_n\) 叫做 \(1,2,\cdots,n\) 的一個排列。

前 \(n\) 個正整數 \(1,2,\cdots,n\) 的不同排列共有 \(n!\) 個。

逆序和逆序數

在一個排列中，如果某一個較大的數排在某一個較小的數前面，就説這兩個數構成一個反序或逆序。

在一個排列裏出現的反序的總個數，叫做這個排列的反序數或逆序數。

一個排列的反序數可能是偶數也可能是奇數。有偶數個反序的排列叫做一個偶排列，有奇數個反序的排列叫做一個奇排列。

對換

如果把 \(1,2,\cdots,n\) 的排列中，任意兩個數 \(i\) 和 \(j\) 交換，其餘數保持不動，就得到一個新排列。對於排列施加這樣一個變換叫做一個對換，用 \((i,j)\) 表示。

定理：設 \(i_1i_2\cdots i_n\) 和 \(j_1j_2\cdots j_n\) 是 \(n\) 個數碼的任意兩個排列，那麼總可以通過一系列對換，由 \(i_1i_2\cdots i_n\) 得出 \(j_1j_2\cdots j_n\)。

定理：每一個對換都改變排列的奇偶性。

定理：當 \(n\) 至少為 \(2\) 時，\(n\) 個數碼的奇排列與偶排列個數相等，各為 \(\frac{n!}{2}\) 個。

逆序數的計算方法

逆序數的編程計算方法，可以使用歸併排序，時間複雜度為 \(O(n\log n)\)。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用