A cousin of the Matryoshka problem is the single problem with several different solutions. Occasionally, one tantrums when I I try to dress it up in Matryoshka form by making variations and coercing a poset structure. This is such a problem.
Take the set of all partitions of . For each partition , let be the product of the parts of and let be the product of the factorials of the multiplicities of each length in . For example, if , then and . Prove that .
Richard Stanley gave this as an exercise in class. Ricky Liu pointed out to me that this was a generalization of a USAMO 1986 problem and has the following pretty combinatorial solution:
We’re going to prove a stronger statement: for each , the number of times appears as a part over is equal to the number of times a multiplicity number of size at least appears in . For example, if , then for the partitions respectively, appears times and the number of times a multiplicity of size at least one (which is just the number of parts of distinct size) are . Checking this statement for all gives the desired statement (the special case for is the USAMO problem).
To do this, consider the following graph, with the partitions as the vertices. For each partition with multiplicity numbers , create directed edges as follows: each corresponds to a rectangle of parts of length . Consider the partitions created by flipping the sub rectangle consisting of of the corresponding parts and draw a directed edge to each of these partitions. For example, will then point to . Now, if we label each edge by the length of the rectangle its flip corresponds to, then each part of size corresponds to a edge labeled by . Then, how many edges with label point to a vertex? If the vertex has elements of size , then we could have gotten there by a flip if , so we get exactly one edge for each multiplicity at least , and we’re done.
Direct, pretty, doesn’t invoke machinery, uselessly ungeneralizable, all standard traits of elementary combinatorial proofs; the first two traits satisfying but the latter two lacking. After some searching, I came across an attack on the original USAMO problem by Phelpedo (the blog seems to be down at present) with generating functions. I’ve noticed a paradigm of tableaux combinatorics is that it lends itself well to generating functions; this is, as my limited knowledge suggests, mostly due to the fact that the partition function doesn’t behave very nicely as a numerical function, but its generating function does. Here’s his proof, generalized for our current problem with minimal effort on my part:
Consider the generating function for the partition function, modified at the piece corresponding to parts of size :
Note that in the resulting sum, the coefficient of will count the number of parts of size used, summed over all the partitions of size . But the modified piece is just , so we really just have the generating function for the partitions, multiplied by a factor .
But what is this counting? For the coefficient of , we’re summing over the coefficients of in the original generating function for partitions. This means our desired count is the sum of the partition numbers , which I claim is the same as the number of parts which repeat at least times. This is because the number of times that appears at least times in a partition is exactly via the obvious bijection that adds / removes parts of size .
Finally, while doing some research on representation theory, Anatoly Preygel and I recognized that for a partition , where counts the number of elements of in the conjugacy class labeled by . This leads to a third proof, involving some (rudimentary) knowledge of symmetric functions:
Consider the conjugacy matrix of , rows indexed by the irreducible representations and the columns indexed by the conjugacy classes. Then (nothing special about yet, just elementary character theory. By the way, I’m very surprised I haven’t seen this elementary algebra fact until now; it was a fun short exercise). We can also write this as . For example, for , ordering the partitions left-to-right and up-to-down we get , which has determinant .
However, there is another basis of the character table, namely corresponding to the induced representations from the trivial representations on the Young subgroups of . These are also indexed by the partitions as well, and correspond to the basis of homogeneous symmetric functions (whereas the ‘s correspond to the basis of the Schur symmetric functions). The change of basis is upper-triangular with diagonal 1 (equivalently, the Kostka numbers are 1 if and 0 if in the standard ordering), so the determinant is preserved. But in this basis, the resulting matrix is itself triangular with diagonal equal to the . In our example, the resulting matrix is
The easiest way to see the triangularity is to see what we are doing in the symmetric functions world as opposed to the characters world. Here, our matrix elements express in terms of , which is equivalent to expressing in terms of because the and are dual and is self-dual with a factor of . It is well-known (check, for example, Enumerative Combinatorics 2, Corrollary 7.7.2) that these coefficients are just . So , which gives us the desired equality.
Take care, everyone.