同济大学线性代数 1-2 全排列及其逆序数

§2

全排列及其逆序数

引例 用1、2、3三个数字，可以组成多少个没 有重复数字的三位数？ 解百位 十位 个位

1 1 1 2

2

3 33种放法 2种放法 1种放法

21 3

1 2 3共有 3 2 1 6

种放法.

问题 把 n 个不同的元素排成一列，共有多少种不同的 排法？定义 把 n 个不同的元素排成一列，叫做这 n 个元素 的全排列. n 个不同元素的所有排列的种数，通常用 Pn 表示.

显然

Pn n ( n 1) ( n 2 ) 3 2 1 n !

即n 个不同的元素一共有n! 种不同的排法.

3个不同的元素一共有3! =6种不同的排法

123,132,213,231,312,321 所有6种不同的排法中，只有一种排法 (123)中的数字是按从小到大的自然 顺序排列的，而其他排列中都有大的 数排在小的数之前.因此大部分的排列都不是“顺序”, 而是“逆序”.

对于n 个不同的元素，可规定各元素之间的标准次序.n 个不同的自然数，规定从小到大为标准次序. 定义 当某两个元素的先后次序与标准次序不同时， 就称这两个元素组成一个逆序. 例如 在排列32514中， 逆序 3 2 5 1 4 逆序 逆序

思考题：还能找到其它逆序吗？

答：2和1,3和1也构成逆序.

定义 排列中所有逆序的总数称为此排列的逆序数.

排列 i1 i 2 i n的逆序数通常记为 t ( i1 i 2 i n ) .奇排列：逆序数为奇数的排列. 偶排列：逆序数为偶数的排列. 思考题：符合标准次序的排列是奇排列还是偶排列？

答：符合标准次序的排列(例如：123)的逆序数等于零，因而是偶排列.

计算排列的逆序数的方法设 p1 p 2 p n 是 1, 2, …, n 这n 个自然数的任一排列，并规定由小到大为标准次序. 先看有多少个比 p 1 大的数排在 p 1 前面，记为 t 1 ; 再看有多少个比 p 2 大的数排在 p 2 前面，记为 t 2 ; …… 最后看有多少个比 p n 大的数排在 p n 前面，记为 t n ; 则此排列的逆序数为 t t 1 t 2 t n

例1:解：

求排列 32514 的逆序数.t (32514) 0 1 0 3 1 5

练习：

求排列 453162 的逆序数.t 9

解：