教程目录
阅读：
全排列及其逆序数
由一个问题引入全排列的概念: 用1，2，3三个数字，可以组成多少个没有重复数字的三位数?
这个问题相当于说，把三个数字分别放在百位、十位与个位上，有几种不同的放法?
显然，百位上可以从 1,2,3 三个数字中任选一个，所以有 3 种放法；十位上只能从剩下的两个数字中选一个，所以有 2 种放法；而个位上只能放最后剩下的一个数字，所以只有 1 种放法。
因此，用 1，2，3 三个数字组成没有重复数字的三位数，共有 3 x 2 x 1 = 6 种放法。这六个不同的三位数分别是: 123，231，312，132，213，321。
在数学中把考察的对象，例如上例中的数字 1，2，3 ，叫做元素。上述问题就可以转换为：把 3 个不同的元素排成一列，共有几种不同的排法?
把 n 个不同的元素排成一列，叫做这 n 个元素的全排列(也简称排列)。
为了得出计算 Pn 的公式，可以仿照引例进行讨论:
从 n 个元素中任取一个放在第一个位置上，有 n 种取法；又从剩下的 n – 1 个元素中任取一个放在第二个位置上，有 n – 1 种取法…这样继续下去，直到最后只剩下一个元素放在第 n 个位置上，只有 1 种取法。于是就有：Pn = n * (n - 1) * … * 3 * 2 * 1 = n! 。
对于 n 个不同的元素，先规定各元素之间有一个标准次序(例如 n 个不同的自然数，可规定由小到大为标准次序)，于是在这 n 个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。
一个排列中所有逆序的总数叫做这个排列的逆序数。逆序数为奇数的排列叫做奇排列，逆序数为偶数的排列叫做偶排列。
全体元素的逆序数之总和：t = t1 + t2 + t3 + … + tn，t 即是这个排列的逆序数。
解:
于是这个排列的逆序数为 t = 0 + 1 + 0 + 3 + 1 = 5 。
这个问题相当于说，把三个数字分别放在百位、十位与个位上，有几种不同的放法?
显然，百位上可以从 1,2,3 三个数字中任选一个，所以有 3 种放法；十位上只能从剩下的两个数字中选一个，所以有 2 种放法；而个位上只能放最后剩下的一个数字，所以只有 1 种放法。
因此，用 1，2，3 三个数字组成没有重复数字的三位数，共有 3 x 2 x 1 = 6 种放法。这六个不同的三位数分别是: 123，231，312，132，213，321。
在数学中把考察的对象，例如上例中的数字 1，2，3 ，叫做元素。上述问题就可以转换为：把 3 个不同的元素排成一列，共有几种不同的排法?
把 n 个不同的元素排成一列，叫做这 n 个元素的全排列(也简称排列)。
逆序数
n 个不同元素的所有排列的种数，通常用 Pn 表示。由引例的结果可知：P3 = 3 * 2 * 1 = 6。为了得出计算 Pn 的公式，可以仿照引例进行讨论:
从 n 个元素中任取一个放在第一个位置上，有 n 种取法；又从剩下的 n – 1 个元素中任取一个放在第二个位置上，有 n – 1 种取法…这样继续下去，直到最后只剩下一个元素放在第 n 个位置上，只有 1 种取法。于是就有：Pn = n * (n - 1) * … * 3 * 2 * 1 = n! 。
对于 n 个不同的元素，先规定各元素之间有一个标准次序(例如 n 个不同的自然数，可规定由小到大为标准次序)，于是在这 n 个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。
一个排列中所有逆序的总数叫做这个排列的逆序数。逆序数为奇数的排列叫做奇排列，逆序数为偶数的排列叫做偶排列。
逆序数的计算
设 n 个元素为 1 至 n 这 n 个自然数，并规定由小到大为标准次序。设 p1p2…pn 为这 n 个自然数的一个排列，考虑元素 pi (i = 1，2，...，n)，如果比 pi 大的且排在 pi 前面的元素有 ti 个，就说 Pi 这个元素的逆序数是 ti 。全体元素的逆序数之总和：t = t1 + t2 + t3 + … + tn，t 即是这个排列的逆序数。
实例讲解
求排列 32514 的逆序数。解:
在排列32514中：
3 排在首位，逆序数为0;
2 的前面比 2 大的数有一个 (3)，故逆序数为 1;
5 是最大数，逆序数为0;
1 的前面比 1 大的数有三个 (3,2,5)，故逆序数为 3;
4 的前面比 4 大的数有一个 (5)，故逆序数为 1。
3 排在首位，逆序数为0;
2 的前面比 2 大的数有一个 (3)，故逆序数为 1;
5 是最大数，逆序数为0;
1 的前面比 1 大的数有三个 (3,2,5)，故逆序数为 3;
4 的前面比 4 大的数有一个 (5)，故逆序数为 1。
于是这个排列的逆序数为 t = 0 + 1 + 0 + 3 + 1 = 5 。