§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，这就是：