07c-binomialcoeff3.tex

\include{commons}
\lecturetitle{Lecture 7c: Binomial Coefficients (3)} 

\begin{frame}\frametitle{The binomial coefficients\footnote{This lecture mostly follows Chapter 3 of [LPV].}}
  In this lecture, we discuss advanced counting with binomial
  coefficients.
\end{frame}

\begin{frame}\frametitle{More on counting}
  We shall see more techniques for counting when we consider the
  following problems.
  \begin{itemize}
  \item How many anagrams does the word ``KASETSARTUNIVERSITY'' have?
    (They do not have to be real English words.)
  \item How can you give out $n$ different presents to $k$ students
    when student $i$ has to get $n_i$ pieces of presents?
  \item How many ways can you distribute $n$ baht coins to $k$
    children?
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{Easy anagrams}
  \begin{itemize}
  \item An anagram of a particular word is a word that uses the same
    set of alphabets.  For example, the anagrams of $ADD$ are $ADD$,
    $DAD$, and $DDA$. \pause
  \item How many anagrams does ``$ABCD$'' have? \pause
    \begin{itemize}
    \item $4!$, because every permutation of A B C or D is a different
      anagram. \pause
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{Harder anagrams}
  \begin{itemize}
  \item How many anagrams does ``$ABCC$'' have? Is it $4!$ ? \pause
    \begin{itemize}
    \item This time we have to be careful because the answer of $4!$
      is too large as it over counts many anagrams, i.e., it
      ``distinguishes'' the two $C$'s. \pause
    \item Let's try to be concrete. How many times does ``$CABC$'' get
      counted in $4!$? \pause
    \item If we treat two $C$'s differently as $C_1$ and $C_2$, we can
      see that $CABC$ is counted twice as $C_1ABC_2$ and $C_2ABC_1$.
      This is true for any anagram of $ABCC$.  \pause
    \item Since each anagram is counted in $4!$ twice, the number of
      anagrams is $4! / 2 = 4\cdot 3 = 12$.
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{General anagrams}
  \begin{tcolorbox}
    Let's try to use the same approach to count the anagram of
    $HELLOWORLD$. (It has 3 $L$'s, 2 $O$'s, $H$, $E$, $W$, $R$, and
    $D$.)
  \end{tcolorbox}
  
  \pause
  \vspace{0.2in}
  
  The number of permutation of alphabets in $HELLOWORLD$, treating
  each character differently is $10!$.  However, each anagram is
  counted for $3!2!$ times because of the 3 copies of $L$ and the 2
  copies of $O$.  Therefore, the number of anagrams is
  \[
  \frac{10!}{3!2!}.
  \]
\end{frame}

\begin{frame}\frametitle{Distributing presents}
  \begin{tcolorbox}
    I have $9$ different presents.  I want to give them to $3$
    students: A, B, and C.  I want to give each student $3$ presents.
    In how many ways can I do it?
  \end{tcolorbox}
  
  \pause

  {\small
    \begin{itemize}
    \item Let's think about the process of distributing the
      presents. \pause We can first let A choose $3$ presents, then B
      chooses the next $3$ presents, and C chooses the last $3$
      presents. \pause If we distinguish the order which each child
      chooses the presents, then there are $9!$ ways. \pause However, in
      this case, we consider the distribution of presents, i.e., we
      consider the set of presents each child gets. \pause
    \item To see how many times each distribution is counted in the $9!$
      ways, we can let children form a line and let each child permute
      his or her presents.  Each child has $3!$ choices.  Thus, one
      distribution appears $3!3!3!$ times. \pause
    \item Thus, the number of ways we can distribute presents is
      \[ 
      \frac{9!}{3!3!3!}
      \]
    \end{itemize}
  }
\end{frame}

\begin{frame}\frametitle{Another way to look at the present distribution}
  \begin{itemize}
  \item Let's look closely at a particular present distribution in the
    previous question.  Let $\{1,2,\ldots,9\}$ be the set of presents.
  \item Consider the case where A gets $\{1,3,8\}$, B gets
    $\{2,4,6\}$, and C gets $\{5,7,9\}$. \pause
  \item Another way to look at this distribution is to fix the order
    of the presents and see who gets each of the presents.  Thus, the
    previous distribution is represented in the following table:
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
      Presents & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline
      Children & A & B & A & B & C & B & C & A & C
    \end{tabular}
  \item \pause This is essentially an anagram problem.  You can think
    of one particular way of present distribution as anagram of
    AAABBBCCC.  Thus, we reach the same solution of
    \[\frac{9!}{3!3!3!}.\]
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{Distributing identical presents}
  \begin{tcolorbox}
    Now suppose that I have $9$ identical presents.  I want to give
    them to $3$ students: A, B, and C.  I want to give each student
    $3$ presents.  In how many ways can I do it?
  \end{tcolorbox}
  \begin{itemize}
  \item Note that when we state that the presents are identical, we
    mean that we do not distinguish them, i.e., the first present and
    the second present are indistinguishable.
  \end{itemize}
  \vspace{1in}
\end{frame}

\begin{frame}\frametitle{Distributing coins (1)}
  \begin{tcolorbox}
    I have $9$ identical coins.  I want to give them to $3$ students:
    A, B, and C.  In how many ways can I do it so that each student
    gets at least one coin?
  \end{tcolorbox}

  \begin{itemize}
  \item Let's first try to organize the distribution of coins.  \pause
    We place all 9 coins in a line.  We let the first student picks
    some coin, then the second student, then the last one. \pause
  \item Since each coin is identical, we can let the first student
    picks the coin from the beginning of the line.  Then the second
    one pick the next set of coins, and so on. \pause
  \item One possible distribution is
    \[
    \underbrace{o o}_{1} \underbrace{o o o o}_{2} \underbrace{o o o}_{3}
    \]
    \pause
  \item In how many ways can we do that?
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{Distributing coins (2)}
  The example below provides us with a hint on how to count.
  \[
  \underbrace{o o}_{1} \underbrace{o o o o}_{2} \underbrace{o o o}_{3}
  \]
  \pause

  Since all coins are identical, what matters are where the first
  student and the second student stop picking the coins. \pause
  I.e, the previous example can be depicted as
  \[
  o o | o o o o | o o o
  \]

  Thus, in how many ways can we do that? \pause
  
  Since there are 8 places we can mark starting points, and
  there are 2 starting points we have to place, then there are
  $\binom{8}{2}$ ways to do so. \pause

  This is a fairly surprising use of binomial coefficients.
\end{frame}

\begin{frame}\frametitle{Distributing coins (3)}
  Let's consider a general problem where we have $n$ identical coins
  to give out to $k$ students so that each student gets at least one
  coin.  In how many ways can we do that?

  \pause Since there are $n-1$ places between $n$ coins and we need to
  place $k-1$ starting points, there are $\binom{n-1}{k-1}$ ways to do
  so.

  \pause
  \begin{tcolorbox}
    There are $\binom{n-1}{k-1}$ ways to distribute $n$ identical
    coins to $k$ children so that each child get at least one coin.
  \end{tcolorbox}
\end{frame}

\begin{frame}\frametitle{Distributing coins (4)}
  \begin{tcolorbox}
    I have $9$ indentical coins.  I want to give them to $3$ students:
    A, B, and C.  In how many ways can I do it, given that some
    student may not get any coins?
  \end{tcolorbox}
  
  \vspace{1.5in}
\end{frame}