第二节 排列

【课前导读】

为了从理论上系统地介绍n阶行列式的定义，本节介绍了排列、逆序数、排列的奇偶性和对换等概念，讨论了对换对排列奇偶性的影响，并分析了n阶排列中奇偶排列的数量关系．同时，为了更好地理解排列等概念，本节还介绍了加法原理和乘法原理．

【学习要求】

1．了解加法原理与乘法原理．

2．理解关于排列奇偶性的两个定理及证明．

3．掌握排列逆序数的计算方法．

一、加法原理和乘法原理

加法原理和乘法原理是在大量观察、实践的基础上，经过归纳、概括而得出的．加法原理与分类有关，乘法原理与分布有关，它们是分析处理排列组合等问题的基本原理．下面对它们作一个简单的介绍．

加法原理：如果完成一件事情共有n类方法，在第一类方法中有m1种不同的方法，在第二类方法中有m2种不同的方法，…，在第n类方法中有mn种不同的方法，那么完成这件事情共有m1+m2+…+mn种不同的方法

乘法原理：如果完成一件事件需要分成n步，在第一步中有m1种不同的方法，在第二步中有m2种不同的方法，…，在第n步中有mn种不同的方法，那么完成这件事情共有m1m2…mn种不同的方法．

例4 在所有的两位数中，个位数大于十位数的两位数共有多少个？

解 据题意，可按个位数分别为2,3,4,5,6,7,8,9将所求的两位数分成8类．在每一类中，满足条件的两位数分别有1个、2个、3个、4个、5个、6个、7个、8个．根据加法原理，满足条件的两位数共有

1+2+3+4+5+6+7+8=36（个）.

例5 将n个球随机地放入N（N≥n）个盒子中，且每个盒子内至多只有一个球，问共有多少种放法？

解 将n个球随机地放入N个盒子中，共需分成n步，先放第一个球，再放第二个球，…，最后放第n个球．由题意知，第一个球有N种放法，第二个球有N-1种放法，…，第n个球有N-n+1种放法．根据乘法原理共有N（N-1）…（N-n+1）种放法．

二、排列及其逆序数

定义1-1 由n个数码1,2, …, n组成的一个n元有序数组i1i2…in称为一个n阶全排列（简称排列）.

在排列i1i2…in中，i1, i2, …, in可以表示数码1,2, …, n中的任意一个，且两两不相等．例如，在五阶排列53421中，i1=5, i2=3, i3=4, i4=2, i5=1.

根据乘法原理，n个数码1,2, …, n共构成n！个排列．其中，排列12…n中的数码由左到右是按从小到大的自然顺序排列的，我们称这样的排列为标准排列．显然，在所有的n阶排列中，只有一个标准排列，而其余的n阶排列都或多或少地破坏了自然顺序．例如，在五阶排列53421中，5和3, 5和4, 5和2, 5和1, 3和2, 3和1, 4和2, 4和1, 2和1的顺序都与自然顺序相反．下面使用逆序和逆序数来描述和统计这种现象．

定义1-2 在一个n阶排列i1i2…in中，如果一对数的排列顺序与自然顺序相反，即排在左边的数比排在右边的数大，那么就称它们为一个逆序．一个排列中，逆序的总数称为排列的逆序数，记为τ（i1i2…in）.

通常，我们使用枚举法来计算排列i1i2i3…in-1in的逆序数．首先分析i1与i2, i3, …，in-1, in是否构成逆序，并计数为m1；然后分析i2与i3, …, in-1, in是否构成逆序，并计数为m2；依次类推，最后分析in-1与in是否构成逆序，并计数为mn-1，从而可得

τ（i1i2…in）=m1+m2+…+mn-1.

例6 求五阶排列53421的逆序数．

解 τ（53421）=4+2+2+1=9.

例7 求n阶排列123…（n-1）n和n（n-1）…321的逆序数．

解 τ（123…（n-1）n）=0+0+0+…+0=0，

定义1-3 逆序数为偶数的排列称为偶排列，逆序数为奇数的排列称为奇排列．

例如，排列53421为奇排列，排列123…（n-1）n为偶排列，排列n（n-1）…321的奇偶性与n有关．

定义1-4 在一个排列i1…is…it…in中，只交换其中数码is和it的位置，其余数码保持不动，可以得到一个新排列i1…it…is…in，对排列施行的这种运算称为对换，一般使用符号（is, it）表示．若交换的数码处于相邻位置，则称该对换为相邻对换．

例如，.

显然，非相邻对换可以通过若干次相邻对换逐步实现．另外，一个n阶排列经过对换后还是n阶排列，不会改变排列的阶数，从这个意义上来说，对换是封闭的．

定理1-1 一次对换会改变排列的奇偶性．

证明 （1）先考虑相邻对换的情形．假设原排列为i1…isabj1…jt，经过相邻对换（a, b）后，得到一个新排列i1…isbaj1…jt.

显然，新排列相对于原排列，数码相对位置发生变化的只有数码a和b．这就是说，在原排列i1…isabj1…jt中，若数码a和b构成逆序，则在新排列i1…isbaj1…jt中，数码b和a不构成逆序．反之亦然．从而

τ（i1…isbaj1…jt）=τ（i1…isabj1…jt）±1，

可见，一次相邻对换会改变排列的奇偶性．

（2）再考虑非相邻对换的情形．假设原排列为i1…isak1…krbj1…jt，经过对换（a, b）后，得到一个新排列i1…isbk1…kraj1…jt，这里r≥1．不难看出，非相邻对换可以经过2r+1次相邻对换实现，具体路径如下：

i1…isak1…krbj1…jti1…isbk1…kraj1…jt，显然，2r+1为奇数，由（1）知奇数次相邻对换也改变了排列的奇偶性．可见，一次非相邻对换会改变排列的奇偶性．

综上（1）和（2）可得，一次对换会改变排列的奇偶性．

定理1-2 在所有n（n≥2）阶排列中，奇排列和偶排列各占一半，即各有个．

证明 易知所有n阶排列共有n！个，用A表示所有n阶奇排列构成的集合，用B表示所有n阶偶排列构成的集合，并用A和B分别表示集合A和B中元素的个数．

若对所有的n阶排列进行一次相同的对换，则集合A中所有奇排列都变成了偶排列．由假设知，在所有n阶排列中，偶排列共有个，从而可得，同理可得≤，从而有.

习题1-2

1．用1,2,3,4,5,6这6个数字，问：

（1）总共可以组成多少个6位数？

（2）总共可以组成多少个6位的偶数？

（3）总共可以组成多少个没有重复数字的6位数？

2．求下列排列的逆序数：

（1）162435；

（2）293674518；

（3）7635421；

（4）135…（2n-1）246…2n.

3．试确定数码i和j的值，使得六阶排列：

（1）63i5j1成为奇排列；

（2）3i26j5成为偶排列．

4．设i1i2…in-1in为一个n阶排列，证明：

5．求证：

（1）一个n阶奇排列i1i2…in-1in，经过奇数次对换变成标准排列12…（n-1）n；

（2）一个n阶偶排列i1i2…in-1in，经过偶数次对换变成标准排列12…（n-1）n.