排列与逆序

出处：按学科分类—数理科学和化学 清华大学出版社《数学手册（大学生用）》第255页（798字）

排列 n个不同的元素排成一列，叫做这n个元素的全排列(简称n元排列)．

例如，由n个自然数1，2，…，n组成的一个有序数组称为一个n元排列．

n个不同元素所有排列的种数为n!种．

排列的逆序、逆序数 对于n个不同的元素．我们规定各元素之间有一个标准次序．对这n个元素的任一排列中，当某两个元素的先后次序与标准次序不相同时，就称这两个元素构成一个逆序，一个排列中所有逆序的总数称为这个排列的逆序数．

例如，n个不同的自然数1，2，…，n，可规定由小到大为标准次序，且排列123…n称为自然序排列．在某个排列中，一对数若较大的数排在较小的数之前，就称这对数构成一个逆序．

奇排列、偶排列 逆序数是偶数的排列称为偶排列，逆序数是奇数的排列称为奇排列．

对换、相邻对换 在排列中，将任意两个元素对调，其余元素不动，得到另一个排列，这样一种变换称为对换，将两个相邻元素对换称为相邻对换．

对换改变排列的奇偶性 对换改变排列的奇偶性，即偶排列经一次对换变成奇排列，奇排列经一次对换变成偶排列．

全部n元排列(共n!种)中，奇排列、偶排列各占一半，都有n!／2种(n≥2)．

化标准排列所用对换次数 任一个n元排列都可以通过一系列的对换化成标准排列．其中奇排列化成标准排列的对换次数是奇数，偶排列化成标准排列的对换次数是偶数．