这是今年举行的CMI（钦奈数学研究所）本科入学考试的B4题：

在一个班级中有$n$个身高各不相同的学生：

(i) 求满足最矮的学生不在队首，最高的学生不在队尾的学生排列数。

(ii) 对于$1≤i≤n$，令$b_i$表示第$i$个学生前面比他高的学生数量。例如，考虑序列[4,1,2,6,7,5]（4在队首，5在队尾），此时：
$$b_1=0,b_2=1,b_3=1,b_4=0,b_5=0,b_6=2$$
定义一个排列的badness为$\max_{i∈[n]}b_i$，上述例子的badness为2。令$f_k(n)$表示$[n]$的排列中badness等于$k$的排列数，求$f_k(n)$。

我第一问肯定是能解出来的，但第二问实在找不到把情况归类的方法来推导公式。如果有人能给个提示或者说清楚怎么分类计数来解决这个问题，那就太有用了！谢谢！

备注：内容来源于stack exchange，提问作者Learningstill