Integer partitions
Definitions, enumeration and constrained generation
Amirhossein Mahmoudi
Definitions, enumeration and constrained generation
Amirhossein Mahmoudi
A partition of a positive integer m is a sum of positive integers, ignoring their order.
m · total being partitioned
N · number of parts
aᵢ · size of part i
Parts may be written in any order.
Think of each part as a coin value.
Order is irrelevant. Repeated parts and [7] are allowed.
The same parts (coin values): one partition.
Part 4 then part 2, or part 2 then part 4: two sequences.
That is a different question.
Standard form: write the parts in nonincreasing order, from largest to smallest, allowing equal parts.
Each part is at least as large as the next.
Equal parts are allowed: this is not strictly decreasing order.
Sorting changes only the written order—not the partition. The generator will preserve this form as it builds each answer.
P(m) counts the partitions of the integer m.
Faster than any polynomial; slower than cᵐ for every fixed c > 1.
The symbol ∼ means the ratio tends to 1 as m grows—not exact equality.
No simple elementary closed-form formula for P(m) is known. However, its asymptotic growth is known and is shown above. Exact computation is still possible.
Goal: given a positive integer m, generate every partition of m exactly once, in standard form.
1. Try each allowed value for the next part.
2. Recursively partition the remaining sum.
3. Limit later parts to the value just chosen, preserving standard form.
When the remainder is zero, output the completed partition.
Invariant: selected-part sum + r = m. Start with r = m, B = m, N = 0.
Meaning of Rec(r, B, N): generate every completion of the current prefix a[1..N].
Try every positive next part allowed by both the bound and the remainder:
Store a[N+1] = i; subtract i from the remainder, set the next bound to i, and add one to the part count.
Base case: if r = 0, output only a[1..N] and return.
Start: empty prefix, full sum remaining. Invariant: selected-part sum + r = m.
procedure Rec(r, B, N):
if r == 0:
output a[1..N]
return
for i = 1 to min(B, r):
a[N + 1] = i
Rec(r - i, i, N + 1)
Rec(m, m, 0)Example: every call from Rec(4,4,0). Nodes show the chosen prefix and remainder; green leaves are outputs.
V counts calls (nodes): here V=12, with P(4)=5 leaves.
The teal path makes 4 choices. Generally, depth is at most m because every chosen part is positive.
Every node lies on a root-to-leaf path. Summing all path lengths gives an upper bound on the number of nodes.
Search takes O(V); output writing adds at most mP(m) parts. These are upper bounds, not exact operation counts.
Selected-part sum + remainder = m.
Output only at remainder zero.
Try every legal next part.
Follow any standard-form partition through its choices.
Parts remain nonincreasing.
One standard vector has one search path.
Each selected part reduces the remainder by at least one, so every branch terminates.
Each row contains one dot per unit of a part. Both diagrams contain seven dots.
Every part is positive and every row starts at the left: one first-column dot per row.
One coin is one part; three coins make three rows.
The three first-column dots become the first conjugate row.
New part j = how many input rows reach column j.
Rows 1 and 2 reach column 2; row 3 does not.
Every part is at most 2, and at least one part equals 2. Thus [1,1,1,1] does not qualify.
We require two parts; the largest part need not equal 2.
Conjugation maps the largest-part family to the part-count family, so we can reuse the generator.
P(m,n) counts partitions of m into exactly n parts (n coins in the analogy).
Every partition has one definite number of parts. These disjoint groups cover all partitions.
The six terms correspond to counts 1 through 6.
Example: P(6,2) = 3: [5,1], [4,2], [3,3].
Example: P(6,3) = 3: [4,1,1], [3,2,1], [2,2,2].
The floor ⌊x⌋ is the greatest integer no larger than x.
For fixed n, as m grows:
Conjugation gives the same count for largest part n (largest coin value n).
Example: count partitions of 6 into exactly 3 parts. Every partition belongs to exactly one group below.
Remove just one part equal to 1: both the sum and the part count decrease by one.
Subtract 1 from each of the three parts: the sum decreases by 3; the part count stays 3.
There is one empty partition: the empty list, with no parts and sum zero. The 1 counts arrangements, not parts.
Removing 1 from [1] leaves the empty list: one valid completion. Impossible cases have count zero.
All partitions of total m
Precondition: m ≥ 1
GenerateAll(m):
Rec(m,m,0)Example m=7, n=3: (r,B,N) = (7,7,0)
Largest part (coin value) exactly n
Precondition: 1 ≤ n ≤ m
GenerateLargest(m,n):
a[1] = n
Rec(m-n,n,1)Example m=7, n=3: (r,B,N) = (4,3,1); first choose a[1] = 3
Rec(r,B,N):
if r == 0:
output a[1..N]
else:
for i = 1..min(B,r):
a[N+1] = i
Rec(r-i,i,N+1)mnrBNaiExactly, not at most: Rec(m,n,0) is insufficient: it can omit the part n.
Goal: partitions of m into exactly n parts; example m = 7, n = 3.
procedure RecPartition2(r, B, N):
if r == 0:
b = ConjPartition(a[1..N])
output b
else:
for i = 1 to min(B, r):
a[N+1] = i
RecPartition2(r-i, i, N+1)
a[1] = n
RecPartition2(m-n, n, 1)For 1 ≤ n ≤ m: initialize as in 3.3; at each leaf output the conjugate, not a.
P(m) counts all partitions; P(m,n) counts partitions with exactly n parts.
| Algorithm / task | Where the bound comes from | Time | Space |
|---|---|---|---|
| 3.1 · All partitions | At most m parts per path and P(m) leaves. Total path lengths bound both search and output writing. | ||
| 3.2 · One conjugate | Initialize a₁ entries, then make m−a₁ increments: m operations altogether. The output array has a₁ entries. | ||
| 3.3 · Largest part n | Same search as 3.1, but only P(m,n) leaves; conjugation gives this family count. | ||
| 3.4 · Exactly n parts | Search from 3.3, plus one Θ(m) conjugation for each of its P(m,n) outputs. |
Assume unit-cost arithmetic and streamed outputs. Space includes the active stack and current output, not storage of all answers. O-bounds are upper bounds, not constant-delay claims.
Target: generate every partition of 7 into exactly 3 parts.
Preselect part 3; partition the remaining 4 with bound 3.
Conjugate each intermediate partition whose largest part is 3; the result has exactly 3 parts.
Algorithm 3.4 is this combination: at each leaf of the 3.3 search, output the conjugate instead of a.
Left: all largest-part-3 partitions. Right: all exactly-3-part partitions. The bijection preserves completeness and uniqueness.
Kreher & Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, 1999.
Use the arrow keys to change slides; use the step controls to explore partitions.