\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{10, Wed.}                    % !! start the paper


%source: spring00 ps7-5
% source: parts from fall95 ps7, parts from fall94 ps7
% topic: binomial coefficients in large polynomials

\begin{problem}
Find the coefficients of 
\begin{problemparts}
\problempart $x^5$ in $(1+x)^{11}$

\solution{
\[
\binom{11}{5} = 462
\]
}

\problempart $x^8y^9$ in $(3x+2y)^{17}$

\solution{
\[
\binom{17}{8}3^82^9
\]
}

\problempart $a^6b^6$ in $(a^2+b^3)^5$
\solution{
$a^6b^6 = (a^2)^3 (b^3)^2$, so the coefficient is
\[
\binom{5}{3} =10
\]
}

\end{problemparts}
\end{problem}

\begin{problem}
According to the Multinomial theorem, $(w+x+y+z)^n$ can be expressed as a
sum of terms of the form
\[
\binom{n}{r_1,r_2,r_3,r_4}w^{r_1}x^{r_2}y^{r_3}z^{r_4}.
\]
How many terms are there in the sum?

\solution{The sum is over all 4-tuples of nonnegative integers
$(r_1,r_2,r_3,r_4)$ such that
\[
r_1+r_2+r_3+r_4 = n.
\]
We know this is the same as the number of binary words with $n$ zeroes and
3 ones, namely
\[
\binom{n+3}{3}.
\]}
\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 $\card{S} = x$ by counting one way.
\item Show that $\card{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{
\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{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 give a combinatorial proof of the following, more interesting theorem:
\[
n 2^{n-1} = \sum_{k=1}^n k \binom{n}{k}
\]

\hint Let $S$ be the set of all length-$n$ sequences of 0's, 1's and a
single *.

\solution{ Let $P \eqdef \set{0,\dots,n-1} \cross \set{0,1}^{n-1}$.  On
the one hand, there is a bijection from $P$ to $S$ by mapping $(k,x)$ to
the word obtained by inserting a * just after the $k$th bit in the
length-$n-1$ binary word, $x$.  So
\begin{equation}\label{P}
\card{S} = \card{P}= n 2^{n-1}
\end{equation}
by the Product Rule.

On the other hand, every sequence in $S$ contains between 1 and $n$
nonzero entries since the $*$, at least, is nonzero.  The mapping from a 
sequence in $S$ with exactly $k$ nonzero entries to a pair consisting of
the set of positions of the nonzero entries and the position of the *
among these entries is a bijection, and the number of such pairs is
$\binom{n}{k}k$ by the Generalized Product Rule.
Thus, by the Sum Rule:
\[
\card{S} = \sum_{k=1}^n k \binom{n}{k}
\]
Equating this expression and the expression~\eqref{P} for $\card{S}$
proves the theorem.}

\iffalse

How would you prove it algebraically?

\solution{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.}

\fi

\end{problem}


\instatements{\newpage}
Learning to count takes practice!  The following problems offer some.

\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 get each one with as many different toppings as
you wish, absolutely free.  That's $22,369,621$ different ways to choose
your pizzas!
\end{quotation}
The ad writer was a former Harvard student who had evaluated the formula
$(2^{9})^3/3!$ on his calculator and gotten close to $22,369,621$.
Unfortunately, $(2^{9})^3/3!$ is obviously not an integer, so clearly
something is wrong.  What mistaken reasoning might have led the ad writer
to this formula?  Explain how to fix the mistake and get a correct
formula.

\solution{The number of ways to choose 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 used the Product Rule to conclude that there
were $(2^{9})^3$ \emph{sequences} of three topping choices.  Then he
probably reasoned that each way of making three topping choices arises
from $3!$ sequences, so the Division Rule would imply that the number of
ways to choose three pizzas is $(2^{9})^3/3!$.

It's true that every set of three \emph{different} topping choices arises
from $3!$ different length-3 sequences of choices.  The mistake is that if
some of the three choices are the same, then the set of three choices
arises from \emph{fewer} than $3!$ sequences.  For example, if all three
pizzas have the same toppings, there is only one sequence of topping
choices for them.

One fix is to consider ways to choose toppings with 1,2 and 3 different
topping choices.  There are $2^{9}(2^{9}-1)(2^{9}-2)/3!$ ways to choose a
set of 3 different choices, $2^{9}(2^{9}-1)$ ways to choose one topping
choice to be used on two pizzas and a second choice for the third pizza,
and $2^{9}$ ways to choose one topping for all three pizzas, giving
\[
\frac{2^{9}(2^{9}-1)(2^{9}-2)}{3!} + 2^{9}(2^{9}-1) + 2^{9}= 22,500,864.
\]
ways to choose three pizzas.

Alternatively, we can observe that this is exactly the problem of
selecting a dozen donuts of five possible different kinds -- except now
there are 3 donuts and $2^9$ kinds.  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}{3} = 22,500,864.
\]
}
\end{problem}


\begin{problem}
\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{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!}
\]
}

\iffalse

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

\solution{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 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{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}$.}

\fi

\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{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}. 
}

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

\solution{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 How many paths are there from point $(0, 0)$ to $(50, 50)$ if every
step increments one coordinate and leaves the other unchanged?  if there
are impassable boulders sitting at points $(10, 10)$ and $(20, 20)$?
\hint Count the number of paths going through $(10,10)$, the number
through $(20,20)$, and use Inclusion-Exclusion.

\solution{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}
\]
}

\eparts

\end{problem}


\end{document}
