S11排列及对换11章节.ppt

§1.1 排列及对换,一、排列及其逆序数 1.排列 2.逆序数 3.排列的奇偶性 二、对换,一、排列及其逆序数,1234，1243，1324，1342，1423，1432， 2134，2143，2314，2341，2413，2431， 3124，3142，3214，3241，3412，3421， 4123，4132，4213，4231，4312，4321,1.排列 定义1 n 个不同的元素按照一定的次序排成一列， 叫做这 n 个元素的一个全排列，简称 n 阶排列一、排列及其逆序数,1.排列 定义1 n 个不同的元素按照一定的次序排成一列， 叫做这 n 个元素的一个全排列，简称 n 阶排列自然数 1，2，3，4的全排列： 1234，1243，1324，1342，1423，1432， 2134，2143，2314，2341，2413，2431， 3124，3142，3214，3241，3412，3421， 4123，4132，4213，4231，4312，4321,n个元素共有 n! 个全排列,一、排列及其逆序数,自然数 1，2，3，4的全排列： 1234，1243，1324，1342，1423，1432， 2134，2143，2314，2341，2413，2431， 3124，3142，3214，3241，3412，3421， 4123，4132，4213，4231，4312，4321,n个元素共有 n! 个全排列,逆序数,1.排列 定义1 n 个不同的元素按照一定的次序排成一列， 叫做这 n 个元素的一个全排列，简称 n 阶排列。

一、排列及其逆序数,2.逆序数 定义：对于1，2，…，这个自然数的任一 n 阶排列，规定自然数从小到大构成的排列12…为标准次序，称为标准排列（或自然排列）.,,逆序数的定义,一、排列及其逆序数,2.逆序数 定义：对于1，2，…，这个自然数的任一 n 阶排列，规定自然数从小到大构成的排列12…为标准次序，称为标准排列（或自然排列）.,定义2 对任一n阶排列，如果两个元素中较大元素排在较小元素的前面，那么就称这两个元素构成一个逆序（反序）.一个排列中所有逆序的总数，叫做这个排列的逆序数. 记为：,,一、排列及其逆序数,逆序数的计算方法,其中 为排在 前面且比 大的数的个数,例1 求排列43152的逆序数.,一、排列及其逆序数,逆序数的计算方法,其中 为排在 前面且比 大的数的个数,练习,例1 求排列43152的逆序数.,=2+3+1+0+0=6,解：,一、排列及其逆序数,逆序数的计算方法,其中 为排在 前面且比 大的数的个数,答案,例1 求排列43152的逆序数.,=2+3+1+0+0=6,解：,练习 求排列28516347的逆序数.,一、排列及其逆序数,逆序数的计算方法,其中 为排在 前面且比 大的数的个数,3.排列的奇偶性,例1 求排列43152的逆序数.,=2+3+1+0+0=6,解：,练习 求排列28516347的逆序数.,13,一、排列及其逆序数,3.排列的奇偶性,定义3 逆序数为偶数的排列称为偶排列； 逆序数为奇数的排列称为奇排列.,自然数1，2，3 构成的6个排列,一、排列及其逆序数,3.排列的奇偶性,,定义3 逆序数为偶数的排列称为偶排列； 逆序数为奇数的排列称为奇排列.,自然数1，2，3构成的6个排列：,132，213，321,123，231，312,,,,一、排列及其逆序数,3.排列的奇偶性,,定义3 逆序数为偶数的排列称为偶排列； 逆序数为奇数的排列称为奇排列.,自然数1，2，3构成的6个排列：,132，213，321,123，231，312,偶排列,,奇排列,对换,二、对换,定义4 在一个排列中，把任意两个元素i,j的位置对调，而其它元素不动，就得到一个新的排列.对于排列所施行的这样一个变换叫做一个对换,记为(i,j).,,,,二、对换,定义4 在一个排列中，把任意两个元素i,j的位置对调，而其它元素不动，就得到一个新的排列.对于排列所施行的这样一个变换叫做一个对换,记为(i,j).,对换改变奇偶,二、对换,定理1 对换改变排列的奇偶性.,奇排列,一次对换,53124,52134,,（2，3）,偶排列,奇偶排列 个数相等,二、对换,定理2 奇排列和偶排列的个数相等.,,,奇排列 个,偶排列 个,＋,＝ 个,奇排列 个,偶排列 个,作业,本节课后可以完成的作业,P18（习题一） 一、填空题 1，2，3，8 二、选择题 1，3 三、计算与证明题 1（1），3（1，2）,。