《线性代数1.1 排列与逆序》由会员分享，可在线阅读，更多相关《线性代数1.1 排列与逆序（20页珍藏版）》请在金锄头文库上搜索。
1、一、一、概念引入概念引入二、全排列及其逆序数二、全排列及其逆序数三、计算排列逆序数的方法三、计算排列逆序数的方法四、小结与思考四、小结与思考DateDate1 1一、概念的引入一、概念的引入引例引例用用1 1、2 2、3 3三个数字，可以组成多三个数字，可以组成多 少个没有重复数字的三位数？少个没有重复数字的三位数？解解1 2 3123百位百位3种放法种放法十位十位1231个位个位12 32种放法种放法 1种放法种放法种放法种放法.共有共有Date2二、全排列及其逆序数二、全排列及其逆序数问题问题把把n n个不同的元素排成一列，共有几种个不同的元素排成一列，共有几种不同的排法？不同的排法？Da
2、te3定义定义1.11.1把把 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 个元素的全排列（或排列）个元素的全排列（或排列）. .通常用通常用 表示表示. .个不同的元素的所有排列的种数，个不同的元素的所有排列的种数，由引例由引例同理同理Date4我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序, , n n 个不同的自然数，规定由小到大为标准个不同的自然数，规定由小到大为标准次序次序. .排列的逆序数排列的逆序数Date5在一个排列在一个排列 中，中，若数若数, , 则则 称这两个数组成一个逆序称这两个数组成一个逆序. .例如例如 排列排列32514 32514
3、 中中， 定义定义1.21.23 2 5 1 4逆序逆序逆序逆序逆序逆序Date6一个排列中所有逆序的总数称为此排列一个排列中所有逆序的总数称为此排列 的逆序数的逆序数. .例如例如 排列排列32514 32514 中，中， 3 2 5 1 4逆序数为逆序数为3 31故此排列的故此排列的逆序数逆序数为为3+1+0+1+0=53+1+0+1+0=5. .定义定义 1.31.3 Date7逆序数为奇数的排列称为奇排列逆序数为奇数的排列称为奇排列; ;逆序数为偶数的排列称为偶排列逆序数为偶数的排列称为偶排列. .排列的奇偶性排列的奇偶性Date8分别计算出排在分别计算出排在 前前面比它大的数码之和即
4、分别算出面比它大的数码之和即分别算出 这这 个元素的逆序数，这些元素的逆序数个元素的逆序数，这些元素的逆序数 的总和即为所求排列的逆序数的总和即为所求排列的逆序数. .方法方法1 1三、计算排列逆序数的方法三、计算排列逆序数的方法Date9分别计算出排列中每个元素分别计算出排列中每个元素前面前面比它比它大大的数码个数之和，即算出排列中每个元素的数码个数之和，即算出排列中每个元素的逆序数，这些元素的逆序数之总和即为的逆序数，这些元素的逆序数之总和即为所求排列的逆序数所求排列的逆序数. .方法方法2 2Date10分别计算出排列中每个元素分别计算出排列中每个元素后面后面比它比它小小的数码个数之和，
5、即算出排列中每个元素的数码个数之和，即算出排列中每个元素的逆序数，这些元素的逆序数之总和即为的逆序数，这些元素的逆序数之总和即为所求排列的逆序数所求排列的逆序数. .方法方法3 3Date11例例 求排列求排列3251432514的逆序数的逆序数. .解解在排列在排列3251432514中中, ,3 3排在首位排在首位, ,逆序数为逆序数为0 0; ;2 2的前面比的前面比2 2大的数只有一个大的数只有一个3,3,故逆序数为故逆序数为1;1;Date123 2 5 1 4于是排列于是排列3251432514的逆序数为的逆序数为5 5的前面没有比的前面没有比5 5大的数大的数, ,其逆序数为其逆
6、序数为0;0;1 1的前面比的前面比1 1大的数有大的数有3 3个个, ,故逆序数为故逆序数为3;3;4 4的前面比的前面比4 4大的数有大的数有1 1个个, ,故逆序数为故逆序数为1;1;Date13计算下列排列的逆序数，并讨论它们计算下列排列的逆序数，并讨论它们 的奇偶性的奇偶性. .解解此排列为此排列为偶排列偶排列.例例Date14解解当当 时为时为偶排列；偶排列； 当当 时为时为奇排列奇排列.Date15解解当当 为偶数时，排列为为偶数时，排列为偶排偶排列，列，当当 为奇数时，排列为奇排列为奇数时，排列为奇排列. .Date16练习练习 求求i i，j j使使2525i4j1i4j1为偶排列为偶排列。解解 6 6元排列使元排列使i i、j j只能取只能取3 3或或6 6；由于；由于所以，所以，i i=6,j=3=6,j=3。奇 排 列偶 排 列（偶数）偶数）Date172 排列具有奇偶性.3 计算排列逆序数常用的方法有2 种.1 个不同的元素的所有排列种数为四、小结与思考四、小结与思考Date18思考题思考题分别用两种方法求排列16352487的逆序数.Date19思考题解答思考题解答解用方法11 6 3 5 2 4 8 7 用方法2由前向后求每个数的逆序数.Date20
