第一萁诿怎对换 排列与递辱 对换 三小 慼考
、排列与逆序 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 为偶数时，该排列为偶排列；