\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{eepic}

%\usepackage{psfig}

\input{macros-course}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\numb}[1]{\card{\text{#1}}}

\renewcommand{\solution}[1]{}

\begin{document}

\tutprobn{16}{11/12/99}{November 10, 1999}

\begin{problems}

\problem %\emph{Stars and Bars.}  S99 Q2

The \emph{king positioning} in an arrangement of a deck of 52 playing
cards is the sequence of numerical positions in the deck, from one to 52,
of the four successive kings.  For example, the king positioning
$(1,2,3,4)$ means all the kings come at the beginning of the deck.  The
king positioning $(1,18,35,52)$ describes the situation in which the kings
are spaced uniformly---with exactly 16 cards between successive kings.

Your answer to each of the following questions may be an arithmetic
expression involving factorials and/or multinomial coefficients.

\bparts
\ppart How many king positionings are there?

\solution{$\binom{52}{4}$.}


\ppart How many king positionings are there in which \emph{no two kings
are adjacent}?

\solution{

Think of kings as bars and the remaining 48 cards as stars.
Place one star between each two adjacent kings (bars).  This requires
three stars and leaves 45 stars that can be placed anywhere; there are
$\binom{45+4}{4}$ ways to do this.}


\ppart Of the $52!$ possible arrangements of the deck, how many have no
two kings adjacent?

\solution{

Now in each of the previous patterns of stars and bars, the kings can be
permuted in $4!$ ways and the remaining cards can be permuted in $48!$
ways, so the total number of desired arrangements is
\[\binom{45+4}{4} 48!\, 4! = 49!\, 48!/45! = 48!\, P(49,4).\]

\iffalse
The form of the RHS suggests that there is another way to do this count,
but I haven't had time to figure what it is.
\fi

}

\eparts


\problem In Quiz 1 we considered rooted order trees, $\ROT$.  In this
problem, we will develop an ingenious method to count the number of $
\ROT$ of size $n$.

\bparts

\ppart
How many $\ROT$ of size 4 are there?

\solution{

5 $\ROT$ with 4 nodes.

\iffalse
CAN'T PRINT THIS VERBATIM ENV; LATEX BUG?

\begin{center}
\begin{verbatim}
   /\    /\   /|\  |   |
    |    |         |   /\
                   |
\end{verbatim}
\end{center}
\fi

}

\eparts

We begin by noting the bijection between $\ROT$ of size $n$ and strings of
$2n$ parentheses of the form $\texttt{(}s\texttt{)}$ where $s$ is an
SMU--- a string of parentheses that ``matches up'' as described in Problem
Set 2.  (This correspondence will be familiar to anyone who is familiar
with a LISP-like programming language such as Scheme.)

In Problem Set 2 we showed that SMU were the same as strings of
parentheses that Count Well.  The strings corresponding to $\ROT$ are the
ones whose count remains positive until the end.  That is, starting with
zero, read the string from left to right adding one for each left
parenthesis and -1 for each right parenthesis.  A string \emph{counts
positive} when the count never goes negative and returns to zero \emph{for
the first time} by the end of the string.  Let \emph{CP} be this set of
strings.  So to count $\ROT$ of size $n$, we need only count CP of length
$2n$.

\bparts

\ppart Write the strings of parentheses corresponding to the $\ROT$ of
size 4.

\solution{

5 $\ROT$ with 4 nodes.  The corresponding expressions are:
\[\texttt{(()(())),\ ((())()),\ (()()()),\ (((()))),\ ((()()))}.\]

}
\eparts



Our approach to counting CP will involve considering \emph{paths} in the
plane from a point $(x_1,y_1)$ to $(x_2,y_2)$ for $x_i,y_i \in \ints$,
where each step in the path is at a $\pm 45$ degree angle, increasing the
x-coordinate by 1 and the y-coordinate by $\pm 1$.  For example, a path
might start at $(1,1)$ and make seven steps to the successive points
$(2,0)$, $(3,-1)$, $(4,0)$, $(5,1)$, $(6,2)$, $(7,1)$, as in
Figure~\ref{fig:path}.

\begin{figure}
\begin{center}
\begin{picture}(345,195)(-45,-45)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)%o(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}
\put(212,32){\makebox(0,0)[bl]{$(x_2, y_2)$}}

%\put(240,0){\circle*{3}}
%\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em A path from $(1,1)$ to $(7,1)$.}

\label{fig:path}

\end{figure}


\bparts

\ppart
Explain why the number of well-matched parenthesized strings of
length $2n$ is the same as the number of paths from $(0,0)$ to $(2n,0)$
that only touch the x-axis at their endpoints.  (That is, if $0<i<2n$ and
$(i,j)$ is a point on the path, then $j>0$.)

\solution{

Interpret left paren as a ``move up'' step and right paren as a ``move
down'' step.  Then every string of $k$ parens corresponds to a path of
length $k$ from the origin and \emph{vice-versa} --- a bijection.  Strings
that count positive exactly to paths from the origin whose x coordinate
stays positve until the end of the path---that is, paths from the origin
back to the x-axis that don't touch the x-axis in between endpoints.

}

\ppart
How many paths are there from $(x_1,y_1)$ to $(x_2,y_2)$?  (Express the
answer as a binomial coefficient.)

\solution{\begin{align*}
\numb{moves}
    & = x_2 - x_1 \\
\numb{up moves} - \numb{down moves}
    & = y_2 - y_1 \\
\numb{up moves} + \numb{down moves}
    & = \numb{moves} = x_2 - x_1 \\
\numb{up moves}
    & = \frac{(x_2 + y_2) - (x_1 + y_1)}{2} ::= u \\
\numb{down moves}
    & = \frac{(x_2 - y_2) - (x_1 - y_1)}{2} ::= d \\
\numb{paths}
    & = \binom{u+d}{u} = \binom{u+d}{d}.
\end{align*}

}

\ppart For $y_1,y_2 > 0$, show that the number of paths from $(x_1,y_1)$
to $(x_2,y_2)$ that touch or cross the x-axis is equal to the number
of paths from $(x_1,-y_1)$ to $(x_2,y_2)$.
\hint See Figure~\ref{fig:reflect}.

\begin{figure}

\begin{center}
\begin{picture}(345,205)(-45,-55)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\put(30,-30){\circle*{3}}
\put(32,-32){\makebox(0,0)[tl]{$(x_1, -y_1)$}}

\dottedline{2}(30,-30)(60,0)

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30) %(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}
\put(212,32){\makebox(0,0)[bl]{$(x_2, y_2)$}}

%\put(240,0){\circle*{3}}
%\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em Reflection of the initial part of a path.}

\label{fig:reflect}

\end{figure}

\solution{

Figure~\ref{fig:reflect} indicates how to define a bijection between the
two kinds of paths.

}

\ppart Conclude that the number of $\ROT$ of size $n$
equals
\[\frac{1}{n} \binom{2n-2}{n-1}.\]
This number is known the $n-1$st \emph{Catalan number}.


\solution{
\begin{eqnarray*}
\numb{paths from $(1, 1)$ to $(2n-1, 1)$}
       & = &  \binom{2n-2}{n-1}, \qquad \text{because}\\
    u   &= & \frac{2n-2}{2}     = n-1,\\
    d   &= & \frac{(2n-2)-0}{2} = n-1.
\end{eqnarray*}

\begin{eqnarray*}
\numb{paths from $(1, 1)$ to $(2n-1, 1)$ touching x-axis}
    &= &\numb{paths from $(1, -1)$ to $(2n-1, 1)$} \\
    &= & \binom{2n-2}{n} = \binom{2n-2}{n-2} \qquad \text{because}\\
    u &= &\frac{2n - 0}{2} = n, \qquad \text{and}\\
    d &= & \frac{(2n - 2) - 2}{2} = n - 2.
\end{eqnarray*}

\begin{eqnarray*}
\lefteqn{\numb{paths from $(1, 1)$ to $(2n-1, 1)$ above x-axis}}\\
    &= &\numb{paths from $(1, 1)$ to $(2n-1, 1)$}
        - \numb{paths from $(1, 1)$ to $(2n-1, 1)$ touching x-axis}\\
    &= &\binom{2n-2}{n-1} - \binom{2n-2}{n}\\
    &= &\binom{2n-2}{n-1}
        - \frac{(2n-2)!}{n! \, (n-2)!}\\
    &= &\binom{2n-2}{n-1}
        - \frac{(2n-2)!(n-1)}{n(n-1)! \, (n-1)!}\\
    &= &\binom{2n-2}{n-1} - \frac{n-1}{n}\binom{2n-2}{n-1}\\
    &= & \binom{2n-2}{n-1} \cdot \frac{1}{n}
\end{eqnarray*}
}

\eparts


\problem  %from S99 tut9

\bparts

\ppart

In lecture we demonstrated how to ``guess'' the fifth card in a poker hand
when a collaborator reveals the other four cards.  Describe a method for
guessing two hidden cards in a hand of nine cards, when your collaborator
reveals the other seven cards.

\solution{There must be $\ceil{9/4} = 3$ cards with the same suit, so our
collaborator chooses to hide two of them and then use the third one as the
first card to be revealed.  So this first revealed card fixes the suit of
the two hidden cards; it will also be used as the origin for the offset
position of the first hidden card.  This first hidden card will in turn be
used as the origin for the offset of the other hidden card.  There are six
cards to code the two offset positions.  These suffice to code two offsets
of size from one to six.  That is, our collaborator can choose one of the
$3! = 6$ orders in which to reveal the first three cards and thereby tell
us the offset position of the first hidden card.  Our collaborator can
then choose the order of the final three cards to describe the offset
position of the second hidden card from the first.  Note that the first
revealed card must be chosen so that both offsets are less $\leq 6$; since
the sum of the offsets between successive cars ordered in a cycle from Ace
to King is 13, it is not possible for more than one offset between
successive cards to exceed seven, so this is always possible.}

\ppart Show that there is no procedure for ``guessing'' a hidden card
among four when your collaborator reveals three. \hint Compare the number
of hands to the number of revealed three-card sequences.
~
\solution{
There are $\binom{52}{4}$ possible four-card hands.  There are $P(52,3)$
three-card sequences that can ever be revealed.  Since
\[
\frac{\binom{52}{4}}{P(52,3)}=
\frac{52\cdot 51\cdot 50 \cdot 49/4!}{52 \cdot 51 \cdot 50} = 49/24 > 1,
\]
there must, by pigeonholing, be two (actually three) hands for which the
collaborator reveals the same three cards.  Therefore the magician cannot
determine the hidden card, since these hands must have different hidden
cards.}

\eparts



\iffalse

\problem %from S99 tut9

How many poker hands are there with no pairs?

\solution{

Straight from the lecture notes:

{\em First count. } There are 52 choices for the first card, 48
choices for the second card given the first, 44 choices for the third
given the first two, etc.  After each card, the number of remaining
choices drops by four, since we can not subsequently pick the card
just taken or any of the other three cards with the same value.  This
gives $52 \cdot 48
\cdot 44
\cdot 40 \cdot 36$ hands with no pair.  Is this answer right?

The references to ``first card'', ``second card'', $\ldots$ are a
warning signal that we may be inadvertantly counting an ordered set.
To be sure, we can check how many times a particular hand is counted.
Consider the hand $A \heartsuit \ K \spadesuit \ Q \clubsuit \ J \clubsuit
\ 10 \heartsuit$.  We could have obtained this hand by drawing cards in
the order listed, but we could also have drawn them in another order.
In fact, we counted this hand once for every possible ordering of the
five cards; that is, each hand is counted $5! = 120$ times!  We can
correct our initial answer by applying the Division Rule.  This gives:

\[
\numb{hands with no pairs}
 =  \frac{52 \cdot 48 \cdot 44 \cdot 40 \cdot 36}{120}
 =  1,317,888
\]

{\em Second count. } There is another way to count the hands with no
pairs that avoids this confusion.  Since there are no pairs, no two
cards have the same value.  This means that we could first choose 5
distinct values from the set of 13 possibilites.  Then we could choose
one of the four suits for each of the five cards.  This gives:

\[
\numb{hands with no pairs}
 =  \binom{13}{5} \cdot 4^5
 =  \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9}
                   {5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \cdot 4^5 = 1,317,888
\]

This is the same answer as before.  Notice that the number of hands
with no pairs is more than half of all the hands.  This means that in
more than half our games of Five-Card Draw, we will not even have one
pair!
}
\fi

\end{problems}

\end{document}
