Question

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

Answer 1

分析 （1）當n=3時，寫出所有的排列，再找到滿足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）猜想出結論f（n）=2ⁿ-n-1，再根據排列組合即可證明．

解答 解：（1）當n=3時，1，2，3的所有排列有（1，2，3），（1，3，2），（2，1，3），（2，3，1），（3，1，2），（3，2，1），其中滿足僅存在一個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）猜想出結論f（n）=2ⁿ-n-1，
證明如下：在1，2，…，n的所有排列（a₁，a₂，…a_n）中，
若a_i=n（1≤i≤n-1），從n-1個數1，2，3，…，n-1中選i-1 個數按從小到大的順序排列為a₁，a₂，…a_i-1，其余按從小到大的順序排列在余下位置，
于是滿足題意的排列個數為C_n-1^i-1．
若a_i=n，則滿足題意的排列個數為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．

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