Fact-checked by Grok 2 weeks ago

Integer partition

In and , an integer partition of a positive n is a way of writing n as a sum of positive integers in which the order of the summands does not matter. Partitions are conventionally represented in non-increasing order of parts, such as $5 = [3 + 1 + 1](/page/3-1-1) or 5 = [2 + 2](/page/2_+_2_=_?) + 1. The number of distinct partitions of n is denoted by the partition function p(n); for instance, p(4) = 5 and p(5) = 7. The for the partition function is the \prod_{k=1}^{\infty} \frac{1}{1 - x^k}, which encodes p(n) as the coefficient of x^n in its . This function was first derived by Leonhard Euler in the , marking a foundational development in the theory. In 1918, and provided the seminal asymptotic approximation p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left(\pi \sqrt{\frac{2n}{3}}\right) as n \to \infty, revealing the rapid growth of p(n). Integer partitions have profound connections to other areas of mathematics, including modular forms, q-series, and symmetric functions, and they appear in applications such as statistical mechanics and representation theory. Rademacher later refined the Hardy-Ramanujan formula into an exact in 1937, further solidifying the analytic foundations of theory.

Fundamentals

Definition

In number theory and combinatorics, an integer partition of a positive integer n is a way of expressing n as a sum of positive integers in which the order of the summands is disregarded. To avoid ambiguity arising from different orderings, each partition is conventionally written in non-increasing order as \lambda = (\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k > 0), where \sum_{i=1}^k \lambda_i = n and k \geq 1. This representation ensures that every partition of n corresponds uniquely to such a decreasing sequence of parts. The summands \lambda_i are termed the parts of the partition. The multiplicity of a specific part size m refers to the number of times m appears among the \lambda_i. The length of the partition, denoted \ell(\lambda), is the total number of parts k. The largest part is \lambda_1, the first entry in the sequence. Partitions differ fundamentally from compositions of n, which are ordered sums and number $2^{n-1}; the partitions of n are equinumerous to these only in trivial cases such as n=1 and n=2. Standard notation includes \lambda \vdash n to signify that \lambda is a of n, and p(n) to denote the total number of unrestricted partitions of n. The concept of partitions traces its origins to the , when Leonhard Euler conducted the first systematic studies, including derivations of generating functions and identities. Systematic exploration expanded in the through contributions by and others, who introduced combinatorial proofs and refinements to Euler's results.

Examples

The integer partitions of small positive integers provide concrete illustrations of the concept. For n=1, there is only one partition: $1. For n=2, the partitions are $2 and $1+1. For n=3, they are $3, $2+1, and $1+1+1. For n=4, the five partitions are $4, $3+1, $2+2, $2+1+1, and $1+1+1+1. For n=5, there are seven partitions: $5, $4+1, $3+2, $3+1+1, $2+2+1, $2+1+1+1, and $1+1+1+1+1. These examples highlight basic patterns in integer partitions. Every positive integer n has a partition consisting of a single part n, as well as a partition into n ones (all parts equal to 1). Partitions may feature repeated parts, such as $2+2 for n=4, or all distinct parts, such as $3+2 for n=5. A fundamental symmetry in unrestricted partitions equates the number of partitions of n into exactly k parts with the number of partitions of n where the largest part is k. This bijection arises from the conjugation operation on partitions, preserving the total sum while transposing the roles of part count and maximum size. Manual enumeration reveals the rapid growth of the partition function p(n), which counts the total number of partitions of n: p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11, p(7)=15, p(8)=22, p(9)=30, p(10)=42. These values can be computed by systematically listing all possible ways to sum to n with non-increasing positive integers, starting from the largest possible parts and decreasing. Ferrers diagrams offer a visual method to represent these partitions by arranging dots or boxes into rows corresponding to part sizes.

Visual Representations

Ferrers Diagrams

A Ferrers diagram provides a graphical representation of an integer \lambda = (\lambda_1, \lambda_2, \dots, \lambda_k) by arranging \lambda_i dots in the i-th row, with rows left-aligned and typically ordered in non-increasing length from top to bottom. This arrangement visually encodes the parts of the partition as horizontal rows of dots, facilitating intuitive understanding of their structure and relationships. The concept was introduced by British mathematician Norman Macleod Ferrers in the mid-19th century, as credited by J. J. Sylvester in a 1853 publication in the , where he employed these diagrams to explore properties of partitions. Ferrers diagrams offer a concrete way to derive key properties; for instance, the conjugate partition \lambda' is obtained by reflecting the diagram over its , effectively transposing the rows into columns (and vice versa). A partition is self-conjugate if the diagram remains unchanged under this reflection, meaning it is symmetric across the diagonal. To illustrate, consider the partition (4, 2, 1) of 7: 
••••
••
•
Reflecting over the main diagonal produces the diagram for the conjugate partition (3, 2, 1, 1): 
•••
••
•
•
This reflection visually demonstrates the bijection between \lambda and \lambda', preserving the total number of dots (the partitioned integer) while interchanging the number of parts and the size of the largest part. Beyond conjugation, Ferrers diagrams enable visual proofs of fundamental identities and structural analyses. The reflection itself serves as a direct combinatorial bijection, confirming that the number of partitions with a given largest part equals the number with a given number of parts. Ferrers diagrams are closely related to Young diagrams, which adapt the dot representation to filled boxes for applications in representation theory.

Young Diagrams

A Young diagram for an integer partition \lambda = (\lambda_1, \lambda_2, \dots, \lambda_k) of n is constructed by representing the partition as a left-justified array of unit squares (or boxes), where the i-th row contains exactly \lambda_i boxes, extending the geometric visualization provided by Ferrers diagrams that use dots instead of filled boxes. This box-based structure facilitates algebraic extensions, such as fillings that encode combinatorial objects. One key extension is the standard Young tableau (SYT), which fills the n boxes of a Young diagram of shape \lambda bijectively with the integers $1 through n such that entries strictly increase across each row from left to right and down each column from top to bottom. The number of SYT of shape \lambda, denoted f^\lambda, counts these valid fillings and is given by the hook-length formula: f^\lambda = \frac{n!}{\prod_{(i,j) \in \lambda} h_{i,j}}, where h_{i,j} is the hook length of the box at row i, column j, defined as one plus the number of boxes to the right (arm length) plus the number below (leg length). This formula, discovered by Frame, Robinson, and Thrall in 1953, provides an explicit product formula for f^\lambda without enumeration. The value f^\lambda also equals the dimension of the irreducible representation of the symmetric group S_n corresponding to the partition \lambda, linking Young diagrams directly to group representation theory. Alfred Young developed these diagrams in the early as a tool for studying representations of the , originating from his work on . For example, consider the partition (3,2) of $5. The Young diagram consists of two rows: the first with three boxes and the second with two boxes. 
□ □ □
□ □
A sample SYT filling is: 
1 2 3
4 5
The hook lengths for this diagram are h_{1,1} = 4, h_{1,2} = 3, h_{1,3} = 1, h_{2,1} = 2, and h_{2,2} = 1, yielding f^{(3,2)} = 5! / (4 \cdot 3 \cdot 1 \cdot 2 \cdot 1) = 5.

The Partition Function

Generating Functions

The ordinary generating function for the partition function p(n), which counts the number of unrestricted partitions of the non-negative n with p(0) = 1, is given by P(q) = \sum_{n=0}^\infty p(n) q^n = \prod_{k=1}^\infty \frac{1}{1 - q^k}. This product form arises because each positive integer k can appear any number of times (including zero) in a partition, corresponding to the \frac{1}{1 - q^k} = \sum_{m=0}^\infty q^{k m}, where the exponent k m tracks the total contribution from m copies of the part k. Multiplying these factors over all k generates all possible partitions, with the coefficient of q^n yielding p(n). Leonhard Euler discovered this generating function in the 1740s, prompted by a query from Philippe Naudé on counting partitions. The reciprocal of P(q) is the Euler function \varphi(q) = \prod_{k=1}^\infty (1 - q^k), which Euler related to the : an infinite product expansion equaling an alternating sum over generalized pentagonal numbers, providing a recursive way to compute partition numbers via inclusion-exclusion of partitions into distinct parts. In the early 1910s, used the properties of P(q) to derive remarkable congruences, such as p(5k + 4) \equiv 0 \pmod{5} for non-negative integers k, along with similar relations modulo 7 and 11. The series expansion of P(q) begins as $1 + q + 2q^2 + 3q^3 + 5q^4 + 7q^5 + 11q^6 + 15q^7 + 22q^8 + 30q^9 + 42q^{10} + \cdots, where the coefficients are the partition numbers up to n=10.

Recurrence Relations and Algorithms

One of the most fundamental computational tools for the partition function p(n) is the recurrence derived from Euler's , which provides an exact relation allowing iterative computation of p(n) from smaller values. The theorem implies the formula p(n) = \sum_{k \in \mathbb{Z} \setminus \{0\}} (-1)^{k-1} p\left(n - \frac{k(3k-1)}{2}\right), where the sum is over nonzero integers k, the generalized pentagonal numbers are \frac{k(3k-1)}{2} for k = \pm 1, \pm 2, \dots, p(0) = 1, and p(m) = 0 for m < 0. This recurrence terminates after finitely many terms since the pentagonal numbers grow quadratically, and it enables computation of p(n) in O(n \sqrt{n}) time when implemented iteratively up to n, as the number of relevant terms per p(n) is O(\sqrt{n}). Another exact recurrence is the Hardy-Ramanujan-Rademacher series, a convergent infinite sum expressing p(n) directly without recursion: p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty \sqrt{k} A_k(n) \frac{d}{dn} \left( \frac{1}{\sqrt{n - \frac{1}{24}}} I_{k-1}\left( \frac{\pi \sqrt{\frac{2}{3}\left(n - \frac{1}{24}\right)}}{k} \right) \right), where I_\nu is the modified of the first kind and A_k(n) are certain ; this formula, finalized by Rademacher in 1937, improves upon the 1918 Hardy-Ramanujan asymptotic approximation by providing precise values for any n. It supports exact computation for large n but requires numerical evaluation of special functions, making it suitable for high-precision arithmetic rather than simple iteration. Practical algorithms for computing p(n) include a naive recursive approach with memoization, which follows the definition by summing over the largest part but becomes inefficient for large n due to exponential growth without optimization. A more efficient dynamic programming method uses a sieve-like array initialization where p{{grok:render&&&type=render_inline_citation&&&citation_id=0&&&citation_type=wikipedia}} = 1, and for each possible part size i from 1 to n, increments p += p[j - i] for j \geq i, achieving O(n^2) time to compute all p(k) for k \leq n. The pentagonal recurrence offers a superior O(n \sqrt{n}) alternative for sequential computation up to large n, balancing speed and simplicity without needing advanced functions. The rapid growth of p(n) is evident in small values, as shown in the following table:
np(n)
11
22
33
45
57
611
715
822
930
1042
1156
1277
13101
14135
15176
16231
17297
18385
19490
20627
These values illustrate the function's exponential increase, with p(20) = 627 already substantial. Rademacher's 1937 exact formula marked a significant advancement in the 1930s, transforming the Hardy-Ramanujan asymptotic series into a fully convergent exact expression and enabling reliable computation for arbitrarily large n.

Types of Restricted Partitions

Distinct and Odd Parts

Integer partitions into distinct parts require that all summands are unique positive integers, such as the partitions of 5 given by (5), (4+1), and (3+2). The generating function for the number of such partitions of n, denoted p_d(n), is \prod_{k=1}^\infty (1 + q^k). Partitions into odd parts, in contrast, allow repetitions but restrict each part to an odd positive integer, as seen in the partitions of 5: (5), (3+1+1), and (1+1+1+1+1). The generating function for the number of these partitions, denoted p_o(n), is \prod_{k=1}^\infty \frac{1}{1 - q^{2k-1}}. Euler's theorem establishes that p_o(n) = p_d(n) for all positive integers n, meaning the number of partitions into odd parts equals the number into distinct parts. This identity follows from equating the two generating functions, providing a foundational result in partition theory. A bijective proof of Euler's theorem was provided by Glaisher in 1883 through an explicit map between the sets of odd-part and distinct-part partitions. In Glaisher's bijection, starting from a partition into odd parts, the multiplicity of each odd number $2m+1 is expressed in binary as $2^{a_1} + 2^{a_2} + \cdots + 2^{a_r} with a_1 > a_2 > \cdots > a_r \geq 0; this is replaced by r distinct parts $2^{a_i} (2m+1) for each such group, yielding a distinct-part partition, with the process reversible. For example, consider the odd-part partition (3 + 1 + 1) of 5. The multiplicity of 1 is 2 = $2^1, which is replaced by the single part $2^1 \cdot 1 = 2. The multiplicity of 3 is 1 = $2^0, replaced by $2^0 \cdot 3 = 3. Thus, it maps to the distinct-part partition (3 + 2). This equality p_o(n) = p_d(n) has applications in variants of the pentagonal number theorem, where the generating function \prod_{k=1}^\infty (1 + q^k) relates to the reciprocal of the Euler function and aids in deriving recurrence relations for restricted partition counts.

Conjugate and Self-Conjugate Partitions

In integer partition theory, the conjugate partition of a given partition \lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k) of a positive integer n, denoted \lambda', is defined by \lambda'_i = |\{ j \mid \lambda_j \geq i \}\| for i = 1, 2, \dots, \lambda_1, which counts the number of parts in \lambda that are at least i. This construction establishes a bijection between partitions via reflection of the corresponding Ferrers diagram over its main diagonal, where rows become columns and vice versa. The operation of conjugation is an involution on the set of all partitions of n, meaning applying it twice yields the original partition, and it preserves the integer n since the total number of dots in the diagram remains unchanged. Key properties of conjugate partitions include that the number of parts in \lambda equals the largest part \lambda'_1 of \lambda', and symmetrically, the largest part \lambda_1 of \lambda equals the number of parts in \lambda'. For example, the partition (4,1,1) of 6 has conjugate (3,1,1,1), as there are three parts at least 1, one part at least 2, and one part at least 3 (with no parts at least 4). In contrast, (3,2,1) of 6 is self-conjugate, satisfying \lambda = \lambda', because its Ferrers diagram is symmetric across the main diagonal: three parts at least 1, two at least 2, and one at least 3. Self-conjugate partitions represent the fixed points under the conjugation involution and correspond visually to symmetric Young diagrams. The enumeration of self-conjugate partitions of n, denoted sc(n), is combinatorially significant as it equals the number of partitions of n into distinct parts. The generating function for sc(n) is \sum_{n=0}^\infty sc(n) q^n = \prod_{k=1}^\infty (1 + q^{2k-1}), reflecting the choice of including or excluding each exponent in the product. This connection highlights self-conjugate partitions as fixed points in the conjugation action, with applications in combinatorial identities and studies within theory.

Bounded Parts or Number of Parts

Integer partitions can be restricted by bounding the size of the largest part or the total number of parts. The number of partitions of a positive integer n with largest part at most k, denoted here as p(n \mid \lambda_1 \leq k), counts the ways to write n as a sum of positive integers each no larger than k, disregarding order. The generating function for these partitions is \prod_{i=1}^k \frac{1}{1 - q^i}, where the coefficient of q^n gives p(n \mid \lambda_1 \leq k)./04%3A_Generating_Functions/4.02%3A_Generating_Functions_for_Integer_Partitions) By the conjugation of partitions, which transposes the Ferrers diagram to obtain the conjugate partition, there is a between partitions of n with largest part at most k and those with at most k parts. Thus, p(n \mid \lambda_1 \leq k) = p(n \mid \ell(\lambda) \leq k), where \ell(\lambda) denotes the number of parts in \lambda. The number of partitions of n into exactly k parts, denoted p(n, k), satisfies the p(n, k) = p(n-1, k-1) + p(n-k, k), with boundary conditions p(n, k) = 0 if n < 0 or k < 0, p(0, k) = 0 for k > 0, p(n, 0) = 0 for n > 0, and p(0, 0) = 1. This recurrence arises by considering whether the smallest part is 1 (reducing to p(n-1, k-1)) or all parts are at least 2 (subtracting 1 from each part to get p(n-k, k)). By conjugation, p(n, k) also equals the number of partitions of n with largest part exactly k. For example, the partitions of 5 with at most 2 parts are $5, $4+1, and $3+2, so p(5 \mid \ell(\lambda) \leq 2) = 3. Similarly, the partitions into exactly 2 parts are $4+1 and $3+2, so p(5, 2) = 2. The values of p(n, k) for small n and k are shown in the following table:
n \setminus k12345
110000
211000
311100
412110
512211
These values can be computed using the recurrence. When k = n, p(n, n) = 1, corresponding to the single partition consisting of n ones; this aligns with the unique composition of n into n parts, all ones.

Plane Partitions and Gaussian Binomials

A plane partition is a two-dimensional analog of an integer partition, represented as a finite array of nonnegative integers \pi = (\pi_{i,j})_{i,j \geq 1} that is weakly nonincreasing in each row and each column (i.e., \pi_{i,j} \geq \pi_{i,j+1} and \pi_{i,j} \geq \pi_{i+1,j} for all i,j), with only finitely many nonzero entries. The size | \pi | of the plane partition is the sum \sum_{i,j} \pi_{i,j}. This structure generalizes the one-dimensional case, where rows or columns collapse to a single sequence, and was first systematically studied by Percy A. MacMahon in his 1915–1916 treatise on combinatory analysis. For small sizes, plane partitions illustrate their combinatorial richness. The plane partitions of size 2 consist of three: the $1 \times 1 array (2); the $1 \times 2 array (1,1); and the $2 \times 1 array \begin{pmatrix} 1 \\ 1 \end{pmatrix}. For size 3, examples include the $1 \times 1 array (3); the $1 \times 3 array (1,1,1); the $3 \times 1 array \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}; the $1 \times 2 array (2,1); and a $2 \times 2 array such as \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}. The enumeration of plane partitions is intimately connected to Gaussian binomial coefficients, which provide the generating function for the basic bounded case corresponding to height at most 1. Gaussian binomial coefficients, or q-binomial coefficients, are q-analogs of ordinary binomial coefficients, defined as \binom{a+b}{a}_q = \prod_{i=1}^{a} \frac{(1 - q^{b+1})(1 - q^{b+2}) \cdots (1 - q^{b+i})}{(1 - q)(1 - q^2) \cdots (1 - q^i)}, and were originally introduced by Carl Friedrich Gauss in his investigations of q-series and quadratic residues. An equivalent product form is \binom{a+b}{a}_q = \prod_{i=1}^a \prod_{j=1}^b \frac{1 - q^{a + b + 1 - i - j}}{1 - q^{i + j - 1}}. When q=1, this reduces to the ordinary binomial coefficient \binom{a+b}{a}, counting the number of plane partitions of height at most 1 (i.e., 0-1 arrays) fitting inside an a \times b rectangle, which are precisely the Ferrers diagrams of partitions with at most a parts each of size at most b. The full q-series enumerates these with weight q^{|\pi|}. For general plane partitions fitting inside an a \times b rectangle (unbounded height), the generating function is the more intricate product \prod_{i=1}^a \prod_{j=1}^b \frac{1}{1 - q^{i+j-1}}. For plane partitions of fixed size n without spatial bounds, the enumeration is given by the partition function for plane partitions pp(n), with generating function \sum_{n=0}^\infty pp(n) q^n = \prod_{k=1}^\infty (1 - q^k)^{-k}. Bounded plane partitions, such as those inside an a \times b \times c box (at most a rows, b columns, and entries at most c), are enumerated by MacMahon's classical product formula \prod_{i=1}^a \prod_{j=1}^b \prod_{k=1}^c \frac{i+j+k-1}{i+j+k-2}, $$ with a $q$-analog variant derivable via a hook-content formula adapted from the one-dimensional case, weighting by $q^{|\pi|}$ and incorporating hook lengths and contents of the positions in the array.[](https://math.mit.edu/~rstan/pubs/pubfiles/12-2.pdf) ## Structural Properties ### Durfee Square and Rank The Durfee square of an [integer](/page/Integer) partition $\lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_{\ell(\lambda)})$ is the largest integer $d$ such that $\lambda_i \geq d$ for all $1 \leq i \leq d$, or equivalently, the side length of the largest square that fits in the top-left corner of the Ferrers diagram of $\lambda$.[](https://mathworld.wolfram.com/DurfeeSquare.html) This $d \times d$ square represents the "core" geometric feature capturing the initial [descent](/page/Descent) in part sizes. Every partition possesses a unique Durfee square, as the condition defines a maximal such $d$.[](https://mathworld.wolfram.com/DurfeeSquare.html) The size of the Durfee square remains invariant under conjugation of the partition.[](https://mathworld.wolfram.com/DurfeeSquare.html) The Ferrers diagram of $\lambda$ decomposes uniquely into the Durfee square of size $d$, together with a partition $\mu$ of at most $d$ parts attached to the right of the square (formed by subtracting $d$ from each of the first $d$ parts of $\lambda$), and a partition $\nu$ into at most $d$ parts attached below the square (the skew diagram below the square).[](https://garsia.math.yorku.ca/~zabrocki/math5020fw0910/handouts/proofDsquare.pdf) This decomposition facilitates recursive analyses and [generating function](/page/Generating_function) derivations for the partition function, as the total size $|\lambda| = d^2 + |\mu| + |\nu|$. For example, consider $\lambda = (5,3,1)$: here $d=2$ since $5 \geq 2$, $3 \geq 2$, but $1 < 3$; the right attachment is $(3,1)$ (at most 2 parts), and the below attachment is $(1)$ (at most 2 parts).[](https://garsia.math.yorku.ca/~zabrocki/math5020fw0910/handouts/proofDsquare.pdf) The rank of a partition, introduced by [Freeman Dyson](/page/Freeman_Dyson) in 1944, provides another structural measure: $\rank(\lambda) = \lambda_1 - \ell(\lambda)$, the difference between the largest part and the number of parts (length).[](https://arxiv.org/abs/2203.08987) This integer-valued statistic can be positive, zero, or negative and reflects the imbalance between the diagram's width and height. The generating function for ranks over all partitions is $\sum_{\lambda} q^{|\lambda|} x^{\rank(\lambda)} = \prod_{k=1}^\infty \frac{1 + x q^k}{1 - q^k}$.[](https://annals.math.princeton.edu/wp-content/uploads/annals-v171-n1-p08-p.pdf) [Dyson](/page/Dyson) proposed the rank to study symmetries in partitions modulo primes, particularly for bijectively proving Ramanujan congruences like $p(5m+4) \equiv 0 \pmod{5}$, by grouping partitions into equal-sized classes based on rank modulo 5.[](https://mathworld.wolfram.com/PartitionFunctionPCongruences.html) However, the rank fails to fully separate certain congruence classes, prompting [Dyson](/page/Dyson) to suggest an alternative statistic, the [crank](/page/Crank). The crank of $\lambda$, also introduced by Dyson in 1944 without an explicit definition at the time, is defined as the largest part $\lambda_1$ if $\lambda$ contains no part equal to 1, and otherwise as the number of parts of $\lambda$ strictly larger than the multiplicity of 1 in $\lambda$. This non-negative integer better captures the desired equidistribution for Ramanujan congruences; for instance, the number of partitions of $5m+4$ with crank congruent to 0 [modulo](/page/Modulo) 5 equals $p(5m+4)/5$. Andrews and Garvan later provided a combinatorial realization of the crank in 1988, establishing bijective proofs for the modulo 5 and 7 cases and enabling extensions to higher moduli. ### Young's Lattice Young's lattice is the [partially ordered set](/page/Partially_ordered_set) whose elements are all integer [partitions](/page/Partition), with λ ≤ μ if and only if the Young diagram of λ is contained within the Young diagram of μ.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) A covering relation μ covers λ if μ is obtained from λ by adding exactly one box to the Young diagram, ensuring no skips in the growth process.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) This poset is infinite and graded, with the rank of a partition λ given by its size |λ|, so that the number of elements at rank n equals p(n), the number of unrestricted partitions of n.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) As a distributive lattice, Young's lattice admits a symmetric chain decomposition, partitioning its elements into disjoint symmetric chains that span symmetric ranks around the center.[](https://math.mit.edu/~rstan/pubs/pubfiles/77.pdf) This property underscores its combinatorial richness and facilitates proofs of unimodality and Sperner properties in its ranks.[](https://math.mit.edu/~rstan/pubs/pubfiles/77.pdf) Named after Alfred Young, who introduced Young diagrams in his foundational work on the representation theory of the symmetric group, the lattice's structure was further explored in the 1950s through combinatorial studies related to tableaux and symmetric group characters.[](https://www-users.cse.umn.edu/~reiner/REU/REU2018notes/StanleyAlgComb_prepublishing.pdf)[](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B1533D44F5B1DBF6B6903C79AFFDCFEE/S0008414X00023749a.pdf/div-class-title-the-hook-graphs-of-the-symmetric-group-div.pdf) Young's lattice models the incremental growth of Young tableaux: a standard Young tableau of shape μ corresponds to a saturated (maximal) chain from the empty partition ∅ to μ, where each step adds one box in a valid position.[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) The number of such chains from ∅ to a partition λ of size n is given by the hook-length formula: f^\lambda = \frac{n!}{\prod_{u \in \lambda} h_u(\lambda)}, where $h_u(\lambda)$ is the hook length of cell $u$ in the diagram of λ, counting the cells to the right, below, and including $u$ itself.[](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B1533D44F5B1DBF6B6903C79AFFDCFEE/S0008414X00023749a.pdf/div-class-title-the-hook-graphs-of-the-symmetric-group-div.pdf) This formula quantifies the dimension of the [irreducible representation](/page/Irreducible_representation) of the [symmetric group](/page/Symmetric_group) $S_n$ indexed by λ.[](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B1533D44F5B1DBF6B6903C79AFFDCFEE/S0008414X00023749a.pdf/div-class-title-the-hook-graphs-of-the-symmetric-group-div.pdf) The [lattice](/page/Lattice) also connects to the representation theory of the general linear group GL(n,ℂ), where irreducible polynomial representations are parametrized by partitions with at most n parts; the poset structure encodes the branching rules for restricting representations from GL(n+1) to GL(n).[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) For a concrete illustration, consider the subposet of all partitions λ ≤ (2,1). This includes the elements ∅, (1), (2), (1,1), and (2,1), ordered by inclusion: ∅ is covered by (1) and nothing else in this subposet; (1) covers ∅ and is covered by (2) and (1,1); (2) and (1,1) are each covered by (2,1).[](https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf) ## Probabilistic and Asymptotic Aspects ### Random Partitions In the [uniform](/page/Uniform) model for random [integer](/page/Integer) [partitions](/page/Partition), a [partition](/page/Partition) of the [integer](/page/Integer) n is selected uniformly at random from the set of all p(n) possible partitions. This model provides a natural [probability space](/page/Probability_space) for studying the typical properties of partitions as n becomes large. A related but distinct model is the Plancherel measure on partitions of n, which assigns probability (f^λ)^2 / n! to the partition λ, where f^λ is the number of standard Young tableaux of [shape](/page/Shape) λ, computed via the hook-length [formula](/page/Formula). The Plancherel measure arises in the [representation theory](/page/Representation_theory) of the [symmetric group](/page/Symmetric_group) S_n and is connected to the [uniform distribution](/page/Uniform_distribution) on standard Young tableaux of size n.[](https://link.springer.com/article/10.1007/BF02355807) For large n, the typical shape of a random [partition](/page/Partition) under the uniform model, when appropriately scaled (row lengths by √n and column lengths by (√(6n)/π) log n or similar), has its boundary approximating the [limit](/page/Limit) [curve](/page/Curve) derived by Vershik, given implicitly by the solution to a variational problem, distinct from the Vershik-Kerov-Logan-Shepp [curve](/page/Curve) of the Plancherel measure. The largest part λ_1 is asymptotically \frac{2}{\sqrt{6}} \sqrt{n} \log n, while the expected number of parts is asymptotically \frac{\sqrt{6}}{\pi} \sqrt{n} \log n. The probability that a random [partition](/page/Partition) is self-conjugate is asymptotically \frac{1}{\sqrt{n}}.[](https://www.sciencedirect.com/science/article/pii/0001870877900305)[](https://link.springer.com/article/10.1007/BF02355807)[](https://www.math.tugraz.at/~grabner/Publications/PartitionStatistics.pdf) To simulate random partitions under the uniform model, the Vershik-Kerov algorithm can be used, which generates partitions by a dynamic growth process that adds parts successively while maintaining the [uniform distribution](/page/Uniform_distribution) in the limit as n increases. This approach leverages the recursive structure of partitions and the asymptotic behavior to produce samples efficiently for large n.[](https://www.mathnet.ru/eng/mmj31) The asymptotic shape of random partitions was first derived in the 1970s by [Logan](/page/Logan) and Shepp, who solved a variational problem to find the limit form for the Plancherel measure, and independently by Vershik and Kerov, who also contributed to the [uniform](/page/Uniform) measure case. These seminal works laid the [foundation](/page/Foundation) for probabilistic aspects of [partition](/page/Partition) [theory](/page/Theory).[](https://www.sciencedirect.com/science/article/pii/0001870877900305)[](https://link.springer.com/article/10.1007/BF02355807) ### Asymptotic Behavior The asymptotic behavior of the partition function $p(n)$, which counts the number of unrestricted integer partitions of $n$, is captured by the leading term derived using the [Hardy](/page/Hardy)–Ramanujan circle method: p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left( \pi \sqrt{\frac{2n}{3}} \right) as $n \to \infty$. This formula, established in 1918, reveals the exponential growth dominated by the term $\exp\left( \pi \sqrt{2n/3} \right)$, with the prefactor providing subexponential corrections.[](https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-17.1.75) Refinements to this approximation were provided by Rademacher in [1937](/page/1937) through an exact infinite series representation for $p(n)$: p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty \sqrt{k} A_k(n) I_{3/2} \left( \frac{\pi \sqrt{24n-1}}{6k} \right), where $A_k(n)$ are coefficients involving Kloosterman sums and $I_{3/2}$ is a modified [Bessel function](/page/Bessel_function); this series converges rapidly to $p(n)$, and its first term asymptotically matches the Hardy–Ramanujan [formula](/page/Formula), with the truncation error bounded by $O(n^{-1/4})$. For restricted partitions, the number $q(n)$ of partitions into distinct parts admits the asymptotic q(n) \sim \frac{1}{4 \cdot 3^{1/4} n^{3/4}} \exp\left( \pi \sqrt{\frac{n}{3}} \right) as $n \to \infty$, obtained via a variant of the circle method. This was first derived by Lehner in 1941. Since the number of partitions into odd parts equals $q(n)$ by [Euler's theorem](/page/Euler's_theorem), it shares the same asymptotic growth. The slower exponential growth compared to unrestricted partitions reflects the stricter constraints on part selection. These asymptotics explain the superexponential increase in partition counts, underscoring their combinatorial richness. The [generating function](/page/Generating_function) $\sum p(n) q^n = \prod_{k=1}^\infty (1 - q^k)^{-1}$ is the reciprocal of the [Dedekind eta function](/page/Dedekind_eta_function), a fundamental [modular form](/page/Modular_form) of weight 1/2 for the [modular group](/page/Modular_group) SL(2,ℤ), linking partitions to [analytic number theory](/page/Analytic_number_theory). In modern physics, post-2000 developments in [string theory](/page/String_theory) connect the Hardy–Ramanujan growth to [black hole](/page/Black_hole) [entropy](/page/Entropy): the [microstate](/page/Microstate) counting for certain supersymmetric black holes in heterotic string compactifications yields partition functions whose large-$n$ asymptotics match the Bekenstein–Hawking area law $S = A/4$, providing a quantum explanation for classical [entropy](/page/Entropy). To illustrate the accuracy of the [Hardy](/page/Hardy)–Ramanujan approximation, the following table compares exact values of $p(n)$ with the asymptotic estimates for selected large $n$: | $n$ | Exact $p(n)$ | Asymptotic approximation | |-------|---------------------------------|--------------------------------| | 100 | 190,569,292 | 199,178,532 | | 1000 | 24,061,467,864,032,622,473,692,149,727,991 | 24,061,467,867,287,944,000,000,000,000,000,000,000 | The relative error decreases with $n$, approaching zero asymptotically.[](http://www.numericana.com/data/partition.htm)