Enumerative Combinatorics: Activities and Exercises

1. Set Partitions into Two Blocks.

Let \(n\) be a positive integer. Find a general formula for \(S(n,2)\text{,}\) the number of ways to partition the set \([n]\) into two blocks.

2. The Next Row of the Stirling Triangle.

Use the Stirling Recurrence

to find the \(n=6\) row of the Stirling triangle.

3. Balls and Boxes.

What balls-in-boxes problem is equivalent to partitions of \([n]\) into \(k\) parts? There are four decisions to make about the balls and boxes.

4. Another Stirling Recurrence.

Stirling numbers of the second kind satisfy the following identity \[ S(n+1,k) = \sum_{i=0}^n { n \choose i} S(n-i, k-1). \]

1. Use the Stirling triangle we made in class to verify the identity is true for \(n=4\) and \(k=3\text{.}\) Note that \(S(n,0)=0\) and \(S(n,k)=0\) when \(k>n\text{.}\)

2. Give a combinatorial proof of the identity. That is, explain why the LHS and the RHS count the exact same thing.

5. Sets of Functions.

Consider the set \({\cal F}\) of all functions \(f : [n] \rightarrow [k]\text{.}\) For each subset of \({\cal F}\) below, determine (i) which balls-in-boxes problem is equivalent to the subset (ii) any restrictions on \(n\) and \(k\text{,}\) and (iii) the formula for the size of the set (if we know it).

1. The set of all functions \(f: [n] \rightarrow [k]\)

2. The set of injections \(f: [n] \rightarrow [k]\)

3. The set of surjections \(f: [n] \rightarrow [k]\)

4. The set of bijections \(f: [n] \rightarrow [k]\)

6. Writing \(x^n\) as a combination of \((x)_k\)'s.

In this problem, you will prove the following cool formula for \(n \geq 0\text{:}\)

1. Recall that the set \(\R[x]\) of (finite) polynomials in \(x\) form a vector space over \(\R\text{.}\) Our typical basis for \(\R[x]\) is:

   \begin{equation*} 1, x, x^2, \ldots, x^k, \ldots. \end{equation*}

   Explain why another basis for \(\R[x]\) is:

   \begin{equation*} 1, (x)_1, (x)_2, (x)_3, \ldots, (x)_k, \ldots. \end{equation*}

   Just give an intuitive explanation (not a rigorous proof).

2. Give a combinatorial proof that

   \begin{equation*} m^n = \sum_{k=0}^n S(n,k) (m)_k. \end{equation*}

   In particular, both sides count the number of ways to assign \(n\) students to \(m\) classrooms where some classrooms can be empty. Explain.

3. Fixing \(n\text{,}\) now consider the polynomial equation

   \begin{equation*} x^n - \sum_{k=0}^n S(n,k) (x)_k= 0. \end{equation*}

   Explain why part (b) shows that this equation has an infinite number of solutions. Then conclude that the LHS must in fact be the zero polynomial, so

   \begin{equation*} x^n = \sum_{k=0}^n S(n,k) (x)_k. \end{equation*}