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


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 Answer 1


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\ge0} ja_j} y^{\sum_{j\ge0} a_j} \prod_{j\ge0} \frac1{a_j!} \\ &= \sum_{a_1,a_2,\dots\ge0} \prod_{j\ge0} \frac{x^{ja_j} y^{a_j}}{a_j!} = \prod_{j\ge0} \sum_{a_j\ge0} \frac{x^{ja_j} y^{a_j}}{a_j!} \\ &= \prod_{j\ge0} \exp(x^jy) = \exp\bigg( \sum_{j\ge0} 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}. $$

  • 1
    $\begingroup$ Of course! Sir, you just made my day! :D $\endgroup$
    – Ziofil
    Sep 19, 2014 at 22:59
  • $\begingroup$ I'd like to practice and learn these tricks, could you point me in the right direction if I wanted to generalize this result to the case in which $G=\prod_{k=1}^La_k!$ with $L<n$? $\endgroup$
    – Ziofil
    Sep 19, 2014 at 23:12
  • 1
    $\begingroup$ I think that sort of truncated statistic is much harder to access with generating functions; I'd be inclined to try to understand it by induction on $L$. As for a source for generating functions, I recommend the excellent and capitvating book "Concrete Mathematics" by Graham, Knuth, and Patashnik. $\endgroup$ Sep 21, 2014 at 1:58
  • $\begingroup$ I got the book, it's really helpful. And I like the students comments on the side! Thanks again for the tip $\endgroup$
    – Ziofil
    Sep 23, 2014 at 23:18

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.