一、置換

一個(gè)有限集合S到自身的雙射（即一一對應(yīng)）稱為S的一個(gè)置換。集合上的置換可以表示為

意為將映射為，其中是1,2，…，n的一個(gè)排列。顯然S上所有置換的數(shù)量為n!。

乘法

對于兩個(gè)置換和 ，f 和 g 的乘積記為，其值為

簡單來說就是先后經(jīng)過 f 的映射，再經(jīng)過 g 的映射。

二、排列

設(shè)是前 n 個(gè)正整數(shù)構(gòu)成的集合，是I的一個(gè)置換。記：

于是仍然為1,2，…，n這 n 個(gè)數(shù)，只是順序有所不同。

由1,2，…，n組成的一個(gè)有序組，稱為1,2，…，n的一個(gè)排列。例如把前文叫做1,2，…，n的一個(gè)排列。

前 n 個(gè)正整數(shù)1,2，…，n的不同排列共有 n! 個(gè)。

（1）逆序和逆序數(shù)

在一個(gè)排列中，如果某一個(gè)較大的數(shù)排在某一個(gè)較小的數(shù)前面，就說這兩個(gè)數(shù)構(gòu)成一個(gè)反序或逆序。

在一個(gè)排列里出現(xiàn)的反序的總個(gè)數(shù)，叫做這個(gè)排列的反序數(shù)或逆序數(shù)。

一個(gè)排列的反序數(shù)可能是偶數(shù)也可能是奇數(shù)。有偶數(shù)個(gè)反序的排列叫做一個(gè)偶排列，有奇數(shù)個(gè)反序的排列叫做一個(gè)奇排列。

（2）對換

如果把1,2，…，n的排列中，任意兩個(gè)數(shù) i 和 j 交換，其余數(shù)保持不動(dòng)，就得到一個(gè)新排列。對于排列施加這樣一個(gè)變換叫做一個(gè)對換，用 (i,j) 表示。

定理：設(shè)和是 n 個(gè)數(shù)碼的任意兩個(gè)排列，那么總可以通過一系列對換，由 得出。

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

定理：當(dāng) n 至少為 2 時(shí)，n 個(gè)數(shù)碼的奇排列與偶排列個(gè)數(shù)相等，各為個(gè)。

（3）逆序數(shù)的計(jì)算方法

逆序數(shù)的編程計(jì)算方法，可以使用歸并排序，時(shí)間復(fù)雜度為。