\documentclass[12pt]{article}
\usepackage{light}

\hidesolutions
%\showsolutions

\begin{document}

\recitation{15}{April 6, 2005}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}
Learning to count takes practice! 
\bparts

\ppart In how many different ways can Blockbuster arrange 64 copies of
{\em 13 conversations about one thing}, 96 copies of {\em L'Auberge
Espagnole} and 1 copy of {\em Matrix Revolutions} on a shelf? What if
they are to be arranged in 5 shelves?

\solution[\vspace{1in}]{For 1 shelf, this is the number of ways to arrange 64
$C$'s, 96 $A$'s, and 1 $M$. By the bookeeper rule:
\[
\frac{(64 + 96 + 1)!}{64!\ 96!\ 1!}
\]
For 5 shelves, we can do the simple trick of introducing the dividers
between the shelves as new objects. That is, we want the number of
ways to arrange 64 $C$'s, 96 $A$'s, 1 $M$, and 4 $X$'s (dividers).  By
the bookeeper theorem, again: 
%
\[
\frac{(64 + 96 + 1 + 4)!}{64!\ 96!\ 1!\ 4!}
\]
}

\ppart Find the number of 5-card hands with exactly three aces.

\solution[\vspace{1in}]{We can choose the three aces in $\binom{4}{3}$
ways, and we can choose the remaining two cards in $\binom{48}{2}$
ways.  Thus, there are $\binom{4}{3} \binom{48}{2}$ such hands.}

\ppart Find the number of 5-card hands in which every suit
appears at most twice.

\solution[\vspace{1in}]{There are two cases.  Either one suit appears
twice or else two suits appear twice.  The number of hands in which
one suit appears twice is $\binom{13}{2} \cdot 13^3 \cdot 4$, since
there are 4 ways to choose the doubly-represented suit,
$\binom{13}{2}$ ways to choose two values from this suit, and $13^3$
ways to choose values for cards in the three remaining suits.
Similarly, the number of hands in which two suits appear twice is
$\binom{13}{2}^2 \cdot 13 \cdot \binom{4}{2} \cdot 2$.  Therefore,
there are a total of
%
\[
\binom{13}{2} \cdot 13^3 \cdot 4 + \binom{13}{2}^2 \cdot 13 \cdot \binom{4}{2} \cdot 2
\]
%
such hands.}

\ppart In how many ways can 20 indistinguishable pre-frosh be stored
in four different crates if each crate must contain an \textit{even}
number of pre-frosh?

\solution[\vspace{1in}]{There is a bijection from 13-bit strings with
exactly 3 ones. In particular, the string $0^a10^b10^c10^d$
corresponds to to storing $2a$ prefrosh in the first crate, $2b$ in
the second, $2c$ in the third, and $2d$ in the fourth.  Therefore, the
number of ways to store the pre-frosh is equal to the number of 13-bit
strings with exactly 3 ones, which is $\binom{13}{3}$.}

\ppart How many paths are there from point $(0, 0)$ to $(50, 50)$ if
every step increments one coordinate and leaves the other unchanged
and there are impassable boulders sitting at points $(10, 10)$ and
$(20, 20)$?

\solution[\vspace{1.5in}]{We use inclusion-exclusion.  The total
number of paths is $\binom{100}{50}$, but we must subtract off the
obstructed paths.  There are $\binom{20}{10} \cdot \binom{80}{40}$
paths through the first boulder, since there are $\binom{20}{10}$
paths from the start to the boulder and $\binom{80}{40}$ paths from
the boulder to the finish.  Similarly, there are $\binom{40}{20} \cdot
\binom{60}{30}$ paths through the second boulder.  However, we must
subtract off paths going through both boulders, and there are
$\binom{20}{10} \cdot \binom{20}{10} \cdot \binom{60}{30}$ of those.
Therefore, the total number of paths is:
%
\[
\binom{100}{50}
- \binom{20}{10} \cdot \binom{80}{40}
- \binom{40}{20} \cdot \binom{60}{30}
+ \binom{20}{10} \cdot \binom{20}{10} \cdot \binom{60}{30}
\]
}

\ppart In how many ways can the 72 students in 6.042 be divided into
18 groups of 4?

\solution[\vspace{1in}]{There is a $18!$-to-1 mapping from sequences
containing four $1$'s, four $2$'s, \dots, and four $18$'s.
Specifically, the sequence $(t_1, \dots, t_{72})$ corresponds to the
assignment where each student $i$ is placed in group $t_i$.  The
mapping is $18!$-to-1, because we can permute the team numbers (in
$18!$ different ways) without altering the way the class is
partitioned.  Therefore, the number we want is
\[
\frac{72!}{(4!)^{18} 18!}
\]
by the bookeeper rule and the division rule.
}

\ppart
Set $A$ has $r$ elements and set $B$ has $n$ elements. How many
functions are there from $A$ to $B$? How many of them are injective
(one-to-one)? How many of them are bijective?

\solution[\vspace{1in}]{Say $A=\{a_1,\dots,a_r\}$ and
$B=\{b_1,\dots,b_n\}$ and consider the mapping that sends every
function $f:A\to B$ to the sequence $(f(a_1),\dots,f(a_r))$. This is a
bijection between functions from  $A$ to $B$ and $r$-long sequences of
elements from $B$. By the product rule, the number of such sequences
is 
$$
\underbrace{n\cdot n \cdots  n}_{r\text{ times}} = n^r.
$$

For injections, first note that (by the pigeonhole principle) there is
no way to inject $A$ into $B$ if $B$ has fewer elements than $A$. That
is: if $r>n$, then the number of injections from $A$ to $B$ is~0. If
$r\leq n$, though, the same mapping as previously becomes a bijection
between injections from $A$ to $B$ and $r$-long sequences of
\emph{distinct} elements from $B$. By the generalized product rule,
the number of such sequences is 
$$
n\cdot (n-1)\cdot (n-2) \cdots  (n-r+1) =  \frac{n!}{(n-r)!},
$$
that is, the number of $r$-permutations of $n$ elements.

For bijections, we similarly note that in the case $r\neq n$ the
number of bijections from $A$ to $B$ is $0$. If $r=n$, then a
function from $A$ to $B$ is a bijection iff it is an injection. So
the number of bijections equals the number of injections: $n!/(n-n)! =
n!$, which is exactly the number of different permutations of $n$
elements. 

Notice how \emph{functions}, \emph{injections}, and \emph{bijections}
correspond respectively to \emph{sequences}, $r$-\emph{permutations},
and \emph{permutations}. 
}

\eparts

\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
A pizza house is having a promotional sale. Their commercial reads:
\begin{quotation}\noindent
We offer 9 different toppings for your pizza!  Buy $3$ large pizzas at the
regular price, and you can order each one with any combination of toppings
absolutely free.  That's $22,369,621$ different ways to design your order!
\end{quotation}
The ad writer was a former Harvard student who had evaluated the formula
$(2^{9})^3/3!$ on her calculator and gotten close to $22,369,621$.
Unfortunately, $(2^{9})^3/3!$ is obviously not an integer, so clearly
something is wrong. What? In particular, did she overcount or did she
undercount? What is the correct number? 

\solution[\vspace{2in}]{The number of ways to choose different
toppings for one pizza is the number of the possible subsets of the
set of 9 toppings, namely, $2^{9}$.  The ad writer presumably then
figured out that there were $(2^{9})^3$ ways to place a
\emph{sequence} of three pizza orders.  Then she probably reasoned that
each \emph{set} of three orders arises from $3!$ sequences, so the
Division Rule would imply that the number of orders is $(2^{9})^3/3!$.

It's true that every set of three \emph{different} orders arises from $3!$
different sequences of three orders.  The bug is that if some of the three
orders are the same, then the set of three orders arises from \emph{fewer}
than $3!$ sequences.  For example, if all three pizzas have the same
toppings, there is only one sequence of orders for them.  So dividing by
$3!$ will undercount.

We really need to count the number of ways to ``throw'' three
indistinguishable balls (the three orders) into $2^9$ distinguishable
bins (the different toppings). Hence, there is a bijection to 
the number of ($2^9+2$)-bit strings with exactly $2^9-1$  ones and 3
zeros: 
\[
\binom{2^9 + 2}{2^9 - 1} =
\binom{2^9 + 2}{3} = 22,500,864.
\]
}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\instatements{\newpage}\textbox{
\centerline{\textbf{Combinatorial proofs of identities}}
Recall the basic plan for a combinatorial proof of an identity $x=y$:
\begin{enumerate}
\item Define a set $S$.
\item Show that $\size{S} = x$ by counting one way.
\item Show that $\size{S} = y$ by counting another way.
\item Conclude that $x = y$.
\end{enumerate}
}


\begin{problem}
You want to choose a team of $m$ people from a pool of $n$ people for
your startup company, and from these $m$ people you want to choose $k$
to be the team managers.  You took 6.042, so you know you can do this
in
\[
\binom{n}{m}\binom{m}{k}
\]
ways.  But your CFO, who went to Harvard Business School, comes up with
the formula
\[
\binom{n}{k}\binom{n-k}{m-k}.
\]
Before doing the reasonable thing ---dump on your CFO or Harvard
Business School--- you decide to check his answer against yours.

\bparts
\ppart
Start by giving an \emph{algebraic proof} that your CFO's formula
agrees with yours. 

\solution[\vspace{2in}]{
\begin{eqnarray*}
\binom{n}{m}\binom{m}{k}
& = & \frac{n!}{m! (n-m)!} \frac{m!}{k! (m-k)!} \\
& = & \frac{n!}{(n-m)! k! (m-k)!} \\
& = & \frac{n! (n-k)!}{(n-m)! k! (m-k)! (n-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{(n-m)!(m-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{((n-k) - (m-k))! (m-k)!} \\
& = & \binom{n}{k}\binom{n-k}{m - k}.
\end{eqnarray*} 
}

\ppart Now give a \emph{combinatorial argument} proving this same fact.

\solution[\vspace{2in}]{Instead of choosing first $m$ from $n$ and
then $k$ from $m$, you could alternately choose the $k$ managers from
the $n$ people and then choose $m-k$ people to fill out the team from
the remaining $n-k$ people.  This gives you $\dbinom{n}{k}
\dbinom{n-k}{m-k}$ ways of picking your team.  Since you must have the
same number of options regardless of the order in which you choose to
pick team members and managers,
\[
\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}.
\]
}

\eparts
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Now try the following, more interesting theorem:
\[
n 2^{n-1} = \sum_{k=1}^n k \binom{n}{k}
\]


\bparts
\ppart
Start with a combinatorial argument. \emph{Hint}: let $S$ be the set
of all sequences in $\set{0, 1, *}^n$ containing exactly one $*$.

\solution[\vspace{1in}]{
Let $S$ be the set of all sequences in
$\set{0, 1, *}^n$ containing exactly one $*$.

On one hand, $\size{S} = n 2^{n-1}$, since the $*$ can appear in $n$
positions and there are $2^{n-1}$ settings for the remaining symbols.

On the other hand, every sequence in $S$ contains between 1 and $n$
nonzero entries since the $*$, at least, is nonzero.  The number of
sequences in $S$ with exactly $k$ nonzero entries is $k \binom{n}{k}$,
since there are $\binom{n}{k}$ ways to select the positions of the
nonzero entries and then $k$ ways to select one of those entries to be
the $*$.  Thus, by the Sum Rule:
%
\[
\size{S} = \sum_{k=1}^n k \binom{n}{k}
\]
%
Equating these two expressions for $\size{S}$ proves the theorem.
}

\ppart
How would you prove it algebraically?

\solution[\vspace{1in}]{We calculate:
\begin{eqnarray*}
\sum_{k=1}^n k\binom{n}{k}
& = & \sum_{k=1}^n k\frac{n!}{k! (n-k)!} \\
& = & \sum_{k=1}^n \frac{n!}{(k-1)! (n-k)!} \\
& = & \sum_{k=1}^n n \frac{(n-1)!}{(k-1)! ((n-1)-(k-1))!} \\
& = & n \sum_{j=0}^{n-1} \frac{(n-1)!}{j! ((n-1)-j)!} \\
& = & n \sum_{j=0}^{n-1} \binom{n-1}{j} \\
& = & n 2^{n-1}
\end{eqnarray*} 
The first three steps are algebra: replacing the binomial coefficient
with its ratio of factorials, then simplifying $k$, then trying to
form another coefficient by drawing $n$ out of $n!$ (and eventually
out of the sum). In the fourth step, we change variables, from $k$ to
$j=k-1$. In the fifth step, we recognize the new coefficient we were
after. The final step uses the binomial theorem.}

\eparts
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
