Lets say that $p(n)$ is the number of ways of partitioning $n$ into integers (order doesn't matter).

How does one prove that $$p(n) \equiv p(n|\text{distinct odd parts}) \mod 2$$?

For $n=1$, there's only one partition with one part, $1$. And this is also a partition into distinct odd parts.

For $n=2$, there are $2$ partitions and $0$ partitions into distinct odd parts.

For $n=3$, there are $3$ partitions and $1$ partition into distinct odd parts (partition into a single part $3$)

For $n=4$, there are $5$ partitions and $1$ partition into distinct odd parts ($3+1$)

and so on. This seems to hold for small $n$, I calculated it by hand.

I don't really know how to prove this though. One thing one might prove is that $$p(n|\text{odd parts with at least one part occurring twice})+p(n|\text{at least one even part}) \equiv 0\mod2$$

But I don't know how to prove that either. I'm looking for a solution that doesn't invoke generating functions, but a solution with generating functions is welcome. Any help is very appreciated, thanks!


2 Answers 2


Here the lazy person approach: the number of partitions is given by $$ p(n) = [x^n]\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots} $$ while the number of partitions into distinct odd parts is given by $$ p_1(n) = [x^n](1+x)(1+x^3)(1+x^5)\cdots $$ so we just need to prove that all the coefficients of $(1-x)(1-x^2)(1-x^3)\cdots(1+x)(1+x^3)(1+x^5)\cdots$ except the very first one are even. On the other hand in $\mathbb{F}_2[[x]]$ we have $$ \prod_{n\geq 1}(1-x^n)\prod_{m\geq 0}(1+x^{2m+1})=\prod_{n\geq 1}(1-x^{2n})\prod_{m\geq 0}(1+x^{4m+2})=\prod_{n\geq 1}(1-x^{4n})\prod_{m\geq 0}(1+x^{8m+4}) $$ since $(1-x^{2n+1})(1+x^{2n+1})=(1-x^{4n+2})=(1+x^{4n+2})$ and so on. By induction $$ \prod_{n\geq 1}(1-x^n)\prod_{m\geq 0}(1+x^{2m+1})=\prod_{n\geq 1}(1-x^{2^k n})\prod_{m\geq 0}(1+x^{2^{k+1}m+2^k})$$ for any $k\in\mathbb{N}$. It follows that in $\mathbb{F}_2[[x]]$ both series equal $1$, so $p(n)$ and $p_1(n)$ always have the same parity.

By playing a bit with the Jacobi triple product we also have $$ \prod_{n\geq 1}(1-x^n)\prod_{m\geq 0}(1+x^{2m+1})=1+2\sum_{d\geq 1}(-1)^d x^{2d^2}.$$


The number of partitions of $n$ into distinct odd parts equals the number of self-conjugate partitions of $n$. The number of non-self-conjugate partitions of $n$ is even.

  • $\begingroup$ I just saw the definitions of the relevant terms - why are there an even number of non-self-conjugate partitions? $\endgroup$ Commented Jun 14, 2020 at 20:44
  • $\begingroup$ @ramseysdream111: Pair each one with its conjugate. $\endgroup$ Commented Jun 14, 2020 at 20:46
  • $\begingroup$ @BrianM.Scott Ahh yes of course! $\endgroup$ Commented Jun 14, 2020 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .