全排列及其逆序数

1、2 全排列及其逆序数全排列及其逆序数全排列的概念全排列的概念 逆序的概念逆序的概念 计算排列逆序数的方法计算排列逆序数的方法下页关闭 由于对角线法则只适用于二、三由于对角线法则只适用于二、三阶行列式，为研究四阶及更高阶的行阶行列式，为研究四阶及更高阶的行列式，必须用到逆序数的概念。本节列式，必须用到逆序数的概念。本节主要介绍全排列的概念以及逆序数的主要介绍全排列的概念以及逆序数的求法。求法。用用1 1、2 2、3 3三个数字，可以组成多少个没有重三个数字，可以组成多少个没有重引例引例 解解总共有总共有3 32 21= 1= 6 6种种放法。放法。123123， 132132， 213213，

2、231231， 312312， 321321。这这6 6个不同的三位数是：个不同的三位数是：复数字的三位数？复数字的三位数？上页下页返回在数学中，把考察的对象叫做在数学中，把考察的对象叫做元素元素。全排列的概念全排列的概念于是引例可抽象成：把于是引例可抽象成：把 3 个不同的元素排成一列，个不同的元素排成一列，共有几种不同的排法？共有几种不同的排法？ 一般地，我们可以讨论一般地，我们可以讨论“把把 n 个元素排成一列，共个元素排成一列，共有几种不同的排法有几种不同的排法”的问题。的问题。上页下页返回 定义定义 把把 n 个不同的元素排成一列，叫做这个不同的元素排成一列，叫做这 n 个元素的个元

3、素的全排列全排列（简称（简称排列排列）。）。 n 个不同元素的所有排列的种数，通常用个不同元素的所有排列的种数，通常用 Pn表表示。示。例如例如, , 引例的结果是引例的结果是 P3=3=32 21=61=6。上页下页返回 首先从首先从 n 个元素中任取一个放在第一个位置上，个元素中任取一个放在第一个位置上，有有 n 种取法；种取法； 又从剩下的又从剩下的 n1 1 个元素中任取一个放在第二个元素中任取一个放在第二个位置上，有个位置上，有 n1 1 种取法；种取法； 这样继续下去，直到最后只剩下一个元素放在这样继续下去，直到最后只剩下一个元素放在第第 n 个位置上，只有种取法。个位置上，只有种

4、取法。计算计算 Pn 的公式：的公式：上页下页返回于是于是 n 个元素全排列的个元素全排列的总数总数是：是：!12)1(nnnPn 例如例如;241234! 44 P.12012345! 55 P上页下页返回 对于对于 n 个不同的元素，规定各元素之间有一个个不同的元素，规定各元素之间有一个标准次序标准次序（例如（例如 n 个不同的自然数，可以规定个不同的自然数，可以规定由小由小到大到大为标准次序）。为标准次序）。 在这在这 n 个元素的任一排列中，当某两个元素的个元素的任一排列中，当某两个元素的先后次序与标准次序不同先后次序与标准次序不同时，就说有时，就说有1 1个逆序个逆序。逆序的概念与全

5、排列的分类逆序的概念与全排列的分类 一个排列中所有逆序的总数叫做这个排列的一个排列中所有逆序的总数叫做这个排列的逆逆序数序数。上页下页返回偶排列：偶排列：逆序数为偶数的排列逆序数为偶数的排列 显然，排列的逆序数为非负整数，因此按数的显然，排列的逆序数为非负整数，因此按数的一个分类得到：一个分类得到：排列分类排列分类 奇排列：奇排列：逆序数为奇数的排列逆序数为奇数的排列上页下页返回 不妨设不妨设 n 个元素为个元素为 1 1 至至 n 这这 n 个自然数，并个自然数，并规定规定由小到大由小到大为标准次序。为标准次序。设设 为这为这 n 个自然数的一个排列。个自然数的一个排列。nppp21方法一方

6、法一在排列在排列nppp21中，直接找出次序颠中，直接找出次序颠倒了的元素对的个数，这也就是该排列的逆序数。倒了的元素对的个数，这也就是该排列的逆序数。例例1判断排列判断排列2341的奇偶性。的奇偶性。解解 在排列在排列2341中，构成逆序的数对有中，构成逆序的数对有21, 31, 41,故排列故排列2341的逆序数的逆序数. 3 t所以所以2341是奇排列。是奇排列。计算排列的逆序数的方法计算排列的逆序数的方法上页下页返回方法二方法二nppp21在排列在排列中，中， 如果比如果比,n),(ipi21 大的且排在大的且排在ip前面的元素有前面的元素有it则这个排列的则这个排列的逆序逆序数数是是.121 niinttttt个，个，上页下页返回求排列求排列3251432514的逆序数。的逆序数。解解01t12t03t34t15t于是排列的于是排列的总逆序数总逆序数为为. 513010 t例例3上页下页返回3 2 5 1 43 2 5 1 4Ex.2求排列求排列1 3 5 7 9 10 8 6 4 2的逆序数。的逆序数。解解208642000000 tEx.3 求求ji,使使9561274ji成为偶排列。成为偶排列。解解