高等代数理论基础13：排列

2018-12-25 本文已影响34人溺于恐

排列

n级排列

定义：由 $1,2,\cdots,n$ 组成的一个有序数组称为一个n级排列

自然顺序

定义： $12\cdots n$ 是一个按照递增的顺序排起来的n级排列,称为自然顺序

逆序

定义：在一个排列中,若一对数的前后位置与大小顺序相反,即前面的数大于后面的数,则称为一个逆序,一个排列中逆序的总数就称为这个排列的逆序数

排列 $j_1j_2\cdots j_n$ 的逆序数记为 $\tau(j_1j_2\cdots j_n)$

偶排列与奇排列

定义：逆序数为偶数的排列称为偶排列,逆序数为奇数的排列称为奇排列

注： $12\cdots n$ 逆序数是零,是偶排列

对换

定义：把一个排列中某两个数的位置互换,其余的数不动,就得到另一个排列,这样的变换称为一个对换

注：

1.若连续进行两次相同的对换,则排列还原

2.一个对换把全部n级排列两两配对,使每两个配对的n级排列在这个对换下互变

定理：对换改变排列的奇偶性

即经过一次对换,奇排列变成偶排列,偶排列变成奇排列

证明：

$若对换的两个数在排列中相邻$

$即\cdots jk\cdots\qquad (1)$

$经过对换变成$

$\cdots kj\cdots\qquad (2)$

$在排列(1)中若j,k与其他数构成逆序,则在排列(2)中仍构成逆序$

$若不构成逆序,则在(2)中也不构成逆序$

$(1)和(2)仅j,k的次序不同$

$若原来j,k构成逆序$

$则经过对换,逆序数减少一个$

$若原来j,k不构成逆序$

$则经过对换,逆序数就增加一个$

$\therefore 排列的逆序数奇偶性改变,定理成立$

$若j,k不相邻,设排列为$

$\cdots ji_1i_2\cdots i_sk\cdots\qquad (3)$

$经过j,k对换变成$

$\cdots ki_1i_2\cdots i_sj\cdots\qquad (4)$

$以上对换可以通过一系列的相邻数对换实现$

$从(3)出发,把k与i_s对换,再与i_{s-1}对换\cdots$

$即把k一位一位向左移动$

$经过s+1次相邻位置对换,排列(3)变成$

$\cdots kji_1i_2\cdots i_s\cdots\qquad (5)$

$从(5)出发,再把j一位一位向右移动$

$经过s次相邻位置对换,排列(5)变成排列(4)$

$\therefore j,k对换可通过2s+1次相邻位置的对换实现$

$2s+1为奇数,相邻位置的对换改变排列的奇偶性$

$\therefore 奇数次这样的对换的最终结果还是改变奇偶性\qquad \mathcal{Q.E.D}$

推论：在全部n级排列中,奇、偶排列的个数相等,各有 ${n!\over 2}$ 个

证明：

$假设在全部n级排列中,共有s个奇排列,t个偶排列$

$将s个奇排列中的前两个数字对换$

$得到s个不同的偶排列$

$\therefore s\le t$

$同理可得t\le s$

$\therefore s=t$

$即奇、偶排列的总数相等,各有{n!\over 2}个\qquad \mathcal{Q.E.D}$

定理：任一n级排列与排列 $12\cdots n$ 都可经过一系列对换互变,且所作对换的个数与这个排列有相同的奇偶性

证明：

$对排列的级数n作数学归纳法$

$证任一n级排列都可经过一系列对换变成12\cdots n$

$对1级排列,结论显然成立$

$假设对n-1级排列,结论成立$

$下证对n级排列,结论也成立$

$设j_1j_2\cdots j_n是一个n级排列$

$若j_n=n,则根据归纳假设$

$n-1级排列j_1j_2\cdots j_{n-1}可经过一系列对换变成12\cdots n-1$

$\therefore 这一系列对换也把j_1j_2\cdots j_n变成12\cdots n$

$若j_n\neq n$

$则对j_1j_2\cdots j_n作j_n,n对换$

$变成j_1'\cdots j_{n-1}'n,结论成立$

$\therefore 结论普遍成立$

$同理可得$

$1,2,\cdots,n也可由一系列对换变成j_1j_2\cdots j_n$

$\because 12\cdots n是偶排列$

$\therefore 所作变换的个数与排列j_1j_2\cdots j_n有相同的奇偶性\qquad \mathcal{Q.E.D}$

上一篇下一篇

猜你喜欢

热点阅读