\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}{Fact}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\left\{#1\right\}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }

\begin{document}

\begin{center}
{\Large Notes for Tutorial 12} \\
6.042 - May 2 and May 5 \\
\bigskip
\end{center}

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

There are three main topics.  An understanding of this stuff should
translate pretty directly to a higher final exam score.

\begin{itemize}

\item More counting practice.

\item Inclusion-exclusion

\item Combinatorial proof

\end{itemize}

\noindent In addition, there is a brief brush with probability
distributions, a topic that we won't cover in detail.  (So far as I
know...)

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

\section{More Counting Practice}

As before, I suggest you pose these questions to the group.  Have
people explain their answers so that everyone understands and can ask
questions.

\begin{enumerate}

\item How many ways are there to arrange the letters in the word
``bumblebee''?

\beqn
\binom{9}{3,3,1,1,1} & = & \frac{9!}{3!\ 3!\ 1!\ 1!\ 1!}
\eeqn

First, suppose that the letters were all distinct, as in
$b_1umb_2le_1b_3e_2e_3$.  Then there would be $9!$ arrangements.
However, ``b'' is repeated three times and ``e'' is repeated three
times.  Therefore, there is a $(3! \cdot 3!)$-to-1 mapping from
arrangements of letters in the subscripted word to arrangements of
letters in the ordinary word.  (The mapping is performed by erasing
the subscripts.)  Thus, the division rule gives the answer above.

\item How many ways are there to arrange the letters in the word
``booboo''?

(Call on a student who was confused on the previous question, if there
was one.)  By the same reasoning as before:

\beqn
\binom{6}{4,2} & = & \frac{6!}{4!\ 2!}
\eeqn

\item In how many ways can 20 identical balls be arranged in 5
distinguishable bins?

There is a bijection with sequences containing 20 stars and 4 bars, so
we get:

\[
\binom{(20 + 5 - 1)!}{20!\ (5-1)!}
\]

\item How many sequences are there containing 12 stars and 4 bars?

\[
\frac{(12 + 4)!}{12!\ 4!}
\]

Some students reflexively subtract 1 from the nearest expression
whenever they see the words ``stars'' and ``bars''.  Make sure
understand why this was necessary in the preceeding problem, but not
in this one.

\item I want to string together $k > 3$ unique beads to form a
bracelet.  In how many ways can this be done?

There are $k!$ ways to line up the beads.  There is a $k$-to-1 mapping
from lineups of beads to circles of beads, as we saw in the Knights of
the Round Table example in lecture.  Futhermore, there is a 2-to-1
mapping from circles of beads to bracelets, because we can turn the
bracelet over.  Therefore, two applications of the division rule give:

\beqn
\frac{n!}{2n} & = & \frac{(n-1)!}{2}
\eeqn

\item How many distinct positive factors does the number $3^4 \cdot
5^2 \cdot 7^3 \cdot 11$ have?

A factor is a product of between zero and four 3's, between zero and
two 5's, between zero and three 7's and either zero or one 11.
Therefore, by the product rule, the answer is:

\beqn
(4 + 1) \cdot (2 + 1) \cdot (3 + 1) \cdot 2 & = & 120
\eeqn

\item In how many ways can 20 identical books be placed on 5 different
shelves?

This is equivalent to asking how many ways there are to arrange 20
stars and 4 bars in a string.  The answer is:

\[
\frac{24!}{20!\ 4!}
\]

\item In how many ways can 20 identical books be placed on 5 different
shelves, if every shelf must get at least 1 book?

First, we place one book on every shelf.  Then we may place the
remaining 15 books on the 5 shelves without restrictions.  By a
stars-and-bars argument, the number of ways to do this is:

\[
\frac{19!}{15!\ 4!}
\]

\item In how many ways can 20 distinguishable books be placed on 5
different shelves?

This is equivalent to asking how many ways there are to arrange the
symbols $b_1, b_2, \ldots, b_{20}$ together with four bars in a
string.  The answer is:

\[
\frac{24!}{4!}
\]

\item What is the probability of flipping 80 heads and 20 tails on a
coin that comes up heads with probability 0.6?

There are $\binom{80+20}{20}$ such sequences, and each sequence has
probability $0.6^{80} \cdot 0.4^{20}$.  Therefore, the probability is:

\[
\binom{80+20}{20} \cdot 0.6^{80} \cdot 0.4^{20}
\]

\item How many injective functions are there from an $n$-element
domain to an $m$-element range?

If $m < n$, then there are none.  Otherwise, we can map the first
domain element to $m$ points in the range, the second domain element
to $m-1$ points in the range, etc., until we run out of domain
elements.  Overall, this gives:

\beqn
m \cdot (m-1) \cdots (m - n + 1)
    & = & \frac{m!}{n!}
\eeqn

\end{enumerate}

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

\section{Inclusion-Exclusion}

The inclusion-exclusion formula is easier to describe than to write
down.  It says that the size of a union of sets is equal to the sum of
the set sizes {\em minus} the sizes of the pairwise intersections {\em
plus} the sizes of the three-way intersections {\em minus} the size of
the four-way intersections, etc.  (You could ask three students two
write up the inclusion-exclusion formulas for 2, 3, and 4 sets in
parallel for reference.)

The following problems are suitable for small teams.

\subsection{An easy problem}

On an island, everyone is healthy, wealthy, or wise.  There are
exactly 1000 people with each property.  There are exactly 200 people
with each pair of properties.  And there are exactly 50 people with
all three properties.  How many people are on the island?

Let $H$ be the set of healthy people, $\$$ be the set of wealthy
people, and $W$ be the set of wise people.  By the inclusion-exclusion
formula, we have:

\beqn
|H \cup \$ \cup W|
    & = & |H| + |\$| + |W| - |H \cap \$| - |H \cap W| - |\$ \cap W|
          + |H \cap \$ \cap W| \\
    & = & 3 \cdot 1000 - 3 \cdot 200 + 50 \\
    & = & 2450
\eeqn

\subsection{A harder problem}

A number is {\em cube-free} if it is not divisible by a perfect cube
greater than 1.  For example, 36 is cube-free, but $54 = 3^3 \cdot 2$
is not.  Use inclusion-exclusion to count the cube-free integers in
the range from 1 to 999.

Initially, we'll compute the size of the complementary set; that is,
we'll count the numbers from 1 to 999 that {\em are} divisible by a
perfect cube.

Let $S_q$ be the set of natural numbers from 1 to 999 that are
divisible by $q^3$.  Our goal is to compute:

\[
|S_2 \cup S_3 \cup S_4 \cup S_5 \cup S_6 \cup S_7 \cup S_8 \cup S_9|
\]

\noindent This would be a lot of work!  But notice that $S_4 \subseteq
S_2$; that is, every number divisible by $4^3$ is also divisible by
$2^3$.  Since $S_4$ adds nothing to the union above, we can forget
about it.  By similar reasoning, we can reduce the problem to
computing:

\[
|S_2 \cup S_3 \cup S_5 \cup S_7|
\]

This is more tractable.  We now compute the terms of the
inclusion-exclusion formula:

\[
\begin{array}{rcccl}
|S_2| & = & \lfloor \frac{999}{2^3} \rfloor & = & 124 \\
|S_3| & = & \lfloor \frac{999}{3^3} \rfloor & = & 37 \\
|S_5| & = & \lfloor \frac{999}{5^3} \rfloor & = & 7 \\
|S_7| & = & \lfloor \frac{999}{7^3} \rfloor & = & 2 \\
|S_2 \cap S_3| & = & \lfloor \frac{999}{2^3\ 3^3} \rfloor & = & 4
\end{array}
\]

All other terms are ZERO!  So we have:

\beqn
|S_2 \cup S_3 \cup S_5 \cup S_7|
    & = & 124 + 37 + 7 + 2 - 4 \\
    & = & 166
\eeqn

This means that 166 numbers in the range 1 to 999 are multiples of
perfect cubes.  Therefore, the number of cube-free numbers in this
range is:

\beqn
999 - 166 & = & 833
\eeqn

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

\section{Combinatorial Proofs}

Give a combinatorial proof of the following identity:

\beqn
(r-k) \cdot \binom{r}{k} & = & r \cdot \binom{r-1}{k}
\eeqn

Remember the general structure of a combinatorial proof:

\begin{enumerate}

\item Define an appropriate set $S$.

\item Show that the left side counts the number of elements in $S$.

\item Show that, from another perspective, the right side also counts
the number of elements in $S$.

\item Conclude that the two sides must be equal, because they are both
equal to $|S|$.

\end{enumerate}

Let set $S$ consists of all $(k+1)$-element subsets of $\{1, \ldots,
n\}$ where one element of the subset is specially marked.  Formally:

\beqn
S & = & \{ 
(T, x) \mid T \subseteq \{1, \ldots, n\}, |T| = k, \text{ and } x \in T
\}
\eeqn

(More intuitively, $S$ consists of all $k+1$ person committees with a
designated chairman.)

On one hand, we could pick $k$ elements in $\binom{r}{k}$ ways and
then choose the special element from among the remaining elements in
$(r-k)$ ways.  Thus, the left side of the equation is equal to $|S|$.
On the other hand, we could choose the special element first in $r$
ways and then choose the remaining $k$ elements in $\binom{r-1}{k}$
ways.  Thus, the right side is equal to $|S|$.  Since both sides are
equal to $|S|$, they must be equal to each other.

\subsection{A harder identity}

\beqn
n 2^{n-1} & = & \sum_{k=1}^n k \cdot \binom{n}{k}
\eeqn

Set $S$ consists of {\em all} subsets of $\{1, \ldots, n\}$ where one
element is special.  Formally:

\beqn
S & = & \{ (T, x) \mid T \subseteq \{1, \ldots, n\} \text{ and } x \in T \}
\eeqn

(Intuitively, $S$ consists of all committees with one or more people
and a designated chairman.)

On one hand, we could first pick one of the $n$ elements to be special
and then either include or exclude every other element.  (That is, we
first pick $x$ and stick it in $T$.  Then we decide whether or not to
include every other element in $T$.)  This can be done in $n \cdot
2^{n-1}$ ways.  Therefore, the left side is equal to $|S|$.

On the other hand, our subset must contain $k$ elements for some $k$
between 1 and $n$.  For each $k$, we can choose the subset is
$\binom{n}{k}$ ways and then choose the special element from that
subset in $k$ ways.  Therefore, the right side is also equal to $|S|$.
Since the left and right sides of the equation are both equal to
$|S|$, they must be equal to each other.

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

\section{Distributions}

Let the random variable $Q$ be the number of 1's in an $n$-bit string
selected uniformly at random.  Let the random variable $R$ be the
number of times heads comes up on $n$ tosses of a fair coin.  From one
perspective, these random variables have nothing to do with one
another; after all, they are defined on different sample spaces.  On
the other hand, they clearly have a lot in common.  In particular,
these two random variables have the same {\em probability density
function}:

The {\em probability density function (pdf)} of a random variable $R$
is denoted $\text{PDF}_R$ and defined by:

\beqn
\text{PDF}_R(x) & = & \pr{R = x}
\eeqn

If we graph the probabiilty density functions for the random variables
$Q$ and $R$, we get something like this.  [Draw a binomial
distribution.  It is defined only on integral points, but put a curve
through those points to illustrate the shape.] This is called the {\em
binomial distribution}.

By studying properties of the binomial distribution, we can reach
conclusions about all random variables with this probability density
function-- and such random variables come up all the time!  For
example, what is the height of the graph at $x$?

\beqn
{\text PDF}_R(x)
    & = & \pr{R = x} \\
    & = & \frac{1}{2^n} \cdot \binom{n}{x}
\eeqn

\noindent This is the probability that an $n$-bit string contains $x$
1's and also the probability that we flip $x$ heads in $n$ tosses of a
fair coin.  One fact about the probability density function gives an
answer to multiple problems.

There's one other probability density function that we've already
encountered many times.  What does the probability density function
for a {\em uniform} random variable look like?  (horizontal line)

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

\end{document}
