1.2排列-精品课程在线.docVIP

1.2 排 列 　　教　学　过　程 备　注 教学引入 教学内 容 一、排列及其奇偶性： 1、排列： 1）n个数码1，2，…，n组成的一个有序组i1 i2…in称为一个n元排列. 注：n元排列就是n个不同元素的全排列，n个数码1，2，…，n的排列共有：n(n(1)…21＝n! (个)（用提问的方式） n元排列中的n!个排列中，排列123…n称为标准排列，它具有自然顺序，而在其它n!-1个排列中，都或多式少地违反了自然顺序。 2）在一个排列中若有较大的数码排在较小的数码之前（不一定定相邻），把这种大小颠倒的情形称为该排列的一个反序(或逆序)。 在一个排列中出现的反序总数叫做这个排列的反序数，记作((i1 i2…in).如：((2431)=4， ((534162)=9。 提问：如何计算n元排列的反序数？ 一个排列i1 i2…in的反序数((i1 i2…in)的计算方法归纳如下： ▲先看有多少个数码排在1的前面，设为m1个，那么就有m1个数码与1构成反序；然后把1划去，再看有多少个数码排在2的前面，设为m2个，那么就有m2个数码与2构成反序；再划去2，……由此可得: ( (i1 i2…in)＝m1＋m2＋＋mn( (i1 i2…in)＝( (i1 i2…in)＝1 由数码1，2，3，4构成的全部4元排列共有4！＝24 1234，1243，1324，1342，1423，1432 2134，2143，2314，2341，2413，2431 3124，3142，3214，3241，3412，3421 4123，4132，4213，4231，4312，4321. 定义2 反之，在一个排列中，如果一个较小的数码排在一个较大的数码之前，那么称这两个数码构成一个顺序. 给定由数码1，2，…，n构成的一个排列i1 i2…in后，我们可以这样来 例2 ( (986754231)＝8＋6＋6＋5＋4＋2＋2＋1＋0＝34 . 由数码1，2，…，n构成的反序数最多的排列是哪一个？反序数是多少？ 显然任意两个数码都能构成反序的排列其反序数最大. 因此，反序数最大的排列是n (n-1)…21，其反序数是 ( [n(n(1)…2 1]＝( n(1)＋( n(2)＋＋2＋1＝n(n(1). 定义3 如果( (i1 i2…in)是偶数(零也算做偶数)，则称 i1 i2…in为偶排列；如果( (i1 i2…in)是奇数，则称i1 i2…in为奇排列. 例如，1243是奇排列，2143是偶排列. 在全部的6个3元排列中，123，231，312是偶排列，而132，213，321是奇排列. 在这里，奇、偶排列各占一半. 一般说来，在所有n!个n元排列中，奇排列与偶排列各占一半. 为了证明这一结论，还需要进一步研究排列的奇偶性. 把一个排列中某两个数码的位置互换，而其余的数码保持不动，就得到一个新排列，这样的一个变换称为对换. 例4 ( (4312)＝54312是奇排列，对换数码1与4得到排列1342，( (1342)＝21342是偶排列. 定理1.2.1 一次对换改变排列的奇偶性. 证 情形1 被对换的两个数码在排列中是相邻的情形. 设 … j k … (1) 经对换j与k变成排列 … k j … (2) 这里“…”表示不变动的数码，显然在(1)与(2)中，j和k与前后不动的数码构成的反序或顺序都是相同的，不同的只是j与k的次序变了，若原来构成反序，经对换后，则k与j不构成反序，这样排列(2)比排列(1)的反序数少1. 反之，则排列(2)比(1)的反序数多1. 无论是减少1或增加1，排列的奇偶性都改变了. 情形2 被对换的两个数码不相邻. 设排列为 … j i1 i2 … is k …， (3) 对换j与k，得到排列 … k i1 i2 … is j …. (4) 不难看出，这样一个不相邻的两个数码的对换可以通过若干个相邻两个数码的对换来实现. 从(3)出发，将k与is对换，再与is(1对换，…，与i1对换，最后与j对换，共经s＋1(3)变成 … k j i1 i2 … is …. (5) 再从(5)出发，把j与i1, i2,…, is 一个一个地对换，共经过s次相邻数码的对换，排列(5)就变成了排列(4). 因此，j与k的直接对换可经2s＋12s＋11，排列(3)与(4)的奇偶性不同. □ 推论1.2.2 奇数次对换改变排列的奇偶性，偶数次对换不改变排列的奇偶性. 有了定理1.2.1，便可证明 定理1.2.3 在n! (n ( 2)个n元排列中，奇偶排列的个数相等，各有个.