1.2.2　逆序的概念

1.2.2　逆序的概念

例1.2.1　写出自然数1,2,3构成的所有排列.

解　1,2,3构成的所有排列:123,132,213,231,312,321.

对于n个不同的元素,先规定各元素之间有一个标准次序(例如n个不同的自然数,可规定由小到大为标准次序).

定义1.2.2　在一个排列中,如果一对数的前后位置与标准次序相反,那么这一对数就构成一个逆序,一个排列中逆序的总数就称为这个排列的逆序数.

一个排列j1j2…jn的逆序数记为t(j1j2…jn).

例1.2.2　计算下列各排列的逆序数.

(1)t(4231);　(2)t(312).

解　(1)由于排列4231中只有42、43、41、21和31构成逆序,因此t(4231)=5.

(2)由于排列312中只有31和32构成逆序,因此t(312)=2.

定义1.2.3　逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列.

例如,4231是奇排列,312是偶排列.