Partition Function Calculator
Solve partition function problems step-by-step with our free calculator. See formulas, worked examples, and clear explanations.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Partition Function Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: p(n) = number of ways to write n as a sum of positive integers
Worked example — p(10) = 42 | Distinct parts: 10 | Odd parts: 10 | Hardy-Ramanujan estimate: 48
Formula
p(n) = number of ways to write n as a sum of positive integers
The partition function p(n) counts unordered representations of n as sums of positive integers. The Hardy-Ramanujan asymptotic formula approximates p(n) as (1/(4n*sqrt(3))) * exp(pi*sqrt(2n/3)). Dynamic programming computes exact values efficiently.
Worked Examples
Example 1: Computing p(10) - Partitions of 10
Problem:Find the number of ways to partition the integer 10 into sums of positive integers.
Solution:Using dynamic programming: dp[0]=1, then add each part size 1 through 10. After processing all parts: dp[10] = 42 Some partitions: 10, 9+1, 8+2, 7+3, 7+2+1, 6+4, 6+3+1, ... Distinct-part partitions: 10, 9+1, 8+2, 7+3, 7+2+1, 6+3+1, 5+4+1, 5+3+2, 4+3+2+1 = 10 Odd-part partitions: also 10 (Euler identity confirmed)
Result:p(10) = 42 | Distinct parts: 10 | Odd parts: 10 | Hardy-Ramanujan estimate: 48
Example 2: Verifying Ramanujan Congruence p(5n+4) mod 5 = 0
Problem:Check that p(4), p(9), p(14), and p(19) are all divisible by 5.
Solution:p(4) = 5 = 5 * 1 p(9) = 30 = 5 * 6 p(14) = 135 = 5 * 27 p(19) = 490 = 5 * 98 All are divisible by 5, confirming the congruence.
Result:p(4)=5, p(9)=30, p(14)=135, p(19)=490 - all divisible by 5
Frequently Asked Questions
What is the partition function p(n) in number theory?
The partition function p(n) counts the number of distinct ways a positive integer n can be written as a sum of positive integers, where the order of summands does not matter. For example, p(4) = 5 because 4 can be partitioned as 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. The function grows extremely rapidly: p(10) = 42, p(50) = 204,226, and p(100) = 190,569,292,356. The partition function was studied extensively by Euler, Hardy, Ramanujan, and Rademacher, and it connects to deep areas of modular forms, combinatorics, and representation theory. It has applications in statistical mechanics and quantum physics.
What is the Hardy-Ramanujan asymptotic formula for partitions?
In 1918, G.H. Hardy and Srinivasa Ramanujan proved that the partition function grows asymptotically as p(n) ~ (1 / (4n * sqrt(3))) * exp(pi * sqrt(2n/3)). This was one of the first applications of the circle method in analytic number theory. The formula shows that p(n) grows sub-exponentially but faster than any polynomial. For large n, the approximation becomes remarkably accurate in relative terms. Rademacher later improved this to an exact convergent series in 1937, providing a way to compute p(n) precisely. The Hardy-Ramanujan result is considered one of the most beautiful achievements in analytic number theory.
What is Euler distinct-odd partition theorem?
Euler proved that for any positive integer n, the number of partitions into distinct parts equals the number of partitions into odd parts. For example, for n = 5: the distinct partitions are 5, 4+1, 3+2, giving 3 partitions; the odd-part partitions are 5, 3+1+1, 1+1+1+1+1, also giving 3. This elegant identity can be proven using generating functions, where the generating function for distinct partitions is the product of (1+x^k) for k = 1,2,3,..., which equals the product of 1/(1-x^(2k-1)), the generating function for odd partitions. This identity is one of the foundational results in the theory of integer partitions and combinatorial identities.
How are partitions computed efficiently with dynamic programming?
The most practical method for computing p(n) uses dynamic programming based on the recurrence relation from Euler pentagonal number theorem or a straightforward bottom-up table. In the DP approach, we build a table where dp[j] represents the number of partitions of j. We iterate through each possible part size k from 1 to n, and for each j from k to n, we add dp[j-k] to dp[j]. Starting with dp[0] = 1 (the empty partition), this fills the table in O(n^2) time and O(n) space. For very large n, Rademacher exact formula or implementations using modular arithmetic and the pentagonal number theorem can be faster than the full DP computation.
What are Ramanujan congruences for the partition function?
Ramanujan discovered remarkable divisibility patterns in the partition function. He proved that p(5n+4) is always divisible by 5, p(7n+5) is always divisible by 7, and p(11n+6) is always divisible by 11. For example, p(4) = 5, p(9) = 30, p(14) = 135, and p(19) = 490 are all divisible by 5. These congruences were later understood as consequences of deep properties of modular forms. Ken Ono and others extended these results, showing that for any prime m >= 5, there are infinitely many congruences of the form p(An+B) divisible by m. These discoveries reveal that the partition function has hidden periodic structure governed by modular arithmetic.
What are conjugate partitions and Ferrers diagrams?
A Ferrers diagram (or Young diagram) represents a partition visually by arranging dots or boxes in left-justified rows, where each row has as many elements as the corresponding part. For example, the partition 4+2+1 of 7 is shown with 4 dots in the first row, 2 in the second, and 1 in the third. The conjugate partition is obtained by reflecting the diagram along its main diagonal, interchanging rows and columns. The conjugate of 4+2+1 is 3+2+1+1. Conjugation is an involution on partitions (applying it twice returns the original) and is fundamental to proving many partition identities, including connections between partitions with at most k parts and partitions with largest part at most k.
How do partitions appear in physics and statistical mechanics?
In statistical mechanics, integer partitions arise naturally in the study of Bose-Einstein statistics, which describes the quantum behavior of bosonic particles. The number of ways to distribute n quanta of energy among identical particles corresponds to partition counting. The partition function of statistical mechanics (sharing the name but distinct from the number-theoretic partition function) sums over all microstates of a system. In string theory, the partition function determines the number of string states at each energy level. The Hagedorn temperature in string theory is related to the exponential growth rate of partitions. These connections make partition theory essential to modern theoretical physics.
What is the pentagonal number theorem and how does it help compute partitions?
Euler pentagonal number theorem states that the product (1-x)(1-x^2)(1-x^3)... equals 1 + sum over k from 1 to infinity of (-1)^k * (x^(k(3k-1)/2) + x^(k(3k+1)/2)). The exponents k(3k-1)/2 are the generalized pentagonal numbers: 1, 2, 5, 7, 12, 15, 22, and so on. This gives a recurrence for p(n): p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + ..., with alternating signs in pairs. This recurrence computes p(n) in O(n * sqrt(n)) time, much faster than the O(n^2) DP approach. Euler original proof was algebraic, but bijective proofs now exist using Franklin involution on Ferrers diagrams.
What are restricted partitions and why do they matter?
Restricted partitions impose additional conditions on the parts, creating important subfamilies. Common restrictions include: partitions into distinct parts (no repeated values), partitions into odd parts only, partitions with at most k parts, partitions with largest part at most m, and partitions into parts from a specific set. Each restriction leads to different generating functions and counting formulas. The coin change problem in computer science is equivalent to counting partitions into parts from a given denomination set. In representation theory, restricted partitions enumerate irreducible representations of symmetric groups. Understanding restricted partitions provides tools for solving optimization, scheduling, and resource allocation problems.
What is the rank and crank of a partition?
The rank of a partition, defined by Freeman Dyson in 1944, is the largest part minus the number of parts. Dyson conjectured that the rank modulo 5 and modulo 7 would explain Ramanujan first two congruences, which was later proved by Atkin and Swinnerton-Dyer. However, the rank fails to explain the modulo 11 congruence. To resolve this, Dyson hypothesized a statistic he called the crank, which was eventually discovered by Andrews and Garvan in 1988. The crank is defined as the largest part if no 1s appear in the partition, or as the number of parts larger than the number of 1s minus the number of 1s. The crank modulo 5, 7, and 11 simultaneously explains all three Ramanujan congruences.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Bessel Function Calculator
Calculate bessel function with inputs, formulas, and instant results.
🧮Composite Function Calculator
Calculate composite function with inputs, formulas, and instant results.
🧮Error Function Calculator
Calculate error function with inputs, formulas, and instant results.
🧮Function Domain Calculator
Calculate function domain with inputs, formulas, and instant results.
🧮Function Range Calculator
Calculate function range with inputs, formulas, and instant results.
🧮Gamma Function Calculator
Calculate gamma function with inputs, formulas, and instant results.
🧮Inverse Function Calculator
Calculate inverse function with inputs, formulas, and instant results.
🧮Piecewise Function Evaluator
Calculate piecewise function evaluator with inputs, formulas, and instant results.