Question

已知集合是正整数的一个排列，函数

 

对于，定义：，，称为的满意指数．排列为排列的生成列．

（Ⅰ）当时，写出排列的生成列；

（Ⅱ）证明：若和为中两个不同排列，则它们的生成列也不同；

（Ⅲ）对于中的排列，进行如下操作：将排列从左至右第一个满意指数为负数的项调至首项，其它各项顺序不变，得到一个新的排列．证明：新的排列的各项满意指数之和比原排列的各项满意指数之和至少增加．

Answer 1

（Ⅰ）解：当时，排列的生成列为．         

（Ⅱ）证明：设的生成列是；的生成列是与．

从右往左数，设排列与第一个不同的项为与，即：，，，，．

显然 ，，，，下面证明：．    

由满意指数的定义知，的满意指数为排列中前项中比小的项的个数减去比大的项的个数．

由于排列的前项各不相同，设这项中有项比小，则有项比大，从而．

同理，设排列中有项比小，则有项比大，从而．

因为 与是个不同数的两个不同排列，且，

所以 ， 从而 ．

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

（Ⅲ）证明：设排列的生成列为，且为中从左至右第一个满意指数为负数的项，所以 ．            

依题意进行操作，排列变为排列，设该排列的生成列为．                                                   

所以

     

．

所以，新排列的各项满意指数之和比原排列的各项满意指数之和至少增加．