Recipe

Compute p(n) by splitting on the largest part

Use when: you need p(n) for a value of n too large to recall from memory but small enough to list by hand

Goal: the exact value of p(n), built from disjoint cases that together cover every partition exactly once

Taught in The partition function

1. 1

   Every partition of n has some largest part, somewhere between 1 and n; these values will become the disjoint cases.

   Example

   For p(7): the largest part can be 7,6,5,4,3,2, or 1.

   Why: splitting by largest part covers every partition exactly once, since every partition has exactly one largest part.

2. 2

   Fixing the largest part at k leaves the remaining n-k to be partitioned, using only parts of size k or smaller (repeats of k itself allowed).

   Example

   Largest part 4 in a partition of 7: count partitions of 7-4=3 using parts \le 4, giving 4+3, 4+2+1, and 4+1+1+1, so 3 of them.

   Why: capping the remaining parts at k is what keeps k genuinely the largest part, rather than allowing a bigger part to sneak into the remainder.

3. 3

   Work through every largest-part value systematically, from n down to 1, so no case is skipped or counted twice.

   Example

   For p(7): largest part 7 gives 1, 6 gives 1, 5 gives 2, 4 gives 3, 3 gives 4, 2 gives 3, 1 gives 1.

   Why: each value of k is a genuinely separate, non-overlapping case, so every one has to be worked out on its own.

4. 4

   Sum the counts from every largest-part case found in Step 3.

   Example

   1+1+2+3+4+3+1.

   Why: the cases are disjoint and cover every partition exactly once, so a plain sum, not a more elaborate combination, gives the true total.