54对换
§4 对换
、对换的定义 定义在排列中,将任意两个元素对调,其余的元素 不动,这种作出新排列的手续叫做对换 将相邻两个元素对换,叫做相邻对換 例如 1…a1abb1…bn anab1…bnb 1 a,…a,ba bi b c
a a b b c 1 1 1 l m n a b c 一、对换的定义 定义 在排列中，将任意两个元素对调，其余的元素 不动，这种作出新排列的手续叫做对换． 将相邻两个元素对换，叫做相邻对换． 例如 a a b b 1 1 l m a b a a b b 1 1 l m b a a a b b c 1 1 1 l m n b a c
备注 1.相邻对换是对换的特殊情形 2.一般的对换可以通过一系列的相邻对换来实现 3.如果连续施行两次相同的对换,那么排列就还原了 ab,bbc,…c. m次相邻对换 a1…a1abb1…bnC1…cn m+次相邻对换 bb,…ba m次相邻对换 bab1…bnC1…Cn mH+次相邻对換,a1…aab…bnbc1…Cn
备注 1. 相邻对换是对换的特殊情形. 2. 一般的对换可以通过一系列的相邻对换来实现. 3. 如果连续施行两次相同的对换，那么排列就还原了. m 次相邻对换 1 1 1 l m n a a b b c a b c 1 1 1 l m n a a b b c a b c 1 1 1 l m n m a a b b c b a c +1次相邻对换 m 次相邻对换 1 1 1 l m n a a b b c b a c 1 1 1 l m n m a a b b c a b c +1次相邻对换
二、对换与排列奇偶性的关系 定理1对换改变排列的奇偶性 证明先考虑相邻对换的情形 a bb...b m1bab1…b
二、对换与排列奇偶性的关系 定理1 对换改变排列的奇偶性. 证明 先考虑相邻对换的情形． a a b b 1 1 l m a b a a b b 1 1 l m b a a a b b 1 1 l m a b t t t t = + + + + + + + t t t a a b b 1 1 l m b a r t t t = + + + + + + + t r r
t=tn+…+t+tn+b+tb+…+ a,…·a,abb,b b r=an+…+++z++…+tn 注意到除a,外,其它元素的逆序数不改变
a a b b 1 1 l m a b a a b b 1 1 l m b a a a b b 1 1 l m a b t t t t = + + + + + + + t t t a a b b 1 1 l m b a r t t t = + + + + + + + t r r 注意到除 a b, 外，其它元素的逆序数不改变
t=ta+…+ta+ta+tb+tb,+…+ a,…·a,abb,b b P=t,十十t十n十十t,+… 当a时,后÷t 因此相邻对换改变排列的奇偶性
a a b b 1 1 l m a b a a b b 1 1 l m b a a a b b 1 1 l m a b t t t t = + + + + + + + t t t a a b b 1 1 l m b a r t t t = + + + + + + + t r r 当 a b 时， ， ， . 当 a b 时， ， ， . 因此相邻对换改变排列的奇偶性. 1 a a r t = + b b r t = a a r t = 1 b b r t = − r t = +1 r t = −1
既然相邻对换改变排列的奇偶性,那么 .bb 1 2mH1次相邻对换 a1…a1bb1…bmc1…cn 因此,一个排列中的任意两个元素对换,排列的奇偶性改变 推论奇排列变成标准排列的对换次数为奇数, 偶排列变成标准排列的对换次数为偶数 证明定理1知,对换的次数就是排列奇偶性的变化次数 而标准排列是偶排列(逆序数为零),因此可知推论成立
既然相邻对换改变排列的奇偶性，那么 2m+1次相邻对换 因此，一个排列中的任意两个元素对换，排列的奇偶性改变. a a b b c 1 1 1 l m n a b c a a b b c 1 1 1 l m n b a c 推论 奇排列变成标准排列的对换次数为奇数， 偶排列变成标准排列的对换次数为偶数. 由定理1知，对换的次数就是排列奇偶性的变化次数， 而标准排列是偶排列(逆序数为零)，因此可知推论成立. 证明
因为数的乘法是可以交换的,所以n个元素相乘的次 序是可以任意的,即 r1小hl/2 ggq.. ="1P12P2 Pn P1Ip22.a Pun 每作一次交换,元素的行标与列标所成的排列讠i 与都同时作一次对换,即…同购蛮 偶性,但是这两个排列的逆序数之和的奇偶性不变
1 1 2 2 1 2 1 2 1 2 1 2 , , n n n n i j i j i j p np p p p n p a a a = a a a = a a a 因为数的乘法是可以交换的，所以 n 个元素相乘的次 序是可以任意的，即 每作一次交换，元素的行标与列标所成的排列 与 都同时作一次对换，即 与 同时改变奇 偶性，但是这两个排列的逆序数之和的奇偶性不变. 1 2 n i i i 1 2 n j j j 1 2 n j j j 1 2 n i i i
设对换前行标排列的逆序数为s,列标排列的逆序数为t 设经过一次对换后行标排列的逆序数为s 列标排列的逆序数为 因为对换改变排列的奇偶性,s‘是奇数,c也是奇数 所以(s-s)+是偶数, 即(s'+t)-是偶数 于是(s+与同时为奇数或同时为偶数 因此,交换 I1J1 2232 中征意两个元素的位置后,其行标 排列与列标排列的逆序数之和的奇偶性不变
于是 与 同时为奇数或同时为偶数. 即 是偶数. 因为对换改变排列的奇偶性， 是奇数， 也是奇数. 设对换前行标排列的逆序数为 s ，列标排列的逆序数为 . t s t 所以 是偶数， s s − t t − ( ) ( ) s s t t − + − ( ) ( ) s t s t + − + ( ) s t + ( ) s t + 因此，交换 中任意两个元素的位置后，其行标 排列与列标排列的逆序数之和的奇偶性不变. 1 1 2 2 , , n n i j i j i j a a a 设经过一次对换后行标排列的逆序数为 列标排列的逆序数为
经过一次对换是如出,经过多次对换还是如此所以,在 系列对换之后有 (i1i2…in)+t(12…jn) r(12n)+t(1P2Pn) =(-1)nppn)
1 2 1 2 1 2 1 2 ( ) ( ) (12 ) ( ) ( ) ( 1) ( 1) ( 1) n n n n t i i i t j j j t n t p p p t p p p + + − = − = − 经过一次对换是如此，经过多次对换还是如此. 所以，在 一系列对换之后有