已知1，2，…，n满足下列性质T的排列a1，a2，…，an的个数为f（n）（n≥2）排列a1，a2，…，an中有且只有一个ai>ai+1（i∈{1，2，…，n-1}）（1）求f（3）=；f（4）=；f（5）=（2）求f（n

Question

已知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）=___；f（4）=___；f（5）=___
（2）求f（n）的表达式，并证明你的结论．

Answer 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）+

n-1

i=1

C

i-1 n-1

=f（n-1）+2ⁿ⁺¹-1，
从而f（n）=(23(1-2n-3))/(1-2)-（n-3）+f（3）=2ⁿ-n-1，
故答案为：4，11，26．