线性代数 排列与逆序精品文稿.ppt
线性代数 排列与逆序2022/10/241第1页，本讲稿共20页一、概念的引入一、概念的引入引例引例用用1、2、3三个数字，可以组成多三个数字，可以组成多少个没有重复数字的三位数？少个没有重复数字的三位数？解解1 2 3123百位百位3种放法种放法十位十位1231个位个位12 32种放法种放法1种放法种放法种放法种放法.共有共有2022/10/242第2页，本讲稿共20页二、全排列及其逆序数二、全排列及其逆序数问题问题 把把n个不同的元素排成一列，共有几种个不同的元素排成一列，共有几种不同的排法？不同的排法？2022/10/243第3页，本讲稿共20页定义定义1.11.1把把 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 个元素的全排列（或排列）个元素的全排列（或排列）.通常用通常用 表示表示.个不同的元素的所有排列的种数，个不同的元素的所有排列的种数，由引例由引例同理同理2022/10/244第4页，本讲稿共20页 我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序,n 个不同的自然数，规定由小到大为标准个不同的自然数，规定由小到大为标准次序次序.排列的逆序数排列的逆序数2022/10/245第5页，本讲稿共20页 在一个排列在一个排列 中，若数中，若数 ,则则 称这两个数组成一个逆序称这两个数组成一个逆序.例如例如 排列排列32514 中中，定义定义1.21.23 2 5 1 4逆序逆序逆序逆序逆序逆序2022/10/246第6页，本讲稿共20页 一个排列中所有逆序的总数称为此排列一个排列中所有逆序的总数称为此排列的逆序数的逆序数.例如例如 排列排列32514 中，中，3 2 5 1 4逆序数为逆序数为逆序数为逆序数为3 31故此排列的故此排列的逆序数逆序数为为3+1+0+1+0=5.定义定义 1.3 1.3 2022/10/247第7页，本讲稿共20页逆序数为奇数的排列称为奇排列逆序数为奇数的排列称为奇排列;逆序数为偶数的排列称为偶排列逆序数为偶数的排列称为偶排列.排列的奇偶性排列的奇偶性2022/10/248第8页，本讲稿共20页 分别计算出排在分别计算出排在 前面比它大前面比它大的数码之和即分别算出的数码之和即分别算出 这这 个元个元素的逆序数，这些元素的逆序数的总和即素的逆序数，这些元素的逆序数的总和即为所求排列的逆序数为所求排列的逆序数.方法方法1 1三、计算排列逆序数的方法三、计算排列逆序数的方法2022/10/249第9页，本讲稿共20页 分别计算出排列中每个元素分别计算出排列中每个元素前面前面比它比它大大的数码个数之和，即算出排列中每个元素的数码个数之和，即算出排列中每个元素的逆序数，这些元素的逆序数之总和即为的逆序数，这些元素的逆序数之总和即为所求排列的逆序数所求排列的逆序数.方法方法2 22022/10/2410第10页，本讲稿共20页 分别计算出排列中每个元素分别计算出排列中每个元素后面后面比它比它小小的数码个数之和，即算出排列中每个元素的数码个数之和，即算出排列中每个元素的逆序数，这些元素的逆序数之总和即为的逆序数，这些元素的逆序数之总和即为所求排列的逆序数所求排列的逆序数.方法方法3 32022/10/2411第11页，本讲稿共20页例例 求排列求排列32514的逆序数的逆序数.解解在排列在排列32514中中,3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;2022/10/2412第12页，本讲稿共20页3 2 5 1 4于是排列于是排列32514的逆序数为的逆序数为5的前面没有比的前面没有比5大的数大的数,其逆序数为其逆序数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;2022/10/2413第13页，本讲稿共20页 计算下列排列的逆序数，并讨论它们计算下列排列的逆序数，并讨论它们的奇偶性的奇偶性.解解此排列为此排列为偶排列偶排列.例例2022/10/2414第14页，本讲稿共20页解解当当 时为时为偶排列；偶排列；当当 时为时为奇排列奇排列.2022/10/2415第15页，本讲稿共20页解解当当 为偶数时，排列为为偶数时，排列为偶排偶排列，列，当当 为奇数时，排列为奇排列为奇数时，排列为奇排列.2022/10/2416第16页，本讲稿共20页练习练习 求求i i，j j使使2525i4j1i4j1为偶排列为偶排列。解解 6 6元排列使元排列使i i、j j只能取只能取3 3或或6 6；由于；由于所以，所以，i i=6,j=3=6,j=3。奇奇排排列列 偶排列（偶数）（偶数）2022/10/2417第17页，本讲稿共20页2 2 排列具有奇偶性排列具有奇偶性.3 计算排列逆序数常用的方法有计算排列逆序数常用的方法有2 种种.1 个不同的元素的所有排列种数为四、小结与思考四、小结与思考2022/10/2418第18页，本讲稿共20页思考题思考题分别用两种方法求排列16352487的逆序数.2022/10/2419第19页，本讲稿共20页思考题解答思考题解答解解用方法用方法1 11 6 3 5 2 4 8 7 用方法用方法2 2由前向后求每个数的逆序数由前向后求每个数的逆序数.2022/10/2420第20页，本讲稿共20页
