Question

已知集合是正整數(shù)的一個排列，函數(shù)

 

對于，定義：，，稱為的滿意指數(shù)．排列為排列的生成列．

（Ⅰ）當時，寫出排列的生成列；

（Ⅱ）證明：若和為中兩個不同排列，則它們的生成列也不同；

（Ⅲ）對于中的排列，進行如下操作：將排列從左至右第一個滿意指數(shù)為負數(shù)的項調至首項，其它各項順序不變，得到一個新的排列．證明：新的排列的各項滿意指數(shù)之和比原排列的各項滿意指數(shù)之和至少增加．

Answer 1

（Ⅰ）解：當時，排列的生成列為．         

（Ⅱ）證明：設的生成列是；的生成列是與．

從右往左數(shù)，設排列與第一個不同的項為與，即：，，，，．

顯然 ，，，，下面證明：．    

由滿意指數(shù)的定義知，的滿意指數(shù)為排列中前項中比小的項的個數(shù)減去比大的項的個數(shù)．

由于排列的前項各不相同，設這項中有項比小，則有項比大，從而．

同理，設排列中有項比小，則有項比大，從而．

因為 與是個不同數(shù)的兩個不同排列，且，

所以 ， 從而 ．

所以排列和的生成列也不同．              

（Ⅲ）證明：設排列的生成列為，且為中從左至右第一個滿意指數(shù)為負數(shù)的項，所以 ．            

依題意進行操作，排列變?yōu)榕帕?img src='http://thumb.1010pic.com/pic1/files/down/test/2014/04/03/05/2014040305354992681555.files/image298.gif'>，設該排列的生成列為．                                                   

所以

     

．

所以，新排列的各項滿意指數(shù)之和比原排列的各項滿意指數(shù)之和至少增加．