Pay Before You Enter

In order for there to always be sufficient change, the line-up must, at any point in the line (starting from the front of the line), have at least as many $50$ cent holders as $ $1$ bill holders.

So set up a $5$ by $5$ grid where the $x$ -axis represents the number of $50$ cent holders who have been admitted and the $y$ -axis represents the number of $ $1$ bill holders who have been admitted. We then need to count the number of grid paths, (where the path can only go up or to the right, one unit at a time), which never goes above the line $x = y$ . These are known as Dyck paths , which are enumerated by the Catalan numbers . For $n = 5$ we have $C_{5} = \frac{1}{6} \binom{10}{5} = 42$ paths.

Now for each of these $42$ paths the five $50$ cent holders can be ordered in $5!$ ways and the five $ $1$ bill holders can be ordered in $5!$ ways. Thus the number of possible ways the people can line up so that there is always sufficient change is $42*(5!)^{2} = \boxed{604800}$ .