第二节全排列及其逆序数全排列的概念排列的逆序数排列的奇偶性.PDF

2011/9/27 全排列的概念 引例 用1、2、3三个数字，可以组成多少个没 第二节 全排列及其逆序数 有重复数字的三位数？ 解解 1 2 3 百位 1 2 3 3种放法 十位 1 2 1 3 2种放法 个位 1 2 3 1种放法 共有3 ×2 ×1=6种方法 2 把n个不同的元素排成一列，共有几种不同的排法？ 排列的逆序数 规定各元素之间有一个标准次序，n 个不同 定义 把n个不同的元素排成一列，叫做这n个元 的自然数，规定由小到大为标准次序。 素的全排列（或排列）。 定义 在一个排列 i i i i i 中，若数i i 1 2 t s n t s n个不同的元素的所有排列的种数，通常用P 表示。 则称这两个数组成则称这两个数组成一个个逆序逆序。 n 例 排列32514 中 由引例 P3= 3 ×2 ×1=6 逆序 同理 Pn=n·(n-1)·(n-2)·····3·2·1=n! 3 2 5 1 4 逆序 逆序 3 4 定义 一个排列中所有逆序的总数称为此排列 排列的奇偶性 的逆序数。 逆序数为奇数的排列称为奇排列； 例 排列32514 中