第一与对换 排列与逆序 二对换 三小结 思考
、排列与逆序 1、引例 没有重复元素 “小羊上山吃草”六字可以构成多少句话? 123456″六个数字可以组成多少个六位数? 2、定义 把n个不同的元素排成一列,叫做这n个元素的 全排列(或排列) 特别:把n个不同的数码1、2、…、n组成 的有序数组称为一个n级(阶、元)排列 记作:D1D2…P 12 n n级排列共有n!种 如:2级排列共有2种:1221 3级排列共有6种:123132213231312321
一、排列与逆序 “小 羊 上 山 吃 草” 六字可以构成多少句话？ “１２３４５６”六个数字可以组成多少个六位数？ 没有重复元素 2、定义 1、引例 把ｎ个不同的元素排成一列，叫做这ｎ个元素的 全排列（或排列）. ｎ级排列共有 种 123 132 213 231 312 321 如： 12 21 特别：把ｎ个不同的数码１、２、…、ｎ组成 的有序数组称为一个ｎ级（阶、元）排列. 1 2 1 2 . . . n n p p p x x x or n! 记作： ２级排列共有２种： ３级排列共有６种：
國请同学们以最快的速度写出所有4级排列 3、逆序数 我们规定各元素之间有一个标准次序,n个不同 的自然数,规定由小到大为标准次序 定义在一个排列n1…P1…P1…P中,若数P1>P, 则称这两个数组成一个逆序 定义排在元素P前面比大的元素的个数称为元素 P的逆 例排列3254中 逆序6逆序 分析 3-2514 逆序逆序逆序
1 i j n p p p p , i j p p 例 排列３２５１４中， 我们规定各元素之间有一个标准次序, ｎ个不同 的自然数，规定由小到大为标准次序. 3、逆序数 3 2 5 1 4 定义 逆序 逆序 逆序 逆序 逆序 分析 定义 i p i p i p 的逆序. 则称这两个数组成一个逆序. 在一个排列 中，若数 排在元素 前面比 大的元素的个数称为元素 请同学们以最快的速度写出所有４级排列
定义一个排列中所有逆序的总数称为此排列的 逆序数.记为t.or.z,or.N(P1…P…P…P) 排列的奇偶性 逆序数为奇数的排列称为奇排列 逆序数为偶数的排列称为偶排列 例1计算下列排列的逆序数,并讨论它们的奇偶性 1)217986354 解:217986354 010013445 t=5+4+4+3+1+0+0+1+0=18 故此排列为偶排列
逆序数为奇数的排列称为奇排列； 逆序数为偶数的排列称为偶排列. 4、排列的奇偶性 例1 计算下列排列的逆序数，并讨论它们的奇偶性. 1） ２１７９８６３５４ 定义 一个排列中所有逆序的总数称为此排列的 逆序数. 1 . . . . ( ) i j n 记为 t N P P P P or or 解： t = 5 = 18 故此排列为偶排列. +4 + 4 + 3 + 1 + 0 + 0 + 1 + 0 2 1 7 9 8 6 3 5 4 0 1 0 0 1 3 4 4 5
2)n(m-1)(n-2)…321 解:n(m-1)(n-2)…32 01 2 3 t=(n-1)+(n-2)+…+2+ (n-1) 当n=4,4为偶排列; 当n=4k+射时为排列 ■习计算排列的逆序数,并讨论奇偶性 (2k)1(2k-1)2(2k-2)3(2k-3)…(k+1)k 分析01 22 ●·dk-1k 当防偶数时,该排列为偶排列 t=k 当伪奇数时,该排列为奇排列
( 1) 2 1 2 n n − + + + = 当 n = 4k,4k 时为偶排列； +1 当 n = 4k + 2 时为奇排列 ,4k + 3 . t = (n −1) + (n − 2) 解： n n n ( − − 1 2 3 2 1 )( ) 0 1 2 n − 3 n − 2 n − 1 2） n n n ( − − 1 2 321 )( ) (2 1 2 1 2 2 2 3 2 3 1 k k k k k k ) ( − − − + ) ( ) ( ) ( ) 计算排列的逆序数，并讨论奇偶性. 分析 0 1 1 2 2 k 1 k − 2 t k = 当 k为奇数时，该排列为奇排列. 当 k 为偶数时，该排列为偶排列；
对换 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 ｎ个元素(ｎ＞１)共有ｎ!个ｎ阶排列,其 中奇、偶排列各占一半