[Math] Number of ways to arrange items

combinatorics

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?

Best Answer

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}$

Related Question