§22排列
§2.2 排列
、排列与对换 排列的定义:由n个数码1,2,…,n组成的 个无重复的有序数组称为这n个数 码的一个排列,简称为n元排列 例如,312是一个3元排列,2341是一个4元排列, 45321是一个5元排列,等等。 3元排列共有多少种不同的排列? 123132213231312321 n元排列共有多少种不同的排列? 在n元排列中,只有123..n这个排列是按自然 顺序排列,其他排列或多或少破坏自然排列 第二章行列式
第二章 行列式 一、排列与对换 ◼ 排列的定义：由n个数码1，2，…，n组成的一 个无重复的有序数组称为这n个数 码的一个排列，简称为n元排列。 例如，312是一个3元排列，2341是一个4元排列， 45321是一个5元排列，等等。 3元排列共有多少种不同的排列？ 123 132 213 231 312 321 n元排列共有多少种不同的排列？ 在n元排列中，只有123…n这个排列是按自然 顺序排列，其他排列或多或少破坏自然排列
反序的定义:在一个n元排列中,如果有一个较大 的数码排在一个较小的数码前面, 则称这两个数码在这个排列中构成 个反序,一个n元排列中所有反序 的总和称为这个排列的反序数,记 为τ(1…)或z(…) 例如:z(32)=2+1=3 z(3241)=3+1=4 z(45321)=4+3+2=9 般地,(2…i)=m+m2+…+mn1 这是计算一个n元排列的反序数的一般方法,特别在 证明题中有用 第二章行列式
第二章 行列式 ◼ 反序的定义：在一个n元排列中，如果有一个较大 的数码排在一个较小的数码前面， 则称这两个数码在这个排列中构成 一个反序，一个n元排列中所有反序 的总和称为这个排列的反序数，记 为 ( j j j 1 2 n ) 或 ( j j j 1 2 n ) 。 例如： (321 2 1 3 ) = + = (3241 3 1 4 ) = + = (45321 4 3 2 9 ) = + + = 一般地， ( j j j m m m 1 2 1 2 1 n n ) = + + + − 这是计算一个n元排列的反序数的一般方法，特别在 证明题中有用
对换的定义:在一个n元排列2…中,如果交换 某两个数码的位置而别的数码不动, 则称对这个排列施行了一个对换 如果交换的两个数码是i和j,就把这个对换记为(,) 例如341625-(15)>345621 问题1:任意两个n元排列是否可经一系列对换而互变? 引理1:任意一个n元排列2…可经一系列对换变为 自然排列12.n。 证明(用归纳法): 1、当n=2时,结论显然成立 2、假设结论对n-1元排列成立, (1)则对任一个n元排列方2…, 第二章行列式
第二章 行列式 ◼ 对换的定义：在一个n元排列 1 2 n j j j 中，如果交换 某两个数码的位置而别的数码不动， 则称对这个排列施行了一个对换。 如果交换的两个数码是 i 和 j ，就把这个对换记为 (i j , ) 例如 (1,5) 341625 345621 ⎯⎯⎯→ 问题1：任意两个n元排列是否可经一系列对换而互变？ 引理1：任意一个n元排列 1 2 n j j j 可经一系列对换变为 自然排列12…n。 证明（用归纳法）： 1、当n=2时，结论显然成立。 2、假设结论对n-1元排列成立， （1） 则对任一个n元排列 1 2 n j j j
假如j=n,则由归纳假设知2…j21可经 系列对换变为12..(n-1)。于是经同样 系列的对换,1…n变为12(n-1)n (2)假如方≠n,设=n(1≤k≤n-1),于是经 次对换(,n),得i……n→i…元n…n 由(1)知,经一系列对换可把六…nn变为 12.n。因而方……可经一系列变换变为 12.n。(证毕)由于对换是可逆的,因此有 推论1:自然排列12n可经一系列的对换变到任意 n元排列:元/2…Jn 由引理1和推论1,我们圆满地解决上面提出的 问题1,这就是: 第二章行列式
第二章 行列式 假如 n j n = ，则由归纳假设知 1 2 1 n j j j − 可经 一系列对换变为12…（n-1）。于是经同样 一系列的对换， 1 2 1 n j j j n− 变为12…(n-1)n； （2）假如 n j n ，设 j n k n k = − (1 1) ，于是经 一次对换 ( j j k n , ) ，得 ( , ) 1 1 k n j j k n n j j j j j n ⎯⎯⎯→ 由（1）知，经一系列对换可把 1 n j j n 变为 12…n。因而 1 k n j j j 可经一系列变换变为 12…n。(证毕) 由于对换是可逆的，因此有 推论1：自然排列12…n可经一系列的对换变到任意一 个n元排列： j j j 1 2 n 。 由引理1和推论1，我们圆满地解决上面提出的 问题1，这就是：
定理2.21:任意两个n元排列可经一系列对换互化 问题2:排列的反序数可以是01…(x,反序数 2 究竟有何作用? 二、排列的奇偶性。 排列的奇偶性:如果一个n元排列的反序数是 个奇数,则称该排列为奇排列 反序数是偶数的排列称为偶排 列 例如:(321),(45321是奇排列,而(3241)是偶排列。 问题3:对n元排列施行一次对换,对排列的奇偶性 有没有影响? 第二章行列式
第二章 行列式 定理2.2.1：任意两个n元排列可经一系列对换互化。 问题2：排列的反序数可以是 n n-1 ( ) 0,1, 2 ，反序数 究竟有何作用？ 二、排列的奇偶性。 ◼ 排列的奇偶性：如果一个n元排列的反序数是一 个奇数，则称该排列为奇排列， 反序数是偶数的排列称为偶排 列。 例如： (321 , 45321 ) ( ) 是奇排列，而 (3241) 是偶排列。 问题3：对n元排列施行一次对换，对排列的奇偶性 有没有影响？
例如,r(321)=3,(123)=0 定理2.22:每一个对换均改变排列的奇偶性。 证明:(先特殊后一般) 1、先考虑特殊情况,即对换的两个数在n元 排列中是相邻的。 设排列(1):…j…经对换(k) 化为排列(2):……,在排列(1)中, 若j,k与其他数构成反序,则在排列(2)中仍 然构成反序; 若j,与其他数不构成反序的,则在排列(2) 中也不构成反序。不同的是j,k的顺序发生变化 若在(1)中j,k构成一个反序,则在(2)中 第二章行列式
第二章 行列式 例如， (321 3 ) = ， (123 0 ) = 。 定理2.2.2：每一个对换均改变排列的奇偶性。 证明：（先特殊后一般） 1、先考虑特殊情况，即对换的两个数在n元 排列中是相邻的。 设排列（1）： jk 化为排列（2）： kj ，在排列（1）中， 若 j k, 与其他数构成反序，则在排列（2）中仍 然构成反序； 若 j k, 与其他数不构成反序的，则在排列（2） 中也不构成反序。不同的是 j k, 的顺序发生变化， 若在（1）中 j k, 构成一个反序，则在（2）中 经对换(j,k)
k,j不构成反序,或在(1)中j2k不构成一个反序, 则在(2)中k,构成一个反序。无论是减少还是增 加一个反序,排列反序数的奇偶性均发生变化,因此 定理成立。 2、再考虑一般情况,设排列为(3):j2…k 经(,)对换后化为排列(4) 这样一个对换可以经由一系列相邻数码的对换来实 现。从(3)出发,依次把k与i对换,与对换 ,与j对换。经过S+1次相邻数码的对换,排列 (3)化为排列(5):…k2……;再把j依次与 2s对换,则经S次相邻数码的对换,排列(5) 就化为排列(4)。故经2S+1相邻数码的对换, 第二章行列式 }
第二章 行列式 k j , 不构成反序，或在（1）中 j k, 不构成一个反序， 则在（2）中 k j , 构成一个反序。无论是减少还是增 加一个反序，排列反序数的奇偶性均发生变化，因此 定理成立。 2、再考虑一般情况，设排列为（3）： 1 2 s ji i i k 经 ( j k, ) 对换后化为排列（4）： 1 2 s ki i i j 这样一个对换可以经由一系列相邻数码的对换来实 现。从（3）出发，依次把 k 与 s i 对换，与 s 1 i − 对换， …，与 j 对换。经过S+1次相邻数码的对换，排列 （3）化为排列（5）： 1 2 s kji i i ；再把 j 依次与 1 2 , , , s i i i 对换，则经S次相邻数码的对换，排列（5） 就化为排列（4）。故经2S+1相邻数码的对换
就把排列(3)化为排列(4) 由第一步知每一次相邻位置的对换均改变排列的奇 偶性,因此,奇数次的对换的最终结果仍然改变排 列的奇偶性 问题4:在全体n元排列中,究竞是奇排列多还是偶排 列多? 定理2.2.3:当n≥2时,在n!个n元排列中,奇、偶排列 各占一半,即各有 证明:由于n≥2,故由定理222知,在n元排列中总有 奇排列和偶排列,设在n!个n元排列中,有S个 奇排列和千个偶排列 把S个奇排列中的每一个排列的任两个数码对换 第二章行列式
第二章 行列式 就把排列（3）化为排列（4）。 由第一步知每一次相邻位置的对换均改变排列的奇 偶性，因此，奇数次的对换的最终结果仍然改变排 列的奇偶性。 问题4：在全体n元排列中，究竟是奇排列多还是偶排 列多？ 定理2.2.3：当 n 2 时，在n!个n元排列中，奇、偶排列 各占一半，即各有 ! 2 n 个。 证明：由于 n 2 ，故由定理2.2.2知，在n元排列中总有 奇排列和偶排列，设在n!个n元排列中，有S个 奇排列和T个偶排列。 把S个奇排列中的每一个排列的任两个数码对换
这S个奇排列就都变成偶排列,但总共只有T个偶排 列,故S≤T。同理对T个偶排列中每一个进行对换 得T≤S。因此S=T,又S+T=n!, S=T= 第二章行列式
第二章 行列式 这S个奇排列就都变成偶排列，但总共只有T个偶排 列，故 S T 。同理对T个偶排列中每一个进行对换， 得 T S 。因此 S T= ，又 S T n + = ! ， ! 2 n = = S T