1、一、概念的引入一、概念的引入引例引例用用1、2、3三个数字，可以组成多少个没三个数字，可以组成多少个没有重复数字的三位数？有重复数字的三位数？解解1 2 3123百位百位3种放法种放法十位十位1231个位个位12 32种放法种放法1种放法种放法种放法种放法.共有共有6123 二、全排列及其逆序数二、全排列及其逆序数同的排法？同的排法？，共有几种不，共有几种不个不同的元素排成一列个不同的元素排成一列把把 n问题问题定义定义把把 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 个个元素的全排列（或排列）元素的全排列（或排列）.nn 个不同的元素的所有排列的种数，通常个不同的元素的所有排列
2、的种数，通常用用 表示表示.nnP由引例由引例1233 P.6 nPn)1(n)2(n123 !.n 同理同理 在一个排列在一个排列 中，若数中，若数 则称这两个数组成一个逆序则称这两个数组成一个逆序.nstiiiii21stii 例如例如 排列排列32514 中，中，定义定义 我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序,n 个个不同的自然数，规定由小到大为不同的自然数，规定由小到大为标准次序标准次序.排列的逆序数排列的逆序数3 2 5 1 4逆序逆序逆序逆序逆序逆序定义定义 一个排列中所有逆序的总数称为此排列的一个排列中所有逆序的总数称为此排列的逆序数逆序数.例如例如
3、排列排列32514 中，中，3 2 5 1 4逆序数为逆序数为31010故此排列的故此排列的逆序数为逆序数为3+1+0+1+0=5.计算排列逆序数的方法计算排列逆序数的方法方法方法1 1分别计算出排在分别计算出排在 前面比它大的数前面比它大的数码之和即分别算出码之和即分别算出 这这 个元素个元素的逆序数，这个元素的逆序数的总和即为所求的逆序数，这个元素的逆序数的总和即为所求排列的逆序数排列的逆序数.n,n,121 n,n,121 n逆序数为奇数的排列称为逆序数为奇数的排列称为奇排列奇排列;逆序数为偶数的排列称为逆序数为偶数的排列称为偶排列偶排列.排列的奇偶性排列的奇偶性分别计算出排列中每个元素
4、前面比它大的数码分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数，个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆这每个元素的逆序数之总和即为所求排列的逆序数序数.方法方法2 2例例1 1 求排列求排列32514的逆序数的逆序数.解解在排列在排列32514中中,3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;3 2 5 1 40 1 0 3 1于是排列于是排列32514的逆序数为的逆序数为13010 t.5 5的前面没有比的前面没有比5大的数大的数,其逆序数为其逆序
5、数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;例例2 2 计算下列排列的逆序数，并讨论它们的奇计算下列排列的逆序数，并讨论它们的奇偶性偶性.2179863541解解453689712544310010 t18 此排列为此排列为偶排列偶排列.54 0100134 321212 nnn解解12 ,21 nn当当 时为偶排列；时为偶排列；14,4 kkn当当 时为奇排列时为奇排列.34,24 kkn 1 nt 2 n 32121 nnn1 n 2 n kkkkkk132322212123 解解0 t k
6、kk 21112,2k 当当 为偶数时，排列为偶排列，为偶数时，排列为偶排列，k当当 为奇数时，排列为奇排列为奇数时，排列为奇排列.k1 1 2 kkk 112 kkkkkk13232221212 0 1 1 2 2 k2 2 排列具有奇偶性排列具有奇偶性.3 计算排列逆序数常用的方法有计算排列逆序数常用的方法有2 种种.1 1 个不同的元素的所有排列种数为个不同的元素的所有排列种数为n!.n三、小结三、小结分别用两种方法求排列分别用两种方法求排列16352487的逆序数的逆序数.思考题解答思考题解答解解用方法用方法1 11 6 3 5 2 4 8 7 用方法用方法2 201012130 t8 由前向后求每个数的逆序数由前向后求每个数的逆序数.810231100 t
