热门试卷

（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。

（2）证明：设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的生成列也不同。

（3）证明：设排列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）=，

即整个排列的各项满意指数之和为有限数，

所以经过有限次变换τ后，一定会使各项的满意指数均为非负数。