对换 1、定义 在排列中,将任意两个元素对调,其余元素不 动,这种作出新排列的手续叫做对换 特别:将相邻两个元素对调,叫做相邻对换 例 1…a1abb1…bn a1…·a1bab1…bm ab,…·bb 2) 1a1bb,、、、c
特别：将相邻两个元素对调，叫做相邻对换. 1、定义 二、对换 在排列中，将任意两个元素对调，其余元素不 动，这种作出新排列的手续叫做对换. 例 a a b b 1 1 l m a b a a b b 1 1 l m b a 1 1 1 l m n a a b b c a b c 1 1 1 l m n a a b b c b a c 1） 2）
2、对换与排列的奇偶性的关系 定理1一个排列中的任意两个元素对换,排列改 变奇偶性。 证明:设排列为1) 7abb1…b, 对换u,b n b a b, 易见除a外,其它元素的逆序数不改变, 若a>b 对换后a的逆序数不变,而逆序数减1; 若a<b 对换后a的逆序数增1,而b的逆序数不变 因此对换相邻两个元素,排列改变奇偶性
2、对换与排列的奇偶性的关系 1 1 l m a a b b a b 1 1 l m a a b b b a 定理1 一个排列中的任意两个元素对换，排列改 变奇偶性。 证明：设排列为 1） 易见除 a b, 外，其它元素的逆序数不改变， 若 a b 对换 a b, 对换后 a 的逆序数不变，而 b 的逆序数减1； 若 a b 对换后 a 的逆序数增1，而 b 的逆序数不变. 因此对换相邻两个元素，排列改变奇偶性
设排列为2 欲a1…a1ab1…bnbc1…Cn 对换a,b bb,…b.a 即 l( m次相邻对换 abb,…b a1…abb1…bna m+1次相邻对换 2m+1次相邻对换 a1…a1b1… b bc bb C…C 所以任意兩个元素对换,排列改变奇偶性
1 1 1 l m n a a b b c a b c 1 1 1 l m n a a b b c b a c 设排列为 2） 对换 a,b m 次相邻对换 1 1 1 l m n a a b b c a b c 1 1 1 , l m n a a b ab bc c 1 1 1 , l m n a a b b b ac c 所以任意两个元素对换，排列改变奇偶性. 1 1 1 l m n a a b b c a b c 1 1 1 l m n a a b b c b a c 2 1 m + 次相邻对换 欲 即 m + 1 次相邻对换
推论奇排列调成标准排列的对换次数为奇数, 偶排列调成标准排列的对换次数为偶数 定理2n个元素(n>1)共有n!个n阶排列其中 奇、偶排列各占一半 证明:设共有s个奇排列,t个偶排列,现证s=t s个奇排列前两个数换s个偶排列所以s≤t t个偶排列三 前两个数对换 t个奇排列所以t≤s 故必有s=t
推论 奇排列调成标准排列的对换次数为奇数， 偶排列调成标准排列的对换次数为偶数. 定理2 ｎ个元素(ｎ＞１)共有ｎ!个ｎ阶排列,其中 奇、偶排列各占一半. 证明: 设共有ｓ个奇排列,ｔ个偶排列，现证ｓ＝ｔ. 故必有 s = t. 奇排列 偶排列 所以 s t 前两个数对换 ｓ个 ｓ个 偶排列 奇排列 所以 t s 前两个数对换 ｔ个 ｔ个
小结 1n个不同的元素的所有排列种数为n! 2排列具有奇偶性 3一次对换,排列改变奇偶性 4n个元素(n>1)共有n!个n阶排列其 中奇、偶排列各占一半
２ 排列具有奇偶性. ３ 一次对换，排列改变奇偶性. １ ｎ个不同的元素的所有排列种数为ｎ! 三、小结 4 ｎ个元素(ｎ＞１)共有ｎ!个ｎ阶排列,其 中奇、偶排列各占一半