+0

# Proving partitions.

+1
302
3

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
$$6,~~~5+1,~~~4+2,~~~3+2+1,~~~2+2+2,$$
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!

Oct 5, 2018
edited by Max0815  Oct 5, 2018

#1
+1

Oct 5, 2018
#2
+1

Try to find a bijection between the two sets- You are given a partition where no odd number appears more than once, try to find a way to turn that partition (maybe by splitting up some of the members of the partition, or by adding up some of them) into a partition that contains no element from the set A. Try to find a way to do that for ever partition, such that every partition that contains no element from the set A has EXACTLY one partition where no odd number appears more than once, that when applying your method/algorithm/function to will produce that partition.

Maybe melody/Cphill can explain that better, they are very smart and surely can solve your question

Oct 5, 2018
#3
+1

Okay. I have found more on the problem. So if β∈P_0, let $$\overline{\beta}$$ be the partition of n obtained by splitting each member of β that is in A into two halves and leaving all other numbers of the partition where they are. This clearly appears to map $$P_0(n)$$ into $$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? Melody? CPhill??

Oct 5, 2018
edited by Max0815  Oct 5, 2018