§2全排列及其逆序数
§2 全排列及其逆序数
问题把n个不同的元素排成一列,共有多少种不同的 排法? 定义把n个不同的元素排成一列,叫做这n个元素 的全排列.n个不同元素的所有排列的种数,通常用Pn 表示 显然P=n·(n-1)·(n-2)…3.2l=n 即n个不同的元素一共有n种不同的排法
问题 把 n 个不同的元素排成一列，共有多少种不同的 排法？ 定义 把 n 个不同的元素排成一列，叫做这 n 个元素 的全排列. n 个不同元素的所有排列的种数，通常用Pn 表示. ( 1) ( 2) 3 2 1 ! 显然 P n n n n n = − − = 即n 个不同的元素一共有n! 种不同的排法
3个不同的元素一共有3!=6种不同的排法 123,132,213,231,312,321 所有6种不同的排法中,只有一种排法 (123)中的数字是按从小到大的自然 顺序排列的,而其他排列中都有大的 数排在小的数之前 因此大部分的排列都不是“顺序 而是“逆序
所有6种不同的排法中，只有一种排法 （123）中的数字是按从小到大的自然 顺序排列的，而其他排列中都有大的 数排在小的数之前. 因此大部分的排列都不是“顺序” ， 而是“逆序” . 3个不同的元素一共有3! =6种不同的排法 123，132，213，231，312，321
对于n个不同的元素,可规定各元素之间的标准次序 n个不同的自然数,规定从小到大为标准次序 定义当某两个元素的先后次序与标准次序不同时, 就称这两个元素组成一个逆序 例如在排列32514中, 逆序 逆序逆序 思考题:还能找到其它逆序吗? 答:2和1,3和1也构成逆序
对于n 个不同的元素，可规定各元素之间的标准次序. n 个不同的自然数，规定从小到大为标准次序. 定义 当某两个元素的先后次序与标准次序不同时， 就称这两个元素组成一个逆序. 例如 在排列32514中， 3 2 5 1 4 逆序 逆序 逆序 思考题：还能找到其它逆序吗？ 答：2和1，3和1也构成逆序
定义排列中所有逆序的总数称为此排列的逆序数 排列运2的逆序数通常记为t(i2…in 奇排列:逆序数为奇数的排列. 偶排列:逆序数为偶数的排列 思考题:符合标准次序的排列是奇排列还是偶排列? 答:符合标准次序的排列(例如:123)的逆序数 等于零,因而是偶排列
定义 排列中所有逆序的总数称为此排列的逆序数. 排列 的逆序数通常记为 . 1 2 n i i i 1 2 ( ) n t i i i 奇排列：逆序数为奇数的排列. 偶排列：逆序数为偶数的排列. 思考题：符合标准次序的排列是奇排列还是偶排列？ 答：符合标准次序的排列（例如：123）的逆序数 等于零，因而是偶排列
计算排列的逆序数的方法 设P1P2…·Pn是1,2,…,n这n个自然数的任一排列,并 规定由小到大为标准次序 先看有多少个比P大的数排在1前面,记为t1 再看有多少个比P2大的数排在P2前面,记为t2; 最后看有多少个比p大的数排在pn前面,记为tn 则此排列的逆序数为=t1+t2+…+tn
计算排列的逆序数的方法 则此排列的逆序数为 1 2 n t t t t = + + + 设 是 1, 2, …, n 这n 个自然数的任一排列，并 规定由小到大为标准次序. 先看有多少个比 大的数排在 前面，记为 ； 再看有多少个比 大的数排在 前面，记为 ; …… 最后看有多少个比 大的数排在 前面，记为 ; 1 2 n p p p 1 p 1 p 1 t 2 p 2 p 2 t n p n p n t
例1:求排列32514的逆序数 解 t(32514)=0+1+0+3+1=5 练习:求排列453162的逆序数 解 t
例1： 求排列 32514 的逆序数. 解： t(32514) 0 1 0 3 1 5 = + + + + = 练习： 求排列 453162 的逆序数. 解： t = 9