§ 2.2 n元排列
2.2.3 小结
2.2.1 排列与逆序
2.2.2 排列的奇偶性
2.2.1 排列与逆序定义 2-1 由自然数 1,2,······,n 组成的一个有序数组称为一个 n 元 排列,
例如,1,2,3,4,5
5,1,2,3,4
5,3,2,1,4
都是数 1,2,3,4,5的一个排列,
问题,n个数的不同排列有 个,n !
自然排列,
按数的大小次序，由小到大的排列称为定义 2-2
n阶排列 1234… n 称为 n阶 自然序排列,
在一个排列中，若某个较大的数排在某个较小的数前面，就称这两个数构成一个 逆序,一个排列中出现的逆序的总数
),,,( 21 niii通常记为注意 n元排列中，自然排列只有一种，
除此之外，任一 n元排列都一定出现较大数码排在较小数码之前的情况,
定义 2-3
称为这个排列的 逆序数，
计算排列的 逆序数 的方法：
方法 1：
n个数的任一 n元排列，先看数 1，看有多少个比 1大的数排在 1前面，记为 ; 1m
再看有多少个比 2大的数排在 2前面，记为 ; 2m
继续下去，最后至数 n，前面比 n大的数显然没有，; 0?nm记为则此排列的 逆序数 为
nmmm21?
方法 2,n 元排列 niii,,,21? 的逆序数
),,,( 21 niii 小的数的个数后面比数 11 ii
小的数的个数后面比数 22 ii?
小的数的个数后面比数 11 nn ii
方法 3：
),,,( 21 niii 大的数的个数前面比数 nn ii
大的数的个数前面比数 11 nn ii
大的数的个数前面比数 22 ii?
求排列 3,2,5,1,4 的逆序数,
解 （ 法 1）,31?m,12?m,03?m,14?m 05?m
5113)3 2 5 1 4(
（ 法 2）
500212)3 2 5 1 4(
后前?
（法 3） 前后?
501031)32514(
例 2 求排列 4,5,3,1,6,2 的逆序数,
9
例 1
解逆序数为奇数的排列 奇排列,
逆序数为偶数的排列 偶排列,
定义 2-4
例如,5)3 2 5 1 4( 所以 32514是 奇排列,
,0)123(?n 所以 123 ···n是 偶排列,
,2 )1()3 2 1)1(( nnnn
,144 时或当 knkn n(n-1)···321是 偶排列,
,3424 时或当 knkn
n(n-1)···321是 奇排列,
考虑，在 1,2,3 的全排列中有 个偶排列,
有 个奇排列：
123,231,312
132,213,321
3
3
一般说来，在 n个数码的全排列中，奇偶排列各占一半,
定义 2-5 把一个排列中的任意两个数交换位置，
其余数码不动，叫做对该排列作一次对换，简称 对换,
将相邻的两个数对换，称为 相邻对换,
ml bbbaaa 11例如 ba
ml bbabaa 11 ab
nml ccbbbaaa 111
nml ccabbbaa 111
b
a
a
b
2.2.2 排列的奇偶性定理 2-1 一个排列中的任意两个元素对换，排列改变奇偶性．
证明 设排列为
ml bbabaa 11
对换 与a b
ml bbbaaa 11
除 外，其它元素的逆序数不改变,b,a
ab ba
a b 的逆序数不变 ;经对换后 的逆序数增加 1,
当 时，ba?
当 时，ba?
经对换后 的逆序数不变,的逆序数减少 1.a b
因此对换相邻两个元素，排列改变奇偶性,
设排列为 nml cbcbabaa 111
现来对换 与a,b
次相邻对换m
nml ccbbabaa 111
次相邻对换1?m
nml ccabbbaa 111
,111 nml cbcbabaa
次相邻对换12?m,
111 nml cacbbbaa
所以一个排列中的任意两个元素对换，排列改变奇偶性,
ab
nml ccbbbaaa 111 a b
ab
定理 2-2 2?n 时,n个数的所有排列中，奇偶排列各占一半，各 为 2!n 个,
证明 设 n个数的排列中，
奇排列有 p 个，偶排列有 q 个,则 p＋ q＝ n！
对 p 个奇排列，施行同一对换，
则由定理 1得到 p 个偶排列,（而且是 p个不同的偶排列）
因为总共有 q 个偶排列，所以 qp?,同理 pq?
所以 2!nqp
定理 2-3 任意一个 n阶排列都可以经过一系列对换变成 自然序排列,并且 所作对换的次数与该排列有相同的奇偶性,
证明 用数学归纳证明当 n=1时,结论显然成立,
假设结论对 n-1阶排列成立,现证对 n阶排列也成立,
.,,,21 阶排列是任一设 njjj n?
,nj n?若,1,,,121 阶排列个是一则 njjj n?
由假设知,121,,,?njjj? 可经过一系列对换变成自然序排列，从而 nn jjjj,,,,121 可经过一系列对换变成 自然序排列,
),,,nn jnnj 则先作对换（若?
nnnn jjjjjjjj,,,,,,,,121121 变成使这就归结为上面的情形，结论成立,
所以任意一个 n阶排列都可以经过一系列对换变成自然序排列,
由于自然序排列是 偶排列，由 定理 2-1,对换一个改变排列奇偶性，所以将一奇排列变成 自然序排列推论 2-1
需要作奇数次对换，而将一偶排列变成 自然序排列则需要作偶数次对换,证毕,
任意两个 n阶排列都可以经过一系列对换互变，而且若这 两个 排列的奇偶性相同，则所作的则所作的对换次数是奇数,
对换次数是偶数；若这 两个 排列的奇偶性相反，
2.一个排列中的任意两个元素对换，排列改变奇偶性．
2.2.3 小结
1.排列,逆序数，奇排列,偶排列,对换的定义,
思考题证明 在全部 阶排列中,奇偶排列各占一半,n2?n
思考题解答证 设在全部 阶排列中有 个奇排列,个偶排列,现来证,
n s t
ts?
将 个奇排列的前两个数对换,则这 个奇排列全变成偶排列,并且它们彼此不同,所以
s s
.ts?
若将 个偶排列的前两个数对换,则这 个偶排列全变成奇排列,并且它们彼此不同,于是有
t t
.st?
故必有,ts?
2.2.3 小结
2.2.1 排列与逆序
2.2.2 排列的奇偶性
2.2.1 排列与逆序定义 2-1 由自然数 1,2,······,n 组成的一个有序数组称为一个 n 元 排列,
例如,1,2,3,4,5
5,1,2,3,4
5,3,2,1,4
都是数 1,2,3,4,5的一个排列,
问题,n个数的不同排列有 个,n !
自然排列,
按数的大小次序，由小到大的排列称为定义 2-2
n阶排列 1234… n 称为 n阶 自然序排列,
在一个排列中，若某个较大的数排在某个较小的数前面，就称这两个数构成一个 逆序,一个排列中出现的逆序的总数
),,,( 21 niii通常记为注意 n元排列中，自然排列只有一种，
除此之外，任一 n元排列都一定出现较大数码排在较小数码之前的情况,
定义 2-3
称为这个排列的 逆序数，
计算排列的 逆序数 的方法：
方法 1：
n个数的任一 n元排列，先看数 1，看有多少个比 1大的数排在 1前面，记为 ; 1m
再看有多少个比 2大的数排在 2前面，记为 ; 2m
继续下去，最后至数 n，前面比 n大的数显然没有，; 0?nm记为则此排列的 逆序数 为
nmmm21?
方法 2,n 元排列 niii,,,21? 的逆序数
),,,( 21 niii 小的数的个数后面比数 11 ii
小的数的个数后面比数 22 ii?
小的数的个数后面比数 11 nn ii
方法 3：
),,,( 21 niii 大的数的个数前面比数 nn ii
大的数的个数前面比数 11 nn ii
大的数的个数前面比数 22 ii?
求排列 3,2,5,1,4 的逆序数,
解 （ 法 1）,31?m,12?m,03?m,14?m 05?m
5113)3 2 5 1 4(
（ 法 2）
500212)3 2 5 1 4(
后前?
（法 3） 前后?
501031)32514(
例 2 求排列 4,5,3,1,6,2 的逆序数,
9
例 1
解逆序数为奇数的排列 奇排列,
逆序数为偶数的排列 偶排列,
定义 2-4
例如,5)3 2 5 1 4( 所以 32514是 奇排列,
,0)123(?n 所以 123 ···n是 偶排列,
,2 )1()3 2 1)1(( nnnn
,144 时或当 knkn n(n-1)···321是 偶排列,
,3424 时或当 knkn
n(n-1)···321是 奇排列,
考虑，在 1,2,3 的全排列中有 个偶排列,
有 个奇排列：
123,231,312
132,213,321
3
3
一般说来，在 n个数码的全排列中，奇偶排列各占一半,
定义 2-5 把一个排列中的任意两个数交换位置，
其余数码不动，叫做对该排列作一次对换，简称 对换,
将相邻的两个数对换，称为 相邻对换,
ml bbbaaa 11例如 ba
ml bbabaa 11 ab
nml ccbbbaaa 111
nml ccabbbaa 111
b
a
a
b
2.2.2 排列的奇偶性定理 2-1 一个排列中的任意两个元素对换，排列改变奇偶性．
证明 设排列为
ml bbabaa 11
对换 与a b
ml bbbaaa 11
除 外，其它元素的逆序数不改变,b,a
ab ba
a b 的逆序数不变 ;经对换后 的逆序数增加 1,
当 时，ba?
当 时，ba?
经对换后 的逆序数不变,的逆序数减少 1.a b
因此对换相邻两个元素，排列改变奇偶性,
设排列为 nml cbcbabaa 111
现来对换 与a,b
次相邻对换m
nml ccbbabaa 111
次相邻对换1?m
nml ccabbbaa 111
,111 nml cbcbabaa
次相邻对换12?m,
111 nml cacbbbaa
所以一个排列中的任意两个元素对换，排列改变奇偶性,
ab
nml ccbbbaaa 111 a b
ab
定理 2-2 2?n 时,n个数的所有排列中，奇偶排列各占一半，各 为 2!n 个,
证明 设 n个数的排列中，
奇排列有 p 个，偶排列有 q 个,则 p＋ q＝ n！
对 p 个奇排列，施行同一对换，
则由定理 1得到 p 个偶排列,（而且是 p个不同的偶排列）
因为总共有 q 个偶排列，所以 qp?,同理 pq?
所以 2!nqp
定理 2-3 任意一个 n阶排列都可以经过一系列对换变成 自然序排列,并且 所作对换的次数与该排列有相同的奇偶性,
证明 用数学归纳证明当 n=1时,结论显然成立,
假设结论对 n-1阶排列成立,现证对 n阶排列也成立,
.,,,21 阶排列是任一设 njjj n?
,nj n?若,1,,,121 阶排列个是一则 njjj n?
由假设知,121,,,?njjj? 可经过一系列对换变成自然序排列，从而 nn jjjj,,,,121 可经过一系列对换变成 自然序排列,
),,,nn jnnj 则先作对换（若?
nnnn jjjjjjjj,,,,,,,,121121 变成使这就归结为上面的情形，结论成立,
所以任意一个 n阶排列都可以经过一系列对换变成自然序排列,
由于自然序排列是 偶排列，由 定理 2-1,对换一个改变排列奇偶性，所以将一奇排列变成 自然序排列推论 2-1
需要作奇数次对换，而将一偶排列变成 自然序排列则需要作偶数次对换,证毕,
任意两个 n阶排列都可以经过一系列对换互变，而且若这 两个 排列的奇偶性相同，则所作的则所作的对换次数是奇数,
对换次数是偶数；若这 两个 排列的奇偶性相反，
2.一个排列中的任意两个元素对换，排列改变奇偶性．
2.2.3 小结
1.排列,逆序数，奇排列,偶排列,对换的定义,
思考题证明 在全部 阶排列中,奇偶排列各占一半,n2?n
思考题解答证 设在全部 阶排列中有 个奇排列,个偶排列,现来证,
n s t
ts?
将 个奇排列的前两个数对换,则这 个奇排列全变成偶排列,并且它们彼此不同,所以
s s
.ts?
若将 个偶排列的前两个数对换,则这 个偶排列全变成奇排列,并且它们彼此不同,于是有
t t
.st?
故必有,ts?
