Three Ways to Skin a Combinatorics Problem

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.

-Yan

Posted in Algebra, Combinatorics, Representation Theory | Tags: Combinatorics, generating functions, Representation Theory, young tableaux

Responses

Here is a reference to this problem and the bijective proof: http://www.jstor.org/pss/2323477
By: PS on March 17, 2010
at 6:01 AM

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

Cancel

Connecting to %s

Concrete Nonsense