Question

8．已知1，2，…，n滿足下列性質(zhì)T的排列a₁，a₂，…，a_n的個(gè)數(shù)為f（n）（n≥2）排列a₁，a₂，…，a_n中有且只有一個(gè)a_i＞a_i+1（i∈{1，2，…，n-1}）
（1）求f（3）=4；f（4）=11；f（5）=26
（2）求f（n）的表達(dá)式，并證明你的結(jié)論．

Answer 1

分析 （1）當(dāng)n=3時(shí)，寫出所有的排列，再找到滿足a_i＞a_i+1的排列有，（1，3，2），（2，1，3），（2，3，1），（3，1，2），即f（3）=4，
同理求出f（4），f（5）
（2）由（1）猜想出結(jié)論f（n）=2ⁿ-n-1，再根據(jù)排列組合即可證明．

解答 解：（1）當(dāng)n=3時(shí)，1，2，3的所有排列有（1，2，3），（1，3，2），（2，1，3），（2，3，1），（3，1，2），（3，2，1），其中滿足僅存在一個(gè)i∈{1，2，3}，使得a_i＞a_i+1的排列有，（1，3，2），（2，1，3），（2，3，1），（3，1，2）
所以f（3）=4，
同理可求f（4）=11，f（5）=26，
（2）由（1）猜想出結(jié)論f（n）=2ⁿ-n-1，
證明如下：在1，2，…，n的所有排列（a₁，a₂，…a_n）中，
若a_i=n（1≤i≤n-1），從n-1個(gè)數(shù)1，2，3，…，n-1中選i-1 個(gè)數(shù)按從小到大的順序排列為a₁，a₂，…a_i-1，其余按從小到大的順序排列在余下位置，
于是滿足題意的排列個(gè)數(shù)為C_n-1^i-1．
若a_i=n，則滿足題意的排列個(gè)數(shù)為f（n-1），
綜上，f（n）=f（n-1）+$\sum_{i=1}^{n-1}{C}_{n-1}^{i-1}$=f（n-1）+2ⁿ⁺¹-1，
從而f（n）=$\frac{{2}^{3}（1-{2}^{n-3}）}{1-2}$-（n-3）+f（3）=2ⁿ-n-1，
故答案為：4，11，26．

點(diǎn)評(píng) 本題考查了歸納推理和排列組合的問題，關(guān)鍵是轉(zhuǎn)化，培養(yǎng)了學(xué)生的分析解決問題的能力，屬于難題．