Integer Partition Calculator
Calculate the number of ways to partition a positive integer into sums of positive integers.
Enter a number n (1 to 200) to calculate p(n), the partition function
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 summands does not matter. The partition function p(n) counts the number of distinct partitions of n.
Example: The partitions of 5 are: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1. Therefore, p(5) = 7.
Key Properties: Unlike permutations and combinations, partitions do not consider the order of elements. The partition 3+2 is the same as 2+3, so we only count it once. This makes partitions fundamentally different from combinatorial selections.
Algorithm: This calculator uses dynamic programming to compute p(n) efficiently. The recurrence builds a table where dp[j] represents the number of ways to partition j using parts up to size i. The time complexity is O(n²) and space complexity is O(n).
Historical Note: The partition function was studied extensively by Euler, Ramanujan, and Hardy. Ramanujan discovered remarkable congruences like p(5n+4) being divisible by 5, and p(7n+5) being divisible by 7. The Hardy-Ramanujan asymptotic formula approximates p(n) for large n.
Applications: Integer partitions appear in statistical mechanics (counting microstates), representation theory (Young tableaux), number theory, and combinatorics. They are also used in algorithms for subset sum problems and knapsack optimization.
What is an integer partition?
An integer partition of n is a way of writing n as a sum of positive integers where order doesn't matter. For example, 4 can be partitioned as 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. Since order is irrelevant, 3+1 and 1+3 are considered the same partition.
How fast does the partition function grow?
The partition function p(n) grows incredibly fast. For example, p(10) = 42, p(50) = 204,226, and p(100) = 190,569,292. Hardy and Ramanujan discovered an asymptotic formula showing p(n) grows roughly like e^(pi*sqrt(2n/3))/(4n*sqrt(3)).
What did Ramanujan discover about partitions?
Ramanujan discovered remarkable congruences: p(5n+4) is always divisible by 5, p(7n+5) is divisible by 7, and p(11n+6) is divisible by 11. These surprising patterns sparked extensive research in partition theory and modular forms.
Where are integer partitions used?
Integer partitions appear in statistical mechanics (counting energy states), representation theory (Young tableaux), symmetric functions, and combinatorics. They're also used in algorithms for the subset sum problem and in analyzing integer compositions.