# Proving correspondence and partitions via generating functions, or at least I think so.

Let $$A=\{2,6,10,14,\ldots\}$$ be the set of integers that are twice an odd number.

Prove that, for every positive integer $$n$$, the number of partitions of $$n$$ in which no odd number appears more than once is equal to the number of partitions of $$n$$ containing no element of $$A$$.

For example, for $$n=6$$, the partitions of the first type are $$6,~~~5+1,~~~4+2,~~~3+2+1,~~~2+2+2,$$ and the partitions of the second type are $$5+1,~~~4+1+1,~~~3+3,~~~3+1+1+1,~~~1+1+1+1+1+1,$$ and there are $$5$$ of each type.

I believe that I could show the generating functions of the two are the same, but I do not know where to start. So I'm thinking to first set some variables and functions, so I decided to let $$\operatorname{P}_0(n)$$ be the set of partitions of $$n$$ in which no odd number appears more than once, and let $$\operatorname{P}_1(n)$$ be the set of partitions of $$n$$ containing no element of $$A$$. How do I move out from there? If there is anyone who would guide me to the correct proof, or give a proof, their help would be appreciated. Thanks!

• What do you mean "I do not know where to start"? You start with the generating functions. Do you know what the generating function for partitions is and why it is what it is? Do you know how to modify that generating function to count partitions with unique parts or only odd parts? These are standard examples that you can find in most references. – Trevor Gunn Oct 5 '18 at 17:04
• I do not know the generating function for partitions. How do I make one? – Max0815 Oct 5 '18 at 17:08
• You should read a textbook on this. – Trevor Gunn Oct 5 '18 at 17:12
• You said you were in 7th grade and you're not familiar with the notion involving the $\sum$ and $\prod$? So is it safe to say you don't know what a generating function is? If that's the case then it would take too long to explain this question here properly. As admirable as it is that you are taking an interest in such advanced topics at this stage, unfortunately you aren't yet ready to ask this kind of question here. This web site is better suited for questions that can be answered within a page or less, whereas to answer your question you'd need to read an entire book almost. – Trevor Gunn Oct 5 '18 at 17:20
• No I know what the summation function is, but I just don't know what the pi thing is. – Max0815 Oct 5 '18 at 17:33

## 2 Answers

Let $$a_n$$ be the number of partitions of $$n$$ of the first kind, and let $$b_n$$ be the number of partitions of $$n$$ of the second kind.

Then $$A(q)=\sum_{n=0}^\infty a_nq^n=\prod_{m=1}^\infty\frac{1+q^{2m-1}}{1-q^{2m}}$$ and $$B(q)=\sum_{n=0}^\infty b_nq^n=\prod_{m=1}^\infty\frac{1-q^{4m-2}}{1-q^m}.$$

I would try writing $$1-q^{4m-2}=(1+q^{2m-1})(1-q^{2m-1})$$ in the formula for $$B(q)$$.

• Sorry, but I am only on 7th grade. I do not fully understand the notation you just gave. Mind clarifying??? – Max0815 Oct 5 '18 at 17:09
• @Max0815: $\prod_{i=1}^\infty a_i$ stands for $a_1 a_2 a_3 \cdots$. Of course, such an infinite product doesn't always make sense (e.g., you cannot make sense of $\prod_{i=1}^\infty i = 1\cdot 2 \cdot 3 \cdot \cdots$), but the one in Lord Shark's posts do, because the factors "recede" further and further away (more formally speaking: multiplying by the factor $\dfrac{1-q^{4m-2}}{1-q^m}$ doesn't change the first $m$ coefficients of a power series, so that every coefficient stabilizes after finitely many factors of the product have been multiplied). For details on formal power series, ... – darij grinberg Oct 5 '18 at 17:41
• ... see the appropriate chapter of Nicholas Loehr, Bijective Combinatorics. – darij grinberg Oct 5 '18 at 17:41
• I have found more on the problem. So if $\beta\in\operatorname{P}_0$, let $\overline{\beta}$ be the partition of $n$ obtained by splitting each member of $\beta$ that is in $A$ into two halves and leaving all other numbers of the partition where they are. This clearly appears to map $\operatorname{P}_0(n)$ into $\operatorname{P}_1(n)$. However, I am having trouble showing that the map is actually a bijection. It seems clearly injective, but I just can't solve it from what I have now. Can I have another hint? – Max0815 Oct 5 '18 at 17:45
• @LordSharktheUnknown can you help me on what I have currently? – Max0815 Oct 5 '18 at 17:55

Prove that, for every positive integer $$n$$, the number of partitions of $$n$$ in which no odd number appears more than once is equal to the number of partitions of $$n$$ containing no [number which is twice an odd number].

Flip it round: it suffices to prove that the number of partitions of $$n$$ in which an odd number occurs twice is the same as the number of partitions of $$n$$ which contain a number of the form $$4k+2$$. Denote the set of partitions of the first type as $$Q$$ and the set of partitions of the second type as $$R$$.

It is possible that the intersection $$Q \cap R$$ is non-empty. We simplify things greatly by further reducing the problem to showing that $$Q \setminus R$$ and $$R \setminus Q$$ have the same cardinality.

Consider $$f: (Q \setminus R) \to (R \setminus Q)$$ which combines as many equal odd numbers as possible. E.g. $$f(1^6) = 2^3$$. Clearly this is bijective.