Question

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'）為奇數．

Answer 1

分析 （Ⅰ）由逆序對的定義，列舉即可得到所求值為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）可知僅有相鄰兩數的位置發(fā)生變化時，排列的逆序對個數的奇偶性發(fā)生變化，
而排列A經過2m+1次的前后兩數交換位置，可以得到排列A'，
所以排列A與排列A'的逆序數的奇偶性不同，
所以S（A）+S（A'）為奇數．
綜上，得S（A）+S（A'）為奇數．

點評 本題考查新定義的理解和運用，考查列舉法和排列組合的運用，運用分類討論的思想方法是解題的關鍵．