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

\begin{problem}
{\bf The Pig Walk}
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).  In this problem, we'll use the Division
Rule to count how many different ways he can reach position $(n, n)$, for
$n \in \naturals$.

\begin{problemparts}

\problempart Let's take a mapping that maps a length $2n$ sequence, $p$, 
of the integers $1, 2,
\ldots, 2n$, into a sequence, $p'$, in which odd numbers remain in the same
positions and even numbers remain in the same positions, but the odd and
even numbers are each sorted into increasing order.  This map is $k$ to
one for what $k$?  Explain.

\solution{$k=n!^2$.  Let's look at the even numbers in $p'$ first.  
How many different
ways can we re-order them so as to get strings $p$?  
Take the first even number and consider the
locations we can put it in.  There are $n$ choices, corresponding to the locations
where even numbers occur in string $p'$.  The next even number in $p'$ has $n-1$
choices, etc... so we have $n \times n-1 \times \cdots \times 1 = n!$ possible
re-orderings.  Similarly, there are $n!$ re-orderings for the odd numbers, and so
we have a total of $n!^2$ re-orderings for both the odd and even numbers together,
by the Product Rule.  Since each re-ordering corresponds to a $p$ that maps to
the same $p'$, the given map must be a $n!^2$ to 1 mapping. 
}

\ppart 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$.
Mapping any such list, $p$, into, $p'$, defines a $n!^2$-to-1 mapping that
takes an arbitrary listing to a listing in which the odd and even numbers
are sorted in increasing order.  Thus, by the Division Rule, there are
$(2n)!/n!^2$ listings in which the odd and even numbers appear in
increasing order.}

\problempart Explain why the number of paths Theory Pig can follow is the
same as the answer to part~(b).

\solution{Each time Theory Pig takes a step North, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step East, write down an odd number, starting with $2n-1$ and working down.

Note that if we use binomial coefficients, to be introduced next week,
then the solution is easy: 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)$.}

\end{problemparts}

\end{problem}