Integer Partitions

Why Integer Partitions Matters

How many ways can you write $4$ as a sum of positive integers if order does not matter? There are five: $4$, $3+1$, $2+2$, $2+1+1$, and $1+1+1+1$. Writing $1+3$ does not add a sixth possibility: it is the same partition as $3+1$.

An integer partition describes the sizes of indistinguishable pieces that add to a total. It differs from a set partition: dividing four distinct people into unnamed groups gives a Bell number, while dividing four identical units into positive group sizes gives an integer partition. It also differs from a composition, where the order of the summands matters.

This lesson computes the partition numbers $p(0),p(1),\ldots,p(n)$ using a one-array dynamic program. The method is the unbounded coin-change counting pattern with every positive part size up to $n$ available. You will trace every update through $p(5)=7$, understand the required loop order, and implement identical Python, C++, and Java programs with checked mathematical notation and explicit modular arithmetic.

Core Concepts and Terminology

A partition of a nonnegative integer $n$ can be written as

$$n=\lambda_1+\lambda_2+\cdots+\lambda_k,\qquad \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_k\ge 1.$$

Sorting the parts into nonincreasing order gives one canonical representation, so permutations of the summands do not create new partitions. The number of parts is $k$; the largest part is $\lambda_1$ when the partition is nonempty. Multiplicity records how many times a given positive size appears.

For $n=0$, there is one empty partition, so $p(0)=1$. For $n>0$, every part must be positive. Allowing arbitrary zero-sized parts would destroy the intended finite representation. The sequence begins $1,1,2,3,5,7,11,15,22,30,42$ for $n=0$ through $10$.

A Ferrers diagram represents each part by a left-aligned row of squares. The partition $2+1+1$ has row lengths $2,1,1$ and four squares in total. These diagrams make unordered size patterns visible; the squares do not represent four individually labeled people.

For the DP, define $P_d(s)$ as the number of partitions of total $s$ using only part sizes from $1$ through $d$. Split those partitions into ones using no $d$ and ones using at least one $d$. Removing one copy of $d$ from the latter gives

$$P_d(s)=P_{d-1}(s)+P_d(s-d).$$

Use $P_0(0)=1$, $P_0(s)=0$ for $s>0$, and $P_d(s)=0$ for $s\lt 0$. The second term stays at the same allowed-part stage $d$, because the remaining partition may contain more copies of $d$.

How Integer Partitions Works, Step by Step

Allocate dp with $n+1$ zero entries and set dp[0] = 1. Initially, the empty partition is the only available object. Process part sizes $d=1,2,\ldots,n$ in the outer loop. For each $d$, visit totals $s=d,d+1,\ldots,n$ in ascending order and apply

$$\mathtt{dp}[s]\leftarrow\mathtt{dp}[s]+\mathtt{dp}[s-d].$$

The old value of dp[s] counts partitions that use only smaller sizes. The source dp[s-d] already belongs to the current stage $d$, because its index is smaller than $s$. Appending one part $d$ to each source partition counts all partitions using at least one $d$. This permits repeated copies without explicitly iterating over multiplicities.

The part-size loop must be outside the total loop. Every partition is counted when its largest allowed size becomes available, with no distinction between reordered sums. Ascending totals are also essential: descending totals would read the previous-stage source and allow each size at most once, counting partitions into distinct parts instead.

For example, while processing size $d=2$ for target $n=5$, after totals $2$ and $3$ the array is $[1,1,2,2,1,1]$. At $s=4$, update dp[4] from $1$ to $1+2=3$. The source dp[2] includes both $1+1$ and $2$, so adding another $2$ creates $2+1+1$ and $2+2$. The old partition $1+1+1+1$ remains, giving three in total.

After all sizes have been processed, dp[s] equals $p(s)$ for every $0\le s\le n$: no partition of $s$ can require a part larger than $s$. The programs reduce each addition modulo $M=1\,000\,000\,007$; the recurrence still holds for these residues.

flowchart TD
    A["Read n"] --> B{"n negative?"}
    B -->|Yes| X["Reject input"]
    B -->|No| C["dp[0..n] = 0; dp[0] = 1; d = 1"]
    C --> D{"d at most n?"}
    D -->|No| R["Return dp: p(0) through p(n) modulo M"]
    D -->|Yes| E["s = d"]
    E --> F{"s at most n?"}
    F -->|Yes| G["dp[s] = (dp[s] + dp[s - d]) mod M"]
    G --> H["s = s + 1"]
    H --> F
    F -->|No| I["d = d + 1"]
    I --> D

Worked Example with a Full Trace

Compute the prefix through $p(5)$. Start with dp equal to $[1,0,0,0,0,0]$. The entries correspond to totals $0,1,2,3,4,5$. Here are all $15$ updates, grouped by the currently allowed part size.

1. Part $d=1$: at $s=1$, $0+1=1$; at $s=2$, $0+1=1$; at $s=3$, $0+1=1$; at $s=4$, $0+1=1$; at $s=5$, $0+1=1$. After every update, the next total can reuse the current-stage count one position earlier. The completed array is $[1,1,1,1,1,1]$.
2. Part $d=2$: at $s=2$, $1+1=2$, giving $[1,1,2,1,1,1]$; at $s=3$, $1+1=2$, giving $[1,1,2,2,1,1]$; at $s=4$, $1+2=3$, giving $[1,1,2,2,3,1]$; at $s=5$, $1+2=3$, giving $[1,1,2,2,3,3]$.
3. Part $d=3$: at $s=3$, $2+1=3$, giving $[1,1,2,3,3,3]$; at $s=4$, $3+1=4$, giving $[1,1,2,3,4,3]$; at $s=5$, $3+2=5$, giving $[1,1,2,3,4,5]$.
4. Part $d=4$: at $s=4$, $4+1=5$, giving $[1,1,2,3,5,5]$; at $s=5$, $5+1=6$, giving $[1,1,2,3,5,6]$.
5. Part $d=5$: at $s=5$, $6+1=7$, giving $[1,1,2,3,5,7]$.

The final entry is $p(5)=7$. Its seven partitions are $5$, $4+1$, $3+2$, $3+1+1$, $2+2+1$, $2+1+1+1$, and $1+1+1+1+1$. Listing these canonical forms provides an independent check that no reordered sum was counted again.

The intermediate target counts also have a meaning: with allowed sizes at most $1,2,3,4,5$, the numbers of partitions of $5$ are respectively $1,3,5,6,7$. They count different allowed-size stages, rather than different numbers of parts.

Implementation in Python, C++, and Java

Each panel is a complete standalone program. It computes the prefix through $p(200)$ once, then prints the same selected entries. Stored values are $p(n)\bmod M$, where $M=1\,000\,000\,007$. The displayed values through $p(100)$ are also full counts; the $p(200)$ line is a remainder.

Python uses arbitrary-precision integers. C++ uses long long, and every addition is at most $2M-2=2\,000\,000\,012$, safely within its range. Java uses BigInteger addition and explicit reduction. No division or modular inverses are needed. Every program rejects negative $n$ and preserves dp[0] = 1 throughout the calculation.

C++ and Java accept signed 32-bit $n$, with practical sizes limited by memory and quadratic work. Their array-size calculations avoid unchecked signed overflow. Part sizes are outermost and totals increase in the inner loop, exactly as in the trace.

MOD = 1_000_000_007


def partition_numbers(n: int) -> list[int]:
    if n < 0:
        raise ValueError("n must be nonnegative")
    dp = [0] * (n + 1)
    dp[0] = 1
    for part in range(1, n + 1):
        for total in range(part, n + 1):
            dp[total] = (dp[total] + dp[total - part]) % MOD
    return dp


def main() -> None:
    samples = [0, 1, 2, 3, 4, 5, 10, 50, 100, 200]
    dp = partition_numbers(max(samples))
    print(f"modulus = {MOD}")
    for n in samples:
        print(f"p({n}) = {dp[n]}")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

constexpr long long MOD = 1'000'000'007LL;

std::vector<long long> partition_numbers(int n) {
    if (n < 0) {
        throw std::invalid_argument("n must be nonnegative");
    }
    std::vector<long long> dp(static_cast<std::size_t>(n) + 1, 0);
    dp[0] = 1;
    for (std::size_t part = 1; part < dp.size(); ++part) {
        for (std::size_t total = part; total < dp.size(); ++total) {
            dp[total] = (dp[total] + dp[total - part]) % MOD;
        }
    }
    return dp;
}

int main() {
    const std::vector<int> samples = {0, 1, 2, 3, 4, 5, 10, 50, 100, 200};
    const int maximum = *std::max_element(samples.begin(), samples.end());
    const std::vector<long long> dp = partition_numbers(maximum);
    std::cout << "modulus = " << MOD << '\n';
    for (int n : samples) {
        std::cout << "p(" << n << ") = " << dp[n] << '\n';
    }
}

import java.math.BigInteger;
import java.util.Arrays;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

    public static BigInteger[] partitionNumbers(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be nonnegative");
        }
        BigInteger[] dp = new BigInteger[Math.addExact(n, 1)];
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE;
        for (int part = 1; part < dp.length; ++part) {
            for (int total = part; total < dp.length; ++total) {
                dp[total] = dp[total].add(dp[total - part]).mod(MOD);
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        int[] samples = {0, 1, 2, 3, 4, 5, 10, 50, 100, 200};
        int maximum = 0;
        for (int n : samples) {
            maximum = Math.max(maximum, n);
        }
        BigInteger[] dp = partitionNumbers(maximum);
        System.out.println("modulus = " + MOD);
        for (int n : samples) {
            System.out.println("p(" + n + ") = " + dp[n]);
        }
    }
}

Run Python with Python 3.9 or later. Compile C++ with C++14 or later. Save Java as Main.java, compile with javac Main.java, and run with java Main. Each program prints these exact eleven lines:

• modulus = 1000000007
• p(0) = 1
• p(1) = 1
• p(2) = 2
• p(3) = 3
• p(4) = 5
• p(5) = 7
• p(10) = 42
• p(50) = 204226
• p(100) = 190569292
• p(200) = 999001584

The full count is $p(200)=3\,972\,999\,029\,388$. Its residue modulo $1\,000\,000\,007$ is $999\,001\,584$. To obtain full counts in Python or Java, remove the modular reduction while retaining arbitrary-precision integers. C++ then needs arbitrary-precision arithmetic or a proven bound on its intermediate sums; removing % MOD does not make fixed-width integers unbounded.

Complexity, Correctness, and Invariants

Part size $d$ performs $n-d+1$ additions. For $n\ge 1$, the total number of updates is

$$\sum_{d=1}^{n}(n-d+1)=\frac{n(n+1)}{2}.$$

Thus the fixed-modulus implementation takes $\Theta(n^2)$ time and $\Theta(n+1)$ storage, including its returned array. It uses $O(1)$ additional state beyond that array in the bounded-residue model. For $n=0$, time and storage are $\Theta(1)$. Negative inputs are rejected before allocation.

For a fixed $n$, best, average, and worst cases have identical update counts. There are no data-dependent early exits. The time bound is expressed in the numeric target $n$, not merely its binary encoding length. With unrestricted full counts, growing integer lengths make addition nonconstant in bit operations; the bounds here count fixed-modulus additions and stored residues.

For correctness, the outer-loop invariant is: after processing part size $d$, every dp[s] equals $P_d(s)$ modulo $M$. Before the first part size, dp[0] = 1 and all positive totals are zero, matching the stage with no available sizes.

During stage $d$, process totals in ascending order. Immediately before updating total $s$, dp[s] still contains $P_{d-1}(s)$, while the smaller source dp[s-d] contains $P_d(s-d)$. If $s-d\lt d$, that source needed no update at this stage because it cannot contain a part $d$ anyway. Adding these two counts implements the disjoint no-$d$/at-least-one-$d$ cases. Removing or appending one indistinguishable part $d$ is a bijection for the second case, so no multiplicity factor is needed.

After the final stage $d=n$, every partition of every total $s\le n$ uses only allowed sizes, proving dp[s] equals $p(s)$ modulo $M$. The use of a current-stage source explains both ascending totals and the permission to reuse a size.

Euler's alternative uses generalized pentagonal offsets $k(3k-1)/2$ and $k(3k+1)/2$:

$$p(t)=\sum_{k\ge 1}(-1)^{k-1}\left[p\!\left(t-\frac{k(3k-1)}{2}\right)+p\!\left(t-\frac{k(3k+1)}{2}\right)\right],\qquad t\ge 1.$$

Take $p(0)=1$ and $p(t)=0$ for $t\lt 0$. Only $O(\sqrt t)$ offsets contribute to each $p(t)$. The first offsets are $1,2,5,7,12,15$, with signs $+,+,-,-,+,+$. This gives a useful independent check on the simpler allowed-size DP.

Variants, Pitfalls, and Optimizations

Distinguish partitions, compositions, and set partitions. Integer partitions ignore summand order and use indistinguishable units. Compositions retain summand order; for total $4$, there are eight compositions but only five partitions. Set partitions group distinct objects; four distinct labels have $15$ set partitions, not $p(4)=5$.

Use the loop direction that matches multiplicity. Ascending totals permit unlimited copies of the current size. Descending totals permit each size at most once and count partitions into distinct parts. Moving the total loop outside the part loop instead counts ordered compositions when every positive size is available. Each schedule corresponds to a different counting model.

Keep allowed sizes positive and unique. A zero part does not belong in the ordinary partition model. Repeating the same allowed size as though it were a new type also changes the count. For a coin-change variant, deduplicate denomination values unless the problem deliberately distinguishes types. Keep dp[0] = 1: it is the one empty remainder that completes a partition using a part equal to the target.

Restrict the largest part or the number of parts deliberately. To allow only sizes at most $m$, stop the outer loop at $\min(m,n)$. To count exactly $k$ positive parts, introduce a part-count state. One recurrence is

$$Q(n,k)=Q(n-1,k-1)+Q(n-k,k),\qquad n\ge k\ge 1,$$

with $Q(0,0)=1$ and impossible cases zero. The first case removes a part $1$; the second subtracts one from every part when all parts are at least two. Transposing a Ferrers diagram, called conjugation, exchanges its number of parts and its largest part, proving that partitions into at most $k$ parts are equinumerous with partitions whose largest part is at most $k$.

Use generating functions to explain variants. For unrestricted partitions,

$$\sum_{n\ge 0}p(n)x^n=\prod_{d\ge 1}\frac{1}{1-x^d}.$$

The factor $1+x^d+x^{2d}+\cdots$ chooses a multiplicity for size $d$. For distinct parts, replace that factor with $1+x^d$. Euler's identity says partitions into distinct parts are equinumerous with partitions into odd parts; for total $5$, each count is three. These are restricted variants, so neither count is the unrestricted $p(5)=7$.

Choose a method for the scale and output. The one-array DP makes restrictions easy to express, while the pentagonal recurrence reduces the arithmetic work for unrestricted large prefixes. Listing partitions remains output-dependent even if the count is computed quickly. Modular residues are suitable only when the requested output is a remainder; they do not list partitions, provide full counts, or automatically define a uniform sampler.

Practice Problems and Real-World Use

Before choosing the recurrence, decide whether units are indistinguishable, whether group or destination labels matter, whether order matters, and whether each size may repeat. Ordinary integer partitions describe unlabeled size profiles. Assigning amounts to named recipients is a different problem because exchanging the recipients can change an outcome.

The allowed-size DP also counts unordered coin selections with unlimited supply, provided each denomination is treated as one size type. It counts selections, not the order in which coins are handed over. For constrained batch-size profiles, the model similarly counts size patterns; it does not identify which distinct records enter each batch.

In the coin example, the four selections are $5$, $2+2+1$, $2+1+1+1$, and $1+1+1+1+1$. In a named-recipient allocation, those same amount patterns can correspond to multiple assignments, so the partition count alone is insufficient. Likewise, groupings of distinct objects generally need set-partition or assignment counts.

Verify small inputs by generating nonincreasing sequences of positive parts and counting only sequences with the requested sum. Cross-check larger prefixes with Euler's pentagonal recurrence. Include $n=0$, rejection of negative input, $p(4)=5$, $p(5)=7$, and a distinct-parts comparison where descending totals deliberately give another answer. Finally, test an index such as $200$ where modular reduction changes the displayed result.