# Integer Partitions

The ways of writing an integer as a sum of positive integers, ignoring order — a classic counting problem with surprisingly deep structure.

**Rests on:** Proof by Induction

*Mathematical Foundations · Discrete Mathematics*


## Why learn this

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.


## The intuition

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.


## An analogy

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.


## Definition

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.


## How it connects

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.


## The mathematics

**Integer Partitions: Counting Ways to Break a Number**

This topic belongs to **discrete mathematics**, the branch that deals with countable structures—things you can list one by one, like whole numbers or sets of objects—rather than continuous quantities like lengths or temperatures. Integer partitions are a counting problem: we want to know the number of distinct ways to write a positive integer as a sum of smaller positive integers. The order of the numbers in the sum does not matter. For example, 1+3 is the same partition as 3+1.

Think of it as breaking a pile of identical items into groups. Imagine you have n dots. You want to arrange them into rows so that every row has at least one dot. The number of dots in each row forms a "part" of the sum. Because the order of rows does not matter, we usually write the parts from largest to smallest.

For example, take the number 4. We can break it down in these ways:
1. Just 4 (one row of four dots)
2. 3 + 1 (a row of three, then a row of one)
3. 2 + 2 (two rows of two)
4. 2 + 1 + 1 (a row of two, then two rows of one)
5. 1 + 1 + 1 + 1 (four rows of one)

There are exactly 5 ways to partition the number 4. We write this count as p(4) = 5. The symbol p(n), read "p of n", means the total number of partitions of the integer n.

To calculate p(n) for larger numbers without listing every possibility by hand, we use a step-by-step method called recursion. This method builds the answer for n using answers we already know for smaller numbers. We do this by tracking two pieces of information:
1. The number we are trying to partition, which we call n.
2. The largest part allowed in the sum, which we call k.

We define a helper count, p(n, k), read "p of n with maximum part k". This is the number of ways to write n as a sum where no single number in the sum is larger than k. If we know how to calculate p(n, k) for all relevant k, we can find the total count p(n) by setting k equal to n (since no part can be larger than the number itself).

The rule for calculating p(n, k) relies on a simple choice: does the partition include at least one part that is exactly equal to k?

**Case 1: The partition does NOT use any part of size k.**
If we are not allowed to use the number k, then all parts must be smaller than k. This means we are effectively partitioning n using only numbers up to k-1. The number of ways to do this is p(n, k-1).

**Case 2: The partition DOES use at least one part of size k.**
If we include one part of size k, we have used up k units of our total n. We are left with a remainder of n - k. We still need to break this remainder into parts, but we can still use the number k again (because we might have multiple rows of size k). So, we need to find the number of ways to partition the remainder (n - k) using parts no larger than k. This count is p(n - k, k).

**Combining the cases:**
The total number of ways to partition n with maximum part k is the sum of the ways from Case 1 and Case 2:
p(n, k) = p(n, k-1) + p(n-k, k)

This formula works for most numbers. However, we must handle special boundary cases where the logic above breaks down:

1. **If n is 0:** There is exactly one way to partition zero: use no parts at all (the empty sum). So, p(0, k) = 1 for any k.
2. **If n is greater than 0 but k is 0:** You cannot form a positive number using only zeros or negative numbers. So, p(n, 0) = 0 for any n > 0.
3. **If k is greater than n:** You cannot have a part larger than the total sum. In this case, allowing parts up to k is the same as allowing parts up to n. So, p(n, k) = p(n, n). (In our table calculation below, we will simply stop increasing k once it reaches n).

To find the final answer p(n), we calculate p(n, n). This means we allow parts up to size n.


## A worked example

**Example: Calculating p(5)**

We want to find the total number of partitions of the number 5. We will build a table of values for p(n, k) where n goes from 0 to 5 and k goes from 0 to 5.

**The Rules Recap:**
- Formula: p(n, k) = p(n, k-1) + p(n-k, k)
- Base Case 1: p(0, any k) = 1
- Base Case 2: p(n > 0, 0) = 0

**Step-by-Step Calculation:**

**Row n=0:**
- p(0, 0) to p(0, 5): All are 1. (There is one way to make zero: do nothing).

**Row n=1:**
- k=0: p(1, 0) = 0. (Cannot make 1 with max part 0).
- k=1: Use formula. p(1, 1) = p(1, 0) + p(1-1, 1) = p(1, 0) + p(0, 1).
  - We know p(1, 0) = 0.
  - We know p(0, 1) = 1.
  - So p(1, 1) = 0 + 1 = 1. (Partition: [1]).

**Row n=2:**
- k=0: p(2, 0) = 0.
- k=1: Use formula. p(2, 1) = p(2, 0) + p(2-1, 1) = p(2, 0) + p(1, 1).
  - p(2, 0) = 0.
  - p(1, 1) = 1 (from above).
  - So p(2, 1) = 0 + 1 = 1. (Partition: [1+1]).
- k=2: Use formula. p(2, 2) = p(2, 1) + p(2-2, 2) = p(2, 1) + p(0, 2).
  - p(2, 1) = 1.
  - p(0, 2) = 1.
  - So p(2, 2) = 1 + 1 = 2. (Partitions: [2], [1+1]).

**Row n=3:**
- k=0: p(3, 0) = 0.
- k=1: Use formula. p(3, 1) = p(3, 0) + p(3-1, 1) = p(3, 0) + p(2, 1).
  - p(3, 0) = 0.
  - p(2, 1) = 1 (from above).
  - So p(3, 1) = 0 + 1 = 1. (Partition: [1+1+1]).
- k=2: Use formula. p(3, 2) = p(3, 1) + p(3-2, 2) = p(3, 1) + p(1, 2).
  - p(3, 1) = 1.
  - p(1, 2): Since k > n (2 > 1), this is the same as p(1, 1). We know p(1, 1) = 1.
  - So p(3, 2) = 1 + 1 = 2. (Partitions: [2+1], [1+1+1]).
- k=3: Use formula. p(3, 3) = p(3, 2) + p(3-3, 3) = p(3, 2) + p(0, 3).
  - p(3, 2) = 2.
  - p(0, 3) = 1.
  - So p(3, 3) = 2 + 1 = 3. (Partitions: [3], [2+1], [1+1+1]).

**Row n=4:**
- k=0: p(4, 0) = 0.
- k=1: Use formula. p(4, 1) = p(4, 0) + p(3, 1).
  - p(4, 0) = 0.
  - p(3, 1) = 1.
  - So p(4, 1) = 1. (Partition: [1+1+1+1]).
- k=2: Use formula. p(4, 2) = p(4, 1) + p(4-2, 2) = p(4, 1) + p(2, 2).
  - p(4, 1) = 1.
  - p(2, 2) = 2 (from above).
  - So p(4, 2) = 1 + 2 = 3. (Partitions: [2+2], [2+1+1], [1+1+1+1]).
- k=3: Use formula. p(4, 3) = p(4, 2) + p(4-3, 3) = p(4, 2) + p(1, 3).
  - p(4, 2) = 3.
  - p(1, 3): Since k > n (3 > 1), this is same as p(1, 1) = 1.
  - So p(4, 3) = 3 + 1 = 4. (Partitions: [3+1], [2+2], [2+1+1], [1+1+1+1]).
- k=4: Use formula. p(4, 4) = p(4, 3) + p(4-4, 4) = p(4, 3) + p(0, 4).
  - p(4, 3) = 4.
  - p(0, 4) = 1.
  - So p(4, 4) = 4 + 1 = 5. (Partitions: [4], [3+1], [2+2], [2+1+1], [1+1+1+1]).

**Row n=5 (The Final Answer):**
- k=0: p(5, 0) = 0.
- k=1: Use formula. p(5, 1) = p(5, 0) + p(4, 1).
  - p(5, 0) = 0.
  - p(4, 1) = 1.
  - So p(5, 1) = 1. (Partition: [1+1+1+1+1]).
- k=2: Use formula. p(5, 2) = p(5, 1) + p(5-2, 2) = p(5, 1) + p(3, 2).
  - p(5, 1) = 1.
  - p(3, 2) = 2 (from above).
  - So p(5, 2) = 1 + 2 = 3. (Partitions: [2+2+1], [2+1+1+1], [1+1+1+1+1]).
- k=3: Use formula. p(5, 3) = p(5, 2) + p(5-3, 3) = p(5, 2) + p(2, 3).
  - p(5, 2) = 3.
  - p(2, 3): Since k > n (3 > 2), this is same as p(2, 2) = 2.
  - So p(5, 3) = 3 + 2 = 5. (Partitions: [3+2], [3+1+1], plus the three from k=2).
- k=4: Use formula. p(5, 4) = p(5, 3) + p(5-4, 4) = p(5, 3) + p(1, 4).
  - p(5, 3) = 5.
  - p(1, 4): Since k > n (4 > 1), this is same as p(1, 1) = 1.
  - So p(5, 4) = 5 + 1 = 6. (Partitions: [4+1], plus the five from k=3).
- k=5: Use formula. p(5, 5) = p(5, 4) + p(5-5, 5) = p(5, 4) + p(0, 5).
  - p(5, 4) = 6.
  - p(0, 5) = 1.
  - So p(5, 5) = 6 + 1 = 7.

**Result:**
The total number of partitions of 5 is p(5) = 7. The seven partitions are:
1. [5]
2. [4+1]
3. [3+2]
4. [3+1+1]
5. [2+2+1]
6. [2+1+1+1]
7. [1+1+1+1+1]


## From scratch, in Python

```python
def partition_count(n, k=None):
    if k is None:
        k = n
    if n == 0:
        return 1
    if k == 0:
        return 0
    return partition_count(n, k-1) + partition_count(n-k, k)

# Print the partitions count for numbers 1 to 10
for i in range(1, 11):
    print(f"p({i}) = {partition_count(i)}")
```


## What the code does

This function uses the same recurrence we derived mathematically. The Python list is not even needed—just a function with two arguments. But to understand the recursive call, think of each call as asking a smaller question, which eventually hits a base case. For example, partition_count(3, 2) calls partition_count(3, 1) and partition_count(1, 2). The first knocks the max part down to 1, the second subtracts a 2. The recursion stops when n becomes 0 (that's one valid partition) or k becomes 0 (that branch is impossible). This mirrors the mathematical steps exactly—the code is just the formula translated line by line. Note that this recursive version is straightforward but slow for larger n because it repeats the same subproblems many times (like Fibonacci). Later you can add a dictionary to cache results, but the core idea is here.


## Common misconceptions

**Order matters** — I think 1+4 and 4+1 are different partitions.

By definition, partitions ignore order. They are sets of parts, not sequences. In fact: Both 1+4 and 4+1 represent the same partition: one part of size 1 and one of size 4.

**Zero is a valid part** — I can include 0 in the sum because 0 doesn't change the total.

Partitions use only positive integers. Adding 0 would create infinite representations of the same partition. In fact: All parts must be at least 1.

**Partition count has a simple closed form** — There must be a formula like p(n) = n^2/2 to compute it directly.

No simple polynomial formula exists. The sequence grows quickly and irregularly (e.g., p(10)=42, p(20)=627). In fact: We use recurrence relations or generating functions to compute it.

**Partitions are the same as combinations** — Choosing 2 parts from n is the same as partitioning n into 2 parts.

Combinations choose distinct objects; partitions allow repeats and any number of parts. In fact: Partitions are a different combinatorial object where repetition is allowed and parts are indistinguishable.


## In short

An integer partition is a way to write a number as a sum of positive integers, ignoring order. The count p(n) grows fast and has no simple closed form, but we can compute it using a recurrence based on the largest part. This recurrence is also a natural recursive function in Python, mirroring the mathematical definition. Partitions connect to discrete mathematics, recurrences, and combinatorial counting—useful for understanding search spaces and algorithm complexity.


## Where this is used

Integer partitions appear in several places in machine learning and AI, often behind the scenes.

- **Large language models (LLMs)**: LLMs use tokenisation to break text into words or subwords. The choice of how many tokens and how they combine can be seen as a partition of a sentence into segments—although not in the strict mathematical sense, the counting of ways to split sequences is related. More concretely, the number of ways to split a sequence of length n into k parts grows like a combinatorial count, and understanding partition counts helps designers reason about the space of possible segmentations when training tokenisers.

- **Small models on devices**: When you compress a model for a phone, you often reduce the number of parameters. The ways to factor a number into its divisors are a special case of partitions (using only equal parts). Optimising the allocation of memory or compute across layers sometimes reduces to partitioning a given integer (the total memory) into parts (per-layer) that satisfy constraints—this is a variant of integer partitioning.

- **Retrieval-augmented generation (RAG)**: In RAG, you chunk documents into pieces before embedding them. The question 'how many ways can a document of length n be split into chunks of various sizes?' is exactly an integer partition problem if you allow any positive chunk size. While in practice chunks have fixed sizes, understanding the combinatorial explosion helps engineers realise why choosing chunk size is a tradeoff—too small gives too many pieces, too large loses locality.

- **Agentic systems**: An AI agent that plans a series of tool calls might break a total 'budget' of steps into a sequence of actions. The ways to schedule a fixed number of actions into phases is a partition-like problem. More conceptually, the branching factor in search trees is often counted using combinatorial methods—knowing how fast partition counts grow gives intuition for why exhaustive search is impossible.

- **Everyday applied ML**: In recommendation systems, you might partition a user's total interaction time into sessions. In forecasting, you might look at ways to decompose a total number of events into daily counts—a partitioning of the total. Even in fraud detection, you might partition a transaction amount into suspicious parts for testing. These applied uses are not always exact, but the underlying counting logic shows up when you need to enumerate possibilities skilfully.

In practice, a developer might use a recursive function like the one above to compute partition counts in a script, or use a precomputed table for small n. For large n, they'd turn to the generating function, but that is beyond this page. The key takeaway: partition counting is a classic combinatorial tool that trains the intuition for how fast discrete spaces grow—an essential perspective when designing algorithms that search or enumerate.


---

Read this on the web: https://basavapurushottam.com/learn-ai/integer-partitions
