Stirling Numbers (of the first and second kind) are famous in combinatorics. There are well known recursive formulas for them, and they can be expressed through generating functions. Below we mention and explain the recursive definitions of the Stirling numbers through combinatorial ideas.

Since the Stirling numbers of the second kind are more intuitive, we will start with them.

Stirling Numbers of the Second Kind

Suppose you have n different objects labeled 1,2,3,\cdots , n. You also have k identical boxes so you cannot order them, or differentiate between them. The question is: in how many ways can you put these n different objects into these k identical boxes? You cannot leave an empty box. Let’s say the solution is s(n,k). What are the values of s(n,k) for different n and k? These numbers, namely s(n,k), are called the Stirling numbers of the second kind.

Now think about it. Lets start by observing the n^{\text{th}} object. No matter how you throw n different objects into k identical boxes, you will end up in one of the two following scenarios:

(1) The n^{\text{th}} object is all alone in some box.

(2) The box containing the n^{\text{th}} object also contains one or more objects.

Consider case (1). If we delete the  n^{\text{th}} object along with the box, it is evident that the rest of the objects (there are n-1 of them) were arranged in the rest of the boxes (there are k-1 of them). In other words, number of ways we could end up in case (1) is s(n-1,k-1).

Now consider case (2). This time, let’s delete only the n^{\text{th}} object but leave the box and the neighbors as they were. If we want to put the deleted object back into the mix, where do we put it? Boxes are identical and each contains at least one of the elements 1,2,3,\cdots, n-1. Looks like we could put the n^{\text{th}} object back into any of the boxes and the resulting configuration will still be in case (2). Since there are exactly k ways of putting the n^{\text{th}} object back into any of the k boxes, number of ways of generating a configuration of case (2) is k\times s(n-1,k).

Since there are no other cases, we have

s(n,k) = s(n-1,k-1) + k\times s(n-1,k)

The numbers s(n,k) are called the Stirling numbers of the second kind, which essentially tells us (now you see) the number of ways n different objects can be arranged into k identical boxes such that no box is left empty.

You can see Wikipedia for closed form solution and other properties of the Stirling number of the second kind.

Stirling Numbers of the First Kind

The combinatorial idea of the Stirling numbers of the first kind is similar to the previous case, except that now the ordering of the objects inside each box matters.

Suppose you have n numbers 1,2,3,\cdots, n. Let us consider the following permutation of these numbers when n = 9:

value:   | 3 | 1 | 5 | 6 | 7 | 4 | 2 | 8| 9 |
----------------------------------------------
position:| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8| 9 |

Now let’s find cycles. We observe that

— position 1 contains 3
position 3 contains 5,
position 5 contains 7,
position 7 contains 2,
position 2 contains 1 (cycle of length 5)

— position 4 contains 6,
position 6 contains 4 (cycle of length 2)

— position 8 contains 8 (cycle of length 1)

— position 9 contains 9 (cycle of length 1)

In other words, there are 4 cycles in the above permutation:

(35721)(64)(8) (9)

Now we are ready to ask the following question:  in how many ways can you arrange the numbers 1,2,3,\cdots, n so that you end up with exactly k cycles? Suppose the answer to this question is c(n,k). What are the values of c(n,k) for different n and k? As you have guessed it, the numbers c(n,k) are indeed the Stirling numbers of the first kind.

So how can we derive a recursive relation for it? We will go back to our objects-and-boxes analogy. We want to throw n different objects into exactly k identical boxes such that elements inside any given box form a cycle. How many ways to do it? Like before, all admissible permutations of n objects fall into one of two cases:

(1) The number n is forms a cycle by itself.

(2) The number n is part of a larger cycle.

In case (1), the number of ways we can end up here is the same as arranging the rest n-1 numbers “properly” into k-1 cycles. Therefore, there are c(n-1,k-1) different ways of arranging n numbers into k cycles so that they all fall in case (1).

In case (2), once again we delete the  n^{\text{th}} number without touching other elements in its cycle. After we deleted n, observe that the rest of the numbers 1,2,\cdots, n-1 are already arranged in k cycles, which can be done in c(n-1,k) ways. So how many ways could we have deleted n? Observe that this number, n, could have appreared before any of the existing n-1 numbers, so there were n-1 ways we could have deleted n from the permutation.  Therefore, there are (n-1)\times c(n-1,k) different ways of arranging n numbers into k cycles so that they all fall in case (2).

Since there are no other cases, we have

c(n,k) = c(n-1,k-1) +(n-1)\times c(n-1,k)

The numbers c(n,k) are called the Stirling numbers of the second kind, which essentially tell us (now you see) the number of  partitions of integer n, each having exactly k cycles.

You can see Wikipedia for closed form solution and other properties of the Stirling numbers of the second kind.

Advertisements