《推荐全排列与逆序数》由会员分享，可在线阅读，更多相关《推荐全排列与逆序数（7页珍藏版）》请在金锄头文库上搜索。
1、2 2 全排列及其逆序数全排列及其逆序数主要内容：主要内容：一、全排列一、全排列二、排列的逆序数二、排列的逆序数2 2 全排列及其逆序数全排列及其逆序数例例 123,321,132,312,213,231都是元素1,2,3的排列, P332 1 6. 由上例可推知Pn n！定义定义:把考察的对象称为把考察的对象称为元素元素.例如例如:数字数字1,2,31,2,3.定义定义: :把把n个不同的元素排成一列个不同的元素排成一列, ,叫做这叫做这n个元素的个元素的全排全排列列( (简称简称排列排列).). n个元素的所有排列的种数用个元素的所有排列的种数用Pn表示表示. .2 2 全排列及其逆序数全
2、排列及其逆序数定义定义:对于n个不同的元素,规定各元素之间有一个标准次标准次序序(通常规定由小到大为标准次序).例例 123 是元素1,2,3的标准次序 定义定义: : 在这n个元素的任一排列中,当某两个元素的先后次序与标准次序不同时就说有1个逆序逆序. 逆序 逆序例例 132 213 2 2 全排列及其逆序数全排列及其逆序数定义定义: : 一个排列中所有逆序的总数称为这个排列的一个排列中所有逆序的总数称为这个排列的逆序数逆序数. 逆序逆序 例例 312 逆序逆序定义定义: :逆序数为奇数的排列叫做逆序数为奇数的排列叫做奇排列奇排列, , 逆序数为偶数的排列叫做逆序数为偶数的排列叫做偶排列偶排
3、列. .此排列的此排列的逆序数为逆序数为1+1=2.1+1=2.2 2 全排列及其逆序数全排列及其逆序数计算排列逆序数的方法计算排列逆序数的方法 分别计算出排列中每个元素前面比它大的数分别计算出排列中每个元素前面比它大的数码个数之和码个数之和, ,即算出排列中每个元素的逆序数即算出排列中每个元素的逆序数, ,这这每个元素的逆序数之总和即为所求排列的逆序数每个元素的逆序数之总和即为所求排列的逆序数. .2 2 全排列及其逆序数全排列及其逆序数例例 求排列3241的逆序数解: 3排在首位,逆序数为0; 2的前面比2大的数有一个数3,故逆序为1; 4是最大数,逆序为0; 1的前面比1大的数有3个数3、2、4,故逆序数为3. 于是,这个排列的逆序数为t=0+1+0+3=4, 排列3241为偶排列偶排列.2 2 全排列及其逆序数全排列及其逆序数o总结总结o1.n个不同的元素的所有排列种数为个不同的元素的所有排列种数为n!.o2.排列具有奇偶性排列具有奇偶性.o3.计算排列逆序数常用的方法有计算排列逆序数常用的方法有1种种.
