(3.1.1)--2.1.1排列.pdf

行列式行列式Determinant如何计算平面中两个向量所围成的平行四边形的面积？如何计算平面中两个向量所围成的平行四边形的面积？如何计算以空间三个向量为边长所围成的平行六面体的体积？如何计算以空间三个向量为边长所围成的平行六面体的体积？考虑由一个矩阵决定的向量空间中的线性映射，考虑由一个矩阵决定的向量空间中的线性映射，如何确定映射前后的面积比、体积比？如何确定映射前后的面积比、体积比？排列排列Permutation1、辣，怕不？、辣，怕不？“辣”、“怕”“不”三个汉字在一起有多少种不同的组合呢？“辣”、“怕”“不”三个汉字在一起有多少种不同的组合呢？6、不！辣怕、不！辣怕3、辣不怕、辣不怕4、不怕辣、不怕辣5、怕不辣、怕不辣2、怕辣不？、怕辣不？答答问问定义定义:由由n个数个数1，2，,n 组成的一个有序数组组成的一个有序数组称为一个称为一个 n 阶阶排列排列。如如5342153421，1234512345均为五阶排列。显然，均为五阶排列。显然，n阶排阶排列共有列共有n！个。特别的！个。特别的,在在n阶排列阶排列1212 n中中,n个不个不同的自然数按由小到大的自然顺序排列，称这样的排同的自然数按由小到大的自然顺序排列，称这样的排列为列为自然序排列自然序排列。定义定义 在一个排列中在一个排列中，如果两个数前者大于后者如果两个数前者大于后者，则称这两个数构成一个则称这两个数构成一个逆序逆序。一个排列中所含逆一个排列中所含逆序的总数称为该排列的序的总数称为该排列的逆序数逆序数。排列排列的逆序数记为的逆序数记为（）。逆序数为偶数的排逆序数为偶数的排列称为列称为偶排列偶排列；逆序数为奇数的排列称为逆序数为奇数的排列称为奇排列奇排列。121j2jnj.1j2jnj.例如，在排列例如，在排列53412中中，53，54，51，52，31，32，41，42都构成逆序都构成逆序，该排列共有该排列共有8 8个逆序，个逆序，即即，因此这是个偶排列。显然，自因此这是个偶排列。显然，自然序排列的逆序数为零，它是个偶排列然序排列的逆序数为零，它是个偶排列。()853412=计算逆序数的方法计算逆序数的方法I:I:分别计算出排在分别计算出排在前面比它大的数前面比它大的数码之和，即分别算出码之和，即分别算出这这个元素个元素的逆序数，这个元素的逆序数的总和即为所求的逆序数，这个元素的逆序数的总和即为所求排列的逆序数排列的逆序数.n,n,121 n,n,121 n解：用方法解：用方法1 1 由小到大看每个数由小到大看每个数1 6 3 5 2 4 8 7 例例.求排列求排列1635248716352487的逆序数的逆序数.0 01 10 01 12 23 30 01 1t =0 0+3 3+1 1+2 2+1 1+1 1+0 0+0 0=8分别计算出排列中每个元素前面比它大的数码分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数，个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆这每个元素的逆序数之总和即为所求排列的逆序数序数.计算逆序数的方法计算逆序数的方法II:II:于是排列于是排列32514的逆序数为的逆序数为13010+=+=t.5=5的前面没有比的前面没有比5大的数大的数,其逆序数为其逆序数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;例例求排列求排列32514的逆序数的逆序数.解解 在排列在排列32514中中,3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;在一个排列中如果将它的两个数码对调，其它不变，在一个排列中如果将它的两个数码对调，其它不变，得到另一个排列，这样的变换称为一个得到另一个排列，这样的变换称为一个对换对换.定理：定理：对换改变排列的奇偶性，即作一次对换，对换改变排列的奇偶性，即作一次对换，奇排列变成偶排列，偶排列变成奇排列。奇排列变成偶排列，偶排列变成奇排列。例如例如 21354 21354 对换对换 1 1 和和 4 4，得到，得到 2435124351。定理定理任一任一n元排列与元排列与n元自然排列可通过一系列对换互元自然排列可通过一系列对换互变，并且所作对换的次数与这个变，并且所作对换的次数与这个n元排列有相同的奇偶性。元排列有相同的奇偶性。证明思路：只需注意证明思路：只需注意n元自然排列是偶排列元自然排列是偶排列