《线性代数 排列与逆序幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性代数 排列与逆序幻灯片.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性代数 排列与逆序2023/1/131第1页，共20页，编辑于2022年，星期一一、概念的引入一、概念的引入引例引例用用1、2、3三个数字，可以组成多少个三个数字，可以组成多少个没有重复数字的三位数？没有重复数字的三位数？解解1 2 3123百位百位3种放法种放法十位十位1231个位个位1232种放法种放法1种放法种放法种放法种放法.共有共有2023/1/132第2页，共20页，编辑于2022年，星期一二、全排列及其逆序数二、全排列及其逆序数问题问题 把把n个不同的元素排成一列，共有几种个不同的元素排成一列，共有几种不同的排法？不同的排法？2023/1/133第3页，共20页，编辑于2022
2、年，星期一定义定义1.11.1把把 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 个元素的全排列（或排列）个元素的全排列（或排列）.通常用通常用 表示表示.个不同的元素的所有排列的种数，个不同的元素的所有排列的种数，由引例由引例同理同理2023/1/134第4页，共20页，编辑于2022年，星期一 我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序,n 个不同的自然数，规定由小到大为标准次个不同的自然数，规定由小到大为标准次序序.排列的逆序数排列的逆序数2023/1/135第5页，共20页，编辑于2022年，星期一 在一个排列在一个排列 中，若数中，若数 ,则则 称这
3、两个数组成一个逆序称这两个数组成一个逆序.例如例如 排列排列32514 中中，定义定义1.21.23 2 5 1 4逆序逆序逆序逆序逆序逆序2023/1/136第6页，共20页，编辑于2022年，星期一 一个排列中所有逆序的总数称为此排列一个排列中所有逆序的总数称为此排列的逆序数的逆序数.例如例如 排列排列32514 中，中，3 2 5 1 4逆序数为逆序数为逆序数为逆序数为3 31故此排列的故此排列的逆序数逆序数为为3+1+0+1+0=5.定义定义 1.3 1.3 2023/1/137第7页，共20页，编辑于2022年，星期一逆序数为奇数的排列称为奇排列逆序数为奇数的排列称为奇排列;逆序数为
4、偶数的排列称为偶排列逆序数为偶数的排列称为偶排列.排列的奇偶性排列的奇偶性2023/1/138第8页，共20页，编辑于2022年，星期一 分别计算出排在分别计算出排在 前面比它大前面比它大的数码之和即分别算出的数码之和即分别算出 这这 个元个元素的逆序数，这些元素的逆序数的总和即素的逆序数，这些元素的逆序数的总和即为所求排列的逆序数为所求排列的逆序数.方法方法1 1三、计算排列逆序数的方法三、计算排列逆序数的方法2023/1/139第9页，共20页，编辑于2022年，星期一 分别计算出排列中每个元素分别计算出排列中每个元素前面前面比它比它大大的的数码个数之和，即算出排列中每个元素的逆序数，数码
5、个数之和，即算出排列中每个元素的逆序数，这些元素的逆序数之总和即为所求排列的逆序数这些元素的逆序数之总和即为所求排列的逆序数.方法方法2 22023/1/1310第10页，共20页，编辑于2022年，星期一 分别计算出排列中每个元素分别计算出排列中每个元素后面后面比它比它小小的数的数码个数之和，即算出排列中每个元素的逆序码个数之和，即算出排列中每个元素的逆序数，这些元素的逆序数之总和即为所求排列数，这些元素的逆序数之总和即为所求排列的逆序数的逆序数.方法方法3 32023/1/1311第11页，共20页，编辑于2022年，星期一例例 求排列求排列32514的逆序数的逆序数.解解在排列在排列32
6、514中中,3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;2023/1/1312第12页，共20页，编辑于2022年，星期一3 2 5 1 4于是排列于是排列32514的逆序数为的逆序数为5的前面没有比的前面没有比5大的数大的数,其逆序数为其逆序数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;2023/1/1313第13页，共20页，编辑于2022年，星期一 计算下列排列的逆序数，并讨论它们的计算下列排列的逆序数，并讨论它们的奇偶
7、性奇偶性.解解此排列为此排列为偶排列偶排列.例例2023/1/1314第14页，共20页，编辑于2022年，星期一解解当当 时为时为偶排列；偶排列；当当 时为时为奇排列奇排列.2023/1/1315第15页，共20页，编辑于2022年，星期一解解当当 为偶数时，排列为为偶数时，排列为偶排偶排列，列，当当 为奇数时，排列为奇排列为奇数时，排列为奇排列.2023/1/1316第16页，共20页，编辑于2022年，星期一练习练习 求求i i，j j使使2525i4j1i4j1为偶排列为偶排列。解解 6 6元排列使元排列使i i、j j只能取只能取3 3或或6 6；由于；由于所以，所以，i i=6,j
8、=3=6,j=3。奇奇排排列列 偶排列（偶数）（偶数）2023/1/1317第17页，共20页，编辑于2022年，星期一2 2 排列具有奇偶性排列具有奇偶性.3 计算排列逆序数常用的方法有计算排列逆序数常用的方法有2 种种.1 1 个不同的元素的所有排列种数为个不同的元素的所有排列种数为四、小结与思考四、小结与思考2023/1/1318第18页，共20页，编辑于2022年，星期一思考题思考题分别用两种方法求排列分别用两种方法求排列16352487的逆序数的逆序数.2023/1/1319第19页，共20页，编辑于2022年，星期一思考题解答思考题解答解解用方法用方法1 11 6 3 5 2 4 8 7 用方法用方法2 2由前向后求每个数的逆序数由前向后求每个数的逆序数.2023/1/1320第20页，共20页，编辑于2022年，星期一