第9题：

首先说明f(1)=0,f(2)=1,f(3)=2,f(4)=9.....自己手动推算，即可得。

分为2种情况：

1.前n-1个数已经都满足条件了：(n-1)*f(n-1)

2.前n-1个数中只有一个没有满足条件：(n-1)*f(n-2)，这个没有满足条件的数有n-1中可能的选择

所以f(n)=(n-1)*(f(n-1)+f(n-2)).

注意：为什么前n-1个数中不能有2个数不满足条件？因为这两个数最后都会个第三个数进行排序，就回到了第一种情况了。