The thirtyfold way

Robert A. Proctor has written an article Let's Expand Rota's Twelvefold Way for Counting Partitions! I first learned about Rota's "Twelvefold Way" from Stanley's book Enumerative Combinatorics, where it concludes the first chapter; it's a set of twelve basic problems in counting partitions, compositions, etc., organized into a four-by-three table. Proctor's article expands the table to six by five. These are all problems of the sort "how many ways can we put n objects into k boxes", where the problems vary by how many objects are allowed in each box, whether the boxes or the objects are distinguishable or not, whether the order in which the boxes sit on our table or the order in which objects enter each box, and so on, matter. The objects in the table include certain classical objects (and classical sequences of numbers) like set partitions (Bell numbers), set partitions into a given number of parts (Stirling subset numbers), integer partitions (partition numbers), compositions (powers of two), and so on. Unfortunately there is quite a proliferation of idiosyncratic nomenclature for all of these objects; I'm not sure to what extent this can be avoided. (This isn't a complaint about Proctor's paper, but about the subject in general.)

The article has been submitted to the American Mathematical Monthly; as far as I can tell it hasn't been published there yet, and the tables of contents of future issues show that it wont be published by April 2008.

"Partition" is a bit problematic because it refers to both integer partitions and set partitions; furthermore it can refer to multiset partitions, which interpolate between the two, although not too many people seem to have thought hard about multiset partitions because there doesn't seem to be a nice way to compute those numbers. One can view an integer partition as a way of putting n black objects in unlabeled bins; one can view a set partition as a way of putting n all-different-colored objects in unlabeled bins. A mutliset partition is then a way of putting n objects, some of which have the same color, into unlabeled bins; we can associate the coloring of the balls with an integer partition. So, for example, with the integer partition 2 + 1 + 1 we associate the number of ways of putting four balls, two of which are red, one yellow, and one blue, into some bins. The ways of doing this can be written

R/R/G/B; RR/G/B; RG/R/B; RB/R/G; GB/R/R; RR/GB; RG/RB; RRG/B; RRB/G; RGB/R; RRGB

and there are eleven of these; this is intermediate between the number of integer partitions of 4, which is 5, and the number of set partitions of a set of four elements, which is the fourth Bell number, 15. I'll say that these multiset partitions are associated with the integer partition 2 + 1 + 1. I took to calling the numbers of partitions of a multiset Knuth numbers -- the name seems to be taken but I like it anyway -- and writing them as K(integer partition), so for example we'd have K(2,1,1) = 11, which is between K(4) = 5 (the partition number) and K(1,1,1,1) = 15 (the Bell number). At one point a few weeks ago I calculated some of the Knuth numbers and stared at them for a while, but couldn't really get anywhere; part of the problem is just that it's incredibly frustrating working with objects which are indexed by integer partitions! There are some nice cases, though; for example, multiset partitions associated with the integer partition (n-1) + 1 are, in the colored-ball interpretations, ways of putting n balls into indistinguishable boxes, where one of them is marked. This is the number of distinct parts of the partition λ, summed over all integer partitions λ of n. For example, partitions of the multiset RRRB, which contains one marked object, are

R/R/R/B; RR/R/B; RB/R/R; RR/RB; RRB/R; RRR/B; RRRB

of which there are seven. The integer partitions of 4 are 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1, which contain one, two, one, two, and one distinct parts respectively, for a total of seven. So K(3,1) = 7. If you stare at the numbers there's some sense of order -- as partitions of n get more parts the Knuth numbers get larger -- but it's hard to make out much order beyond that.

Another question comes to mind -- are there examples of tables like this where not all the entries are filled in? These would seem to be the more intriguing ones, since the challenge is then to fill in the missing entries; it reminds me of the Periodic Table from chemistry, which was invented when a large number of elements still hadn't been discovered, and properties of the elements that hadn't yet been found could be guessed quite reliable from properties of the surrounding elements.