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 223=122 \cdot 2 \cdot 3 = 12 cases.

All cases are shown and numbered in this table:

balls per urn unrestricted ≤ 1 ≥ 1
n labeled balls, m labeled urns (1) (5) (9)
n unlabeled balls, m labeled urns (2) (6) (10)
n labeled balls, m unlabeled urns (3) (7) (11)
n unlabeled balls, m 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 Ck(m,n)C_k(m,n) for mm urns, nn balls, for each case k=1,2,,12k = 1, 2, \ldots, 12.

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,

C7(m,n)=C8(m,n)=1,nm.C_7(m,n) = C_8(m,n) = 1, \quad n \leq m.

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 nn balls choose among all mm urns, leading to

C1(m,n)=mn.C_1(m,n) = m^n.

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 mm urns to choose from for the first ball, m1m-1 for the second, m2m-2 for the third, leading to

C5(m,n)=m(m1)(mn+1)=m!(mn)!,nm,C_5(m,n) = m (m-1) \cdots (m-n+1) = \frac{m!}{(m-n)!}, \quad n \leq m,

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 nn urns, how many of the permutations have the balls placed in exactly these urns? The answer is the number of ways to arrange/permute nn things, namely n!n!, so we simply divide by this number and arrive at

C6(m,n)=m!(mn)!n!=(mn),nm,C_6(m,n) = \frac{m!}{(m-n)! n!} = {m \choose n}, \quad n \leq m,

the number of n-combinations of m things and (mn){m \choose n} is a binomial coefficient. Let us now introduce the number uk,k=1,,nu_k, k=1, \ldots, n as the urn number that ball k goes into. Using this notation we see that the number of nn-combinations of mm things just considered is equivalent to the number of tuples (u1,u2,,un)(u_1, u_2, \ldots, u_n) that fulfill

1u1<u2<u3<<unm.1 \leq u_1 < u_2 < u_3 < \cdots < u_n \leq m.

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 (u1,u2,,un)(u_1, u_2, \ldots, u_n) that fulfill

1u1u2u3unm1 \leq u_1 \leq u_2 \leq u_3 \leq \cdots \leq u_n \leq m

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

1u1<u2+1<u3+2<<un+n1m+n1,1 \leq u_1 < u_2 + 1 < u_3 + 2 < \cdots < u_n + n - 1 \leq m + n - 1,

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

C2(m,n)=(m+n1n).C_2(m,n) = {m+n-1 \choose n}.

Set Partitions (3, 9, 11)

Let us first consider Case 11 where the nn balls are labeled, the mm 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, …, nn} into mm disjoint subsets whose union is the whole set. This is called the number of (set) partitions of {1, 2, …, nn} into m parts,

C11(m,n)={nm},nm1.C_{11}(m,n) = \left\{ {n \atop m} \right\}, \quad n \geq m \geq 1.

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

{nn}={n1}=1,n1,and{nm}=0,m>n>0,\left\{ {n \atop n} \right\} = \left\{ {n \atop 1} \right\} = 1, \quad n \geq 1, \quad \text{and} \quad \left\{ {n \atop m} \right\} = 0, \quad m > n > 0,

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

{00}=1and{n0}=0,n1.\left\{ {0 \atop 0} \right\} = 1 \quad \text{and} \quad \left\{ {n \atop 0} \right\} = 0, \quad n \geq 1.

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

{nm}={n1m1}+m{n1m},n>m>1.\left\{ {n \atop m} \right\} = \left\{ {n-1 \atop m-1} \right\} + m \left\{ {n-1 \atop m} \right\}, \quad n > m > 1.

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 m!m! permutations of the parts for each set partition of Case 11, so

C9(m,n)=m!{nm},nm1.C_9(m,n) = m! \left\{ {n \atop m} \right\}, \quad n \geq m \geq 1.

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, …, mm urns,

C3(m,n)=k=1m{nk}.C_3(m,n) = \sum_{k=1}^m \left\{ {n \atop k} \right\}.

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,


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

C10(m,n)=(n1m1),nm.C_{10}(m,n) = {n-1 \choose m-1}, \quad n \geq m.

The example above illustrates that 8=2+1+3+28=2+1+3+2 and is called a composition of the integer 8 into 4 parts. So enumerating the ways to place nn unlabeled balls in mm 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 nn unlabeled balls, mm 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 nn as a sum of mm 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

C12(m,n)=nmC_{12}(m,n) = \left| {n \atop m} \right|

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

nn=n1=1,n1,andnm=0,m>n>0,\left| {n \atop n} \right| = \left| {n \atop 1} \right| = 1, \quad n \geq 1, \quad \text{and} \quad \left| {n \atop m} \right| = 0, \quad m > n > 0,

and the boundary conditions

00=1andn0=0,n1.\left| {0 \atop 0} \right| = 1 \quad \text{and} \quad \left| {n \atop 0} \right| = 0, \quad n \geq 1.

In the general case of partitioning nn into mm 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 nn-1 into mm-1 parts, where a 1 could added to each arrangement, and the second type can be obtaining by listing all partitions of nn-mm into mm parts, where 1 could be added to each part. We thus have

nm=n1m1+nmm,n>m>1.\left| {n \atop m} \right| = \left| {n-1 \atop m-1} \right| + \left| {n-m \atop m} \right|, \quad n > m > 1.

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 1,2,,m1, 2, \ldots, m urns,

C4(m,n)=k=1mnk.C_4(m,n) = \sum_{k=1}^m \left| {n \atop k} \right|.

Final remarks

All twelve case can be summarized in the following table:

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

This table also appears in Section of The Art of Computer Programming, Volume 4A 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.