A Game of Change

What is required is that at no time have more $10 note holders approached the clerk than $5 note holders. So form an $xy$ -grid with the number of $5 note holders who have approached the clerk represented on the $x$ -axis and the number of $10 note holders who have approached the clerk represented on the $y$ -axis. Then the allowable "paths" from $(0,0)$ to $(4,4)$ , (where each move involves going either to the right or up one unit), are those that never go above the line $y = x$ .

Now since we just have a $4$ by $4$ grid this is straightforward enough to count manually, with the number of allowable paths being $14$ . In general, for an $n$ by $n$ grid the number of such paths is the Catalan number , $C_{n}$ .

Now for each of these $14$ allowable paths we can arrange the $5 note holders in $4! = 24$ ways and the $10 note holders in $4! = 24$ ways.

Thus $\alpha = 14*24*24 = \boxed{8064}$ .

Since Brian Charlesworth solved the question indirectly by establishing a 1-to-1 correspondence to a known problem, I will provide a direct solution to the problem.

Let a $5$ dollar person be $F$ and a $10$ dollar person be $T$ . Then we need to find all the orderings of $F,F,F,F,T,T,T,T$ given that there is always more or an equal number of $F$ 's than $T$ 's as we go along the line from left to right.

Consider the first person; this person must be an $F$ . Then, consider the first $T$ such that after this person has paid, the number of people who paid who are $F$ 's is the same as the number of people who paid who are $T$ 's: $F [A ]T[B]$

Now in the spaces $[A]$ and $[B]$ , we have smaller versions of the same problem, so let's use recursion. Define $f(n)$ to be the number of ways to order $n$ $F$ 's and $n$ $T$ 's. Then, we see that $f(n+1)=f(0)f(n)+f(1)f(n-1)+\cdots +f(n)f(0)$ $=\sum_{k=0}^{n}f(k)f(n-k)$

Obviously $f(0)=f(1)=1$ . Using the recursion, we find that $f(2)=2, f(3)=5,$ and finally, $f(4)=\boxed{14}$