计算排列的逆序数的方法： 法1：n个数的任一n元排列，先看数1，看有多少个比1大的数 排在1前面，记为m; 再看有多少个比2大的数排在2前面，记为m,; 继续下去，最后至数n,前面比n大的数显然没有， 记为mn=0; 则此排列的逆序数为T=m+m+.+m
计算排列的逆序数的方法： 法1：n个数的任一n元排列，先看数1，看有多少个比1大的数 排在1前面，记为 ; m1 再看有多少个比2大的数排在2前面，记为 ; m2 继续下去，最后至数n，前面比n大的数显然没有， = 0 ; 记为 m n 则此排列的逆序数为 = m1 + m2 ++ m n
法2：n元排列i,i2,.,in的逆序数 x(,.,)=数i后面比i,小的数的个数 +数i,后面比i,小的数的个数 十·· +数i后面比i小的数的个数 法3：(，i,.,)=数in前面比in大的数的个数 +数in,前面比in,大的数的个数 十 +数i,前面比i,大的数的个数
法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）m=3,m2=1,m3=0,m=1,m=0 x(32514)=3+1+1=5 (法2)前→后 (32514)=2+1+2+0+0=5 (法3) 后→前 x(32514)=1+3+0+1+0=5 例2： 求排列4,5,3,1,6,2的逆序数。 t=9
例1： 求排列 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,3的全排列中 有3个偶排列：123,231,312 有3个奇排列：132,213,321 一般说来，在个数码的全排列中，奇偶排列各占一半 定义3：把一个排列中的任意两个数交换位置，其余数码 不动，叫做对该排列作一次对换，简称对换。 将相邻的两个数对换，称为相邻对换
考虑，在 1，2，3 的全排列中 有 个偶排列： 有 个奇排列： 123，231，312 132，213，321 3 3 一般说来，在n个数码的全排列中，奇偶排列各占一半 定义3： 把一个排列中的任意两个数交换位置，其余数码 不动，叫做对该排列作一次对换，简称对换。 将相邻的两个数对换，称为相邻对换。 对换
定理1：对换改变排列的奇偶性。 (书p10定理1.2.1) 证明思路：先证相邻变换，再证一般对换。 定理2：n≥2时，n个数的所有排列中，奇偶排列各占 半，各为影个。 (书pl1定理1.2.2) 证明：设n个数的排列中， 奇排列有p个，偶排列有q个，则p十q=n! 对p个奇排列，施行同一对换， 则由定理1得到p个偶排列。（而且是p个不同的偶排列） 因为总共有q个偶排列，所以p≤q 所以p=9=3 同理I≤P
定理1： 对换改变排列的奇偶性。 （书p10定理1.2.1） 证明思路： 先证相邻变换，再证一般对换。 定理2： n 2 时，n个数的所有排列中，奇偶排列各占 一半，各为 2 n! 个。 （书p11定理1.2.2） 证明： 设n个数的排列中， 奇排列有 p 个，偶排列有q 个， 则 p＋q＝n！ 对 p 个奇排列，施行同一对换， 则由定理1得到p 个偶排列。（而且是p个不同的偶排列） 因为总共有q 个偶排列，所以 p q 同理 q p 所以 2 n! p = q =