Exercise 1.21

Question

Define $\left\{\begin{array}{l}n \ k\end{array}ight\}$ as the number of ways to partition $\{1,2, \ldots, n\}$ into $k$ nonempty subsets, or the number of ways to have $n$ students split up into $k$ groups such that each group has at least one student. For example, $\left\{\begin{array}{l}4 \ 2\end{array}ight\}=7$ because we have the following possibilities.
\begin{itemize}
\item $\{1\},\{2,3,4\}$
\item $\{2\},\{1,3,4\}$
\item $\{1,2\},\{3,4\}$
\item $\{3\},\{1,2,4\}$
\item $\{1,3\},\{2,4\}$
\item $\{4\},\{1,2,3\}$
\item $\{1,4\},\{2,3\}$
\end{itemize}
Prove the following identities:
\begin{enumerate}[label=(\alph*)]
\item 
$$
\left\{\begin{array}{c}
n+1 \
k
\end{array}ight\}=\left\{\begin{array}{c}
n \
k-1
\end{array}ight\}+k\left\{\begin{array}{l}
n \
k
\end{array}ight\}
$$
Hint: I'm either in a group by myself or I'm not.
\item 
$$
\sum_{j=k}^{n}\left(\begin{array}{l}
n \
j
\end{array}ight)\left\{\begin{array}{l}
j \
k
\end{array}ight\}=\left\{\begin{array}{l}
n+1 \
k+1
\end{array}ight\}
$$
Hint: First decide how many people are not going to be in my group.
\end{enumerate}

fifthist x · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item Case 1: If Tony is in a group by himself, then we have to break the 
remaining $n$ people into $k-1$ groups. This can be done in 
  $$
  \left\{
    \begin{array}{cc}
        n\
        k-1
    \end{array}
  ight\}
  $$
  ways.
  
  Case 2: If Tony is not in a group by himself, then we first break up the 
  remaining $n$ people into $k$ groups. Then, Tony can join any of them. 
  The number of possible groups then is
  $$
  k\left\{
    \begin{array}{cc}
        n\
        k
    \end{array}
  ight\}
  $$
  
  Case 1 and 2 together count the number of ways to break up $n+1$ people into 
  $k$ non empty groups, which is precisely what the left side of the equation counts.

\item   Say Tony wants to have $m$ in his group. That is to say he does not want 
$n-m$ people. These $n-m$ people must then be broken into $k$ groups. 
  
  The number of people Tony wants to join his group can range from $0$ to $n-k$. 
  The reason for the upper bound is that at least $k$ people are required to 
  make up the remaining $k$ groups.
  
  Taking the sum over the number of people in Tony's group we get
  $$\sum_{j=0}^{n-k}{n \choose j}\left\{
    \begin{array}{cc}
        n-j\
        k
    \end{array}
  ight\}
  $$
  
  Now, instead of taking the sum over the number of people Tony wants in his 
  group, we can equivalently take the sum over the number of people Tony does 
  not want in his group. Hence,
  
  $$\sum_{j=0}^{n-k}{n \choose j}\left\{
      \begin{array}{cc}
          n-j\
          k
      \end{array}
    ight\} = \sum_{i=n}^{k}{n \choose i}\left\{
      \begin{array}{cc}
          i\
          k
      \end{array}
    ight\}
  $$
Since the sum counts all possible ways to group $n+1$ people into $k+1$ groups, 
we have 
$$
\sum_{i=n}^{k}{n \choose i}\left\{
      \begin{array}{cc}
          i\
          k
      \end{array}
    ight\} = 
    \left\{
      \begin{array}{cc}
          n+1\
          k+1
      \end{array}
    ight\}
$$
as desired.

\end{enumerate}

Exercise 1.21

Answers

Comments

Exercise 1.21

Answers

Comments

Add answer