5
$\begingroup$

Show that the number of parts having odd multiplicities in all partitions of $n$ is equal to difference between the number of odd parts in all partitions of $n$ and the number of even parts in all partitions of $n.$

Example: $n=5.$ The number of partitions $5',\quad4'1',\quad3'2',\quad3'11,\quad221',\quad2'1'11,\quad1'1111$ have $10$ parts with odd multiplicities (marked with $'$). On the other hand, the number of odd parts is $15$, $$5,1,3,3,1,1,1,1,1,1,1,1,1,1,1$$ and the number of even parts is $5$, $$4,2,2,2,2.$$ I gave up solving the problem because in this problem parts are taken in all partitions not any single partition. I tried thinking some bijective proof or analytic proof using generating function but gave up as it seems to me a very different problem . Does anyone have any idea? The problem is very nice and it is recently been proposed by George Andrews in Mathstudent Journal (India).

$\endgroup$
  • 1
    $\begingroup$ A bijection sounds right. Hint: look at conjugate partitions. $\endgroup$ – Peter Taylor Jan 27 '17 at 11:18
  • $\begingroup$ not getting how conjugate partition will help here $\endgroup$ – Subhash Chand Bhoria Jan 27 '17 at 11:49
  • $\begingroup$ @SubhashChandBhoria: Very nice problem. Thanks for posting it. It was great fun to work on it. $\endgroup$ – Markus Scheuer Apr 22 '17 at 13:29
3
$\begingroup$

This answer is based upon generating functions. We start by considering the generating function of all partitions of $n$ \begin{align*} \prod_{m=1}^\infty\frac{1}{1-z^m}=\prod_{m=1}^\infty\frac{1}{(1-z^{2m})(1-z^{2m-1})}\tag{1} \end{align*}

From the RHS of (1) we derive $A(z,t)$, a generating function of all partitions with marked odd parts and $B(z,t)$, a generating function with marked even parts. \begin{align*} A(z,t)&=\prod_{m=1}^\infty\frac{1}{(1-z^{2m})(1-tz^{2m-1})}\\ &=1+tz+(t^2+1)z^2+(t^3+2t)z^3+(t^4+2t^2+2)z^4\\ &\qquad+(t^5+2t^3+4t)z^5+\cdots\\ B(z,t)&=\prod_{m=1}^\infty\frac{1}{(1-tz^{2m})(1-z^{2m-1})}\\ &=1+z+(t+1)z^2+(t+2)z^3+(t^2+2t+2)z^4\\ &\qquad+(t^2+3t+3)z^5+\cdots \end{align*}

Similarly we obtain a generating function $C(z,t)$ with marked odd multiplicities by separating terms with odd and even index \begin{align*} C(z,t)&=\prod_{m=1}^{\infty}\left(\frac{1}{1-z^{2m}}+\frac{tz^m}{1-z^{2m}}\right)\\ &=\prod_{m=1}^{\infty}\frac{1+tz^m}{1-z^{2m}}\\ &=1+tz+(t+1)z^2+(t^2+2t)z^3+(t^2+2t+2)z^4\\ &\qquad+(3t^2+4t)z^5+\cdots \end{align*}

In terms of generating functions the equality of the difference between the number of odd and even partitions of a number $n$ and the number of odd multiplicities of the partitions of $n$ translates to the following

Claim: \begin{align*} \left.\frac{\partial}{\partial t}A(z,t)\right|_{t=1}-\left.\frac{\partial}{\partial t}B(z,t)\right|_{t=1} =\left.\frac{\partial}{\partial t}C(z,t)\right|_{t=1} \end{align*}

Before we show the claim we do a plausibility check and look at partitions of small $n=1,\ldots,5$.

\begin{array}{c|ccc|l} n &[z^n]\left.\frac{\partial}{\partial t}A(z,t)\right|_{t=1} &[z^n]\left.\frac{\partial}{\partial t}B(z,t)\right|_{t=1} &[z^n]\left.\frac{\partial}{\partial t}C(z,t)\right|_{t=1} &partitions\\ 1&1&0&1&1\\ 2&2&1&1&2,1^2\\ 3&5&1&4&3,21,1^3\\ 4&8&4&4&4,31,2^2,21^2,1^4\\ 5&15&5&10&5,41,32,31^2,2^21,21^3,1^5\\ \hline \end{array}

Here we see the coefficients of the power series for $n=1,\ldots,5$ and observe the difference of odd and even parts coincides with the number of odd multiplicities. :-)

The right-most column lists the partitions of $n$ with the compact notation e.g. $21^3$ is a short-hand for $2+1+1+1$.

We obtain using logarithmic differentiation \begin{align*} \left.\frac{\partial}{\partial t}A(z,t)\right|_{t=1} &=\left.\frac{\partial}{\partial t}\prod_{m=1}^\infty\frac{1}{(1-z^{2m})(1-tz^{2m-1})}\right|_{t=1}\\ &=\left.\prod_{m=1}^\infty\frac{1}{(1-z^{2m})(1-tz^{2m-1})}\sum_{k=1}^\infty\frac{z^{2k-1}}{1-z^{2k-1}}\right|_{t=1}\\ &=\prod_{m=1}^\infty\frac{1}{(1-z^{2m})(1-z^{2m-1})}\sum_{k=1}^\infty\frac{z^{2k-1}}{1-z^{2k-1}}\\ &=\prod_{m=1}^\infty\frac{1}{1-z^{m}}\color{blue}{\sum_{k=1}^\infty\frac{z^{2k-1}}{1-z^{2k-1}}}\\ \end{align*} and similarly \begin{align*} \left.\frac{\partial}{\partial t}B(z,t)\right|_{t=1} &=\left.\frac{\partial}{\partial t}\prod_{m=1}^\infty\frac{1}{(1-tz^{2m})(1-z^{2m-1})}\right|_{t=1}\\ &=\prod_{m=1}^\infty\frac{1}{1-z^{m}}\color{blue}{\sum_{k=1}^\infty\frac{z^{2k}}{1-z^{2k}}}\\ \end{align*} Next we get \begin{align*} \left.\frac{\partial}{\partial t}C(z,t)\right|_{t=1} &=\left.\frac{\partial}{\partial t}\prod_{m=1}^\infty\frac{1+tz^m}{1-z^{2m}}\right|_{t=1}\\ &=\left.\prod_{m=1}^\infty\frac{1+tz^m}{1-z^{2m}}\sum_{k=1}^\infty\frac{z^k}{1+tz^k}\right|_{t=1}\\ &=\prod_{m=1}^\infty\frac{1+z^m}{1-z^{2m}}\sum_{k=1}^\infty\frac{z^k}{1+z^k}\\ &=\prod_{m=1}^\infty\frac{1}{1-z^{m}}\color{blue}{\sum_{k=1}^\infty\frac{z^k}{1+z^k}} \end{align*}

We observe the claim is valid if the following holds: \begin{align*} \color{blue}{\sum_{k=1}^\infty\frac{z^{2k-1}}{1-z^{2k-1}} -\sum_{k=1}^\infty\frac{z^{2k}}{1-z^{2k}} =\sum_{k=1}^\infty\frac{z^k}{1+z^k}}\tag{2} \end{align*}

We start with the left-hand side of (2) and get \begin{align*} \color{blue}{\sum_{k=1}^\infty}&\color{blue}{\frac{z^{2k-1}}{1-z^{2k-1}} -\sum_{k=1}^\infty\frac{z^{2k}}{1-z^{2k}}}\\ &=\sum_{k=1}^\infty\left(\frac{z^{k}}{1-z^{k}}-\frac{z^{2k}}{1-z^{2k}}\right) -\sum_{k=1}^\infty\frac{z^{2k}}{1-z^{2k}}\\ &=\sum_{k=1}^\infty\left(\frac{z^{k}}{1-z^{k}}-\frac{2z^{2k}}{1-z^{2k}}\right)\\ &=\sum_{k=1}^\infty\frac{z^k}{1-z^k}\left(1-\frac{2z^k}{1+z^k}\right)\\ &=\sum_{k=1}^\infty\frac{z^k}{1-z^k}\cdot\frac{1-z^k}{1+z^k}\\ &\color{blue}{=\sum_{k=1}^\infty\frac{z^k}{1+z^k}} \end{align*} and the claim follows.

$\endgroup$
  • $\begingroup$ very nice solution sir $\endgroup$ – Subhash Chand Bhoria May 27 '17 at 7:23
  • $\begingroup$ @SubhashChandBhoria: Thanks, my pleasure! :-) $\endgroup$ – Markus Scheuer May 27 '17 at 7:33

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.