Posted by: yanzhang | February 16, 2010

Three Ways to Skin a Combinatorics Problem

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 S of all partitions of n. For each partition \lambda, let A(\lambda) be the product of the parts of \lambda and let B(\lambda) be the product of the factorials of the multiplicities of each length in \lambda. For example, if \lambda = (5, 5, 2, 2, 2), then A(\lambda) = 5^2 2^3 = 200 and B(\lambda) = 3! 2! = 12. Prove that \prod_{\lambda \in S} A(\lambda) = \prod_{\lambda \in S} B(\lambda).

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 k, the number of times k appears as a part over S is equal to the number of times a multiplicity number of size at least k appears in S. For example, if n = 3, = 1, then for the partitions (3), (2, 1), (1, 1, 1) respectively, 1 appears 0, 1, 3 times and the number of times a multiplicity of size at least one (which is just the number of parts of distinct size) are 1, 2, 1. Checking this statement for all k gives the desired statement (the special case for k = 1 is the USAMO problem).

To do this, consider the following graph, with the partitions as the vertices. For each partition \lambda with multiplicity numbers m_1, m_2, \ldots m_t, create \sum m_i directed edges as follows: each i corresponds to a m_i * g(i) rectangle of parts of length g(i). Consider the m_i partitions created by flipping the sub rectangle consisting of j * g(i) of the corresponding parts and draw a directed edge to each of these partitions. For example, (3, 2, 2, 2) will then point to (2, 2, 2, 1, 1 ,1), (3, 2, 2, 1, 1), (3, 2, 2, 2), (3, 3, 3). Now, if we label each edge by the length of the rectangle its flip corresponds to, then each part of size k corresponds to a edge labeled by k. Then, how many edges with label k point to a vertex? If the vertex has m_i elements of size g(i), then we could have gotten there by a flip if m_i \geq k, so we get exactly one edge for each multiplicity at least k, 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 P(x) for the partition function, modified at the piece corresponding to parts of size k:

(1 + x + x^2 + \ldots) (1 + x^2 + x^4 + \ldots) \ldots (x^k + 2 x^{2k} + 3 x^{3k} + \ldots) \ldots

Note that in the resulting sum, the coefficient of x^n will count the number of parts of size k used, summed over all the partitions of size n. But the modified piece is just x^k (1 + x^k + x^{2k} + \ldots)^2, so we really just have the generating function P(x) for the partitions, multiplied by a factor (x^k + x^{2k} + \ldots).

But what is this counting? For the coefficient of x^n, we’re summing over the coefficients of x^{n-k}, x^{n-2k}, \ldots in the original generating function for partitions.  This means our desired count is the sum of the partition numbers p(n-k), p(n-2k), \ldots, which I claim is the same as the number of parts which repeat at least k times. This is because the number of times that m appears at least k times in a partition is exactly p(n-mk) via the obvious bijection that adds / removes k parts of size m.

Finally, while doing some research on representation theory, Anatoly Preygel and I recognized that for a partition z_\lambda = A(\lambda) B(\lambda), where n!/z_\lambda counts the number of elements of S_n in the conjugacy class labeled by \lambda. This leads to a third proof, involving some (rudimentary) knowledge of symmetric functions:

Consider the conjugacy matrix M of S_n, rows indexed by the irreducible representations \chi^\lambda and the columns indexed by the conjugacy classes. Then |\det(M)| = \sqrt{\prod_\lambda z_\lambda} (nothing special about S_n 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 \sqrt{\prod_\lambda A(\lambda)B(\lambda)}. For example, for S_3, ordering the partitions left-to-right and up-to-down (1)(1)(1), (2)(1), (3) we get \begin{pmatrix} 1 & -1 & 1 \\ 2 & 0 & -1 \\ 1 & 1 & 1 \end{pmatrix}, which has determinant 6.

However, there is another basis of the character table, namely corresponding to the induced representations from the trivial representations on the Young subgroups of S_n. These are also indexed by the partitions as well, and correspond to the basis h_\lambda of homogeneous symmetric functions (whereas the \chi^\lambda‘s correspond to the basis s_\lambda of the Schur symmetric functions). The change of basis is upper-triangular with diagonal 1 (equivalently, the Kostka numbers K_{\lambda \mu} are 1 if \lambda = \mu and 0 if \lambda < \mu in the standard ordering), so the determinant is preserved. But in this basis, the resulting matrix is itself triangular with diagonal equal to the B(\lambda). In our S_3 example, the resulting matrix is \begin{pmatrix} 6 & 0 & 0 \\ 3 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix}.

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  h_\lambda in terms of p_\lambda/z_\lambda, which is equivalent to expressing p_\lambda in terms of m_\lambda because the h_\lambda and m_\lambda are dual and p_\lambda is self-dual with a factor of z_\lambda^{-1}. It is well-known (check, for example, Enumerative Combinatorics 2, Corrollary 7.7.2) that these coefficients are just B(\lambda).  So \sqrt{\prod_\lambda A(\lambda)B(\lambda)} = \prod_\lambda B(\lambda), which gives us the desired equality.

Take care, everyone.




  1. Here is a reference to this problem and the bijective proof:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: