Activity272
Use the recursion to find the 6th row of the triangle.
Section3.4Stirling Numbers of the Second Kind
¶Let's take a closer look at the Stirling numbers, first introduced in Section 3.1. Recall, we use the notation \(S(k,n)\) to stand for the number of partitions of a \(k\) element set with \(n\) blocks. Here is a brief summary of what we have already discovered.
Directly from the definition, we see that \(S(k,1) = 1\) and \(S(k,k) = 1\text{.}\) From these we can compute the remaining Stirling numbers using the recursion
\begin{equation*}
S(k,n) = nS(k-1,n) + S(k-1, n-1).
\end{equation*}
This recursion is justified by dividing the partitions of \([k]\) into those which contain \(k\) as a singleton set (there are \(S(k-1, n-1)\) of these) and those that don't (there are \(n\) choices for where \(k\) could for each of the \(S(k-1, n)\) partitions of \([k-1]\) into \(n\) blocks).
From this, we generated Stirling's second triangle.
| 1 | ||||||||
| 1 | 1 | |||||||
| 1 | 3 | 1 | ||||||
| 1 | 7 | 6 | 1 | |||||
| 1 | 15 | 25 | 10 | 1 |
In the remainder of this section we will look at ways to compute Stirling numbers directly, and some consequences of the formulas we find.
Subsection3.4.1Formulas for Stirling Numbers (of the second kind)
¶While we might not have a nice closed formula for all Stirling numbers in terms of \(k\) and \(n\text{,}\) we can give closed formulas for those Stirling numbers close to the edges of the triangle. We have already considered some of these in Activity 198. To get back into the right mindset, start by reproving one of these.
Activity273
Prove \(S(k, k-1) = \binom{k}{2}\text{.}\)
Hint
What are the possible sizes of parts?
The proof of the formula above suggests that looking at the sizes of the blocks might be helpful. Let's see what this might look like with an example.
Activity274
How many ways are there to partition \([5]\) into three sets?
(a)
How many partitions of \([5]\) have two blocks of size 1 and one block of size 3?
(b)
How many partitions of \([5]\) have one block of size 1 and two of size 2?
Hint
Careful here. The answer is NOT \(\binom{4}{2}\binom{4}{2}\text{.}\) Do you see why?
(c)
Are there any other types of partitions we need to consider? What is \(S(5,3)\text{?}\)
(d)
Generalize! Find a formula for \(S(k, k-2)\text{.}\)
(e)
A friend tells you that \(S(k,k-2) = \binom{k}{3} + 3 \binom{k}{4}\text{.}\) Prove this is correct also. If this is the formula you found for the previous part, see the hint.
Hint
If you found this formula for \(S(k,k-2)\) in part (e), then pretend your friend claims that \(S(k, k-2) = \binom{k}{3} + \frac{1}{2}\binom{k}{2}\binom{k-2}{2}\) and prove why that is correct too.
Whenever we want to partition \(k\) items in \(n\) blocks, we can consider cases. We will represent each type of case with a type vector consisting of a sequence \((a_1, a_2, \ldots, a_k)\) where each \(a_i\) is the number of blocks that have size \(i\text{.}\) For example, in partitioning \([5]\) into 3 blocks, the previous activity first asked for the number of partitions with type vector \((2,0,1,0,0)\text{,}\) two blocks of size 1 and one of size 3, and then for the number of partitions with type vector \((1,2,0,0,0)\text{,}\) one block of size 1 and two of size 2. Note that \(\sum_{i=1}^k a_i = n\) and \(\sum_{i=1}^k ia_i = k\text{.}\)
Activity275
(a)
How many partitions of \([6]\) are there into 3 blocks? List all the type vectors and the number of partitions for each.
(b)
Generalize to find a formula for \(S(k,k-3)\text{.}\) Then clean up the formula so it is a linear combination of \(\binom{k}{4}\text{,}\) \(\binom{k}{5}\text{,}\) and \(\binom{k}{6}\text{.}\)
Hint
While you might not get this formula by conisdering type vectors, you should be shooting to prove \(S(k, k-3) = \binom{k}{4} + 10 \binom{k}{5} + 16 \binom{k}{6}\)
Activity276
In how many ways can we partition \(k\) items into \(n\) blocks so that we have \(a_i\) blocks of size \(i\) for each \(i\text{?}\) That is, given the type vector \((a_1, a_2, \ldots, a_k)\text{,}\) how many partitions of \([k]\) into \(n\) blocks have that type vector.
Hint
Suppose we make a list of the \(k\) items. We take the first \(a_1\) elements to be the blocks of size 1. How many elements do we need to take to get \(a_2\) blocks of size two? Which elements does it make sense to choose for this purpose?
Activity277
Describe how to compute \(S(k,n)\) in terms of quantities given by the formula you found in Activity 276.
Activity278
Explain why \(S(k, 2) = 2^{k-1} - 1\text{.}\) Then find another expression for \(S(k,2)\) using type vectors to establish an interesting identity.
Interlude: Multinomial Coefficients
Recall that the Stirling numbers counted the number of ways to distribute 9 distinct sandwiches to three identical sandwich bags. This suggests a more realistic question.
Activity279
In how many ways may the caterer distribute the nine sandwiches into three identical bags so that each bag gets exactly three? Answer this question.
Hint
What if the question asked about six sandwiches and two distinct bags? How does having identical bags change the answer?
Activity280
In how many ways can the sandwiches of Activity 279 be placed into distinct bags so that each bag gets exactly three?
This is an example of a multinomial coefficient. Although these are not directly related to Stirling numbers, we can use the ideas of type vectors to investigate them. Let's do that now.
Activity281
In how many ways may we label the elements of a \(k\)-element set with \(n\) distinct labels (numbered 1 through \(n\)) so that label \(i\) is used \(j_i\) times? (If we think of the labels as \(y_1, y_2, \ldots, y_n\text{,}\) then we can rephrase this question as follows. How many functions are there from a \(k\)-element set \(K\) to a set \(N=\{y_1,y_2,\ldots y_n\}\) so that \(y_i\) is the image of \(j_i\) elements of \(K\text{?}\)) This number is called a multinomial coefficient and denoted by
\begin{equation*}
\binom{k}{j_1,j_2,\ldots, j_n}.
\end{equation*}
Activity282
Explain how to compute the number of functions from a \(k\)-element set \(K\) to an \(n\)-element set \(N\) by using multinomial coefficients.
Hint
The sum principle will help here.
Activity283
Explain how to compute the number of functions from a \(k\)-element set \(K\) onto an \(n\)-element set \(N\) by using multinomial coefficients.
Hint
How are the relevant \(j_i\)'s in the multinomial coefficients you use here different from the \(j_i\)'s in the previous problem.
Activity284
What do multinomial coefficients have to do with expanding the \(k\)th power of a multinomial \(x_1+x_2+\cdots+x_n\text{?}\) This result is called the multinomial theorem.
Hint
Think about how binomial coefficients relate to expanding a power of a binomial and note that the binomial coefficient \(\binom{n}{k}\) and the multinomial coefficient \(\binom{n}{k,n-k}\) are the same.
Subsection3.4.2Identities with Stirling Numbers
¶The entries in the Pascal Triangle, \(\binom{n}{k}\text{,}\) satisfy the nice recursion \(\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}\) and also have a closed formula: \(\binom{n}{k} = \frac{n!}{k!(n - k)!}\text{.}\) Activity 200 gives us a recursion for the Stirling numbers \(S(n,k)\) and, unfortunately, the best we can do for a “closed” formula is the following. 8 This is not really a closed formula since the number of terms in the summation is not fixed.
Theorem3.4.1
\begin{equation*}
S(k,n) = \frac{1}{n!}\left[n^{k} - \binom{n}{1} \left( n - 1 \right)^{k} + \binom{n}{2} \left( n - 2 \right)^{k} - \ldots + \left( - 1 \right)^{n - 1}\binom{n}{n - 1} 1^{k} \right]
\end{equation*}
Activity285
Prove Theorem 3.4.1
Hint
First multiply both sides by \(n!\) and then prove that identity. You might have already done so in Activity 231
Activity286
What does Theorem 3.4.1 tell us about \(S(k, 2)\) (which we already know)? What do we get for \(S(k,3)\text{?}\)
Here is another result identity involving Stirling numbers.
Theorem3.4.2
\(x^{k} = S\left(k,1 \right)x + S\left(k,2 \right)x\left( x - 1 \right) + S\left(k,3 \right)x\left( x - 1 \right)\left( x - 2 \right) + \cdots + S\left(k,k \right)x\left( x - 1 \right)\cdots(x -k + 1)\)
Activity287
Prove Theorem 3.4.2
Hint
You have already done this as well, although not with \(x\text{.}\)
It is in this form that James Stirling originally developed these numbers. \(S(k,n)\) is used to convert from powers to binomial coefficients as shown in the following:
Theorem3.4.3
\(x^{k} = S\left(k,1 \right)\binom{x}{1}1! + S\left(k,2 \right) \binom{x}{2}2! + \ldots + S\left(k,k \right)\binom{k}{k} k!\)
Activity288
Prove Theorem 3.4.3
The remainder of this section contains some additional activities related to the identities above and Stirling numbers in general.
Activity289
List the sequence of elements that are row sums of the Stirling Triangle.
Activity290
How many subsets \(\{a,b,c\}\) are there of \(\{2,3,4,\ldots\}\) such that \(abc = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17\text{?}\)
Activity291
Let \(S = \{2,3,4,\ldots\}\text{.}\) How many ordered triples \((a,b,c)\) are there in \(S\times S \times S\) such that \(abc = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17\text{?}\)
Activity292
Express \(x^3\) as suggested in Theorem 3.4.2. Also, multiply your answer out to verify.
Activity293
Use your results in Activity 292 to express \(x^3\) as a linear combination of the binomial coefficients \(\binom{x}{1}\text{,}\) \(\binom{x}{2}\text{,}\) and \(\binom{x}{3}\text{.}\)
Activity294
Determine the following:
(a)
\(a, b, c\) so that \(n^4 = 24\binom{n}{4} + 6a\binom{n}{3}+2b\binom{n}{2} + c \binom{n}{1}\text{.}\)
(b)
\(a, b, c, d\) so that \(n^5 = 5!\binom{n}{5} + a\binom{n}{4} + b\binom{n}{3} + c \binom{n}{2} + d \binom{n}{1}\text{.}\)
Activity295
Express \(1^4 + 2^4 + 3^4 + \cdots + n^4\) as a polynomial in \(n\text{.}\)
Activity296
Why is \(4^n - 4\cdot 3^n + 6\cdot 2^n - 4\) always divisible by 24?