\problemdata      
        {counting-12} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {Radhika Nagpal} % Source (if known)
        {S02 CP8F} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
Stars and Bars Formula. How many different ways can I line up $n$ bars
and $r$ stars? Give {\em at least two different ways} of counting
this.

\solution{Here are a couple of ways:

1. There are $n+r$ positions, choose the positions for the stars
   ${n+r} \choose r$. The bars go in the remaining positions.


2. Same thing as above but you can choose the positions of the bars,
   ${n+r} \choose n$. In general ${k \choose i} = k \choose {k-i}$.

3. Permutations of the $n+r$ length string with the two letters (*,|)
   where the letter $|$ is repeated $n$ times and * is repeated $r$
   times. So we get the multinomial coefficient ${n+r} \choose
   {n,r}$. 

This tells us (by a combinatorial argument) that ${{n+r} \choose
   {n,r}} = {{n+r} \choose r} = {{n+r} \choose n}$ }
\end{problem}
