下载文档原格式
1.2.1 排列与逆序定义1.2.1由自然数1，2，······，n 组成的一个有序数组称为一个n 元排列.例如：1，2，3，4，55，1，2，3，45，3，2，1，4都是数1，2，3，4，5的一个排列.问题：n 个数的不同排列有个.n !标准排列(自然排列).按数的大小次序，由小到大的排列称为定义n 阶排列1234…n 称为n 阶自然序排列.计算排列的逆序数的方法：分别计算出排在1,2,…,n-1,n前面比它大的数码之和即分别算出1,2,…,n-1,n这n个元素的逆序数，这个元素的逆序数的总和即为所求排列的逆序数例1 求排列32514的逆序数.解在排列32514中,3排在首位,逆序数为0;2的前面比2大的数只有一个3,故逆序数为1;3 2 5 1 401031于是排列32514的逆序数为(32514)01031τ=++++.5=5的前面没有比5大的数,其逆序数为0;1的前面比1大的数有3个,故逆序数为3;4的前面比4大的数有1个,故逆序数为1;例2 计算下列排列的逆序数()2179863541解453689712544310010(217986354)τ=18=54+0100134+++++++()()()212321n n n−−L 解()()(12321)n n n τ−−L ()()12321n n n−−L 0=000000考虑，在1，2，3 的全排列中有个偶排列：有个奇排列：123，231，312 132，213，32133一般说来，在n个数码的全排列中，奇偶排列各占一半.定义1.2.4把一个排列中的任意两个数交换位置，而其余数码不动，叫做对该排列作一次对换，简称对换.将相邻的两个数对换，称为相邻对换.ml b b a a L L 11例如b a ml b b a a a L L 11a b nm l c c b b a a L L L 111n m l c c a b b b a a L L L 111b a a 2.对换定理1 一个排列中的任意两个元素对换，排列改变奇偶性．证明设排列为m l b b ab a a L L 11对换与a bml b b ba a a L L 11除外，其它元素的逆序数不改变.b ,a ba a b 的逆序数不变;经对换后的逆序数增加1 ,当时，b a <当时，b a >经对换后的逆序数不变，的逆序数减少1.a b 因此对换相邻两个元素，排列改变奇偶性.设排列为nm l c bc b ab a a L L L 111现来对换与a .b 次相邻对换m nm l c c b b ab a a L L L 111次相邻对换1+m n m l c c a b b b a a L L L 111,111n m l c bc b ab a a L L L ∴次相邻对换12+m ,111nm l c ac b bb a a L L L 所以一个排列中的任意两个元素对换，排列改变奇偶性.nm l c c b b b a a a L L L 111ab2!n q p ==定理任意一个n 阶排列都可以经过一系列对换变成自然序排列，并且所作对换的次数与该排列有相同的奇偶性.证明用数学归纳证明当n=1时，结论显然成立.假设结论对n-1阶排列成立,现证对n 阶排列也成立..,,,21阶排列是任一设n j j j n L ,n j n =若.1,,,121阶排列个是一则−−n j j j n L 由假设知，121,,,−n j j j L 可经过一系列对换变成自然序排列，从而nn j j j j ,,,,121−L 可经过一系列对换变成自然序排列.),,,n n j n n j 则先作对换（若≠n n n n j j j j j j j j ′′′′−−,,,,,,,,121121L L 变成使这就归结为上面的情形，结论成立.所以任意一个n 阶排列都可以经过一系列对换变成自然序排列.由于自然序排列是偶排列，由定理1可知，对换一个改变排列奇偶性，所以将一奇排列变成自然序排列推论需要作奇数次对换，而将一偶排列变成自然序排列则需要作偶数次对换,证毕.任意两个n 阶排列都可以经过一系列对换互变，而且若这两个排列的奇偶性相同，则所作的则所作的对换次数是奇数.对换次数是偶数；若这两个排列的奇偶性相反，小结1.排列,逆序数，奇排列,偶排列,对换的定义.2.一个排列中的任意两个元素对换，排列改变奇偶性．思考题证明在全部阶排列中,奇偶排列各占一半. n ()2≥n 思考题解答证设在全部阶排列中有个奇排列, 个偶排列,现来证.n s t t s =将个奇排列的前两个数对换,则这个奇排列全变成偶排列,并且它们彼此不同,所以s s .t s ≤若将个偶排列的前两个数对换,则这个偶排列全变成奇排列,并且它们彼此不同,于是有t t .s t ≤故必有.t s =作业：P251（1）（5）2（1）（2）3（2）4（1）56 （1）（3）。
全排列、逆序数§1.2 全排列、逆序数猜测四阶行列式展开项不只是对角线展开项。
还含有其他项。
行列式展开后有正、负项，为什么二、三阶展开项中主对角是正项、副对角是负号？如何确定每项前的正、负号？121.2.1、全排列及其逆序数同的排法？，共有几种不个不同的元素排成一列把n 问题定义1.2.1把个不同的元素排成一列，叫做这 个元素的全排列（或排列）.n n 个不同的元素的所有排列的种数，这里 用表示.n n P 例如1233⋅⋅=P .6=n P n =)1(−⋅n )2(−⋅n 123⋅⋅⋅⋅L !.n =同理3在一个排列 中，若数则称这两个数组成一个逆序.()n s t i i i i i L L L 21s t i i >例如 排列32514 中，定义1.2.2 我们规定各元素之间有一个标准次序, n 个不同的自然数，规定由小到大为标准次序.排列的逆序数3 2 5 1 4逆序逆序逆序定义1.2.3 一个排列中所有逆序的总数称为此排列的逆序数.例如排列32514 中，223 2 5 1 41故此排列的逆序数为2 +1 +2 =5.4排列的奇偶性逆序数为奇数的排列称为奇排列;逆序数为偶数的排列称为偶排列.56例2 计算下列排列的逆序数，并讨论它们的奇偶性.()2179863541解45368971210345401=N 18=此排列为偶排列.10345401++＋＋＋＋＋7()()()321212L −−n n n 解12+++L (),21−=n n 当时为偶排列；14,4+=k k n 当时为奇排列.34,24++=k k n ()1N −=n ()2−+n ()()32121L −−n n n 1−n 2−n8()()()()()()k k k k k k 132322212123+−−−L 解22)12(1)12(31k k k k t =×−+=−+++=L 当为偶数时，排列为偶排列，k 当为奇数时，排列为奇排列.k ()()()()()kk k k k k 132********+−−−L ↓−12k ↓0↓−32k ↓0↓−52k L ↓19 1.2.2、对换的定义定义1.2.4在排列中，将任意两个元素对调，其余元素不动，这种作出新排列的手续叫做对换．将相邻两个元素对调，叫做相邻对换．ml b b b a a a L L 11例如b a m l b b a b a a L L 11a b n m l c c b b a a L L L 111nm l c c a b b b a a L L L 111b a a101.2.3、对换与排列的奇偶性的关系定理定理1.2.11.2.11.2.1 一个排列中的任意两个元素对换， 一个排列中的任意两个元素对换，排列改变奇偶性．证明（思路：先看简单情形：相邻对换，再证一般对换�由相邻对换变化而来由相邻对换变化而来））设排列为m l b b ab a a L L 11对换 与a b m l b b ba a a L L 11除 外，其它元素的逆序数不改变.b ,a ab ba 例：12排列为0－偶数，对换后21排列为1－奇数11当 时，b a >a b 的逆序数不变;经对换后的逆序数增加1 ,经对换后 的逆序数不变 ， 的逆序数减少1.a b 因此对换相邻两个元素，排列改变奇偶性.设排列为nm l c bc b ab a a L L L 111当时，b a <现来对换与a .b12次相邻对换m n m l c c b b ab a a L L L 111次相邻对换1+m n m l c c a b b b a a L L L 111,111n m l c bc b ab a a L L L ∴次相邻对换12+m ,111nm l c ac b bb a a L L L 所以一个排列中的任意两个元素对换，排列改变奇偶性.nm l c c b b b a a a L L L 111ab推论奇排列调成标准排列的对换次数为奇数，偶排列调成标准排列的对换次数为偶数偶排列调成标准排列的对换次数为偶数..证明由定理1知对换的次数就是排列奇偶性的变化次数,而标准排列是偶排列(逆序数为0),因此知推论成立.13142 排列具有奇偶性.1 n 1 n 个不同的元素的所有排列种数为个不同的元素的所有排列种数为个不同的元素的所有排列种数为n! .n! .n !.n 1.2.4、小结3 对换改变排列的奇偶性.。
