§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 大的数的个数