.2.2奇、偶排列的」 定义3看n个数码的一个排列,如果把这个排列里 的任意两个数码与交换一下,而其余数码保持不 动,那么就得到一个新的排列,对于排列所施行的 这样一个变换叫做一个对换,并且用符号(i,j 来表示。 定理1.21设2…和2…是n个数码的任意两个 排列,那么总可以通过一系列对换由 得出 2 证我们已经知道,通过一系列对换可以由 得出2…mo我们只需证明, 通过一系列对换可由12…n得出 上页 返回 下页 结铃
11 首页 上页 返回 下页 结束 铃 1.2.2 奇、偶排列的定义及性质 定义3 看n个数码的一个排列，如果把这个排列里 的任意两个数码i与j交换一下，而其余数码保持不 动，那么就得到一个新的排列，对于排列所施行的 这样一个变换叫做一个对换，并且用符号（i，j） 来表示。 定理1.2.1 n n i i i j j j 设 1 2 和 1 2 是n个数码的任意两个 排列，那么总可以通过一系列对换由 n n i i i j j j 1 2 得出 1 2 证明:我们已经知道，通过一系列对换可以由 i i i no 1 2 n 得出12 我们只需证明， 通过一系列对换可由 n n j j j 12 得出 1 2
而通过一系列对换可以由2…得出2…n ,按照相反的次序施行这些对换,就可由 12…n得出 定理12.2任意一个排列经过一个对换后的奇偶性 改变 证明:1°我们首先看一个特殊的情形,就是被对 换的两个数码是相邻的。设给定的排列为 A B 其中A与B都代表若干个数码施行对换(得 12首页上页【返回匚下页〖结東」铃
12 首页 上页 返回 下页 结束 铃 而通过一系列对换可以由 j 1 j 2 j n 得出12n ，按照相反的次序施行这些对换，就可由 n n j j j 12 得出 1 2 。 定理1.2.2 任意一个排列经过一个对换后的奇偶性 改变. 其中A与B都代表若干个数码.施行对换 (i, j), 得 证明: 我们首先看一个特殊的情形，就是被对 换的两个数码是相邻的。设给定的排列为 1 A B , , , , i j
A且 我们比较这两个排列的反序数显然经过这个对换 后,属于A或B的数码的位置没有改变,因此这些数 码所构成的反序数没有改变同时i,jA或B中的 数码所构成的反序数也没有改变。若在给定的排 列中,7<小那么经过对换(后,门与就构成一个 反序。因面后一排列的反序比前一排列的反序数 增多一个。若在给定的排列中,1>,那么经过对换 后,排列的反序数减少一个。不论是哪一种情形, 排列的奇偶性都有改变。 13首页上页【返回匚下页〖结東」铃
13 首页 上页 返回 下页 结束 铃 我们比较这两个排列的反序数.显然经过这个对换 后,属于A或B的数码的位置没有改变,因此这些数 码所构成的反序数没有改变.同时i，j与A或B中的 数码所构成的反序数也没有改变。若在给定的排 列中， i j, 那么经过对换 (i, j) 后，i与j就构成一个 反序。因面后一排列的反序比前一排列的反序数 增多一个。若在给定的排列中， i j, 那么经过对换 后，排列的反序数减少一个。不论是哪一种情形， 排列的奇偶性都有改变。 A B , j, i,
2°现在来看一般的情形。假定汽这之间有s个数码,我 们用k,k2,…k,来代表。这时给定的排列为 (1ik,k.k 先让响右移动,依次与k1,k2,…,k。交换。这样,经过 s次相邻的两个数码的对换后(1)变为 k。,,j 再让向左移动,依次与k…,k2,k1交换。经过s+1次 相邻的两个数码的对换后,排列变为 2)…J, 但 14首页【上页【返回匚下页【结東铃
14 首页 上页 返回 下页 结束 铃 现在来看一般的情形。假定i与j之间有s个数码，我 们用 s k , k , , k 1 2 来代表。这时给定的排列为 2 , , , , , , , . （1） i k1 k2 ks j 先让i向右移动，依次与 s k , k , , k 1 2 交换。这样，经过 s次相邻的两个数码的对换后（1）变为 , , , , , , , . k1 k2 ks i j 再让j向左移动，依次与 2 1 i, k ,, , k , k s 交换。经过s+1次 相邻的两个数码的对换后，排列变为 , , , , , , . （2） j k1 k2 ks i (i, j) 1 但 （ 2 ） 正 (i, j) (i, j)
在n个数码(n>1)的所有n!个排列,其 中奇偶排列各占一半即各为个。 证明设n个数码的奇排列共有p个,而偶排列 共有q个,对这p个奇排列施行同一个对换 那么由定理122,我们得到p个偶排列由于对这p 个偶排列各不相等又可以得到原来的p个奇排列, 所以这p个偶排列各不相等但我们一共只有q个偶 排列所以P≤q.同样可得q≤p.因此P=q 题选讲 例1计算排列32514的逆序数 例2计算排列217986354的逆序数,并讨论其奇偶性 例3求排列n(n-1)(n-2)…321的逆序数,并讨论其奇偶性 5首页」〖上页【返回下页〖结東」铃
15 首页 上页 返回 下页 结束 铃 定理1.2.3 在n个数码(n>1)的所有n！个排列，其 中奇偶排列各占一半.即各为 2 n! 个。 证明：设n个数码的奇排列共有p个，而偶排列 共有q个，对这p个奇排列施行同一个对换 (i, j), 那么由定理1.2.2,我们得到p 个偶排列.由于对这p 个偶排列各不相等.又可以得到原来的p个奇排列, 所以这p个偶排列各不相等.但我们一共只有q个偶 排列,所以 p q. 同样可得 q p. 因此 p = q. 例题选讲 例 1 计算排列 32514 的逆序数 . 例 2 计算排列 217986354 的逆序数, 并讨论其奇偶性. 例 3 求排列 n(n −1)(n−2)321的逆序数, 并讨论其奇偶性