在数字1，2，…，n（n≥2）的任意一个排列A：a1，a2，…，an中，如果对于i，j∈N*，i<j，有ai>aj，那么就称（ai，aj）为一个逆序对．记排列A中逆序对的个数为S（A）．如n=4时，在排列B：3

Question

在数字1，2，…，n（n≥2）的任意一个排列A：a₁，a₂，…，a_n中，如果对于i，j∈N^*，i<j，有a_i>a_j，那么就称（a_i，a_j）为一个逆序对．记排列A中逆序对的个数为S（A）．
如n=4时，在排列B：3，2，4，1中，逆序对有（3，2），（3，1），（2，1），（4，1），则S（B）=4．
（Ⅰ）设排列 C：3，5，6，4，1，2，写出S（C）的值；
（Ⅱ）对于数字1，2，…，n的一切排列A，求所有S（A）的算术平均值；
（Ⅲ）如果把排列A：a₁，a₂，…，a_n中两个数字a_i，a_j（i<j）交换位置，而其余数字的位置保持不变，那么就得到一个新的排列A'：b₁，b₂，…，b_n，求证：S（A）+S（A'）为奇数．

Answer 1

（Ⅰ）逆序对有（3，1），（3，2），（5，4），（5，1），（5，2），（4，1），（4，2），
（6，4），（6，1），（6，2）则S（C）=10；                                             
（Ⅱ）考察排列D：d₁，d₂，…，d_n-1，d_n与排列D₁：d_n，d_n-1，…，d₂，d₁，
因为数对（d_i，d_j）与（d_j，d_i）中必有一个为逆序对（其中1≤i且排列D中数对（d_i，d_j）共有

C

2 n

=(n(n-1))/(2)个，
所以S(D)+S(D1)=(n(n-1))/(2)．
所以排列D与D₁的逆序对的个数的算术平均值为(n(n-1))/(4)．
而对于数字1，2，…，n的任意一个排列A：a₁，a₂，…，a_n，
都可以构造排列A₁：a_n，a_n-1，…，a₂，a₁，
且这两个排列的逆序对的个数的算术平均值为(n(n-1))/(4)．
所以所有S（A）的算术平均值为(n(n-1))/(4)．
（Ⅲ）证明：（1）当j=i+1，即a_i，a_j相邻时，
不妨设a_i<a_i+1，则排列A'为a₁，a₂，…，a_i-1，a_i+1，a_i，a_i+2，…，a_n，
此时排列A'与排列A：a₁，a₂，…，a_n相比，仅多了一个逆序对（a_i+1，a_i），
所以S（A'）=S（A）+1，
所以S（A）+S（A'）=2S（A）+1为奇数．
（2）当j≠i+1，即a_i，a_j不相邻时，
假设a_i，a_j之间有m个数字，记排列A：a₁，a₂，…，a_i，k₁，k₂，…k_m，a_j，…，a_n，
先将a_i向右移动一个位置，得到排列A₁：a₁，a₂，…，a_i-1，k₁，a_i，k₂，…，k_m，a_j，…，a_n，
由（1）知S（A₁）与S（A）的奇偶性不同，
再将a_i向右移动一个位置，得到排列A₂：a₁，a₂，…，a_i-1，k₁，k₂，a_i，k₃，…，k_m，a_j，…，a_n，
由（1）知S（A₂）与S（A₁）的奇偶性不同，
以此类推，a_i共向右移动m次，得到排列A_m：a₁，a₂，…，k₁，k₂，…，k_m，a_i，a_j，…，a_n，
再将a_j向左移动一个位置，得到排列A_m+1：a₁，a₂，…，a_i-1，k₁，…，k_m，a_j，a_i，…，a_n，
以此类推，a_j共向左移动m+1次，得到排列A_2m+1：a₁，a₂，…，a_j，k₁，…，k_m，a_i，…，a_n，
即为排列A'，
由（1）可知仅有相邻两数的位置发生变化时，排列的逆序对个数的奇偶性发生变化，
而排列A经过2m+1次的前后两数交换位置，可以得到排列A'，
所以排列A与排列A'的逆序数的奇偶性不同，
所以S（A）+S（A'）为奇数．
综上，得S（A）+S（A'）为奇数．