CHAP, ill] PARTITIONS. 105
so that the number of partitions of n into distinct integers equals the number of partitions of n into odd parts not necessarily distinct. Replace x by xz in (3) . Since H(l - a;2*) = PQ,
Q = (1 - x* - z4 + xlQ + x14
~,
= 1 + x + 2x2 + 3x3 + 5x4 +
Hence, by multiplication,
Q = i + x + x* + 2x* + 2x* + 3z5 + 4z« + • • •.
Thus the coefficient of x8 in this series gives the number of partitions of s into distinct parts. Since
(1+ X)(l + Z2)(l + X4*) • • - = 1 + X + X* + X3 + ' «,
(x-1 + 1 + z)(ar3 + 1 + x*)(x~g + 1 + x9) • • • = 1 + x + x2 + x* + - • •
+ x-1 + x~* + or3 + •••,
every integer can be obtained by adding different terms of the progression 1, 2, 4, 8, 16, • • • or of ± 1, db 3, ± 32, • • • . The latter facts were known by Leonardo Pisano,11 Michael Stifel,lla and Frans van Schooten,12 who gave a table expressing each number ^ 127 in terms of 1, 2, 4, - • •, and every number s 121 in terms of db 1, db 3, =k 9,
Euler13 reproduced essentially his preceding treatment. He concluded (§ 41, p. 91) that, if P(n) or n(oe) denotes the number of all partitions of n,
P(n) = P(n - 1) + P(n - 2) - P(n - 5) - P(n - 7) + P(n - 12) + • • -,
the numbers subtracted from n being the exponents in (3). His table of the number n(w) of partitions of n into parts ^ m here extends to n si 59, m ^ 20 and includes m = °o . He proved again that every integer equals a sum of different terms of 1, 2, 4, 8,
Euler14 noted that the number (2V, n, m) of partitions of N into n parfcs each ^ m is the coefficient of XN in the expansion of (x + x* + - • • + zm)n-Set (5) (1 + x + - - • + xm~l)« = 1 + Anx + Bnx* + - - -,
bring to a common denominator the derivatives of the logarithms of each member and equate the coefficients of like powers of a: in the expansions of the numerators. The resulting linear relations determine Any Bn) - • • in turn, whence
X(n + X, n, m) = (n + \ — l)(n + X — 1, n, m)
— (mn + m — X) (n + X — m, n, m)
+ (mn — n + m + 1 — X)(n + X — m — 1, n, m).
u Scritti L. Pisano, I, Liber abbaci, 1202 (revised about 1228), Rome, 1857, 297.
lla Die Coas Christoffs Rudolffs . . . durch Michael Stifel gebessert . . . , 1553.
12 Exercitationum Math., 1657, 410-9.
1S Novi Comm. Acad. Petrop., 3, ad annum 1750 et 1751, 1753, 125 (summary, pp. 15-18) ;
Comm. Arith. Coll., I, 73-101. 14 Novi Comm. Acad. Petrop., 14, I, 1769, 168; Comm. Arith. Coll., I, 391-400.