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

2. The Next Row of the Stirling Triangle.

Use the Stirling Recurrence

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

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

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{.}\) Solution.

   \begin{equation*} \begin{array}{rcl} S(5,3) &=& {4 \choose 0} S(4,2) + {4 \choose 1} S(3,2) + {4 \choose 2} S(2,2) + {4 \choose 3} S(1,2) + {4 \choose 4} S(0,2) \\ &=& 1 \cdot 7 + 4 \cdot 3 + 6 \cdot 1 + 4 \cdot 0 + 1 \cdot 0 \, = \, 25. \end{array} \end{equation*}

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

   • LHS: The number of ways to partition \([n+1]\) into \(k\) parts.

   • RHS: Counts the same set, grouping the partitions according to the number of elements of \([n]\) that occur in the set with element \(n+1\text{.}\) Fix \(i\text{.}\) We count the number of partitions of \([n+1]\) where the element \(n+1\) is in a set with \(i\) elements. We choose our set in two phases.

     • Phase 1: Choose the \(i\) elements to appear in the set with element \(n+1\text{.}\) This can be done in \({n \choose i}\) ways.

     • Phase 2: Partition the remaining \(n-i\) elements into \(k-1\) sets. This can be done in \(S(n-i,k-1)\)

     Now we sum over all possible values of \(i\text{,}\) namely \(0 \leq i \leq n\text{.}\)

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]\) Solution.

   • distinct balls

   • distinct boxes

   • repetition allowed

   • boxes can be empty

   Number of ways: \(k^n\text{,}\) with no restrictions on \(n\) and \(k\text{.}\)

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

   • distinct balls

   • distinct boxes

   • repetition not allowed

   • boxes can be empty

   Number of ways: \((k)_n\) and we must have \(k \geq n\text{.}\)

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

   • distinct balls

   • distinct boxes

   • repetition allowed

   • boxes cannot be empty

   Number of ways: \(k! \cdot S(n,k)\) (see if you can explain why!) and we must have \(k \leq n\text{.}\)

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

   • distinct balls

   • distinct boxes

   • repetition not allowed

   • boxes cannot be empty

   Number of ways: \(k!\) and we must have \(k = n\text{.}\)

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). Solution.

   The set of falling factorial polynomials are:

   \begin{equation*} \begin{array}{ccccc} 1, & (x)_1 = x, &(x)_2 = x(x-1)= x^2 - x, & (x)_3 = x(x-1)(x-2) = x^3 -3x^2 + 2x, & \ldots \end{array} \end{equation*}

   For each \(k \geq 0\text{,}\) we have one polynomial of degree \(k\text{.}\) So this will end up being a basis of \(\R[x]\text{.}\)

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

   RHS:

   • Each of the \(n\) students has her choice of \(m\) classrooms. So the total number of ways is \(m^n\text{.}\)

   LHS:

   • First, pick the number \(k\) of classrooms that will be used

   • Next, split the students into \(k\) nonempty groups. This can be done in \(S(n,k)\) ways.

   • Now, assign each group to a different classroom. This can be done in \((m)_k\) ways.

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*}

   Solution.

   Let \(p(x) = \displaystyle{x^n - \sum_{k=0}^n S(n,k) (x)_k}.\) Part (b) says that \(p(x)= 0\) for \(x=1,2,3, \ldots, m, \ldots\text{.}\) In other words, this polynomial has an infinite number roots. The only such polynomial is the zero polynomial. Therefore,

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

   Our conclusion is: when the polynomial \(x^n\) is expressed in terms of the falling factorial basis \(1, (x)_1, (x)_2, (x)_3, \ldots, (x)_k, \ldots\text{,}\) then the coefficient for basis element \((x)_k\) is \(S(n,k)\text{.}\)