Stirling numbers tell you how many ways there are to parition a set of n items into k parts. We write a Stirling number like this: {

n

k

}

For example, {

3

2

} = 3 since the following 3 partitions are all the partitions of {1,2,3} into 2 parts:

Note that {

3

1

} = 1 (because the only partition is1,2,3), and {

3

3

} = 1 (because the only partition is1 | 2 | 3).

To take a more non-trivial example, {

4

2

} = 7. Here are the partitions:

Now let's deal with base cases and edge cases. {

n

n

} = 1 for all n, since we can put each number into its own part and end up with a partition of size n.

How about {

n

0

} and {

n

1

}? Well, for any positive number n, {

n

1

} = 1 since with just one part in our partition, we have no choice but to put all our numbers in that part. Similarly, {

n

0

} = 0, since we have to put the numbers somewhere, but in a partition with no parts, there's nowhere to put them! There's something funny about zero here, though. You'll note that I was careful to specify above that n was a positive number. In the case of n = 0, the set of numbers that we have to partition is empty: {} Therefore, {

0

0

} = 1 since the partition of 0 parts does a fine job of paritioning 0 items (and there's only a single partition of 0 parts). Meanwhile, {

0

1

} = 0 since each part of the partition has to be non-empty, but we have nothing to put into that part when there are 0 items. So what we end up with is a chart of Stirling numbers with this unusual left column, that starts out as a 1, and becomes all zeros afterwards:

There's a simple rule that lets us fill out this table arbitrarily far. The rule is:

So for example, this formula tells us that {

7

3

} = 3{

6

3

} + {

6

2

} = 3×90 + 31 = 301. Can we see why this must be true? Start with a partition of n+1 items that has k parts. We'll call this a (n+1, k) partition for short. Look at item n+1 and ask how we can make this partition by adding that item to a smaller partiton. If it was in a part of its own, then we can start with a (n, k−1) partition and add one more part to the partition containing only item n+1, which increments the number of parts. Otherwise, if it shared a part with other items, we can start with a (n, k) partition, and add that item to one of the existing parts. This doesn't change the number of parts, and there are k parts, and thus k options for how to do this. Add together these two ways of constructing a (n+1, k) partition, and we get our formula.

Stirling numbers also have an interesting connection to derivatives. Consider the operator x

d

dx

. Let's see what happens when we apply this operator many times to the function e

x

The coefficient of x

k

e

x

is simply {

n

k

} after applying the operator n times. With a bit of thought, we can see that using the product rule to differentiate, and then multiplying by x has the same effect as using the table formula above.

We can also just write down the bare operator, and we still get Stirling numbers:

Stirling numbers have a few nice formulas and identities, some of which we'll now prove:

The proof of this is fairly simple: with n−1 parts to the partition, each item needs to have its own part, except that exactly one of the parts can hold 2 items. There are (

n

2

) = 

n(n−1)

2

choices (a triangular number) for which two items should go in that part, and therefore, {

n

n−1

} = 

n(n−1)

2

.

We can carry out a similar kind of reasoning for {

n

n−2

}. Now, we have two more items than we have parts, so there are 2 cases. Firstly, perhaps there are two parts that each have two items (and all other parts have one item). In this case, the count is (

n

4

)

( 4 2 )

2

 = 

n(n−1)(n−2)(n−3)

8

since we first pick 4 items to be contained in these two parts, then pick two items to be in the first part (the items in the second part are then fixed by elimination), then divide by 2 since the order of the 2 parts doesn't matter. Secondly, perhaps there is a single part that has 3 items (and all other parts have one item). In this case, the count is (

n

3

) = 

n(n−1)(n−2)

6

since we're just picking the 3 items to appear in that part. So overall, the formula should be the sum of these two cases:

For example, taking n = 7 we get {

7

5

} = 

(7)(6)(5)

2

(

1

3

+

4

4

) = 140

Recall the falling factorial identity:

x!

(x−3)!

 = x(x−1)(x−2) Or in general:

x!

(x−k)!

 = x(x−1)(x−2)...(x+1−k) It turns out that the following identity is true for Stirling numbers:

To see if this is plausible, let's take the simple example of n = 3. Then:

Next with n = 4

To handle the general proof, we'll first note that

d k

dx k

t

x

 = 

x!

(x−k)!

t

x−k

. So, by the identity we produced above:

Second, we note that t

d

dt

 t

x

 = t x t

x−1

 = x t

x

. Therefore:

This gives the desired result:

An interesting property of binomial coefficients (a.k.a. the numbers in Pascal's triangle) is that p ∣ (

p

k

) for prime p and 0 < k < p. (In case you're wondering what that vertical line means, in this context it means that (

p

k

) is a multiple of p, and it can be read as "divides".) Looking at the table of Stirling numbers, it seems like a similar property holds for them. I.e. p ∣ {

p

k

} for prime p and 1 < k < p. Can we prove it?

Ignore for a moment the exact number of numbers in a partition, and instead consider the size of the parts of that partition. This kind of "undiscriminating partition" can be written in the form of a Young diagram. This is what it looks like for a partition of 8 items, with 1 part of size 3, 2 parts of size 2, and 1 part of size 1:

Now we can ask the question: How many "discriminating" partitions (the kind counted by Stirling numbers) can we build from this Young diagram? Start with a permutation of 8 items, the number of squares in the diagram, there are 8! such permutations. Write numbers into the squares in the order fixed by the permutation. This determines which partition we get. But there could be multiple ways to get the same partition. The ordering of the items inside each part of the partition doesn't matter, so we divide out by the appropriate factorial for each part. Now we're down to

8!

3!2!2!1!

. But we're still not done! There's no difference between the two parts of size 2, and so if we swap all the items in each of them, we still get the same partition. So we're still overcounting, and have to divide out by all the ways to rearrange parts of the same size. In our case, that's 1!2!1! where we're being pedantic and counting 1 way to rearrage the parts of size 3 and parts of size 1. If we were being really pedantic, we'd add a bunch of 0! factors to account for rearrangements of all the parts of sizes 4 through 8. Overall, we're left with:

We can generalize the same argument. For any given diagram d containing n squares, the formula is:

Now we can write down a formula for Stirling numbers in terms of diagrams:

Now if n = p is a prime, then we can deduce the following for any given n-square diagram of k parts:

1. p ∣ p!

2. If k > 1 then p ∤ 

∏

row r∈d

 |r|! since when there are multiple rows, each row must have less than p items in it, since rows must be non-empty. Thus, the product cannot contain any factors of p

3. If k < p then p ∤ 

n

∏

s=1

 (

∑

row r∈d

[|r| = s])! since the sum is bounded above by k. Thus, the product cannot contain any factors of p

4. Therefore, by the above 3 points: p ∣ #(d) (so long as 1 < k < p)

From this we can conclude: