【线性代数学习笔记】排列及其逆序数

· · 个人记录

定义1：

n个不同的自然数组成排列，从小到大的排列称为 标准排列 或 自然排列

定义2：

逆序：不满足从小到大排列的数对构成逆序

定义3：

逆序数：值排列中构成逆序的总对数，记作

τ(p_1p_2...p_n)

/*

此时，我们记排列中的pi与前面的数所构成的逆序个数为$τ_i

易得

τ(p_1p_2...p_n)=\sum_{i = 1}^{n}τ_i

定义4：

逆序数为奇 奇排列 逆序数为偶 偶排列

定义5：

对换：将两个数的位置对调

性质

相邻对换后，易得，逆序数的奇偶性变化

非相邻对换实际可以拆分为2*m+1次相邻对换（m为对换两数间的数据长度//不包括两数） 故非相邻对换也会改变逆序数的奇偶性

推论：标准排列到奇排列需经过奇数次对换 偶排列同理

下篇【线性代数学习笔记】行列式2