Why is the sum of multiplicity lengths the same as the cumulative sum of partitions up to the previous integer?

54 Views Asked by At

Let $\lambda$ be a partition of $N$ ($\lambda\vdash N$). In the multiplicity representation, $\lambda=(a_{1},a_{2},\ldots a_{m(\lambda)})$, such that $$\sum_{k=1}^{m(\lambda)}{ka_{k}}=N,$$ where $m(\lambda)$ is the largest $k$ with $a_k>0$ within $\lambda$.

Heuristically, I've found that $$\sum_{\lambda \vdash N}s(\lambda)=\sum_{n=0}^{N-1}p(n),$$ where $s(\lambda)$ is the number of non-zero $a_k$ within $\lambda$, and $p(n)$ is the number of partitions of integer $n$.

Is there a formal proof, or better yet, an intuitive understanding of this identity?

I'd also appreciate any suggestions to improve the terminology I used so I can find the appropriate resources on my own in the future.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose that $1\le n\le N$; $k$ is a part of a partition $\lambda$ of $N$ if and only if the rest of $\lambda$ is a partition of $N-k$. Conversely, every partition $\mu$ of $N-k$ can be extended to a partition of $N$ with a part $k$. Note that even if $k$ is also a part of $\mu$, $\mu$ can be extended to a unique partition of $N$ with a part $k$. Thus, there is one partition of $N$ with a part $k$ for each partition of $N-k$. It follows that the number of partitions of $N$ in which $a_k\ne 0$ is $p(N-k)$ and hence that

$$\sum_{\lambda\vdash N}s(\lambda)=\sum_{k=1}^Np(N-k)=\sum_{n=0}^{N-1}p(n)\,.$$