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



\begin{problem}
\begin{problemparts}
\problempart 
Suppose that Theory Pig wants to take a walk on his neighborhood grid
to location $(n,n)$. He starts at position $(0, 0)$.  At any time, he
can step north (incrementing the first coordinate) or step east
(incrementing the second coordinate).  

\problempart 
In how many different ways can he reach position $(n,n)$, where $n$ is
a non-negative integer? 

\solution{
Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $n$ to be north steps.  This gives $\binom{2n}{n}$  
different ways to reach $(n, n)$.
}

\problempart 
How many different ways are there to list the numbers $1,2,\ldots,2n$
such that the even numbers appear in increasing order and the odd
numbers appear in decreasing order? 

\solution{ 
There are $(2n)!$ ways to list the numbers $1,2,\ldots,n$.  We can
define a $n!$-to-1 mapping that takes an arbitrary listing to a
listing in which the even numbers are sorted in increasing order 
and the odd numbers remain as before.  Thus, by the Division Rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are
\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}
listings in which the even numbers are increasing and the odd numbers 
are decreasing.

Yet another argument: Of the total $2n$ positions in the sequence,
there are $\binom{2n}{n}$ ways to choose where the even numbers are
going to be. Once you make this choice, the positions of the odd
numbers are fully specified (just the unoccupied positions) and the
order of both the even and odd numbers is fully specified as
well. So, after this choice, there is exactly one way to determine the 
entire sequence. So there are as many sequences as many choices of
this kind, $\binom{2n}{n}$.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}
\end{problemparts}
\end{problem}
