11 排列与逆序.ppt

* * 线性代数 第一章 行列式第一节 排列与逆序 用1, 2, 3可以组成多少个没有重复数字 的三位数? 解 1 2 3 1 2 3 百位 3种放法 十位 1 2 3 1 个位 1 2 3 2种放法 1种放法 共有 3 × 2 × 1 = 6 个 定义 把 n 个不同自然数 1, 2, …, n 组成的一个有序 数组 p1 p2…pn 称为 n 个元素的全排列 (或排列), 用 Pn 表示 n 个不同元素所有不同排列的种数. 其中 pi 称为第 i 个元素. 规定 全 排 列 Pn = n! = 1 × 2 × n 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 当 n ＝4 时, Pn = 24: 在一个排列 p1 p2 … pn 中, 如有 ps pt 且 s t, 定义 标准顺序: 规定 n 个不同自然数按从小到大的排列 3 2 4 1 5 逆序 逆序 逆 序 如: 1 2 3, 1 2 … n 则称 ps 和 pt 构成该排列的一个逆序. 在排列 p1 p2 … pn 中, 所有元素逆序的总数称 定义 逆 序 数 为该排列的逆序数, 记为 ?( p1 p2…pn) 奇排列: 逆序数为奇数的排列 偶排列: 逆序数为偶数的排列 ? 在排列 p1 p2 … pn 中, 所有元素逆序的总数称 定义 3 逆 序 数 为该排列的逆序数, 记为 ?( p1 p2…pn) 2 4 1 5 1 3 ∴ ?(32415) = 0 + 1 + 0 + 3 + 0 = 4, 是偶排列 0 0 0 计算排列 p1 p2… pn 逆序数的方法: 1. 求 pi 的逆序数 ti: p1…pi－1 中比 pi 大的个数 2. ?( p1 p2…pn) = t1 + t2 + … + tn = ? i = 1 n ti 例1 求下列排列的逆序数, 判断其奇偶性 (1) 365412 (2) n (n－1) … 2 1 解 (1) t1 = 0, t2 = 0, t3 = 1, t4 = 2, t6 = 4 t5 = 4, ∴ ?(365412) = 11, 是奇排列 (2) t1 = 0, t2 = 1, t3 = 2, tn = n－1 … ∴ ?(n…1) = 1 +2 + … + (n－1) = n(n－1) 2 当 n = 4k 或 4k + 1 时, 是偶排列 当 n = 4k + 2 或 4k + 3 时, 是奇排列 在排列 p1 p2 … pn 中, 任意对换两元素 ps 和 pt 定义 排列的对换 的位置, 其它元素不动, 称为该排列的一个对换. p1 … ps … pt … pn p1 … pt … ps … pn 注：对换必定改变排列的逆序数! 3 1 2 1 3 2 1 2 3 ? = 2 ? = 1 ? = 0 (3, 1) (3, 2) (ps, pt) 对换改变排列的奇偶性. 定理1 所有 n 个元素的排列中, 奇偶排列各有一半. 定理2 任意一个排列 p1 p2…pn 都可以经有限次对换 推论1 变成标准顺序的排列12…n, 且对换的次数与 排列 p1 p2…pn 具有相同的奇偶性. 证略! (n 1) * * * *