§2.2n元排列 2.21排列与逆序 2.2.2排列的奇偶性 2.2.3小结 上页
§2.2 n元排列 2.2.3 小结 2.2.1 排列与逆序 2.2.2 排列的奇偶性
生221排列与逆序 王定义21由自然数,2,…,n组成的一个有 序数组称为一个n元排列 黑例如:1,2,3,4,5 5,1,2,3,4都是数1,2,3,4,5的一个排列 5,3,2,1,4 庄问题:n个数的不同排列有n!个 王定义22按数的大小次序,由小到大的排列称为 自然排列.n阶排列1234.n称为n阶自然序排列 上页
2.2.1 排列与逆序 定义2-1 由自然数1，2，······，n 组成的一个有 序数组称为一个n 元排列. 例如：1，2，3，4，5 5，1，2，3，4 5，3，2，1，4 都是数1，2，3，4，5的一个排列. 问题：n个数的不同排列有 n 个. ! 自然排列. 定义2-2 按数的大小次序，由小到大的排列称为 n阶排列1234… n称为n阶自然序排列
注意n元排列中,自然排列只有一种, 除此之外,任一n元排列都一定出现较大数码 排在较小数码之前的情况 中定义2-3在一个排列中,若某个较大的数排在某 个较小的数前面,就称这两个数构成一 个逆序.一个排列中出现的逆序的总数 工工工 称为这个排列的逆序数, 通常记为r(i,i,…,i) 上页
在一个排列中，若某个较大的数排在某 个较小的数前面，就称这两个数构成一 个逆序. 一个排列中出现的逆序的总数 ( , , , ) 1 2 n 通常记为 i i i 注意 n元排列中，自然排列只有一种， 除此之外，任一n元排列都一定出现较大数码 排在较小数码之前的情况. 定义2-3 称为这个排列的逆序数
计算排列的逆序数的方法: 方法1: n个数的任一n元排列,先看数1,看有多少个比1大 的数排在1前面,记为m1; 再看有多少个比2大的数排在2前面,记为m2; 工工工 继续下去,最后至数n,前面比n大的数显然没有, 记为m=0 则此排列的逆序数为 T=m1+m2+…+mn 上页
计算排列的逆序数的方法： 方法1： n个数的任一n元排列，先看数1，看有多少个比1大 的数排在1前面，记为 ; m1 再看有多少个比2大的数排在2前面，记为 ; m2 继续下去，最后至数n，前面比n大的数显然没有， = 0 ; 记为 m n 则此排列的逆序数为 = m1 + m2 ++ m n
王方法2:n元排列,…,的逆序数 王x0,x,…、)=数后面比小的数的个数 +数i2后面比2小的数的个数 +数元n1后面比in1小的数的个数 方法3: ,…、)=数前面比元大的数的个数 +数i,前面比i,大的数的个数 十 +数i2前面比z大的数的个数 上页 圆
方法2：n 元排列 n i ,i , ,i 1 2 的逆序数 (i 1 ,i 2 , ,i n ) = 数i 1 后面比i 1 小的数的个数 + 数i 2 后面比i 2 小的数的个数 + + 数 i n−1 后面比i n−1 小的数的个数 方法3： (i 1 ,i 2 , ,i n ) = 数 i n 前面比i n 大的数的个数 + 数 i n−1 前面比i n−1 大的数的个数 + + 数i 2 前面比i 2 大的数的个数
例1求排列3,2,5,1,4的逆序数 解(法1)m1=3,m2=1,m23=0,m1=1,m=0 (32514)=3+1+1=5 (法2)前→后 (32514)=2+1+2+0+0=5 (法3)后→前 (32514)=1+3+0+1+0=5 例2求排列4,5,3,1,6,2的逆序数 解=9 上页
求排列 3，2，5，1，4 的逆序数. 解（法1） 3, m1 = 1, m2 = 0, m3 = 1, m4 = m5 = 0 (32514) = 3 + 1 + 1 = 5 （法2） (32514) = 2 + 1 + 2 + 0 + 0 = 5 前 → 后 （法3） 后 → 前 (32514) = 1 + 3 + 0 + 1 + 0 = 5 例2 求排列 4，5，3，1，6，2 的逆序数. = 9 例1 解
定义2-4逆序数为奇数的排列奇排列 逆序数为偶数的排列偶排列 例如(32514)=5,所以32514是奇排列 τ(123…n)=0,所以123…m是偶排列 z(n(n-1)…321)= n(n-1) 工工工 2 当n=4或n=4k+1,n(n-1)…321是偶排列 当n=4k+2或n=4k+3时 n(n-1)…321是奇排列 上页
逆序数为奇数的排列奇排列. 逆序数为偶数的排列偶排列. 定义2-4 例如 (32514) = 5, 所以32514是奇排列. (123n) = 0, 所以123 ···n是偶排列. , 2 ( 1) ( ( 1) 321) − − = n n n n 当n = 4k或n = 4k + 1时, n(n-1)···321是偶排列. 当n = 4k + 2或n = 4k + 3时, n(n-1)···321是奇排列
考虑,在1,2,3的全排列中 有3个偶排列:123,231,312 有3个奇排列:132,213,321 般说来,在n个数码的全排列中,奇偶排列各 占一半 上页
考虑，在 1，2，3 的全排列中 有 个偶排列： 有 个奇排列： 123，231，312 132，213，321 3 3 一般说来，在n个数码的全排列中，奇偶排列各 占一半
王2.22排列的奇偶性 定义2-5把一个排列中的任意两个数交换位置, 其余数码不动,叫做对该排列作一次 对换,简称对换. 将相邻的两个数对换,称为相邻对换 例如a1a,abbb 1… a, ba b1…bm a1…ub…bnbc1…Cn 1bb…bmnc1…cn 上页
定义2-5 把一个排列中的任意两个数交换位置， 其余数码不动，叫做对该排列作一次 对换，简称对换. 将相邻的两个数对换，称为相邻对换. 例如 a1 al a bb1 bm a1 al bbaa b1 bm l m n a a a b b b c c 1 1 1 l m n a a b b b a c c 1 1 1 b a a b 2.2.2 排列的奇偶性
定理2-1一个排列中的任意两个元素对换,排 列改变奇偶性。 证明设排列为 a1bb…b对换n与b a1…u1bb1…bn 除a,b外,其它元素的逆序数不改变 王当a<硎时, 经对换后a的逆序数增加1,b的逆序数不变; 上页
定理2-1 一个排列中的任意两个元素对换，排 列改变奇偶性． 证明 设排列为 a1 al ab b1 bm 对换 a 与 b a1 al ba b1 bm 除 a,b 外，其它元素的逆序数不改变. ab ba 经对换后 a 的逆序数增加1 , b 的逆序数不变; 当 a b 时