I need some help for the following homework question.
A permutation $P (\pi_1\pi_2...\pi_n)$ of {$1,2,...,n$} is given. We say that $j$ is a maxima of $P$ whenever $\pi_j$>$j$. How can I find recurrence relation to count the number of $n$-permutations of {$1,2,...,n$} that have exactly $k$ maxima?
Please provide some hints to solve the problem.
A hint was given that this count is related to Stirling Number of First kind.