一、置换
一个有限集合S到自身的双射（即一一对应）称为S的一个置换。集合
上的置换可以表示为
意为将
映射为
，其中
是1,2，…，n的一个排列。显然S上所有置换的数量为n!。
乘法
对于两个置换
和
，f 和 g 的乘积记为
，其值为
简单来说就是先后经过 f 的映射，再经过 g 的映射。
二、排列
设
是前 n 个正整数构成的集合，
是I的一个置换。记：
于是
仍然为1,2，…，n这 n 个数，只是顺序有所不同。
由1,2，…，n组成的一个有序组，称为1,2，…，n的一个排列。例如把前文
叫做1,2，…，n的一个排列。
前 n 个正整数1,2，…，n的不同排列共有 n! 个。
（1）逆序和逆序数
在一个排列中，如果某一个较大的数排在某一个较小的数前面，就说这两个数构成一个反序或逆序。
在一个排列里出现的反序的总个数，叫做这个排列的反序数或逆序数。
一个排列的反序数可能是偶数也可能是奇数。有偶数个反序的排列叫做一个偶排列，有奇数个反序的排列叫做一个奇排列。
（2）对换
如果把1,2，…，n的排列中，任意两个数 i 和 j 交换，其余数保持不动，就得到一个新排列。对于排列施加这样一个变换叫做一个对换，用 (i,j) 表示。
定理：设
和
是 n 个数码的任意两个排列，那么总可以通过一系列对换，由
得出
。
定理：每一个对换都改变排列的奇偶性。
定理：当 n 至少为 2 时，n 个数码的奇排列与偶排列个数相等，各为个
。
（3）逆序数的计算方法
逆序数的编程计算方法，可以使用归并排序，时间复杂度为
。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程