How many height arrangements are there for people? 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 `1`. 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.

Let the persons have lengths $1,2,\dots,n$

Let $a_{n,k}$ denote number of arrangements that you mention in your question.

Then $a_{n,k}=\sum_{m=1}^{n-k+1}a_{n,k,m}$ where $a_{n,k,m}$ denotes the number of these arrangements with the person with length $m$ is _on the left_.

So first we place this person.

Then we place the $n-m$ persons with a length $>m$ on a row on the right side of the person with length $m$. There are $a_{n-m,k-1}$ arrangements for them.

Then we place the $m-1$ with length $
This tells us that $a_{n,k,m}=a_{n-m,k-1}\frac{\left(n-1\right)!}{\left(n-m\right)!}$ hence: $$a_{n,k}=\sum_{m=1}^{n-k+1}a_{n-m,k-1}\frac{\left(n-1\right)!}{\left(n-m\right)!}$$

So we have a recursion formula.