Question

15．在數(shù)字1，2，…，n（n≥2）的任意一個(gè)排列A：a₁，a₂，…，a_n中，如果對(duì)于i，j∈N^*，i＜j，有a_i＞a_j，那么就稱（a_i，a_j）為一個(gè)逆序?qū)Γ�記排列A中逆序?qū)Φ膫�(gè)數(shù)為S（A）．
如n=4時(shí)，在排列B：3，2，4，1中，逆序?qū)τ校?，2），（3，1），（2，1），（4，1），則S（B）=4．
（Ⅰ）設(shè)排列 C：3，5，6，4，1，2，寫(xiě)出S（C）的值；
（Ⅱ）對(duì)于數(shù)字1，2，…，n的一切排列A，求所有S（A）的算術(shù)平均值；
（Ⅲ）如果把排列A：a₁，a₂，…，a_n中兩個(gè)數(shù)字a_i，a_j（i＜j）交換位置，而其余數(shù)字的位置保持不變，那么就得到一個(gè)新的排列A'：b₁，b₂，…，b_n，求證：S（A）+S（A'）為奇數(shù)．

Answer 1

分析 （Ⅰ）由逆序?qū)Φ亩�義，列舉即可得到所求值為10；
（Ⅱ）考察排列D：d₁，d₂，…，d_n-1，d_n，運(yùn)用組合數(shù)可得排列D中數(shù)對(duì)（d_i，d_j）共有$C_n^2=\frac{n（n-1）}{2}$個(gè)，即可得到所有S（A）的算術(shù)平均值；
（Ⅲ）討論（1）當(dāng)j=i+1，即a_i，a_j相鄰時(shí)，（2）當(dāng)j≠i+1，即a_i，a_j不相鄰時(shí)，由新定義，運(yùn)用調(diào)整法，可得S（A）+S（A'）為奇數(shù)．

解答 解：（Ⅰ）逆序?qū)τ校?，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₁，
因?yàn)閿?shù)對(duì)（d_i，d_j）與（d_j，d_i）中必有一個(gè)為逆序?qū)Γㄆ渲?≤i＜j≤n），
且排列D中數(shù)對(duì)（d_i，d_j）共有$C_n^2=\frac{n（n-1）}{2}$個(gè)，
所以$S（D）+S（{D_1}）=\frac{n（n-1）}{2}$．
所以排列D與D₁的逆序?qū)Φ膫�(gè)數(shù)的算術(shù)平均值為$\frac{n（n-1）}{4}$．
而對(duì)于數(shù)字1，2，…，n的任意一個(gè)排列A：a₁，a₂，…，a_n，
都可以構(gòu)造排列A₁：a_n，a_n-1，…，a₂，a₁，
且這兩個(gè)排列的逆序?qū)Φ膫�(gè)數(shù)的算術(shù)平均值為$\frac{n（n-1）}{4}$．
所以所有S（A）的算術(shù)平均值為$\frac{n（n-1）}{4}$．
（Ⅲ）證明：（1）當(dāng)j=i+1，即a_i，a_j相鄰時(shí)，
不妨設(shè)a_i＜a_i+1，則排列A'為a₁，a₂，…，a_i-1，a_i+1，a_i，a_i+2，…，a_n，
此時(shí)排列A'與排列A：a₁，a₂，…，a_n相比，僅多了一個(gè)逆序?qū)Γ╝_i+1，a_i），
所以S（A'）=S（A）+1，
所以S（A）+S（A'）=2S（A）+1為奇數(shù)．
（2）當(dāng)j≠i+1，即a_i，a_j不相鄰時(shí)，
假設(shè)a_i，a_j之間有m個(gè)數(shù)字，記排列A：a₁，a₂，…，a_i，k₁，k₂，…k_m，a_j，…，a_n，
先將a_i向右移動(dòng)一個(gè)位置，得到排列A₁：a₁，a₂，…，a_i-1，k₁，a_i，k₂，…，k_m，a_j，…，a_n，
由（1）知S（A₁）與S（A）的奇偶性不同，
再將a_i向右移動(dòng)一個(gè)位置，得到排列A₂：a₁，a₂，…，a_i-1，k₁，k₂，a_i，k₃，…，k_m，a_j，…，a_n，
由（1）知S（A₂）與S（A₁）的奇偶性不同，
以此類推，a_i共向右移動(dòng)m次，得到排列A_m：a₁，a₂，…，k₁，k₂，…，k_m，a_i，a_j，…，a_n，
再將a_j向左移動(dòng)一個(gè)位置，得到排列A_m+1：a₁，a₂，…，a_i-1，k₁，…，k_m，a_j，a_i，…，a_n，
以此類推，a_j共向左移動(dòng)m+1次，得到排列A_2m+1：a₁，a₂，…，a_j，k₁，…，k_m，a_i，…，a_n，
即為排列A'，
由（1）可知僅有相鄰兩數(shù)的位置發(fā)生變化時(shí)，排列的逆序?qū)�個(gè)數(shù)的奇偶性發(fā)生變化，
而排列A經(jīng)過(guò)2m+1次的前后兩數(shù)交換位置，可以得到排列A'，
所以排列A與排列A'的逆序數(shù)的奇偶性不同，
所以S（A）+S（A'）為奇數(shù)．
綜上，得S（A）+S（A'）為奇數(shù)．

點(diǎn)評(píng) 本題考查新定義的理解和運(yùn)用，考查列舉法和排列組合的運(yùn)用，運(yùn)用分類討論的思想方法是解題的關(guān)鍵．