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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{8F}

% 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.

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

% 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 + {4\choose 3} + \frac{1}{2} {4\choose 2} + {4\choose 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}

% Spring 99 Quiz2 Prob 6
\begin{problem} 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.

\begin{problemparts}
\problempart How many king positionings are there?

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

\problempart 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
$\dbinom{45+4}{4}$ ways to do this.}

\problempart 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
}

\end{problemparts}
\end{problem}


\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 non-negative
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 {\em 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}.
\]
}

\end{problemparts}
\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 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}

\begin{problem} An adequately-prepared 6.042 student has
the following texts:

\begin{itemize}
\item 5 copies of Velleman
\item 2 copies of Rosen, 3rd edition
\item 6 copies of Rosen, 4th edition
\item 4 copies of the Spring '10 Lecture Notes
\end{itemize}

Copies of the same text are indistinguishable.  The student also has
a bookshelf with four distinguishable shelves.  In how many different
ways can the student arrange his texts on his bookshelf?  Assume that
each shelf has enough space to hold all of the texts and that two
arrangements are different if the texts appear in a different order on
a shelf.

\solution{Each arrangement of the texts on the bookshelf corresponds to
a sequence of the texts together with three ``dividers''.  The texts on
the first shelf appear in the sequence before the first divider, the texts
on the second shelf appear between the first and second dividers, etc.
Thus, the number of different arrangements is $\displaystyle
\binom{20}{5,2,6,4,3}$.
}
\end{problem}
\end{document}



