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