在数字1.2.-.n的任意一个排列A:a1.a2.-.an中.如果对于i.j∈N*.i＜j.有ai＞aj.那么就称(ai.aj)为一个逆序对．记排列A中逆序对的个数为S(A)．如n=4时.在排列B:3.2.4.1中.逆序对有.=4．(Ⅰ)设排列 C:3.5.6.4.1.2.写出S(C)的值,(Ⅱ)对于数字1.2.-.n的一切排列A.求所有S(A)的算术平均值,(Ⅲ)如果把排� 题目和参考答案——青夏教育精英家教网—

题目内容

15．在数字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'）为奇数．

分析（Ⅰ）由逆序对的定义，列举即可得到所求值为10；
（Ⅱ）考察排列D：d₁，d₂，…，d_n-1，d_n，运用组合数可得排列D中数对（d_i，d_j）共有$C_n^2=\frac{n（n-1）}{2}$个，即可得到所有S（A）的算术平均值；
（Ⅲ）讨论（1）当j=i+1，即a_i，a_j相邻时，（2）当j≠i+1，即a_i，a_j不相邻时，由新定义，运用调整法，可得S（A）+S（A'）为奇数．

解答解：（Ⅰ）逆序对有（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＜j≤n），
且排列D中数对（d_i，d_j）共有$C_n^2=\frac{n（n-1）}{2}$个，
所以$S（D）+S（{D_1}）=\frac{n（n-1）}{2}$．
所以排列D与D₁的逆序对的个数的算术平均值为$\frac{n（n-1）}{4}$．
而对于数字1，2，…，n的任意一个排列A：a₁，a₂，…，a_n，
都可以构造排列A₁：a_n，a_n-1，…，a₂，a₁，
且这两个排列的逆序对的个数的算术平均值为$\frac{n（n-1）}{4}$．
所以所有S（A）的算术平均值为$\frac{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'）为奇数．