09级第章行列式n级排列及其逆序数课件.ppt

四、对换与排列的奇偶性的关系 跳转到第一页 第一章 行列式 (1)-2 §1.2 n级排列 引例 用1、2、3三个数字，可以组成多少个没有重复数字的三位数？ 种取法. 共有 解 1 2 3 1 2 3 百位 百位数有3种取法 1 如百位 数取1 1 2 1 十位 3 百位数确定后,十位数有2种取法 一、概念的引入 个位 1 2 3 个位数有1种取法 如十位 数取2 问题 定义1 将 n 个不同的元素排成一行(或列)，叫做这 n个元素的一个全排列（或排列）. 二、 n级排列及其逆序数 (2) 自然数1,3,…,2n-1 的一个排列 例如: (1) 自然数1,2,…,n 的一个排列 n 个自然数1,2,…,n的所有排列的种数，通常用 由引例 同理 定义2 由自然数1,2,…,n所组成的一个有序数组,称为一个n级排列.将n级排列(1 2 … n)称为自然顺序排列(简称自然排列). 以下提到的排列是指n级排列,提到的元素是指n级排列中某个数. 在排列中,我们规定各元素之间由小到大为标准次序. 排列的逆序数 例如 在排列32514 中共有5个逆序,如图示. 3 2 5 1 4 逆序 逆序 逆序 逆序 逆序 在一个排列 中,若元素 满足 则称这两个元素构成一个逆序(或反序). 定义3 中所有逆序的总数称为此排列的的逆序数,记为 定义4 一个排列 方法1 在它后面比它小的数码的个数,即对这 n-1 个元素分别算出与它后面的元素构成逆序的个数，逆序的个数总和即为所求排列的逆序数.简称向后(或向右)比较法. 例1 求排列32514的逆序数. 故此排列的逆序数为2+1+2+0=5. 3 2 5 1 4 1 2 2 0 计算排列逆序数的方法 例2 求排列32514的逆序数. 故此排列的逆序数为1+0+3+1=5. 3 2 5 1 4 3 1 *方法2 在它前面比它大的数码的个数,即对这 n-1 个元素分别算出与它前面的元素构成逆序的个数，逆序的个数总和即为所求排列的逆序数.简称向前(或向左)比较法. 例3 计算下列排列的逆序数，并讨论它们的 奇偶性. 解: (采用“向后比较法”计算排列的逆序数) 此排列为偶排列. =1+0+4+5+4+3+0+1=18 定义5 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 解: (采用“向后比较法”计算排列的逆序数) 当n=2, 逆序数=1 时为奇排列; 当n=3, 逆序数=3 时为奇排列; 当n=4, 逆序数=6 时为偶排列; 当n=5, 逆序数=10时为偶排列; 当n=4k+2, 逆序数= (2k+1)(4k+1) 时为奇排列; 当n=4k+3, 逆序数= (4k+3)(2k+1) 时为奇排列; 当n=4k+4, 逆序数= (2k+2)(4k+3) 时为偶排列; 当n=4k+5, 逆序数= (4k+5)(2k+2) 时为偶排列; 其中,k是非负整数. 三、对换的定义 定义1 在排列中，将某两个元素互换，其余元素不动，将原排列变成新排列的这种变换叫做对换(或互换)．将相邻两个元素对换，叫做相邻对换(或相邻互换) ． 例如,相邻对换 例如,对换 定理1　一个排列中的任意两个元素对换，改变排列的奇偶性． 证明: 1.先证相邻对换的情形 设排列为 除 a,b 外，对其它元素的逆序个数不改变. 将相邻两个元素a,b对换: 经对换后 , a 的逆序个数不变, b的逆序个数增加1,则逆序数增加1; 当 时， 采用“向后比较法” 1 6 3 5 2 4 8 7 例如: 排列 将相邻两个数2,4对换,得 1 6 3 5 4 2 8 7 排列 则逆序数增加1. 当 时， 经对换后 a 的逆序个数减少1 ，b 的逆序个数 不变,则逆序数减少1. 1 6 3 5 2 4 8 7 例如: 排列 将相邻两个数5,2对换,得 1 6 3 2 5 4 8 7 排列 则逆序数减少1. 总之,对换相邻两个元素，逆序数增加1或减少1. 改变排列的奇偶性. 次相邻对换 将b向前作m次相邻对换: 设排列为 现来对换 与 将a向后作m+1次相邻对换: 2.再证一般对换的情形 则 所以排列中的任意两个元素a,b对换，可通过2m+1次相邻对换得到.