2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shailesh Jul 26 '15 at 14:13
  • $\begingroup$ @Shailesh: This is not true, for example: [2, 1, 3, 4], [4, 1, 2, 3] and [3, 1, 2, 4] all translate to $+$ $-$ $+$ $+$. $\endgroup$ – pts Jul 26 '15 at 14:17
  • $\begingroup$ Yes you are right. Did not think of that. Sorry. $\endgroup$ – Shailesh Jul 26 '15 at 14:19
  • $\begingroup$ I don't understand. 2 is on the left. How come s(he) can't see 1 ? Also is the tallest 1 or 4 ? $\endgroup$ – true blue anil Jul 26 '15 at 14:35
  • $\begingroup$ @trueblueanil: 4 is the tallest. The observer can't see 1, because 2 is blocking the view ($2 > 1$). $\endgroup$ – pts Jul 26 '15 at 14:55
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.