Question

设N>=3,在1、2……N，构成的N！个N级排列中，逆序数为2的个数是？

Answer 1

设w（n,j）表示n级排列的逆序数为j的排列的个数。
则有：w（n,j）=w(n-1,j)+w(n-1,j-1)+w(n-1,j-2)+…+w(n-1,j-(n-1))
解释如下：
将w（n,j）分为n个部分，如：1,i1,i2,i3,...i(n-1) 第一个数为1，逆序数相当于w（n-1,j）
2,i1,i2,i3,...i(n-1) 第一个数为2，则1与2构成一对逆序（1在2后面），且其他不与2构成一对逆序，即后n-1个数的逆序数为j-1
3,i1,i2,i3,...i(n-1) 同理 后n-1个数的逆序数为j-2
n,i1,i2,i3,...i(n-1) 后n-1个数的逆序数为j-(n-1)
其中 j-(n-1) 的取值为非负整数。
有：w（n,2）=w(n-1,2)+w(n-1,1)+w(n-1,0) (只有三项)
迭代如下w（n-1,2）=w(n-2,2)+w(n-2,1)+w(n-2,0)
w(3,2)=w(2,2)+w(2,1)+w(2,0) (最后一项) w(2,2)=0
引理1：w（n,0）=1 (逆序数为0的排列只有一个)
引理2：w（n,1）=n-1 (证明如下：两种方式)
方式一：如上公式 w（n,1）=w(n-1,1)+w(n-1,0)
有 w（n,1)=w(n-1,1)+1
w(n-1,1)=w(n-2,1)+1
w(3,1)=w(2,1)+1 (w(2,1)=1)
故 w（n,1）=n-1
方式二：对于一个自然排列1,2,3,4,5...n (逆序数为0)
对任意两个相邻的数对换则得到逆序数为1的排列
共n-1中情况
通过上述引理：
w(n,2)=w(n-1,1)+w(n-2,1)+w(n-3,1)+...+w(2,1) +w(n-1,0)+w(n-2,0)+...w(3,0)+w(2,0)
=n-2 + n-3 + n-4 +....+2+1 + n-2
=(n-2+1)*(n-2)/2+n-2
=(n-2)*(n+1)/2
求答案啊。。。。。。。。

Answer 2

逆序数的计算　PASCAL源码
　　type 　　f=array[0..1000] of longint; 　　var 　　j,k,n:longint; 　　a:f; 　　procedure input(var a:f); 　　var 　　s:string; 　　i,j,k,t,n:longint; 　　begin 　　readln(s); 　　a[0]:=length(s); 　　for i:=1 to length(s) do 　　begin 　　if (s[i]<='9') and (s[i]>='0') then 　　a[a[0]+1-i]:=ord(s[i])-ord('0') 　　else 　　a[a[0]+1-i]:=ord(s[i])-ord('A')+10; 　　end; 　　end; 　　begin 　　readln(t); 　　input(a); 　　for j:=1 to a[0] do 　　write(a[j]); 　　writeln; 　　end. 　　C++归并排序求逆序数 　　void mergeSort(long first, long last) 　　{ 　　if(first < last) { 　　long mid = (first + last) / 2; 　　mergeSort(first, mid); 　　mergeSort(mid+1, last); 　　merge(first, mid, last); 　　} 　　} 　　void merge(long p, long q, long r) 　　{ 　　long i, j = 0; 　　long beginA = p, endA = q, beginB = q+1, endB = r; 　　while(beginA <= endA && beginB <= endB) { 　　if(a[beginA] <= a[beginB]) { 　　b[j++] = a[beginA++]; 　　} else { 　　for(int t = beginA; t <= q; t++) { 　　cout << "Found: " <<a[t] <<", "<<a[beginB]<<endl; 　　} 　　b[j++] = a[beginB++]; 　　} 　　} 　　while(beginA <= endA) { 　　b[j++] = a[beginA++]; 　　} 　　while(beginB <= endB) { 　　b[j++] = a[beginB++]; 　　} 　　for(i = 0; i < j; i++) { 　　a[p+i] = b[i]; 　　} 　　}

Answer 3

n-2+(n-2)(n-3)/2