Main Applications Identities History FAQ Algorithms

What are the Stirling numbers of the first and second kind?

                                       
In Concrete Mathematics, the authors use the symbols and  to indicate the Stirling numbers of the first and second kinds, named for 18th Century mathematician James Stirling (1692-1770). Just as we say “n choose k” to refer to binomial coefficients, the authors of Concrete Mathematics recommend the phrases “n cycle k” to the first kind Stirling numbers and “n subset k” to refer to the second kind Stirling numbers.

                                                                Combinatorial explanations

Stirling numbers of the second kind   or “n subset k”
Just as in Concrete Mathematics, we will talk about the second kind of Stirling numbers first because the question is a little simpler. Usually, the curly brackets {} refer to sets in math, so using these brackets for the Stirling numbers of the second kind is a good mnemonic. The question answered by  is “how many ways are there to split up a set with n elements into k non-empty subsets?”

For example,  let’s show why . The set {1,2,3,4} can split into two non-empty subsets in the following ways.
1. {1,2,3} and {4}
2. {1,2,4} and {3}
3. {1,3,4} and {2}
4. {2,3,4} and {1}
5. {1,2} and {3,4}
6. {1,3} and {2,4}
7. {1,4} and {2,3}

By standard convention   for all k > 0. Here are the first few rows of the Stirling’s triangle for subsets.
           

n=0	1
n=1	0	1
n=2	0	1	1
n=3	0	1	3	1
n=4	0	1	7	6	1
n=5	0	1	15	25	10	1
n=6	0	1	31	90	65	15	1

One pattern we see emerge from the first rows of this matrix is = 2^n-1-1.  Another pattern which is also present in the Stirling numbers of the first kind will be mentioned below.

 Stirling numbers of the first kind  or “n cycle k”

The question answered by   is “how many ways are there to split up n objects into k cycles”. Like in the first part, we split the n elements into subsets, but now a subset of more than two elements can be represented as a cycle in several ways. For example, the set {1,2,3} can be permuted six ways, but in cycles we “wrap around” from front to back and starting from any position is considered the same cycle. On the other hand, going backwards is a different cycle when we have more than two elements.

For three elements, here are the two cycles.
1. [1,2,3] = [2,3,1] = [3,1,2]
2. [1,3,2] = [3,2,1] = [2,1,3]

        Here are the first few rows of the Stirling triangle for cycles.

n=0	1
n=1	0	1
n=2	0	1	1
n=3	0	2	3	1
n=4	0	6	11	6	1
n=5	0	24	50	35	10	1
n=6	0	120	274	225	85	15	1

As we can see, the sums of the n^th row of the subset triangle is n! and the first column  = (n-1)! for all n > 0; also since one element or two element sets can only be written one way as a cycle, we have that and .