全排列及其逆序数

《全排列及其逆序数》由会员分享，可在线阅读，更多相关《全排列及其逆序数（12页珍藏版）》请在金锄头文库上搜索。

1、2 全排列及其逆序数全排列的概念 逆序的概念 计算排列逆序数的方法下页关闭由于对角线法则只适用于二、三 阶行列式，为研究四阶及更高阶的行 列式，必须用到逆序数的概念。本节 主要介绍全排列的概念以及逆序数的 求法。用1、2、3三个数字，可以组成多少个没有重引例解总共有321= 6种放法 。123， 132， 213， 231， 312， 321。这6个不同的三位数是 ：复数字的三位数？上页下页返回在数学中，把考察的对象叫做元素。全排列的概念于是引例可抽象成：把 3 个不同的元素排成一列， 共有几种不同的排法？一般地，我们可以讨论“把 n 个元素排成一列，共有 几种不同的排法”的问题。上页下页返回

2、定义 把 n 个不同的元素排成一列，叫做这 n 个元素的全排列（简称排列）。n 个不同元素的所有排列的种数，通常用 Pn表 示。例如, 引例的结果是 P3=321=6 。上页下页返回首先从 n 个元素中任取一个放在第一个位置上 ，有 n 种取法；又从剩下的 n1 个元素中任取一个放在第二 个位置上，有 n1 种取法；这样继续下去，直到最后只剩下一个元素放在 第 n 个位置上，只有种取法。计算 Pn 的公式 ：上页下页返回于是 n 个元素全排列的总数是：例如上页下页返回对于 n 个不同的元素，规定各元素之间有一个 标准次序（例如 n 个不同的自然数，可以规定由小 到大为标准次序）。在这 n 个元

3、素的任一排列中，当某两个元素的 先后次序与标准次序不同时，就说有1个逆序。逆序的概念与全排列的分类一个排列中所有逆序的总数叫做这个排列的逆 序数。上页下页返回偶排列：逆序数为偶数的排列显然，排列的逆序数为非负整数，因此按数的 一个分类得到：排列分类奇排列：逆序数为奇数的排列上页下页返回不妨设 n 个元素为 1 至 n 这 n 个自然数，并 规定由小到大为标准次序。 设 为这 n 个自然数的一个排列 。方法一在排列中，直接找出次序颠 倒了的元素对的个数，这也就是该排列的逆序数。例1判断排列2341的奇偶性。解 在排列2341中，构成逆序的数对有21, 31, 41, 故排列2341的逆序数所以2341是奇排列。计算排列的逆序数的方法上页下页返回方法二在排列中， 如果比大的且排在前面的元素有则这个排列的逆序数是个，上页下页返回求排列32514的逆序数。解于是排列的总逆序数为例3上页下页返回3 2 5 1 4Ex.2求排列1 3 5 7 9 10 8 6 4 2的逆序数。 解Ex.3 求使成为偶排列。解 只有两种可能，即或由于1 2 7 4 3 5 6 8 9的逆序数故不合要求。 所以上页返回