第二节全排列及其逆序数

第二节全排列及其逆序数从上节的例子我们知道，对角线法则只适用于二阶与三阶行列式，对四阶和四阶以上的行列式就不适用了.怎样计算四阶和四阶以上的行列式呢?我们先从二阶与三阶行列式的计算中找一找规律先看二阶行列式二阶行列式一共有两项，每一项均由不同行不同列的元素组成。其组成的规律是如果行标都取自然数1，2；列标只能取1，2或2，1。所以二阶行列式中有两项2211aa，。再看三阶行列式三阶行列式一共有6项，每一项均由不同行不同列的元素组成。其组成的规律是如果行标都取自然数1，2，3；列标只能取1，2，3；2，3，1；3，1，2；3，2，1；2，1，3；1，3，2。所以三阶行列式中有6项通过上述分析，我们知道了二阶行列式和三阶行列式项的组成方法。既和排列有关。2112aa.2112221122211211aaaaaaaaD333231232221131211aaaaaaaaa,312213332112322311322113312312332211aaaaaaaaaaaaaaaaaa一、全排列二阶行列式和三阶行列式项的组成方法1）行标取自然排列时，列标分别取全排列.2）项的个数就是全排列的个数。另外，我们还发现无论二阶行列式还是三阶行列式，均有一些项的前面取“+”，一些项的前面取“-”。怎样确定那些项的前面取“+”，那些项的前面取“-”呢？我们发现和排列的顺序有关。定义3把n个不同的自然数按一定次序排成一列,称为一个n元排列.记为{p1,…,pn}。例如{1，2，3}是一个三元排列，{2，3，1}也是一个三元排列。排列{1，2，…,n}称为n元自然排列n个不同的自然数的所有排列，称为n元全排列,n元全排列的个数通常用Pn表示.二阶行列式和三阶行列式项的组成方法1）行标取自然排列时，列标分别取全排列2）项的个数就是全排列的个数。另外，我们还发现无论二阶行列式还是三阶行列式，均有一些项的前面取“+”，一些项的前面取“-”。怎样确定那些项的前面取“+”，那些项的前面取“-”呢？我们发现和排列的顺序有关排列的逆序数我们规定各元素之间有一个标准次序,n个不同的自然数，规定由小到大为标准次序.定义4在一个n元排列中，若一个大的数排在一个小的数的前面，则称这个排列有一个逆序。定义5一个n元排列{p1,…,pn}中所有逆序的总数称为此排列的逆序数，记为计算排列逆序数的方法分别计算出排列中每个元素前面比它大的数码nPn)1(n)2(n123!.n)(,...,1npp个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆序数.例4求排列{3,2,5,1,4}的逆序数解在排列{3,2,5,1,4}中排在首位,逆序数为0;2的前面比2大的数只有一个3,故逆序数为1;5的前面没有比5大的数,其逆序数为0;1的前面比1大的数有3个,故逆序数为3;4的前面比4大的数有1个,故逆序数为1;32514于是排列的逆序数为例5计算下列排列的逆序数，并讨论它们的奇偶性.解逆序数的性质排列的奇偶性逆序数为奇数的排列称为奇排列逆序数为偶数的排列称为偶排列0103113010)4,1,5,2,3(.5}4,5,3,6,8,9,7,1,2{118010013445}4,5,3,6,8,9,7,1,2{1}1,2,3,,2,1,{2nnn.2)1(12...)2()1(}1,2,3,,2,1,{)2(nnnnnnn定义5将一个排列中的某两个数的位置互换而其余的数不动,这样得到一个新的排列.这种变换称为对排列作一次对换,将相邻的两个数对换称为相邻对换.定理1对排列进行一次对换将改变其奇偶性.证：首先证明对排列进行一次相邻的对换将改变其奇偶性设原排列为{a1,…,an,a,b,b1,…,bm}将a,b对换后所得新排列为{a1,…,an,b,a,b1,…,bm}由于在新排列中a1,…,an,b1,…,bm的位置没有改变，所以它们的逆序数没有改变。只有a,b的位置改变了。因此对排列进行一次相邻的对换将改变其奇偶性。再证一般情况},...,,,,...,,,,...,{...},...,,,...,,,,,...,{},...,,,...,,,,,...,{},...,,,...,,,,...,{,},...,,,...,,,,...,{12111211212111111111smnsmnsmnsmnsmnccbabbbaamccbbabbaabaccbbbabaabaccabbbaabaccbbbaaa，次相邻对换后，变为，对换，变为与将，对换，变为与将邻对换达到上述目的。我们可以通过一系列相。，对换后的新排列为将，，设原排列为1),...,,,,,...,(),...,,,,,...,(,1),...,,,,,...,(),...,,,,,...,(,11111111mnmnmnmnbbbaaabbabaababbbaaabbabaaba若若.12},...,,,...,,,,...,{,,...,},...,,,,...,,,,...,{,11111211列的奇偶性改变次相邻的对换，所以排一共进行了。，排列就可变为我们所要求的对换分别与再将，变为对换与将mccabbbaabbbccabbbbaabasmnmsmn由定理1可得下列推论推论1将奇排列变成自然排列所需的对换次数为奇数,将偶排列变成自然排列所需的对换次数为偶数.证：因为自然排列的逆序数为零，所以是偶排列。如果原排列是奇排列，变成偶排列需要的对换次数为奇数，所以奇排列变成自然排列所需的对换次数为奇数。同理可证偶排列的情况。证毕推论2在全体n元排列(n1)中,奇排列和偶排列各占一半.证：设在全体n元排列(n1)中,奇排列一共有s个，偶排列一共有t个.将每个奇排列的前面两个数字对换，可得到s个偶排列，所以s≤t。将每个偶排列的前面两个数字对换，可得到t个偶排列，所以t≤s。因此s=t,奇排列和偶排列各占一半.证毕我们有了逆序数的概念后，再来讨论行列式的项前面的符号就很方便了。先看二阶行列式如果行标都取自然数1，2；列标的排列为{1，2}或{2，1}其中{1，2}是偶排列，前面的符号为“+”；{2，1}是奇排列，2112aa前面的符号为“-”；再看三阶行列式如果行标都取自然数1，2，3；列标排列为{1，2，3}；{2，3，1}；{3，1，2}；{3，2，1}；{2，1，3}；{1，3，2}。2211aa.2112221122211211aaaaaaaaD333231232221131211aaaaaaaaa,312213332112322311322113312312332211aaaaaaaaaaaaaaaaaa其中，{1，2，3}；{2，3，1}；{3，1，2}是偶排列，相应的项前面的符号为“+”；{3，2，1}；{2，1，3}；{1，3，2}是奇排列，相应的项前面的符号为“-”。通过上述分析，我们找到了构造二阶行列式和三阶行列式有别于对角线法的新的方法。下面一节，我们将用新的方法定义一般的n价行列式，当然，我们希望用新的方法定义的n价行列式可以原来解一般的n元线性方程组.