全排列
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫n的全排列。
逆序列
逆序
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。
逆序数
一个排列中逆序的总数就称为这个排列的逆序数。
奇偶排列
逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列
相关问题
给排列，求逆序数
这个问题比较简单，直接对每个数字求一下逆序数，相加就可以了。
可以用线段树，树状数组等优化
根据逆序数推排列数
问题1
给定一个n元排列，它的逆序数存在且唯一,那么我们求一下已知一个n元排列的逆序数为m，这样的n元排列有多少？
我们用$f(n,m)$表示逆序数为m的n元排列的个数
前提知识1
对任意n>=2且0<=m<=$C_n^2$时$f(n,m)$>=1；当m>$C_n^2$时,$f(n,m)$=0
$f(2,0)=1,f(2,1)=1,f(2,2)=0$
易证
前提知识2
$f(n,m)=f(n,C_n^2-m)$
对于一个逆序数为m的n元排列，$a_1,a_2,a_3,…a_n$，那么$a_n,a_{n-1},a_{n-2}…a_1$的逆序数为$C_n^2-m$
反过来同理
前提知识3
$f(n+1,m)=f(n,m)+f(n,m-1)+…+f(n,m-n)$
考虑由$a_1,a_2,…a_n$组成的排列，那么我们在其中加上$a_{n+1}（a_{n+1}>\{a_1,a_2,…a_n\}）$的话，$a_{n+1}$ 可以放在排列中的任意一个位置
放在末尾对逆序列没有影响，那么$f(n+1,m)+=f(n,m)$，放在首位的话逆序对增加$n$那么$f(n+1,m)+=f(n,m-n)$,以此类推，放在排列中的其他位置就是$f(n+1,m)=f(n,m-i)$
那么$f(n+1,m)=f(n,m)+f(n,m-1)+f(n,m-2)+…+f(n,m-n)$
前提知识4
$f(n,0)=f(n,C_n^2)=1$
前提知识5
$f(n,1)=f(n,C_n^2-1)=n-1$
$f(n,1)=f(n-1,1)+f(n-1,0)=f(n-1,1)+1$
前提知识6
$f(n,2)=f(n,C_n^2-2)=C_n^2-1(n>2)$
由3，4，5可知
$f(n,2)=f(n-1,2)+f(n-1,1)+f(n-1,0)=f(n-1,2)+n-1$
根据$f(2,2)=0$可证
同理：
$f(n,3)=C_n^3-C_n^2-C_n^1(n>3)$
$f(n,4)=C_n^4+2C_n^3-C_n^1(n>4)$
$f(n,5)=C_n^4+3C_n^4+2C_n^3-C_n^2+1(n>5)$
$….$
问题2
给定逆序数，求满足此逆序数的最小排序
前提知识1
对于n的全排列，在它完全倒序的时候逆序数最多
前提知识2
对于一个形如$1,2,3,…,i-1,i,n,…,i+1$的排列$q$，在数$n$前保证首项为1，且严格以公差为1递增而数n以后排列任意的数列
当数$n$之后是递减的时候$q$的逆序数最多，$t=C_{n-i}^{2}$
排列$q$是出现逆序对为$t$的最小排列
前提知识3
我们把数$n$之后的第$k$小数与数$n$的前一个数(即$i$)交换，然后是数$n$后面保持逆序，这样得到的新排列的逆序对数为
$t=C_{n-i}^2+k$,且这个排列是逆序数$t$的最小排列
