Stirling numbers of the second kind

Let us define a partition. Consider two integers, k, and greater or equal than 1. An n-partition of Ik is a set that is a non-ordered family of n. Non empty disjoint subset of Ik, whose union is Ik. That is, you split the elements of Ik into n boxes in such a way that no box remains empty. Here is, for instance, a 3 partition of a 7. It is formed by the family of sets 2 7, 1 4 5, and 3 6. And, of course, changing the order of these sets in the descriptions does not change the partition. Here, of course, the order does not count. This is because the boxes are indistinguishable. Now notice that partitions are not sharings.

Just to see the difference, consider a group of students. And we want to assign some students to a group A that goes to London, B that goes to New Delhi, say, and C to Tokyo. So distinguishable groups. What we obtain is a 3 sharing of the students from 1 to 14, without empty sets. Because we want somebody to go to London, or to New Delhi, or to Tokyo. Assuming, instead, that we want to subdivide the 14 students into 3 study groups. 3 non empty study groups. The study groups have no name. And what you obtain is a 3 partition of I14.

Now, the number of n partitions of Ik has a name. And it is what we call the Stirling number of second kind k over n. When n and k are integers greater or equal than 1. And it is easy to compute some of them. For instance, let k be greater than 1, then the Stirling number of second kind k over k equals 1. And this is just because there is just one k partition of Ik, which is the family of the sets of singletons 1, 2, 3, and k. Also, the Stirling number of second kind k over 1 equals 1. Because there is just 1 partition of Ik, which is just the partition formed by the set Ik itself.

Consider now, k greater or equal than 2, and we count the k minus 1 partitions of Ik. Now if you think in order to obtain a k minus 1 partition of Ik, so you have to subdivide Ik into k minus 1 subsets that are non empty. Well it turns out easily that there is, at most, one set which has strictly more than one element. And, naturally, it must have two elements. For instance, the partition of Ik even by the sets 1, 2, and singleton 3, 4, 5, k is a k minus 1 partition of Ik. And the other k minus 1 partition, so like that, single elements except one set with two elements.

So, such a partition is uniquely determined from the choice of the set of two elements. And such a set can be chosen in binomial k over two ways. So the Stirling number of second kind k over k minus 1 equals the binomial k over 2.

Now, how many ways can 14 students be partitioned into three non empty groups or sets? Well, the answer is Stirling number of second kind 14 over 3. Let’s count this number.

We want here to count the Stirling numbers of second kind k over n. So the n partitions of Ik, of course, there are no such partitions if n is 3 feet greater than k. So we assume that k is greater or equal than n. Well, it turns out that the Stirling number of second kind k over n equals the number of n sharings of Ik with non empty sets divided by factorial of n, which is 1 over factorial of n times the alternate sum of the binomial and over I times and minus I to the k as I varies from 0 to 10.

Let’s see why.

Consider the case of just computing the number of 4 partitions of I7. So we consider such a partition, and, actually, it arises from a full sharing of I7 into non empty sets. For instance, if we have 7 in a box. We have 7 and 2 in another box, 5 in another box, 4 and 1, and in another box 6 and 3. We can label the boxes and say that 7 to a [? ring ?] box number 1, 5 is in box number 2, 4 and 1 in box number 3, 6 and 3 in box number 4. But we can change the labour as we want.

And, for instance, we can obtain the same partition if we begin by labelling for the box that contains 2 and 7, and so on. And then we erase the labels. In how many ways can we change the labels of the four boxes while n factorial of 4 ways and to a partition so such a partition arises from factorial of 4 sharings with non empty sets?

Now we have such a correspondence between the 4 partitions of I7 and 4 sharings of I7 with non empty sets. And this correspondence is factorial of 4 to 1. So it is enough to apply the division principle, and we get the number of elements of the set y of the 4 partitions of I7 that equals the number of [INAUDIBLE] of I7 with non empty sets divided by factorial of 4. And this number of elements of x was computed in a previous unit. As an application, let us compute in how many ways we can partition a group of 14 students into three non empty groups. Well this is the Stirling number of second kind 14 over 3.

But now we know its value. Actually, it is 1 divided by factorial of 3 times the sum with alternating signs of binomial 3 over i times 3 minus i-14.

And so, what we get is 1 over factorial of 3 times 3 times 14 minus 3 times 2-14 plus 3. We simplify by 3, and we get a final result, which is 1 over 2 times 3-13 minus 2-14 plus 1.