7
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Hint: dual partition. (Draw Young diagrams to see the bijection.) $\endgroup$ – Sammy Black Apr 8 '13 at 19:34
  • $\begingroup$ Can you please provide some more hint. $\endgroup$ – user71613 Apr 9 '13 at 5:21
  • 1
    $\begingroup$ @SammyBlack: Could you elaborate on the hint? It is certainly not true that $F(\pi)$ equals $G(\pi^*)$. $\endgroup$ – Shahab Apr 9 '13 at 16:26
  • $\begingroup$ @Shahab, you're certainly correct. I misread one of the functions. I'm not so sure how to proceed now. Perhaps look at the generating function in two different ways and equate coefficients? $\endgroup$ – Sammy Black Apr 9 '13 at 18:52
  • $\begingroup$ It can be shown that $\sum F(\pi)=p(0)+\cdots p(n-1)$. I am having trouble proving that the RHS equals $\sum G(\pi)$. $\endgroup$ – Shahab Apr 10 '13 at 5:54
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.