7
$\begingroup$

Let $\lambda$ be a partition of an positive integer $n$, it can be presented as $\lambda=(\lambda_{1},\lambda_2,\cdots,\lambda_l)$ such that $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_l>0$, or $\lambda=(1^{m_1},2^{m_2},\cdots,k^{m_k})$, here $m_i$ is the number of times that the part $i$ appears in the partition $\lambda$. Apparently, in this question, we use the second form.

how to prove $$\prod\limits_{\lambda\vdash n}\prod\limits_im_i(\lambda)!=\prod\limits_{\lambda\vdash n}1^{m_1(\lambda)}2^{m_2(\lambda)}\cdots$$ It is clear that the right side of the identity is the product of all parts of all partitions of $n$.

I have seen this problem in Enumerative Combinatorics, Vol.2 of R.P.Stanley, Chapter 7, Symmetric Functions,Section 7.6, An Involution. And any combinatorial interpretation is more expected.

$\endgroup$
  • $\begingroup$ The left hand side, looks like something you might get from taking a coefficient of say $x_1x_2\cdots x_n$ in the sum of all Schur polynomials of degree $n$ expanded in monomial basis, and the right hand side, a similar thing but expanded in the power-sum symmetric basis. en.wikipedia.org/wiki/Schur_polynomial $\endgroup$ – Per Alexandersson Oct 19 '15 at 13:30
  • 2
    $\begingroup$ Write the terms of each product on the left-hand side inside the Young/Ferrers diagram for $\lambda$ and meditate on the result. $\endgroup$ – Ben Barber Oct 19 '15 at 14:35
  • 6
    $\begingroup$ See Enumerative Combinatorics, vol. 1, 2nd ed., Exercise 1.80. (Incidentally, I don't understand the comment of Ben Barber.) $\endgroup$ – Richard Stanley Oct 19 '15 at 16:41
  • $\begingroup$ @RichardStanley I'm afraid at this point, neither do I. $\endgroup$ – Ben Barber Oct 19 '15 at 17:37
1
$\begingroup$

Here is a literal interpretation and proof of the formula using $n=7$ as an example.

We begin with the 15 partitions of $7$:

$$(*)\,\,7, 61, 52, 511, 43, 421, 4111, 331, 322, 3211, 31111, 2221, 22111, 211111, 1111111$$

The left hand side of the formula enumerates by group size, so that each partition of $(*)$ in turn represents:

$$(+)\,\,1, 1, 11, 12, 11, 111, 13, 21, 12, 112, 14, 31, 23, 15, 7$$

and then in the formula each part is turned into a factorial, so the process is, for example,

$$22111\to23\to2!3!$$

The right hand side of the formula counts the number of times each part is used in total over all the partitions of $n$. In our example $(*)$ this is:

$$1^{30},2^{11}, 3^6, 4^3, 5^2, 6^1, 7^1$$

To relate the two representations, take each part from the LHS $(+)$ and write $k,\dots,1$. Count the number of occurrences of each part, and we have the count we get from the right hand side.

In reverse, write the parts from our RHS as descending chains and then read the top of each tower to give the group sizes of $(*)$.

Or, the total number of parts of $k$ over all partitions of $n$ (i.e. in $(*)$) is equal to the number of groups size $\ge k$ (in $(+)$).

For example, the total number of $k=4$'s from $n=7$ is $3$, and we have three groups of size $4$ or greater: $4,5,7$.

A useful feature of this is that the count of $1$'s is equal to the total number of groupings in $(+)$, in this case there are 30.

We can write $\lambda=(1^{m_1},2^{m_2},\cdots,k^{m_k})$ with $|\lambda|=\sum_\limits{m_i\ge 1} 1$.

So the original formula can be written as:

$$\sum_{\lambda\vdash n} |\lambda| = \sum_{\lambda\vdash n} m_1(\lambda)$$

and, in general, $|\lambda|_k=\sum_\limits{m_i\ge k} 1$.

$$\sum_{\lambda\vdash n} |\lambda|_k = \sum_{\lambda\vdash n} m_k(\lambda)$$

We can now read a partition in two ways, for example:

$$1^{m_1},2^{m_2},\cdots,k^{m_k}$$

means we could have $m_2$ 2's, or a set of 2 parts $m_2$.

Enumerating into sets of exactly $k$ parts involves the term:

$$\sum_{\lambda\vdash n} \left(|\lambda|_k-|\lambda|_{k+1}\right)$$

and this term telescopes on addition to give the result.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.