一、排列与逆序
,小 羊 上 山 吃 草,六字可以构成多少句话？
,１２３４５６,六个数字可以组成多少个六位数？
没有重复元素
2、定义
1、引例把ｎ个不同的元素排成一列，叫做这ｎ个元素的全排列 （或 排列 ）,
ｎ级排列共有 种
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
12 21如：
特别,把ｎ个不同的数码１、２,…,ｎ组成的有序数组称为一个 ｎ级（阶、元）排列,
1 2 1 2.,,nnorp p p x x x
!n
记作：
２级排列共有２种：
３级排列共有６种：
1 i njpppp,jip p?
例 排列３２５１４中，
我们规定各元素之间有一个标准次序,ｎ个不同的自然数，规定由小到大为 标准次序,
3、逆序数
3 2 5 1 4
定义逆序逆序逆序逆序逆序分析定义 ip ip
ip 的逆序,
则称这 两个数组成一个逆序,
中，若数在一个排列前面比 大的元素的个数称为 元素排在元素请同学们以最快的速度写出所有４级排列,
逆序数为奇数的排列称为 奇排列 ；
逆序数为偶数的排列称为 偶排列,
4、排列的奇偶性例 1 计算下列排列的逆序数，并讨论它们的奇偶性,
1） ２１７９８６３５４
定义 一个排列中所有逆序的总数称为此排列的逆序数,1.,,,() i j nt N P P P Po r o r?记为解：
5t? 18?
故此排列为偶排列,
4? 0100134
2 1 7 9 8 6 3 5 4
50 1 30 4 40 1
121
2
nn
当 时为偶排列； 14,4 kkn
当 时为奇排列,34,24 kkn
1 nt2 n
解,1 2 3 2 1n n n
0 1 2 1n?2n?3n?
2）1 2 3 2 1n n n
2 1 2 1 2 2 2 3 2 3 1k k k k k k
计算排列的逆序数，并讨论奇偶性,
分析?0?1?1?2?2k1k
2tk?
当 为奇数时，该排列为奇排列,k
当 为偶数时，该排列为偶排列；k
特别,将相邻两个元素对调，叫做 相邻对换,
1、定义二、对换在排列中，将任意两个元素对调，其余元素不动，这种作出新排列的手续叫做 对换,
例 11lmbaa a b b
11lmaba a b b
1 1 1l m na a b b cb ca
1 1 1l m na a b b ca cb
1）
2）
2、对换与排列的奇偶性的关系
11lmbaa a b b11lmaba a b b
定理 1 一个排列中的任意两个元素对换，排列改变奇偶性。
证明,设排列为 1）
易见除 外，其它元素的逆序数不改变，,ab
ba?若对换,ab
对换后 的逆序数不变，而 的逆序数减 1；a b
ab?若对换后 的逆序数增 1，而 的逆序数不变,a b
因此对换相邻两个元素，排列改变奇偶性。
1 1 1l m na a b b cb ca
1 1 1l m na a b b ca cb
设排列为 2）
对换,ab
次相邻对换m
1 1 1l m na a b b cb ca
1 1 1,l m nbaa a b b cc?
1 1 1,l m na a b b a cb c
所以任意两个元素对换，排列改变奇偶性,
1 1 1l m na a b b cb ca
1 1 1l m na a b b ca cb
次相邻对换21m?
欲即次相邻对换1m?
推论 奇排列调成标准排列的对换次数为奇数，
偶排列调成标准排列的对换次数为偶数,
定理 2 ｎ个元素 (ｎ＞１ )共有ｎ !个ｎ阶排列,其中奇、偶排列各占一半,
证明,设 共有 ｓ个奇排列,ｔ个偶排列，现证ｓ＝ｔ,
故必有,ts?
奇排列 偶排列 st?所以前两个数对换ｓ个 ｓ个偶排列 奇排列 ts?所以前两个数对换ｔ个 ｔ个
２ 排列具有奇偶性,
３ 一次对换，排列改变奇偶性,
１ ｎ个不同的元素的所有排列种数为ｎ !
三、小结
4 ｎ个元素 (ｎ＞１ )共有ｎ !个ｎ阶排列,其中奇、偶排列各占一半,
四、思考求排列 的逆序数两种思路排列中比每一元素 大的且排在 前面的元素个数ip
it 12 nt t t t，即是这个排列的逆序数。的总和
ip
排列中比每一元素 小的且排在 后面的元素个数
，也是这个排列的逆序数。的总和
ipip
i? 12 n
例 求下面排列的逆序数，并确定奇偶性,
( 2 1 ),( 2 3),,5,3,1,2,4,6,,( 2 2),( 2 )n n n n
解 1） 从前往后求排在元素前面且比 元素大的数的个数，而后求和,
0 1 2 ( 2) ( 1 )t n n
( 1 ) ( 2) 2 1 0nn( 1)nn
0 0 0 0 0t2 4 6 ( 2 2 )n
( 1)nn
2） 从后往前求排在元素后面且比 元素小的数的个数，而后求和,
