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
Previous Page Next Page