At 03:45 PM 5/15/03, Allan C. Wechsler wrote:
The number of partitions of an integer n into ODD integers equals the number of partitions of the same n into DISTINCT integers.
(All integers positive, of course.) This is Theorem 344 in Hardy & Wright; they give both the generating function and combinatorial proofs. The generating function proof is quite easy. The g.f. for partitions into odd parts is 1/((1-x)(1-x^3)(1-x^5)...) while the g.f. for partitions into distinct parts is (1+x)(1+x^2)(1+x^3)... The latter can be rewritten as (1-x^2)/(1-x) * (1-x^4)/(1-x^2) * (1-x^6)/(1-x^3) * ... The even-exponent terms in the numerators cancel like terms in the denominators; this leaves the odd-exponent terms in the denominators, so the result is the same as the first g.f. -- Fred W. Helenius <fredh@ix.netcom.com>