Solution
Partitions of Fifteen
Show the problem again
A partition of a positive integer n is a way of writing n as a sum of positive integers where the order of the summands does not matter (so 3 + 1 + 1 and 1 + 3 + 1 are the same partition). The single-term sum "15" counts as a partition. How many partitions does 15 have? Give an integer.
Worked solution
**Answer: 176.** Let p(n, k) be the number of partitions of n into exactly k parts. Either some part equals 1 (remove it: p(n − 1, k − 1)) or every part is at least 2 (subtract 1 from each part: p(n − k, k)). So p(n, k) = p(n − 1, k − 1) + p(n − k, k). Building the table up to n = 15 gives, for k = 1, 2, ..., 15: 1, 7, 19, 27, 30, 26, 21, 15, 11, 7, 5, 3, 2, 1, 1, which sum to 176. As a cross-check, Euler's pentagonal number recurrence p(n) = p(n−1) + p(n−2) − p(n−5) − p(n−7) + p(n−12) + p(n−15) − ... gives p(15) = 135 + 101 − 42 − 22 + 3 + 1 = 176, using p(14) = 135, p(13) = 101, p(10) = 42, p(8) = 22, p(3) = 3, p(0) = 1.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.