一、概念的引入引例 用 1,2,3三个数字,可以组成多少个没有重复数字的三位数?
解 1 2 3
1 2 3百位 3种放法十位 1 2 31
个位 1 2 3
2种放法
1种放法种放法,共有 6123
二、全排列及其逆序数同的排法?
,共有几种不个不同的元素排成一列把 n问题定义 把 个不同的元素排成一列,叫做这 个元素的全排列(或排列),
n n
个不同的元素的所有排列的种数,通常用 表示,
n
nP
由引例 1233P,6?
nPn? )1( n )2( n 123 !.n?同理在一个排列 中,若数则称这两个数组成一个逆序,
nst iiiii21
st ii?
例如 排列 32514 中,
定义我们规定各元素之间有一个标准次序,n 个不同的自然数,规定由小到大为 标准次序,
排列的逆序数
3 2 5 1 4
逆序逆序逆序定义 一个排列中所有逆序的总数称为此排列的逆序数,
例如 排列 32514 中,
3 2 5 1 4
逆序数为 31
0 10
故此排列的逆序数为 3+1+0+1+0=5.
计算排列逆序数的方法方法 1
分别计算出排在 前面比它大的数码之和即分别算出 这 个元素的逆序数,这个元素的逆序数的总和即为所求排列的逆序数,
n,n,,,121
n,n,,,121 n
逆序数为奇数的排列称为 奇排列 ;
逆序数为偶数的排列称为 偶排列,
排列的奇偶性分别计算出排列中每个元素前面比它大的数码个数之和,即算出排列中每个元素的逆序数,
这每个元素的逆序数之总和即为所求排列的逆序数,
方法 2
例 1 求排列 32514的逆序数,
解 在排列 32514中,
3排在首位,逆序数为 0;
2的前面比 2大的数只有一个 3,故逆序数为 1;
3 2 5 1 4
0 1 0 3 1
于是排列 32514的逆序数为
13010t,5?
5的前面没有比 5大的数,其逆序数为 0;
1的前面比 1大的数有 3个,故逆序数为 3;
4的前面比 4大的数有 1个,故逆序数为 1;
例 2 计算下列排列的逆序数,并讨论它们的奇偶性,
2179863541
解 453689712
544310010
t
18?
此排列为 偶排列,
5 4? 0100134
3 2 1212 nnn

12
,
2
1 nn
当 时为偶排列; 14,4 kkn
当 时为奇排列,34,24 kkn
1 nt2 n
3 2 121 nnn
1?n

2?n
kkkkkk 132322212123

0?t
kkk
2
1112,2k?
当 为偶数时,排列为偶排列,k
当 为奇数时,排列为奇排列,k
1? 1? 2 kkk 112?
kkkkkk 13232221212
0?1?1?2?2k
2 排列具有奇偶性,
3 计算排列逆序数常用的方法有 2 种,
1 个不同的元素的所有排列种数为n !.n
三、小结思考题分别用两种方法求排列 16352487的逆序数,
思考题解答解 用方法 1
1 6 3 5 2 4 8 7
用方法 2
01012130t 8?
由前向后求每个数的逆序数,
.810231100t