On multiplicity representations of integer partitions of fixed length

718 Views Asked by At

This is a follow-up question on the question computing length of integer partitions and it is loosely related with the paper "On a partition identity".

Let $\lambda$ be a partition of $n$, in the multiplicity representation $\lambda=(a_1,a_2,a_3,\dots)$ meaning that

$$n=\underbrace{1+1+\dots}_{a_1}+\underbrace{2+2+\dots}_{a_2}+\underbrace{3+3+\dots}_{a_3}+\dots$$

I can express $\lambda$ by drawing $a_k$ squares in the $k$-th row of a diagram (this is not the usual Ferrers or Young diagram), e.g. \begin{array}{cccc} a_1&\leftarrow&\square&\square&\square\\ a_2&\leftarrow\\ a_3&\leftarrow&\square&\square&\square&\square\\ a_4&\leftarrow&\square&\square\\ \vdots\\ a_n&\leftarrow&\\ \ &\ &\downarrow&\downarrow&\downarrow&\downarrow&\ &\downarrow\\ \ &\ &\mu_1&\mu_2&\mu_3&\mu_4&\cdots&\mu_n \end{array}

The $\mu_k$ numbers indicate how many squares there are in each column, so one can write the total number of squares $S$ (i.e. the length of the partition $\lambda$) in two ways: $S=\sum_ka_k=\sum_k\mu_k$. It is then very easy to show that the following holds:

$$ G[\lambda]:=\prod_{k=1}^n a_k!=\prod_{k=1}^n k^{\mu_k} $$

Now, there can be many partitions with the same length $S$, which one obtains by rearranging the squares in the diagram above whilst maintaining the number $n=\sum_k ka_k$ constant. So we can divide the set $\Lambda$ of all the partitions of $n$ into non-overlapping subsets $\Lambda_S$ of partitions of fixed length $S$, i.e. $\Lambda=\bigcup_S\Lambda_S$.

I would really like to be able to compute $$F(S)=\sum_{\lambda_i\in\Lambda_S}\frac{1}{G[\lambda_i]}$$

without resorting to the computation of all the partitions of $n$. Is there a way of doing this? Or, if it were not possible, is there a way of obtaining at least the list of the numbers $G[\lambda_i]$ with $\lambda_i\in\Lambda_S$?

1

There are 1 best solutions below

4
On BEST ANSWER

Generating functions to the rescue! We have a sum over all partitions $\lambda$ in the world: \begin{align*} \sum_{\lambda} \frac{x^{n(\lambda)} y^{S(\lambda)}}{G[\lambda]} &= \sum_{a_1,a_2,\dots\ge0} x^{\sum_{j\ge1} ja_j} y^{\sum_{j\ge1} a_j} \prod_{j\ge1} \frac1{a_j!} \\ &= \sum_{a_1,a_2,\dots\ge0} \prod_{j\ge1} \frac{x^{ja_j} y^{a_j}}{a_j!} = \prod_{j\ge1} \sum_{a_j\ge0} \frac{x^{ja_j} y^{a_j}}{a_j!} \\ &= \prod_{j\ge1} \exp(x^jy) = \exp\bigg( \sum_{j\ge1} x^jy \bigg) = \exp\bigg( \frac{xy}{1-x} \bigg). \end{align*} The sum of $1/G[\lambda]$ over all $\lambda$ with $n(\lambda)=n$ and $S(\lambda)=S$ is the coefficient of $x^ny^S$ in this series. Since \begin{align*} \exp\bigg( \frac{xy}{1-x} \bigg) &= \sum_{S\ge0} \frac1{S!} \bigg( \frac{xy}{1-x} \bigg)^S = \sum_{S\ge0} \frac{y^S}{S!} x^S (1-x)^{-S} \\ &= 1+\sum_{S\ge1} \frac{y^S}{S!} x^S \sum_{k\ge0} \binom k{S-1} x^{k - S + 1} \\ &= 1+\sum_{S\ge1} \frac{y^S}{S!} \sum_{n\ge 1} \binom{n-1}{S-1} x^n, \end{align*} we conclude that $$ F(S) = \frac1{S!} \binom{n-1}{S-1}. $$