3
$\begingroup$

The task is to arrange $n$ people in a single line such that exactly $x$ of them are visible from left and $y$ of them visible from right (Since some taller people block the view of the shorter ones).

For example, if the people were arranged in line with heights 30 cm, 10 cm, 50 cm, 40 cm, and then 20 cm, someone looking from the left side would see 2 persons (30 and 50 cm) while someone looking from the right side would see 3 persons (20, 40 and 50 cm).

The answer lies to place the tallest person in such a way that the problem is divided into 2 halves, but I'am not sure how.

Edit : It is to note that all the heights are distinct

$\endgroup$
  • $\begingroup$ Are the heights distinct? At the very least, is there only one tallest person? $\endgroup$ – Joey Zou Sep 2 '16 at 6:02
  • $\begingroup$ @JoeyZou Yes all the heights are distinct $\endgroup$ – Pournima Bedarkar Sep 2 '16 at 6:03
  • $\begingroup$ Place the shortest $x-1$ from the left in increasing order of height, place the tallest person next. Now, place the shortest $y-2$ people from the right again in the increasing order of height. Place the second tallest person next before these $y-2$ people. Place everyone else in between the top two tallest placed. When we look from the left, the smallest $x-1$ people along with the tallest are visible. When we look from the right, the $y-2$ people, the second tallest and the tallest are visible. For example, in 10, 20,30, 40, 50, place 10, 50, 30, 20, 40 to see only two from either side. $\endgroup$ – user348749 Sep 2 '16 at 6:34
1
$\begingroup$

This is building on @Fimpellizieri's answer. As @Fimpellizieri showed, we can reduce this to the problem of calculating $l(n,k)$, the number of ways of ordering $n$ people so that exactly $k$ are visible from the left. (Note that $r(n,k) = l(n,k)$, since you can reverse to order to switch left-visibility into right-visibility.)

We claim that $l(n,k) = \left[ \begin{array}{c} n \\ k \end{array} \right]$, the Stirling number of the first kind. $\left[ \begin{array}{c} n \\ k \end{array} \right]$ denotes the number of permutations of $n$ that, when written in cycle notation, have exactly $k$ cycles.

Now suppose we have a permutation of the $n$ people with exactly $k$ visible from the right. Note that the $k$ visible people must be ordered in increasing order of height, with the last visible person being the tallest. Also, this divides the $n$ people into $k$ ordered sets: the sets of people behind the $i$th visible person, for $1 \le i \le k$.

Hence we can biject these permutations to permutations with $k$ cycles - simply take these ordered sets to be the cycles of a permutation. For the reverse map, given a $k$-cycle permutation, take the $k$ cycles (in their cyclic order) to be the $k$ sets, rotate the cycles so that the tallest person in the cycle is first (since this person should be visible, and none of the others in the set), and then order the cycles in increasing order of the height of their tallest people (so that each of these people is visible).

Hence we get $l(n,k) = \left[ \begin{array}{c} n \\ k \end{array} \right]$. Unfortunately there is not a nice closed formula for this Stirling number, but there are recursive formulae that can be used to compute them quickly.


EDIT: An alternative approach.

While one can substitute the Stirling numbers into the summation formula given in @Fimpellizieri's answer, the bijective argument above can be extended to give a closed (up to the Stirling numbers) formula.

Indeed, suppose we have an ordering with $x$ people visible from the left and $y$ people visible from the right. The tallest person is the last person visible from either side, and to the left there are $x-1$ people visible from the left, and to the right there are $y-1$ people visible from the right.

Hence after removing the tallest person, we can divide the $n-1$ remaining people into $(x-1) + (y-1)$ ordered sets: for each $1 \le i \le x-1$, the people behind the $i$th visible person from the left, and for each $1 \le j \le y-1$, the people in front of the $j$th visible person from the right. As before, thinking of these ordered sets as cyclic permutations gives us a permutation of $n-1$ people with $x + y - 2$ cycles, with $x-1$ "left" cycles and $y-1$ "right" cycles.

Conversely, suppose we have a permutation of $n-1$ people (the tallest person has still been removed) with $x + y - 2$ cycles. From these cycles, choose $x-1$ cycles for the left, with the remaining cycles to be on the right. There are $\binom{x+y-2}{x-1}$ ways to do this.

Arrange the left-cycles in increasing order of the height of their tallest member, and rotate them so that the tallest person is first in each cycle. Place these cycles at the beginning of the line.

Arrange the right-cycles in decreasing order of the height of their tallest member, and rotate them so that the tallest person is last in each cycle. Place these cycles at the end of the line.

Finally, put the (overall) tallest person in the middle, between the left-cycles and the right-cycles.

Hence the number of ways to arrange $n$ people in a line with exactly $x$ visible from the left and exactly $y$ visible from the right should be $$\left[ \begin{array}{c} n-1 \\ x+y-2 \end{array} \right] \binom{x+y-2}{x-1}.$$


Rough notes:

A small sanity check: if $x = 2$ and $y = 1$, we must have the second-tallest person first and the tallest person last, with the $n-2$ people in the middle arranged arbitrarily. Hence there are $(n-2)!$ possible orders. Since $\left[ \begin{array}{c} r \\ 1 \end{array} \right] = (r-1)!$, our formula indeed gives $(n-2)!$.

Also, for an example for the map between line-ups and permutations with cycles, suppose $n = 8$, $x = 3$ and $y = 2$. Consider the permutation (in cyclic notation) of $[7]$ given by $\pi = (5 6) (2 7) (1 3 4)$. We choose two cycles for the left, say $(2 7)$ and $(1 3 4)$, leaving $(5 6)$ for the right.

Now the left-cycles we rotate so that the tallest person is first, giving $(7 2)$ and $(4 1 3)$ [rotating cycles doesn't change the underlying permutation $\pi$], and then order in increasing order of height: $ 4, 1, 3, 7, 2$.

We then put the tallest person ($8$ - I am naming them after their rank), followed by the right-permutations, which are rotated so that the tallest person is last, giving $4, 1, 3, 7, 2, 8, 5, 6$ as the ordering of the people given by this choice of permutation and division of left-/right-cycles. Note that here we have $4, 7$ and $8$ visible from the left, and $6, 8$ visible from the right, matching the desired $x = 3$ and $y=2$.

$\endgroup$
  • $\begingroup$ I find your alternative approach to be the best one. @Fimpellizieri 's equation needs handling some base cases and till yet I am not successful in implementing one, but could implement your version in no time $\endgroup$ – Pournima Bedarkar Sep 3 '16 at 6:22
2
$\begingroup$

Let $f(n,x,y)$ be the number of ways to arrange $n$ people in a line such that exactly $x$ of them are visible from the left and $y$ of them are visible from the right, where no two persons have the same height.

Let $T$ be the tallest of the $n$ people; there are $n$ possible positions for $T$ on the line. Say the line has positions $0,1,\dots,n-1$, from left to right. If $T$ is placed on position $i$, there will be $i$ positions to its left and $(n-1)-i$ positions to its right. We should thus choose $i$ out of the remaining $n-1$ people, in $\binom{n-1}{i}$ ways, to be the left group, and the others to be the right group.

At this point, we've split the problem into two smaller subproblems. We need to:

  • Arrange $i$ people in a line (to the left of $T$) such that exactly $x-1$ of them are visible from the left; and
  • Arrange $(n-1)-i$ people in a line (to the right of $T$) such that exactly $y-1$ of them are visible from the right.

Notice that for the former, it doesn't matter how many people are visible from the right; while for the latter it doesn't matter how many people are visible from the left. We can write this into a recursive formula:

\begin{aligned} f(n,x,y)&=\sum_{i=0}^{n-1}\left[\binom{n-1}{i}\cdot \left(\sum_{j=1}^{\infty}f(i,x-1,j)\right)\cdot\left(\sum_{k=1}^{\infty}f(n-1-i,k,y-1)\right)\right]\\ &=\sum_{i=0}^{n-1}\left[\binom{n-1}{i}\cdot \left(\sum_{j=1}^{i+2-x}f(i,x-1,j)\right)\cdot\left(\sum_{k=1}^{n+1-y-i}f(n-1-i,k,y-1)\right)\right] \end{aligned}

where the second line is merely observing the condition that $x+y\leq n+1$, that is, at most the one person, the tallest, can be seen from both sides. By the same token, $x$ and $y$ are each initially $\geq 1$ (and in fact $x+y \geq 3$).

With some seed values for small values of $n$, we should be able to calculate this recursion without any problem (which is not to say this is an efficient way of doing so).


Perhaps a simpler approach is to first calculate:

  • $l(n,x)$, the number of ways to arrange $n$ people in a line such that exactly $x$ of the are visible from the left; and
  • $r(n,y)$, the number of ways to arrange $n$ people in a line such that exactly $y$ of the are visible from the right.

If we calculte these, the formula for $f(n,x,y)$ in terms of $l,r$ becomes simpler:

$$f(n,x,y)=\sum_{i=0}^{n-1}\left[\binom{n-1}{i}\cdot l(i,x-1)\cdot r(n-1-i,y-1)\right]$$

$\endgroup$
  • $\begingroup$ Thanks for the elegant solution, the second one seems much more intuitive. Can you please elaborate on calculating $l(x, y)$ or $r(x,y)$ , I have come up with a way which I am not very confident about $\endgroup$ – Pournima Bedarkar Sep 2 '16 at 6:57
  • $\begingroup$ The quantities $l(n,x)$ and $r(n,y)$ are given by Stirling numbers of the first kind, as I've outlined below. @Fimpellizieri: if you'd like to incorporate this into your answer to make it self-contained, please feel free to do so. $\endgroup$ – Shagnik Sep 2 '16 at 6:57

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.