Integer Partitions is the habit of counting ways to write integers as unordered sums under restrictions. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
$$p(n) = \#\{\text{ways to write } n \text{ as an unordered sum of positive integers}\}$$
A partition counts the ways to write $n$ as a sum of positive integers where order does not matter.
Why It Works
1
Unlike compositions (ordered sums), partitions treat $3 + 1$ and $1 + 3$ as the same, so list parts in nonincreasing order to avoid duplicates.
2
Restrictions (distinct parts, only odd parts, largest part $\le k$) are imposed by limiting which parts you allow.
3
Small partition counts are found by careful organized listing; larger ones use recurrences or generating functions $\prod_{k \ge 1} \tfrac{1}{1 - x^k}$.
4
Organizing the list by the largest part (a form of casework) is the reliable hand-count method.
Worked Examples
Example 1
Find $p(5)$, the number of partitions of $5$.
1
List partitions with parts in nonincreasing order, grouped by the largest part.
2
Largest part $5$: $5$. Largest part $4$: $4{+}1$. Largest part $3$: $3{+}2,\ 3{+}1{+}1$.
3
Largest part $2$: $2{+}2{+}1,\ 2{+}1{+}1{+}1$. Largest part $1$: $1{+}1{+}1{+}1{+}1$.
4
Count them: $1 + 1 + 2 + 2 + 1 = 7$.
Answer:
$7$
Warm-up
How many partitions of $6$ use only DISTINCT parts (no repeated summand)?
1
List partitions of $6$ into distinct positive integers, in nonincreasing order.
2
Single part: $6$. Two parts: $5{+}1$, $4{+}2$ (not $3{+}3$, repeated).
3
Three parts: $3{+}2{+}1$. (Any other distinct triple exceeds or misses $6$.)
4
Count: $1 + 2 + 1 = 4$.
Answer:
$4$
Contest level
Euler's theorem says the number of partitions of $n$ into ODD parts equals the number into DISTINCT parts. Verify both counts equal $4$ for $n = 6$.
1
Partitions of $6$ into odd parts (parts from $\{1,3,5\}$, repeats allowed): $5{+}1$, $3{+}3$, $3{+}1{+}1{+}1$, $1{+}1{+}1{+}1{+}1{+}1$.
2
That is $4$ partitions into odd parts.
3
Partitions of $6$ into distinct parts (from the warm-up): $6$, $5{+}1$, $4{+}2$, $3{+}2{+}1$ — also $4$.
4
Both counts are $4$, confirming Euler's odd-equals-distinct identity for $n = 6$.
Answer:
$4 = 4$ (Euler's identity verified)
Olympiad / Challenge
How many partitions of $8$ have every part at most $3$ (i.e. parts drawn from $\{1, 2, 3\}$)?
1
Do casework on $t$, the number of $3$s used; the rest of the sum must come from parts in $\{1, 2\}$.
2
$t = 2$ (the $3$s contribute $6$): remaining $2$ from $\{1,2\}$ is $2$ or $1{+}1$ — $2$ ways.
3
$t = 1$ (contributes $3$): remaining $5$ from $\{1,2\}$; the number of $2$s can be $0, 1, 2$ — $3$ ways.
4
$t = 0$: remaining $8$ from $\{1,2\}$; the number of $2$s can be $0, 1, 2, 3, 4$ — $5$ ways. ($t \ge 3$ needs sum $\ge 9 > 8$, impossible.)
5
Add the disjoint cases: $2 + 3 + 5 = 10$.
Answer:
$10$
Going Deeper
The generating function for partitions is $\prod_{k \ge 1} \dfrac{1}{1 - x^k}$, and restricting the allowed parts simply restricts the product: distinct parts give $\prod_{k}(1 + x^k)$, odd parts give $\prod_{k \text{ odd}} \frac{1}{1-x^k}$, and the algebraic identity $\prod (1 + x^k) = \prod \frac{1}{1 - x^{2k-1}}$ is exactly Euler's odd-equals-distinct theorem. Conjugation (transposing the Young diagram) gives 'largest part $\le k$' $=$ 'at most $k$ parts.'
Partition counts appear on AIME as 'ways to write $n$ as a sum (order ignored)' and underlie change-making with one of each denomination, Young-tableau problems, and the unordered analog of stars-and-bars. The conjugation bijection is a recurring olympiad tool for converting a part-size constraint into a part-count constraint.
Pitfall: partitions ignore ORDER (so $3+1$ and $1+3$ are the same) — confusing them with compositions (ordered sums, of which there are $2^{n-1}$) is the dominant error. There is no simple closed form for $p(n)$, so hand-counts must be organized (by largest part or by part multiplicity) to avoid missing or repeating a partition.
Spot the Signal
Look for problems where the key step is counting ways to write integers as unordered sums under restrictions.
You can describe the hard part as counting ways to write integers as unordered sums under restrictions, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the counting object that calls for integer partitions, then rewrite the givens around it.
Name the relation that makes Integer Partitions legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Integer Partitions just because the surface looks familiar; verify the required condition first.
Applying Integer Partitions because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let integer partitions reveal the counting structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is counting ways to write integers as unordered sums under restrictions.