文档介绍：一、概念的引入
引例
用1、2、3三个数字,可以组成多少个没有重复数字的三位数?
解
1 2 3
1
2
3
百位
3种放法
十位
1
2
3
1
个位
1
2
3
2种放法
1种放法
种放法.
共有
二、全排列及其逆序数
问题
定义
把个不同的元素排成一列,叫做这个元素的全排列(或排列).
个不同的元素的所有排列的种数,通常用表示.
由引例
同理
在一个排列中,若数
则称这两个数组成一个逆序.
例如排列32514 中,
定义
我们规定各元素之间有一个标准次序, n 个不同的自然数,规定由小到大为标准次序.
排列的逆序数
3 2 5 1 4
逆序
逆序
逆序
定义一个排列中所有逆序的总数称为此排列的逆序数.
例如排列32514 中,
3 2 5 1 4
逆序数为3
1
故此排列的逆序数为3+1+0+1+0=5.
计算排列逆序数的方法
方法1
分别计算出排在前面比它大的数
码之和即分别算出这个元素
的逆序数,这个元素的逆序数的总和即为所求
排列的逆序数.
逆序数为奇数的排列称为奇排列;
逆序数为偶数的排列称为偶排列.
排列的奇偶性
分别计算出排列中每个元素前面比它大的数码
个数之和,即算出排列中每个元素的逆序数,
这每个元素的逆序数之总和即为所求排列的逆
序数.
方法2
例1 求排列32514的逆序数.
解
在排列32514中,
3排在首位,逆序数为0;
2的前面比2大的数只有一个3,故逆序数为1;
3 2 5 1 4
于是排列32514的逆序数为
5的前面没有比5大的数,其逆序数为0;
1的前面比1大的数有3个,故逆序数为3;
4的前面比4大的数有1个,故逆序数为1;
例2 计算下列排列的逆序数,并讨论它们的奇偶性.
解
此排列为偶排列.
解
当时为偶排列;
当时为奇排列.