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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Radhika Nagpal and Charles E. Leiserson}

\begin{document}
\inclassproblems{9, Fri}

% FRIDAY  LECTURE:
% =================

% MISSISSIPPI
% two ways of counting
% r-permutations with repetition: incorrect count
% -> not all things have closed form
% list of permutation variations?
% similarly for combinations? 

% In-Class Problem 1:

% Balls n Bins Table (explain the solution)
% why do we like balls and bins

% Counting is very Pervasive
% Everywhere
% Occupancy problems: Physics Example
% Bridge example.

% Binomial Theorem and Identities

% Overall picture:
% - Sets (Sum rule, inclusion exclusion)
% - Product Rule 
% - Permutations (rearrangements, r-permutations)
% - Combinations (binomial coefficients, subsets of size r)
% - Permutations with limited repetition (multinomial coefficients)
% - Combinations with repetition (Stars-n-Bars)
% - Trees

% Balls n Bins table. 
% Balls n Bins tutorial example.

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

\begin{problem} 
Recall the definition of a multinomial coefficient:
\begin{equation}
\binom{n}{r_1, r_2, \ldots, r_k}  \eqdef  \frac{n!}{r_1!\,r_2!\cdots r_k!}.
\end{equation}
An alternative definition is
\begin{equation}
\binom{n}{r_1, r_2, \ldots, r_k}  \eqdef 
\binom{n}{r_1}.\binom{n-r_1}{r_2}\binom{n-r_1-r_2}{r_3}\cdots\binom{n-r_1-r_2-\cdots-r_{k-1}}{r_k}
\end{equation}

Prove that the two definitions are equivalent using both a (i) combinatorial
and (ii) an algebraic argument.
\end{problem}

\solution{See Week 9 Notes, Theorem 7.2}

%----------------------------------------------------------------------

\begin{problem} 
Suppose that we have a generalized $n$-letter ``MISSISSIPPI'' word
whose letters break down as follows: $m$ occurrences of ``M'', $i$
occurrences of ``I'', $s$ of ``S'', and $p$ of ``P''.  For example,
for the word ``MISSISSIPPI'' breaks down as $(n;m,i,s,p) =
(11,1,4,4,2)$.  For each of the following formulas, identify which
correctly describe the number of different permutations of the
generalized ``MISSISSIPPI'' word.  For the correct formulas, justify
your answer using a combinatorial (not an algebraic) argument.
\begin{problemparts}

\problempart $\dbinom{n}{m,i,s,p}$.

\solution{True.  A straightforward application of the theorem from
class.}

\problempart	$\dbinom{n}{p,i,m,s}$

\solution{True. The order of the lower arguments of the multinomial
coefficient is not important.}

\problempart	$\dbinom{n}{m,i,s,n-m-i-s}$

\solution{True, because $m+i+s+p=n$ implies $p=n-m-i-s$.}

\problempart	$\dbinom{n}{m}\dbinom{n}{i}\dbinom{n}{s}\dbinom{n}{p}$

\solution{False.}

\problempart	$\dbinom{n}{m}\dbinom{m}{i}\dbinom{i}{s}\dbinom{s}{p}$

\solution{False.}

\end{problemparts}
\end{problem}


%----------------------------------------------------------------------
% Adapted by CEL from C.L. Liu, Introduction to Combinatorial Mathematics, 
% McGraw-Hill, New York, 1968, pp. 14-15.

\begin{problem}

The U.S. House of Representatives has 435 seats.  (In this context, a
``seat'' is not a chair, but a right to belong to the legislative
body.  Thus, all seats are indistinguishable.)


\begin{problemparts}  

\problempart \label{3a}
In how many ways can the seats be distributed among three
political parties?

\solution{Each distribution can be represented by 435 stars for the seats,
and two bars to separate the stars into three groups (Democrat,
Republican, and Ross Perot's Reform Party).  So the answer is
\[
\binom{435+2}{2}.
\]}

\problempart \label{3b} In how many ways can the seats be distributed
among three political parties so that no party has a majority?  (This
implies that a coalition of any two parties \emph{does} form a majority.)

\solution{No party can have 218 seats or more.  We've counted the
total number of ways of distributing seats among three parties in part
(a), and thus we'll subtract the number of ways one party could have a
majority.  We can count the number of ways a party can be in the
majority by giving it 218 seats and distributing the remaining 217
seats among the three parties.  Since there are three parties, the
answer is
\[
\binom{437}{2}-3\binom{219}{2}.
\]
}

\problempart\label{3c} How do your solutions to parts~(\ref{3a}) and
parts~(\ref{3b}) change if the ``seats'' are actually distinguishable
chairs (numbered 1 through 435)?

\solution{
Part~(\ref{3a}): $3^{435}$.

Part~(\ref{3b}):
\[
3^{435} - 3\sum_{i=218}^{435}\binom{435}{i}2^{435-i}.
\]
}

\end{problemparts}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse

%----------------------------------------------------------------------
\begin{problem} Sequences
\begin{problemparts}
\problempart Determine the number of solutions to the equation $x_1 +
x_2 + \ldots + x_n = r$, where all variables are nonnegative
integers.

\solution{Each solution to the equation corresponds to a string of $r$
stars and $n-1$ bars.  The correspondence is illustrated by the
example below, where $n = 4$ and $r = 6$:
\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star \\
3 & + & 1 & + & 0 & + & 2 & = & 6\ .
\end{array}
\]
Therefore, the number of solutions is
\[
\binom{n + r - 1}{r}\ .
\]
}

\problempart Determine the number of sequences of $k$ integers in the
range $0$ to $n$ that are \emph{monotonically increasing}; that is,
each integer in the sequence is greater than or equal to the one
before.

\solution{Each sequence corresponds to a string of $n$ stars and $k$
bars.  The correspondence is illustrated below, where $k = 4$ and $n =
7$:
\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star & \mid & \star\\
3 &,& 4 &,& 4 &,& 6\ .
\end{array}
\]
As the example illustrates, the $k$th number in the sequence is equal
to the total number of stars preceding the $k$th bar.  Therefore, the
number of sequences is
\[
\binom{n + k}{k}\ .
\]
Make sure to double-check one-to-one and onto.
}

\end{problemparts}
\end{problem}


%----------------------------------------------------------------------
% Last Used Fall 01 tutorial 9
% pset7 problem4 spring98, from M&R, # 4.7.5
% balls n urns (all types)
\begin{problem}
How many ways can 4 balls be placed in 4 urns if 

\begin{problemparts}
\problempart both the balls and the urns are distinguishable;

\solution{ $4\cdot 4\cdot 4\cdot 4 =256$. For each ball, we can choose
one of 4 urns to put it in. We can think of this problem as a string
of 4 boxes (balls) from an alphabet of urns, or as a function from a
set of balls to a set of urns. The fact that all the balls are
different is important.}

\problempart the balls are distinguishable but the urns are not;

\solution{15. We can put either all 4 balls in one urn; or 3 in one, 1
in another; or 2 in one, 2 in another; or 2 in one, 1 in one and 1 in
another; or 1 ball in each urn.  The balls are distinguishable, so
there are $4\choose 3$ ways of putting 3 in one urn.  There are
$4\choose 2$ ways of putting 2 in one and 1 in each of the other two.
There are ${4\choose 2}/2$ ways of putting 2 in one and 2 in
another. Since the urns are indistinguishable, the case where all the
balls are placed in the same urn and the case where each ball is
places in a different urn are unique.  So, the total number of ways is
\[
1 + \binom{4}{3} + \frac{1}{2} \binom{4}{2} + \binom{4}{2} + 1 = 15\ .
\]
}

\problempart the urns are distinguishable but the balls are not;

\solution{35. This is a stars and bars problem with the balls being
stars and the urns bars.  The answer is ${4+4-1 \choose 4} = {7
\choose 4} = 35$. Note, there is a fundamental difference between
balls and urns - an urn can hold many balls, but a ball can go into
only one urn. So having urns indistinguishable is not the same as
having balls be indistinguishable.} 

\problempart neither the balls nor the urns are distinguishable.

\solution{5.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 4 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset, \emptyset$ or
$\{1,1,1\}, \{1\}, \emptyset,\emptyset$, or
$\{1,1\}, \{1,1\},\emptyset,\emptyset$, or
$\{1,1\}, \{1\}, \{1\}, \emptyset$, or
$\{1\},\{1\},\{1\},\{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.
}

\end{problemparts}
\end{problem}



%----------------------------------------------------------------------
% Fall 99 Final exam Prob 10, spring00 ps7-5, spring96 ps7
% revised by ARM 10/25/01
% topic: combinatorics, algebraic manipulation
\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 you dump on your CFO or Harvard Business School, you decide to
check his answer against yours --- fortunately.

\begin{problemparts}

\problempart Give an 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*} 
}

\problempart Now give what the Notes call 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}.
\]
}

\end{problemparts}
\end{problem}

%----------------------------------------------------------------------
% source: made it up to make sure they udnerstand stars n bars formula
\begin{problem}
Stars and Bars Formula. How many different ways can I line up $n$ bars
and $r$ stars? Give {\em at least two different ways} of counting
this.

\solution{Here are a couple of ways:

1. There are $n+r$ positions, choose the positions for the stars
   ${n+r} \choose r$. The bars go in the remaining positions.


2. Same thing as above but you can choose the positions of the bars,
   ${n+r} \choose n$. In general ${k \choose i} = k \choose {k-i}$.

3. Permutations of the $n+r$ length string with the two letters (*,|)
   where the letter $|$ is repeated $n$ times and * is repeated $r$
   times. So we get the multinomial coefficient ${n+r} \choose
   {n,r}$. 

This tells us (by a combinatorial argument) that ${{n+r} \choose
   {n,r}} = {{n+r} \choose r} = {{n+r} \choose n}$ }
\end{problem}



%----------------------------------------------------------------------
%source: spring00 ps7-5
% source: spring95 ps7
% topic: basic combinatorics, stars and bars
\begin{problem}A pizza house is having a promotional sale. Their commercial
reads:
\begin{quotation}\noindent
Buy $2$ large pizzas at the regular price, and get up to $11$ different
toppings from $11$ possible for each pizza absolutely free.  That's 
$4,194,304$ different ways to design your order!
\end{quotation}

\iffalse
 $\displaystyle \left( \sum_{k=0}^{11}\binom{11}{k} \right)^2
= \displaystyle \left(2048 \right)^2 = 4,194,304$\fi

The ad writer was a former Harvard student who had figured out that
$(2^{11})^2 = 4,194,304$.  Unfortunately, this number $(2^{11})^2$ is
actually wrong. In how many can you really choose toppings for the two
pizzas?

\solution{The first thing to understand is where the $2^{11}$ came
from. The number of ways to choose different toppings for one pizza is
all the possible subsets of the set of 11 toppings, which is $2^{11}$.

However, when the student says that there are $(2^{11})^2$ different
ways to choose toppings for two pizzas, he is making the mistake of
counting the combination ``one mushroom and anchovy pizza, and one
green-pepper pizza'' as different from the combination ``one
green-pepper pizza and one mushroom and anchovy pizza .''  (At least
he knew enough not to count a mushroom and anchovy pizza as different
from an anchovy and mushroom pizza).

The right solution is
\[
2^{11}+\binom{2^{11}}{2} = 2,098,176,
\]
namely, the number of ways to choose two pizzas with the same topping,
plus the number of ways to choose $2$ pizzas with different sets of
toppings.}
\end{problem}

\fi

\end{document}




