There are $n$ students in a class and no two of them have the same height. The students stand in a line, one behind another, in no particular order of their heights. (a) How many different orders are there in which the shortest student is not in the first position and the tallest student is not in the last position? (b) The badness of an ordering is the largest number $k$ with the following property. There is at least one student $X$ such that there are $k$ students taller than $X$ standing ahead of $X$. Find a formula for $g _ { k } ( n ) =$ number of orderings of $n$ students with badness $k$. Example: The ordering $64\,61\,67\,63\,62\,66\,65$ (the numbers denote heights) has badness 3 as the student with height 62 has three taller students (with heights 64, 67 and 63) standing ahead in the line and nobody has more than 3 taller students standing ahead. Possible hints for (b): It may be useful to first count orderings of badness 1 and/or to find $f _ { k } ( n ) =$ the number of orderings of $n$ students with badness less than or equal to $k$.
There are $n$ students in a class and no two of them have the same height. The students stand in a line, one behind another, in no particular order of their heights.\\
(a) How many different orders are there in which the shortest student is not in the first position and the tallest student is not in the last position?\\
(b) The badness of an ordering is the largest number $k$ with the following property. There is at least one student $X$ such that there are $k$ students taller than $X$ standing ahead of $X$. Find a formula for $g _ { k } ( n ) =$ number of orderings of $n$ students with badness $k$.
Example: The ordering $64\,61\,67\,63\,62\,66\,65$ (the numbers denote heights) has badness 3 as the student with height 62 has three taller students (with heights 64, 67 and 63) standing ahead in the line and nobody has more than 3 taller students standing ahead.
Possible hints for (b): It may be useful to first count orderings of badness 1 and/or to find $f _ { k } ( n ) =$ the number of orderings of $n$ students with badness less than or equal to $k$.