How to prove $\prod_{\lambda\vdash n}\prod_im_i(\lambda)!=\prod_{\lambda\vdash n}1^{m_1(\lambda)}2^{m_2(\lambda)}\cdots$

Question

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.

Answer 1

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.