线性代数 全排列及其逆序数幻灯片.ppt

线性代数线性代数 全排列及全排列及其逆序数其逆序数第1页，共13页，编辑于2022年，星期一一、概念的引入一、概念的引入引例引例用用1、2、3三个数字，可以组成多少个没有重复三个数字，可以组成多少个没有重复数字的三位数？数字的三位数？解解1 2 3123百位百位3种放法种放法十位十位1231个位个位1232种放法种放法1种放法种放法种放法种放法.共有共有第2页，共13页，编辑于2022年，星期一二、全排列及其逆序数二、全排列及其逆序数问题问题定义定义把把 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 个个元素的全排列（或排列）元素的全排列（或排列）.个不同的元素的所有排列的种数，通常个不同的元素的所有排列的种数，通常用用 表示表示.由引例由引例同理同理第3页，共13页，编辑于2022年，星期一 在一个排列在一个排列 中，若数中，若数 则称这两个数组成一个逆序则称这两个数组成一个逆序.例如例如 排列排列32514 中，中，定义定义 我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序,n 个不个不同的自然数，规定由小到大为同的自然数，规定由小到大为标准次序标准次序.3 2 5 1 4逆序逆序逆序逆序逆序逆序 排列的逆序数排列的逆序数热门促销安卓智能手机推荐第4页，共13页，编辑于2022年，星期一一个排列中所有逆序的总数称为此排列的一个排列中所有逆序的总数称为此排列的逆序数逆序数.例如例如 排列排列32514 中，中，3 2 5 1 4逆序数为逆序数为31故此排列的故此排列的逆序数为逆序数为3+1+0+1+0=5.定义定义第5页，共13页，编辑于2022年，星期一计算排列逆序数的方法计算排列逆序数的方法方法方法1 1分别计算出排在分别计算出排在 前面比它大的数前面比它大的数码之和即分别算出码之和即分别算出 这这 个元素个元素的逆序数，这些元素的逆序数的总和即为所求的逆序数，这些元素的逆序数的总和即为所求排列的逆序数排列的逆序数.逆序数为奇数的排列称为逆序数为奇数的排列称为奇排列奇排列;逆序数为偶数的排列称为逆序数为偶数的排列称为偶排列偶排列.排列的奇偶性排列的奇偶性第6页，共13页，编辑于2022年，星期一分别计算出排列中每个元素前面比它大的数码分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数，个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆这每个元素的逆序数之总和即为所求排列的逆序数序数.例例1 1 求排列求排列32514的逆序数的逆序数.解解在排列在排列32514中中,3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;方法方法2第7页，共13页，编辑于2022年，星期一3 2 5 1 4于是排列于是排列32514的逆序数为的逆序数为5的前面没有比的前面没有比5大的数大的数,其逆序数为其逆序数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;第8页，共13页，编辑于2022年，星期一计算下列排列的逆序数，并讨论它们的计算下列排列的逆序数，并讨论它们的奇偶性奇偶性.解解此排列为此排列为偶排列偶排列.例例2第9页，共13页，编辑于2022年，星期一当当 时为偶排列；时为偶排列；当当 时为奇排列时为奇排列.解解第10页，共13页，编辑于2022年，星期一2 2 排列具有奇偶性排列具有奇偶性.3 计算排列逆序数常用的方法有计算排列逆序数常用的方法有2 种种.1 1 个不同的元素的所有排列种数为个不同的元素的所有排列种数为 三、小结三、小结第11页，共13页，编辑于2022年，星期一分别用两种方法求排列分别用两种方法求排列16352487的逆序数的逆序数.思考题思考题第12页，共13页，编辑于2022年，星期一解解用方法用方法1 11 6 3 5 2 4 8 7 用方法用方法2 2由前向后求每个数的逆序数由前向后求每个数的逆序数.思考题解答思考题解答第13页，共13页，编辑于2022年，星期一