The same number of distinct elements and ones in the partitions of the number.

37 Views Asked by At

For a given partition $\pi$ of the number $n$, let $A(\pi)$ denote the number of ones in $\pi$, and $B(\pi)$ the number of distinct parts in $\boldsymbol{\pi}$.
EXAMPLE: for the partition $\pi: 1+1+2+2+2+4$ we have $A(\pi)=2$ and $B(\pi)=3$.
Prove that $\sum_\pi A(\pi)=\sum_\pi B(\pi)$, where the summation is over all partitions of a fixed number $n$.

I know there is already a similar question, but the solution methods are a bit different, and I wanted to know if my approach is correct.

I tried to express each side of the identity using $P(k)$ which is the total number of partitions of the number $k$. $P(0)=1$
I got $$\sum_{\pi} A(\pi) = \sum_{i=1}^n i(P(n-i)-P(n-i-1))$$ where $i$ is the number of $1$'s in the partition, and $P(n-i)-P(n-i-1)$ is number of partitions, of the remaining number $n-i$, without $1$'s. For example, for $n = 6$ and $i = 2$, we have $(1+1)(P(4)-P(3)) = 2 \cdot 2 = 4$, which corresponds to number of $1$'s in $4+1+1$ and $2+2+1+1$.

Also $$\sum_{\pi} B(\pi) = \sum_{i=1}^n P(n-i)$$ where $P(n-i)$ is the number of partitions containing at least one $i$. For example, for $n = 6$ and $i = 3$, we have the partitions $3+3$ and $3+2+1$.

However, I haven't been able to show that these sums are equal, that is $$\sum_{i=1}^n i(P(n-i)-P(n-i-1)) = \sum_{i=1}^n P(n-i)$$

How can this be done?
Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

As @GerryMyerson wrote in the comment, the terms of the $\sum_{\pi} A(\pi) = \sum_{i=1}^n i(P(n-i)-P(n-i-1))$ cancel each other out, and one of each remains.