Let $f(n,k)=$ the number of permutations of the first $n$ positive integers with exactly $k$
numbers that are less than all previous numbers. The first number in any permutation is considered to be less than all previous numbers (in the sense that it sets a new low).
Is there an easy way to calculate $f(n,k)$ in general?
For example, we can show that $f(4,3)=6$ by listing the permutations. (In each permutation, the numbers that are less than all previous numbers are in red.)
$\color{red}3,\color{red}2,\color{red}1,4$
$\color{red}3,\color{red}2,4,\color{red}1$
$\color{red}3,4,\color{red}2,\color{red}1$
$\color{red}4,\color{red}2,\color{red}1,3$
$\color{red}4,\color{red}2,3,\color{red}1$
$\color{red}4,\color{red}3,\color{red}1,2$
I'm looking for a smart way to calculate $f(n,k)$, maybe like stars and bars.
Context: This is related to "Approach 1" in my question about world records. But I find the question here interesting by itself.
Best Answer
The statistic you are counting is called left-to-right minima.
We have the following linear recurrence $$f(n,k)=f(n-1,k-1)+(n-1)f(n-1,k).$$
Familiar as the recurrence for the unsigned Stirling number of the first kind.