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.

• You can denote the arrangements with a $+$ and a $-$ depending on the adjacent number. In the example shown, it is $+-++$. Now the problem reduces to finding how many arrangements have exactly $k$ $+$'s. – Shailesh Jul 26 '15 at 14:13
• @Shailesh: This is not true, for example: [2, 1, 3, 4], [4, 1, 2, 3] and [3, 1, 2, 4] all translate to $+$ $-$ $+$ $+$. – pts Jul 26 '15 at 14:17
• Yes you are right. Did not think of that. Sorry. – Shailesh Jul 26 '15 at 14:19
• I don't understand. 2 is on the left. How come s(he) can't see 1 ? Also is the tallest 1 or 4 ? – true blue anil Jul 26 '15 at 14:35
• @trueblueanil: 4 is the tallest. The observer can't see 1, because 2 is blocking the view ($2 > 1$). – pts Jul 26 '15 at 14:55

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 $<m$ one by one also on the right side of the person with length $m$. There are $\frac{\left(n-1\right)!}{\left(n-m\right)!}$ arrangements for them.

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.