# Homework Help: Partition of Integer need advice

1. Jun 12, 2004

### phoenixy

The Q is: show that the number of partitions of n within Z+ where no summand is divisible by 4 equals the number of partitions of n where no even summand is repeated

Here is what I got so far
Let the partition where no summand is divisible by 4 be P1(x)
Let the partition where no even summand is repeated be P2(x)

My goal is to show that P1(x) = P2(x)

P1(x) = (1+x+x^2 ... )(1+x^2+x^4 ... )(1+x^3+x^6 ...)(1+x^5+x^10 ...)...
(skip x^4, x^8, ... etc.)

P1(x) = [ let i go from 1 to infinity, the products of ( 1 / (1-x^i) ) ] /
[ let i go from 1 to infinity, the prodcuts of ( 1 / (1-x^(4i) )

P2(x) = [ (1+x^2)(1+x^4) ... ][ (1+x+x^2 ...)(1+x^3+x^6) ... ]

P2(x) = [ let i go from 1 to infinity,the products of ( 1 + x^(2i) ) ] *
[ let i go from 1 to infinity, the products of ( 1 / (1-x^(2i-1)) )

So are my equations correct? If so, how do I solve them?

Last edited by a moderator: Jun 12, 2004
2. Jun 12, 2004

### Hurkyl

Staff Emeritus
I imagine finding a 1-1 correspondence between the two types of partitions might be easier.

3. Jun 12, 2004

### AKG

As a start (but just a start, it's definitely not perfect) notice that any partition that has a multiple of four in it can be expressed as a partition that has a repeated integer. Starting with P1, a partition with multiples of 4 in it, simply replace all multiples of fours with two of their halfs, and you get P2, a parition with repeated evens. This is true because any multiple of four is in the form 2 x 2 x k for some k in N. We can clearly replace 2 x 2 x k with two of 2 x k, making 2 x k repeated, and it should be pretty clear that 2 x k is even. However, there are problems. For example, if we have P1 = {4,2,2}, then the corresponding P2 = {2,2,2,2} If we have P1 = {4,4}, the corresponding P2 = {2,2,2,2}, the same as before. This means that for each P1, there exist a P2, but that P2 is not necessarily unique to that P1. If it were, then we could nicely say that if we consider the set of all partitions, the set formed by removing all partitions with multiples of four has the same number of partitions as the set formed by removing all paritions with repeated evens, because for each partition with a multiple of four we remove, we remove one unique parition of the other type. However, this isn't true. You'll have to work around this problem; I'll think about it but this should give you a start.