Integer Partitions

This topic teaches you how to break complex counting problems into smaller steps. It shows you how to figure out the number of ways to combine things when order does not matter. For example, it helps you count how many distinct groups of items can sum up to a specific total. Consider the number 5: it can be written as a sum in exactly seven distinct ways: 5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1; and 1+1+1+1+1. Because order does not matter, the combination 3+2 is the same as 2+3, so we count it only once. This is useful in real-world scenarios like currency exchange or resource allocation.

Imagine you have a big pile of identical coins and you want to distribute them into a row of dishes. Each dish must get at least one coin, and you don't care about the order of the dishes—just how many coins go in each. The question 'how many different distributions are there for, say, 7 coins?' is exactly the integer partition problem. For example, with 4 coins, you could put them all in one dish (4), split into two dishes (1+3 or 2+2), or three dishes (1+1+2), or four (1+1+1+1). These are the partitions of 4. The count grows surprisingly fast: while 4 has just 5 partitions, 10 has 42, and 20 has 627. There is no simple formula like 'n squared' to jump straight to the answer; instead, you build it up by thinking about how to add one more to the pile.

Think of stacking boxes of different heights on a shelf, where you only have a fixed total height. Each arrangement that uses the exact total height is a partition of that height (for example, height 3 could be one box of height 3, or a 2 and a 1, or three 1s—order doesn't matter). The catch: you can reuse the same box height as many times as you like, but swapping the order of boxes doesn't count as a new arrangement. This is like having an unlimited supply of weights in a gym and trying to reach a target weight on the bar—you could use two 10s or four 5s, but putting the 10s in a different order doesn't change the load. The analogy breaks down when you consider that in partitions, the 'boxes' are just numbers, and there is no physical limit on how many times you can use each number—so the count can get huge. Also, unlike real shelves, you cannot leave any gap—the sum must equal exactly the target.

An integer partition of a positive integer n is a way of writing n as a sum of positive integers, where the order of the addends does not matter, and where repetition is allowed.

This topic connects to Integer Arithmetic, which is the basic counting and adding of numbers we do every day. It also links to Combinatorics because both involve counting ways to group items without regard to order.