1-2 全排列及其逆序数

1-2 全排列及其逆序数

1-2 全排列及其逆序数

一、概念的引入引例 用1、2、3三个数字，可以组成多少个互不 相同的三位数？ 解3种放法

设2种放法

是一个三位数字，1种放法

百位上可以从1 2 3三个数字中任选一个，所以有3种放法 十位上只能从剩下的两个数字中任选一个，所以有2种放法 而个位上只能放最后剩下的一个数字，所以只有1种放法 共有 3 2 1 6 种放法. 这6个不同的3位数是

123 231 312 132 213 321

1-2 全排列及其逆序数

二、全排列及其逆序数,共有几种不 问题 把 n 个不同的元素排成一列 同的排法？ n ( n 1) ( n 2) 3 2 1 n!

n 个不同的元素的所有排列的种数，通常用 Pn 表示.那么 Pn n (n 1) (n 2) 3 2 1 n! 同理引例 P3 3 2 1 3! 1. 全排列 定义

把 n 个不同的元素排成一列，叫做这 n 个 元素的全排列(或排列).

1-2 全排列及其逆序数

2. 逆序、逆序数我们规定各元素之间有一个标准次序, n 个 不同的自然数，规定由小到大为标准次序.

定义例如

在一个排列 i1i2 it is in 中，若数 it i s 则称这两个数组成一个逆序. 排列32514 中， 逆序

3 2 5 1 4 逆序 逆序 定义 一个排列i1i2…in中所有逆序的总数称为此 排列的逆序数.记作 t (i1i2…in)或简记为t

1-2 全排列及其逆序数

计算排列逆序数的方法分别计算出排列中每个元素前面比它大的 数字个数之和. 例4 解 求排列32514的逆序数.

在排列32514中,3 2 5 1 4 0 1 0 3 1

于是排列32514的逆序数为

t 0 1 0 3 1 5.

1-2 全排列及其逆序数

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

1 解

217986354

2 1 7 9 8 6 3 5 4

(由后向前求每个数的逆序数.)

0 10 0 1 3 4 4 5t 5 4 4 3 1 0 0 1 0

18

1-2 全排列及其逆序数

2 n n 1 n 2 321解

n 1 n n 1 n 2 321 t n 1 n 2 2 1

n 2

n n 1 , 2

1-2 全排列及其逆序数

3. 排列的奇偶性逆序数为奇数的排列称为奇排列;逆序数为偶数的排列称为偶排列. 在前面例4中t(32514)=5, 故此排列为奇排列. 而t(217986354)=18,故此排列为偶排列.

1-2 全排列及其逆序数

三、小结1.全排列2.逆序、逆序数

3.排列的奇偶性.