4 B. C. BERND T generates the number of ft's that appear in a particular partition of n. Each partition of n appears once and only once on the right side of (1.1.7) when interpreted in this manner. The generating function for the number of partitions of n into distinct parts, denoted by Pd(n)i is given by oo (1.1.8) Y,Pd(n)qn = (-q q)oc = (l + q)(l + q2)---(l+qk)---, n=0 because any particular integer can occur at most once in any given representation of n. We now show that, by elementary product ma- nipulations, we can deduce the following famous theorem of Euler. Theorem 1.1.10 (Euler). The number of partitions of a positive integer n into distinct parts equals the number of partitions of n into odd parts, denoted byp0(n). Proof. From (1.1.8), (1.1.9) 0 0 / 2 2\ i °° 5(»)«" = (-« «)» = { j^ = j-^y = £PO(»)«». n=0 WS^oo W,q Joe n = Q Equating coefficients of gn, n 1, on both sides of (1.1.9), we com- plete the proof of Euler's identity. • For example, p^(6) = 4, because 6 has 4 representations into distinct parts, namely, 6 = 5 + 1 = 4 + 2 = 3 + 2 + 1. On the other hand, p0(6) = 4, because 6 has 4 representations into odd parts, namely, 5 + 1 = 3 + 3 = 3 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1. Exercise 1.1.11. Euler's identity can be slightly refined. Prove that the number of partitions of n into an even (odd) number of odd parts equals the number of partitions of n into distinct parts, where the number of odd parts is even (odd). Exercise 1.1.12. Prove that the number of partitions of the positive integer n into parts that are not divisible by 3 is equal to the number of partitions of n in which no part appears more than twice. Exercise 1.1.13. Euler's identity can be refined in yet another way. Let k and n be positive integers with k 2. Prove that the number of

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2006 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.