Question

已知集合S_n={（x₁，x₂，…，x_n）|x₁，x₂，…，x_n是正整数1，2，3，…，n的一个排列}（n≥2），函数
对于（a₁，a₂，…a_n）∈S_n，定义：b_i=g（a_i-a₁）+g（a_i-a₂）+…+g（a_i-a_i-1），i∈{2，3，…，n}，b₁=0，称b_i为a_i的满意指数．排列b₁，b₂，…，b_n为排列a₁，a₂，…，a_n的生成列；排列a₁，a₂，…，a_n为排列b₁，b₂，…，b_n的母列．
（Ⅰ）当n=6时，写出排列3，5，1，4，6，2的生成列及排列0，-1，2，-3，4，3的母列；
（Ⅱ）证明：若a₁，a₂，…，a_n和a′₁，a′₂，…，a′_n为S_n中两个不同排列，则它们的生成列也不同；
（Ⅲ）对于S_n中的排列a₁，a₂，…，a_n，定义变换τ：将排列a₁，a₂，…，a_n从左至右第一个满意指数为负数的项调至首项，其它各项顺序不变，得到一个新的排列．证明：一定可以经过有限次变换τ将排列a₁，a₂，…，a_n变换为各项满意指数均为非负数的排列．

Answer

（Ⅰ）由bi=g（ai-a1）+g（ai-a2）+…+g（ai-ai-1），g（x）=及“生成列”与“母列”的定义可求得当n=6时排列3，5，1，4，6，2的生成列及排列0，-1，2，-3，4，3的母列；
（Ⅱ）设a1，a2，…，an的生成列是b1，b2，…，bn；a′1，a′2，…，a′n的生成列是与b′1，b′2，…，b′n，从右往左数，设排列a1，a2，…，an与a′1，a′2，…，a′n第一个不同的项为ak与a′k，由满意指数的定义可知ai的满意指数，从而可证得且ak≠a′k，于是可得排列a1，a2，…，an和a′1，a′2，…，a′n的生成列也不同．
（Ⅲ）设排列a1，a2，…，an的生成列为b1，b2，…，bn，且ak为a1，a2，…，an中从左至右第一个满意指数为负数的项，⇒b1≥0，b2≥0，…，bk-1≥0，bk≤-1，经过一次变换τ后，整个排列的各项满意指数之和将至少增加2，利用ai的满意指数bi≤i-1，可知整个排列的各项满意指数之和不超过1+2+3+…+（n-1）=，从而可使结论得证．
（Ⅰ）【解析】
当n=6时，排列3，5，1，4，6，2的生成列为0，1，-2，1，4，-3；
排列0，-1，2，-3，4，3的母列为3，2，4，1，6，5．
（Ⅱ）证明：设a1，a2，…，an的生成列是b1，b2，…，bn；a′1，a′2，…，a′n的生成列是与b′1，b′2，…，b′n，
从右往左数，设排列a1，a2，…，an与a′1，a′2，…，a′n第一个不同的项为ak与a′k，即：an=a′n，an-1=a′n-1，…，ak+1=a′k+1，ak≠a′k．
显然 bn=b′n，bn-1=b′n-1，…，bk+1=b′k+1，下面证明：bk≠b′k．
由满意指数的定义知，ai的满意指数为排列a1，a2，…，an中前i-1项中比ai小的项的个数减去比ai大的项的个数．
由于排列a1，a2，…，an的前k项各不相同，设这k项中有l项比ak小，则有k-l-1项比ak大，从而bk=l-（k-l-1）=2l-k+1．
同理，设排列a′1，a′2，…，a′n中有l′项比a′k小，则有k-l′-1项比a′k大，从而b′k=2l′-k+1．
因为 a1，a2，…，ak与a′1，a′2，…，a′k是k个不同数的两个不同排列，且ak≠a′k，
所以 l≠l′，从而 bk≠b′k．
所以排列a1，a2，…，an和a′1，a′2，…，a′n的生成列也不同．
（Ⅲ）证明：设排列a1，a2，…，an的生成列为b1，b2，…，bn，且ak为a1，a2，…，an中从左至右第一个满意指数为负数的项，所以 b1≥0，b2≥0，…，bk-1≥0，bk≤-1．
进行一次变换τ后，排列a1，a2，…，an变换为ak，a1，a2，…ak-1，ak+1，…，an，设该排列的生成列为b′1，b′2，…，b′n．
所以 （b′1，b′2，…，b′n）-（b1+b2+…+bn）=[g（a1-ak）+g（a2-ak）+…+g（ak-1-ak）]-[g（ak-a1）+g（ak-a2）+…+g（ak-ak-1）]=-2[g（ak-a1）+g（ak-a2）+…+g（ak-ak-1）]=-2bk≥2．
因此，经过一次变换τ后，整个排列的各项满意指数之和将至少增加2．
因为ai的满意指数bi≤i-1，其中i=1，2，3，…，n，
所以，整个排列的各项满意指数之和不超过1+2+3+…+（n-1）=，
即整个排列的各项满意指数之和为有限数，
所以经过有限次变换τ后，一定会使各项的满意指数均为非负数．