For every partition $\pi$ of a fixed integer $n$, $\sum{F(\pi)}=\sum{G(\pi)}$

Question

I need to prove the following question.

For every partition $\pi$ of a fixed integer $n$, define $F(\pi)$=number of occurrences of 1 as a summand, and $G(\pi)$=no. of distinct summands in the partition. Prove that $\sum{F(\pi)}=\sum{G(\pi)}$.

I was trying to solve this taking an example of 5 with Ferrers graph but not getting how to prove it.

Answer 1

The following proof uses ordinary generating functions (bivariate). The partition generating function where ones are marked is $$Q_1(z, u) = \frac{1}{1-uz} \prod_{k\ge 2} \frac{1}{1-z^k}.$$ If we want to sum the occurrences of one as a summand for all partitions of $n$ we need to compute $$\left.\frac{d}{du} Q_1(z, u) \right|_{u=1} = \left. -1\times \frac{1}{(1-uz)^2} \times -z \times \prod_{k\ge 2} \frac{1}{1-z^k} \right|_{u=1} = \frac{z}{1-z} \prod_{k\ge 1} \frac{1}{1-z^k}.$$ On the other hand, marking distinct summands looks like this: $$Q_2(z,u) = \prod_{k\ge 1}\left(1 + u z^k + u z^{2k} + u z^{3k} + \cdots\right).$$ Once more differentiating and setting $u=1$ gives this time $$\left.\frac{d}{du} Q_2(z, u) \right|_{u=1} = \left.\prod_{k\ge 1}\left(1 + u z^k + u z^{2k} + u z^{3k} + \cdots\right) \times \sum_{k\ge 1} \frac{z^k + z^{2k} + z^{3k} + \cdots} {1 + u z^k + u z^{2k} + u z^{3k} + \cdots}\right|_{u=1} \\= \prod_{k\ge 1}\frac{1}{1-z^k} \sum_{k\ge 1} \frac{z^k/(1-z^k)}{1/(1-z^k)} = \prod_{k\ge 1}\frac{1}{1-z^k} \sum_{k\ge 1} z^k = \frac{z}{1-z} \prod_{k\ge 1}\frac{1}{1-z^k}.$$ The two generating functions are exactly the same, QED.

There are similar computations at this MSE link I and this MSE link II.

Answer 2

A counting argument attributed to Richard Stanley appears here.

Briefly, it goes like this:

$$\displaystyle\sum_{\pi\,\vdash n} {F(\pi)}=\displaystyle\sum_{i=1}^n p(n-i)\textrm,$$

because $p(n-i)$ is the number of partitions of $n$ with at least $i$ ones. The sum counts the number of partitions with $k$ ones $k$ times: once in $p(n-1)$, once in $p(n-2)$, and so on up to one final time in $p(n-k)$.

Then $\displaystyle\sum{G(\pi)}$ is shown to be the same thing by a clever observation.

Let $True(P)$ have value $1$ if $P$ is true and $0$ if $P$ is false, and let $H(i)$ be the number of partitions of $n$ that contain (at least one) $i$. Then

$$\sum_{\pi\,\vdash n}{G(\pi)}=\sum_{\pi\,\vdash n}\sum_{i=1}^nTrue\left(\pi \textrm{ contains an }i \right) = \sum_{i=1}^n\sum_{\pi\,\vdash n}True\left(\pi \textrm{ contains an }i \right) = \sum_{i=1}^n H(i)\textrm.$$

The observation that $H(i)=p(n-i)$ completes the proof.