Question

9．將1到n的n個正整數(shù)按下面的方法排成一個排列，要求：除左邊的第一個數(shù)外，每個數(shù)都與它左邊（未必相鄰）的某個數(shù)相差1，將此種排列稱為“n排列”．比如“2排列”為n=2時，有1，2；和2，1；共2種排列．“3排列”為當(dāng)n=3時，有1，2，3；2，1，3；2，3，1；3，2，1；共4種排列．
（1）請寫出“4排列”的排列數(shù)；
（2）問所有“n排列”的結(jié)尾數(shù)只能是什么數(shù)？請加以證明；
（3）證明：“n排列”共有2^n-1個．

Answer 1

分析 （1）根據(jù)題意按順序排列即可；
（2）由題意猜想所有的n排列均以1或n結(jié)尾，根據(jù)歸納法證明即可；
（3）根據(jù)歸納法證明即可．

解答 解：（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結(jié)尾，
證明：由（1）已證當(dāng)n=2，3，4時滿足猜想，
假設(shè)當(dāng)n=k時，所有k排列a₁，a₂，…a_n滿足題意，
則當(dāng)n=k+1時：
①若k排列a₁，a₂，…a_n最后一個數(shù)是1，則k+1排列總符合題意，
②若k排列a₁，a₂，…a_n最后1個數(shù)為k，則考慮k+1這個數(shù)，
只能排在最后一位，否則在它前面沒有一個數(shù)與k+1相差1，
故n排列的結(jié)尾不是1就是n．
（3）①對n=2，3，4結(jié)論均以成立，
②假設(shè)當(dāng)n=k時，k排列共2^k-1，
則n=k+1時，
若k排列結(jié)尾是k，則k+1只能排在最后一位，共2^k-1個，
若k排列尾數(shù)是1，則作這樣一個對應(yīng)：
a₁，a₂，…a_k，k+1→k+2-a₁，k+2-a₂，••k+2-a_k，1，
這樣恰好得到一個結(jié)尾為1的一個k+1排列，所以也有2^k-1，
所以共有2^k-1+2^k-1=2^k個，
即n排列共有2^n-1個．

點評 本題考查了新定義問題，考查數(shù)學(xué)歸納法的應(yīng)用，是一道中檔題．