将1到n的n个正整数按下面的方法排成一个排列，要求：除左边的第一个数外，每个数都与它左边（未必相邻）的某个数相差1，将此种排列称为“n排列”．比如“2排列”为n=2时，有1，2；和2

Question

将1到n的n个正整数按下面的方法排成一个排列，要求：除左边的第一个数外，每个数都与它左边（未必相邻）的某个数相差1，将此种排列称为“n排列”．比如“2排列”为n=2时，有1，2；和2，1；共2种排列．“3排列”为当n=3时，有1，2，3；2，1，3；2，3，1；3，2，1；共4种排列．
（1）请写出“4排列”的排列数；
（2）问所有“n排列”的结尾数只能是什么数？请加以证明；
（3）证明：“n排列”共有2^n-1个．

Answer 1

（1）n=4时，有1，2，3，4；   2，1，3，4；   2，3，1，4；   2，3，4，1；  
3，2，1，4；   3，2，4，1；   3，4，2，1；   4，3，2，1共8个排列；
（2）由题意猜想所有的n排列均以1或n结尾，
证明：由（1）已证当n=2，3，4时满足猜想，
假设当n=k时，所有k排列a₁，a₂，…a_n满足题意，
则当n=k+1时：
①若k排列a₁，a₂，…a_n最后一个数是1，则k+1排列总符合题意，
②若k排列a₁，a₂，…a_n最后1个数为k，则考虑k+1这个数，
只能排在最后一位，否则在它前面没有一个数与k+1相差1，
故n排列的结尾不是1就是n．
（3）①对n=2，3，4结论均以成立，
②假设当n=k时，k排列共2^k-1，
则n=k+1时，
若k排列结尾是k，则k+1只能排在最后一位，共2^k-1个，
若k排列尾数是1，则作这样一个对应：
a₁，a₂，…a_k，k+1→k+2-a₁，k+2-a₂，••k+2-a_k，1，
这样恰好得到一个结尾为1的一个k+1排列，所以也有2^k-1，
所以共有2^k-1+2^k-1=2^k个，
即n排列共有2^n-1个．