3
$\begingroup$

Given a list of $n$ distinct items, where a smaller item behind a larger item is obscured, if you can see $x$ items from one end, and $y$ from the other, how many ways can the items be arranged?

Firstly, I noticed that for $x+y-1\ge n$ there are $0$ ways. Then I tried to find how many elements can be on first, second, third place etc, but it seems that this is not easy way. On $(x+1)$-th must be greatest number of all numbers on first $x$ places, so on this place can be $n-x$ elements. It is similar for $y$. Is it true? Also, what is the easiest way to solve this problem?

$\endgroup$
2
$\begingroup$

We solve a simpler problem first. How many ways are there to arrange $n$ objects so that $k$ are visible when seen from the left? Denote this number by $f_k(n)$, then clearly $f_k(k)=1$ and $f_1(n)=(n-1)!$ since exactly one of the objects can be covered.

After this we obtain $f_{k+1}(n+1)=f_k(n)+(n)f_{k+1}(n)$.

To see this take a configuration with $n+1$ objects and remove the smallest one of those objects, If the smallest object was at the beginning then we shall get an arrangement with $k$ visible items and $n$ objects. Conversely given an arrangement with $k$ visible items and $n$ objects we can obtain one with $n+1$ objects and $k+1$ visible items by placing an item smaller than the rest at the beginning.

If the smallest item was not at the beginning we can take it away, this will give us a configuration with $n$ items and $k$ objects. Moroever there are $n$ configurations which take us to the same exact configuration (depending on the position of the smallest object).

Since $f_k(n)$ has the same recurrence as the stirling numbers of the first kind we conclude $f_k(n)=S^{(k)}_n$.

Finally notice that the problem when there are two sides can be solved classifying on the position of the largest item (this is because the largest item cuts the arrangement into two spots.

Using this let $g_{j,i}(n)$ be the number of ways to arrange $n$ objects so that $j$ are visible from the left and $i$ are visible from the right, we obtain the recursion $g_{j,i}(n)=\sum_{k=1}^nS^{(j-1)}_{k-1}S^{(i-1)}_{n-k}$

$\endgroup$
  • $\begingroup$ $f_k(n)$ are the same as the stirling numbers of the first kind $\endgroup$ – Jorge Fernández Hidalgo Dec 19 '14 at 21:06
0
$\begingroup$

The previous answer is almost correct. You have to multiply to each element of the summation the number of ways to split all the items (except the tallest) into left and right parts. With this modification the formula becomes: $$g_{j,i}(n)=\sum_{k=1}^n\left(\frac{n - 1}{k - 1}\right)S^{(j-1)}_{k-1}S^{(i-1)}_{n-k}$$

$\endgroup$

Your Answer

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