Question

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

Answer 1

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

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

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