Question

9．將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）根據題意按順序排列即可；
（2）由題意猜想所有的n排列均以1或n結尾，根據歸納法證明即可；
（3）根據歸納法證明即可．

解答 解：（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個．

點評 本題考查了新定義問題，考查數學歸納法的應用，是一道中檔題．