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

作者: 溺于恐 | 来源:发表于2018-12-25 07:34 被阅读34次

高等代数理论基础13：排列
逆序数
高等代数理论基础63：同构
机器学习方向数学基础教材推荐
高等代数理论基础7：重因式
高等代数理论基础18：Cramer法则
高等代数理论基础19：Laplace定理
高等代数理论基础49：对角矩阵
高等代数理论基础76：A-矩阵
高等代数理论基础58：初等因子

排列

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}$

高等代数理论基础13：排列
排列 n级排列定义：由组成的一个有序数组称为一个n级排列自然顺序定义：是一个按照递增的顺序排起来的n级排列,...
逆序数
再来一个定义：交换一个排列中的两个数，则排列的奇偶性发生改变。以上定义都摘自《高等代数》。拼图排列必须是偶排列...
高等代数理论基础63：同构
同构定义：对实数域R上欧式空间V与,若由V到有一个双射,满足： 1. 2. 3. 其中,则称为V到V'的同构映射...
机器学习方向数学基础教材推荐
1 线性代数《高等代数——大学高等代数课程创新教材》（上下册）丘维声著清华大学出版社《高等代数》（第四版...
高等代数理论基础7：重因式
重因式重因式定义：给定不可约多项式p(x),若,则称p(x)为f(x)的k重因式若k=0,则p(x)不是f(...
高等代数理论基础18：Cramer法则
Cramer法则 Cramer法则定理：若线性方程组的系数矩阵的行列式,即系数行列式,则线性方程组有且仅有唯一解...
高等代数理论基础19：Laplace定理
Laplace定理余子式和代数余子式的推广余子式定义：在一个n级行列式D中任意选定k行k列,位于这些行和列的...
高等代数理论基础49：对角矩阵
对角矩阵定理：设是n维线性空间V的一个线性变换,的矩阵可在某一组基下为对角矩阵的充要条件为,有n个线性无关的特征...
高等代数理论基础76：A-矩阵
-矩阵任给数域P上n维空间V上线性变换,已定义过P上的多项式,即,,称为P上的多项式,其中为V上恒等变换,仍为V...
高等代数理论基础58：初等因子
初等因子初等因子定义：将矩阵A(或线性变换)的每个次数大于零的不变因子分解成互不相同的首项为1的一次因式方幂的...

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

排列

n级排列

自然顺序

逆序

偶排列与奇排列

对换

相关文章

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

逆序数

高等代数理论基础63：同构

机器学习方向数学基础教材推荐

高等代数理论基础7：重因式

高等代数理论基础18：Cramer法则

高等代数理论基础19：Laplace定理

高等代数理论基础49：对角矩阵

高等代数理论基础76：A-矩阵

高等代数理论基础58：初等因子

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

高等代数