janmr blog

Twelve Ways of Counting

I have for a long time had an ambition of getting better at combinatorics, especially enumerative combinatorics, the discipline of counting the number of arrangements, given some pattern.

Getting introduced to The Twelvefold Way was a real eye-opener in this regard. It is a way to categorize some fundamental combinatorial counting problems by considering different ways of putting balls into urns. Different setups arise depending on whether the balls are labeled or unlabeled, whether the urns are labeled or unlabeled, and whether each urn can contain any number of balls, at most one or at least one, leading to cases.

All cases are shown and numbered in this table:

balls per urn unrestricted
labeled balls, labeled urns (1) (5) (9)
unlabeled balls, labeled urns (2) (6) (10)
labeled balls, unlabeled urns (3) (7) (11)
unlabeled balls, unlabeled urns (4) (8) (12)

I will now consider each one. Not row- or columnwise, but in a rather thematic way. The number of arrangements will be denoted for urns, balls, for each case .

The Trivial (7, 8)

When the urns are unlabeled and a maximum of one ball may be put in each urn, the answer is trivial. Different ways of placing the balls can not be distinguished since the urns are unlabeled, so there is only one way to do it,

The Usual Suspects (1, 2, 5, 6)

If both the urns and the balls are labeled and there is no restriction on the number of balls in each urn (Case 1), we can for each of the balls choose among all urns, leading to

This is equivalent to counting n-tuples of m things, where each element of the tuple corresponds to an urn, and the value of that element corresponds to the number of the ball that goes into that urn. (Note that here, and in all the following cases, different orderings of the balls within each urn are not distinguished.)

If, however, there can be at most one ball in each urn (Case 5), we can not place each ball as we please. We have urns to choose from for the first ball, for the second, for the third, leading to

which is called the number of n-permutations of m things. We now remove the labels from the balls (Case 6). So where exchanging two balls in the setup just considered would lead to a different arrangement, it is no longer. For any choice of urns, how many of the permutations have the balls placed in exactly these urns? The answer is the number of ways to arrange/permute things, namely , so we simply divide by this number and arrive at

the number of n-combinations of m things and is a binomial coefficient. Let us now introduce the number as the urn number that ball k goes into. Using this notation we see that the number of -combinations of things just considered is equivalent to the number of tuples that fulfill

This will come in handy when we turn to Case 2, where we allow any number of balls in each urn—but we still do not distinguish exchanging two balls between two urns. Using the notation just introduced we are thus interested in the number tuples that fulfill

But any less than or equal to can easily be transformed into strictly less than when considering integers,

and we have now transformed the enumeration problem for n-multicombinations of m things into an equivalent -combinations of things enumeration problem, so

Set Partitions (3, 9, 11)

Let us first consider Case 11 where the balls are labeled, the urns are unlabeled, and each urn must contain at least one ball. We first observe that the number of arrangements for this case is equivalent to splitting the set {1, 2, …, } into disjoint subsets whose union is the whole set. This is called the number of (set) partitions of {1, 2, …, } into m parts,

where this curly bracket notation denote the Stirling numbers of the second kind. But this is just answering a question by posing another question. It is easy to see that

and for completeness we define the (agreed-upon) boundary cases

Imagine now that we want to list the set partitions of {1, 2, …, } into parts, , using an inductive/recursive approach. First we list the arrangements that contain the one-element set as one of the parts. This can be done by listing the set partitions of {1, 2, …, } into parts and simply adding to each arrangement. We then list the set partitions of {1, 2, …, } into parts. For each of these arrangements, we can add the element to each of the parts. We thereby list all the arrangements where the part containing the element contains at least one other element. Together with the border cases above, we now have the recursive definition

Case 9 is similar to the one just considered, except the urns are now labeled. This means that if we swap the contents of any two urns, we have a new arrangement. And since all the parts are different (they are disjoint subsets), we have to count all permutations of the parts for each set partition of Case 11, so

We now go to Case 3 where the balls are labeled and the urns are unlabeled, like Case 11, but where any number of urns may be empty. So we can simply use the counting of Case 11 and add the results of using exactly 1, 2, …, urns,

You can read more about Sterling numbers in, e.g., Concrete Mathematics by Graham, Knuth, and Patashnik.

Integer Compositions (10)

If unlabeled balls have to be placed in labeled urns with at least one ball in each urn, we can visualize an arrangement like this,

OO|O|OOO|OO,

meaning 2 balls in the first urn, 1 in the second, 3 in the third, and 2 in the fourth urn (=4 and =8 in this example). So counting the arrangements for Case 10 is equivalent to counting how many ways we can place -1 seperators, "|", among the -1 places in between the O's, leading to

The example above illustrates that and is called a composition of the integer 8 into 4 parts. So enumerating the ways to place unlabeled balls in labeled urns with at least one ball in each urn is equivalent to counting the compositions of the integer m into n parts.

Integer Partitions (4, 12)

Case 12 has unlabeled balls, unlabeled urns and each urn must contain at least one ball. This is similar to Case 10 just considered, except for the labeling of the urns. So we need to count the ways to write the integer as a sum of positive integers, but where the ordering of the parts does not matter. Each such arrangement is called a partition of n into m parts. We use the notation

for the number of partitions of into parts. As we did for set partitions, we will seek a recursively defined expression. We see that

and the boundary conditions

In the general case of partitioning into parts, we can split the partitions into those that have at least one 1 among the parts, and those where each part is greater than 1. The first type can be obtained by listing all partitions of -1 into -1 parts, where a 1 could added to each arrangement, and the second type can be obtaining by listing all partitions of - into parts, where 1 could be added to each part. We thus have

Finally for Case 4, with reasoning similar to that of set partitioning (Case 3), when the urns are unlabeled and any urn is allowed to be empty, it is equivalent to adding the counts for non-empty urns for urns,

Final remarks

All twelve case can be summarized in the following table:

balls per urn unrestricted
labeled balls, labeled urns -tuples of things -permutations of things Set partitions of {1, …, } into ordered parts
unlabeled balls, labeled urns -multicombinations of things -combinations of things Compositions of into parts
labeled balls, unlabeled urns Set partitions of {1, …, } into ≤ parts pigeons into holes Set partitions of {1, …, } into parts
unlabeled balls, unlabeled urns Partitions of into ≤ parts pigeons into holes Partitions of into parts

This table also appears in in Section 7.2.1.4, Fascicle 3, Volume 4 of The Art of Computer Programming by Donald E. Knuth where The Twelvefold Way is briefly mentioned. The Twelvefold Way is originally treated in the book Enumerative Combinatorics, Volume 1 by Richard P. Stanley.