Let's suppose $n$ people of different height stand in line, and the observer (who is smaller than the people in line) looks at them from the side. The observer sees a person unless there is a taller person between them. For example, in permutation
[2, 1, 3, 4], the observer (on the left) sees 3 people: everybody except for
How many arrangements (permutations) of $n$ people are there in which the observer sees $k$ people?
I need a formula (or algorithm) which is faster to compute than checking all $n!$ permutations for the number of people seen.