《全排列和对换》PPT课件.ppt

1,1.2 全排列和对换,二、排列的逆序数,一、全排列,三、对换,四、小结,2,一、全排列,把n个不同的元素排成一列，叫做这n个元素,的全排列(或排列).,例如,1,2有,个全排列：,1 2，,2 1,2,1,2,3有,个全排列：,1 2 3,6,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1,n个不同的元素的所有排列的种数：,？,3,二、全排列的逆序数,先规定一个标准次序.,如自然次序：,-标准次序,-有,个逆序,-有,个逆序,偶排列：,奇排列：,逆序：,两个元素的次序与标准次序不同，,就说有,1个逆序.,逆序数：,排列中所有逆序的总数.,4,逆序数的计算方法,分别计算出排列中每个元素前面比它大的元素,个数之和，,即算出排列中每个元素的逆序数，,它们,之总和即为所求排列的逆序数.,求排列32514的逆序数.,解,例1,3 2 5 1 4,于是排列32514的逆序数为,方法1,5,方法2,分别计算出排在 1,2,n-1 的位置上的数后面比它小的数码之和，即分别算出 1,2,n-1 这 n-1 个元素的逆序个数，这些元素的逆序个数的总和即为所求排列的逆序数.,6,求下列排列的逆序数,例2,解,7,解,当 时为偶排列；,当 时为奇排列.,例3 计算下列排列的逆序数，并讨论它们的奇偶性.,8,解,当 为偶数时，排列为偶排列，,当 为奇数时，排列为奇排列.,9,解,当 为偶数时，排列为偶排列，,当 为奇数时，排列为奇排列.,10,练习,求下列排列的逆序数,(1),一般地,11,三、对换（了解）,定义,在排列中，将任意两个元素对调，其余元素不动，这种作出新排列的手续叫做对换,将相邻两个元素对调，叫做相邻对换,例如,12,定理1一个排列中的任意两个元素对换，排列改变奇偶性,证明：,略,推论,奇排列调成标准排列的对换次数为奇数，偶排列调成标准排列的对换次数为偶数.,13,四、小结,n个不同的元素的所有排列种数为,排列具有奇偶性.,逆序数的计算方法:,计算每个元素的逆序数，其和为所求排列的逆序数.,14,作业：,P21 习题一2.(2)(4)(5)(6),