(DEMO VERSION)

 A partition of a positive integer n is a representation of n as a sum of positive integers, where the order of the summands does not matter. For example, the partitions of 4 are \[ 4, \qquad 3+1, \qquad 2+2,\qquad 2+1+1 \qquad \text{ and } \qquad 1+1+1+1. \]   The individual summands are termed the parts of the partition.The notation p(n ) is used to denote the number of partitions of n , so that, for example, p(4) = 5, since, from just above, there are five partitions of 4.
Similarly, one can easily compute that p(1)=1,  p(2)=2,  p(3) = 3,  p(4) = 5,  p(5) = 7,  p(6) = 11 and p(7) = 15. By convention, p(0) is set equal to 1.

  The function p(n ) increases rapidly with n , and it is difficult to compute p(n ) directly for large n . As an example, p(200) =3,972,999,029,388. The following table shows this growth up to \(n=1000\): $$ \begin{array}{c|c} n&p(n)\\ \hline 10 & 42 \\ 20 & 627 \\ 30 & 5604 \\ 40 & 37338 \\ 50 & 204226 \\ 60 & 966467 \\ 70 & 4087968 \\ 80 & 15796476 \\ 90 & 56634173 \\ 100 & 190569292 \\ 200 & 3972999029388 \\ 300 & 9253082936723602 \\ 400 & 6727090051741041926 \\ 500 & 2300165032574323995027 \\ 600 & 458004788008144308553622 \\ 700 & 60378285202834474611028659 \\ 800 & 573305217232142250445691197 9 \\ 900 & 415873681190459054784114365 430 \\ 1000 & 240614678640326224736921497 27991 \end{array}\\ \text{Table 1.} $$

 George Andrews states in [1] that while the first person to discuss integer partitions was probably Leibniz, the first person to make a systematic study of some of their properties was Leonhard Euler. One of Euler's [E1] achievement's was to determine the generating function for the sequence \(\{p(n)\}_{n=0}^{\infty}\), by showing that \[ \sum_{n=0}^{\infty} p(n)q^n = \frac{1}{(1-q)(1-q^2)(1-q^3)\dots (1-q^k)\dots} =\frac{1}{\prod_{k=1}^{\infty}1-q^k}. \]   For more on generating functions in connection with partition functions, see Generating Functions for Partitions page.

  Euler also derived a recurrence relation for the sequence p(n), which allowed the values of p(n) to be computed recursively: \begin{multline} p(n)-(p(n-1)+p(n-2))+(p(n-5)+p(n-7))-\\\dots - (-1)^k(p(n-k(3k-1)/2)+p(n-k(3k+1)/2))-\dots=0 \end{multline} The sum of course terminates once k is large enough, and \( n\pm k(3k-1)/2< 0 \). Recurrence relations for partition counting functions are discussed further on the Recurrence Formulae for Partition Functions page.
  Euler also considered partition functions with restrictions on the summands, and showed that the number of partitions of any positive integer \(n\) into odd parts equals the number of partitions of \(n\) into distinct parts. For example, if \(n=7\), there are five partitions into distinct parts, \[ 7, \quad 6+1, \quad 5+ 2, \quad 4+ 3, \quad 4+2+1, \] and five partitions into odd parts, \[ 7, \quad 5+ 1+ 1, \quad 3+ 3+ 1, \quad 3+1+ 1+ 1+ 1, \quad 1+ 1+ 1+ 1+ 1+ 1+ 1. \]

  There are two principal ways of proving partition identities of this type (that the number of partitions of each positive integer \(n\) with parts of one type equals the number of partitions of \(n\) with parts of a second type).

 Firstly, one can show, for a given integer \(n\), that there is a bijection between the two types of partition, that is, each partition of the first type may be matched with a unique partition of the second type, and that after this matching process there are no partitions of the second type left over (see Combinatorial Proofs of Partition Identities).

 Secondly, one can show that the the sequences of positive integers derived from the counting functions for the two types of partitions have the same generating function (or more precisely, that one generating function can be transformed into the other by some known analytic identity, or by a sequence of analytic transformations - see Analytic Proofs of Partition Identities). Both methods are illustrated below.

  In [SF1], J.J. Sylvester introduced the graphical representation of a partition in the form of a Ferrers graph (Sylvester attributes the idea to N. M. Ferrers, who was head of Gonville and Caius' College, Cambridge, when [SF1] was written). In such a graph, a part of size \(k\) is represented by a row of \(k\) dots, and the rows are left-justified and arranged in non-increasing order from top to bottom. Each such diagram contains a unique largest square of dots (with top left corner at the top left corner of the Ferrers graph), called the Durfee square of the partition.
  For example, the Ferrers graph of the partition \(6+5+4+2+2+1\), and its associated Durfee square, is shown in Figure 1.

  If the Ferrers graph of a partition \(\lambda\) of a positive integer \(n\) is reflected across the main diagonal, a new partition of \(n\), denoted by \(\lambda'\) and called the conjugate of \(\lambda\), is obtained (see the page Conjugate and Self-conjugate Partitions for more on this topic).
  For example, the conjugate of the partition \(5+ 4+ 4+ 2+ 1\) is the partition \(5+4+ 3+ 3+ 1\)- see Figure 2.

  It is not difficult to see that the conjugate of a partition into distinct parts is a partition in which every part from 1 to the largest part occurs at least once, and vice versa, thus leading to a bijective proof the following partition identity:

  For each positive integer \(n\), let \(p_{\mathcal{D}}(n)\) denote the number of partitions of \(n\) into distinct parts, and let \(p_{\mathcal{L}}(n)\) denote the number of partitions of \(n\) in which every part from 1 to the largest part occurs at least once. Then \[ p_{\mathcal{D}}(n)=p_{\mathcal{L}}(n). \]

  As an example of an analytic proof of a partition identity, recall Euler's identity mentioned above, namely, that if \(p_{\mathcal{D}}(n)\) denotes the number of partitions of \(n\) into distinct parts, and \(p_{\mathcal{O}}(n)\) denotes the number of partitions of \(n\) into odd parts, then \[ p_{\mathcal{D}}(n)=p_{\mathcal{O}}(n). \] The corresponding generating functions (see here for details) are given by \begin{align*} \sum_{n=0}^{\infty}p_{\mathcal{D}}(n)q^n&= \prod_{k=1}^{\infty}(1+q^k),\\ \sum_{n=0}^{\infty}p_{\mathcal{O}}(n)q^n&= \frac{1}{\prod_{k=1}^{\infty}(1-q^{2k-1})}. \end{align*} then \begin{multline*} \sum_{n=0}^{\infty}p_{\mathcal{D}}(n)q^n= \prod_{k=1}^{\infty}(1+q^k) =\prod_{k=1}^{\infty}(1+q^k)\frac{(1-q^k)}{(1-q^k)} =\prod_{k=1}^{\infty}\frac{(1-q^{2k})}{(1-q^k)}\\ =\prod_{k=1}^{\infty}\frac{(1-q^{2k})}{(1-q^{2k-1})(1-q^{2k})} = \frac{1}{\prod_{k=1}^{\infty}(1-q^{2k-1})} =\sum_{n=0}^{\infty}p_{\mathcal{O}}(n)q^n. \end{multline*} Then by uniqueness of Maclaurin series, \(p_{\mathcal{D}}(n)=p_{\mathcal{O}}(n)\) for all non-negative integers \(n\), and Euler's theorem is proved.

  Of course it is also to go in the other direction, and use a partition identity to derive an analytic (basic hypergeometric) identity. For example, the generating function For the restricted partition function \(p_{\mathcal{L}}(n)\) from above is (see here for details) \begin{equation*} \sum_{n=0}^{\infty}p_{\mathcal{L}}(n)q^n =1+ \sum_{k=1}^{\infty} \frac{q^{k(k+1)/2}}{\prod_{j=1}^{k}(1-q^{j})}. \end{equation*} Thus using the fact that \(p_{\mathcal{D}}(n)=p_{\mathcal{L}}(n)\) for all non-negative integers \(n\) and equating the respective generating functions gives that \begin{equation*} 1+ \sum_{k=1}^{\infty} \frac{q^{k(k+1)/2}}{\prod_{j=1}^{k}(1-q^{j})} = \prod_{k=1}^{\infty}(1+q^k). \end{equation*} The connections between integer partitions and basic hypergeometric identities is further investigated here.

  In [MM1], P. A. MacMahon introduced his ``Omega Calculus'' as a tool for solving problems in Diophantine equations and inequalities. This computational method turns out to useful in attacking certain kinds of problems involving the generating functions for various types of partition functions. MacMahon's Omega operator, \(\Omega_\ge\), is defined by: $$\mathop{\Omega}_\ge \sum_{s_1=-\infty}^\infty \cdots \sum_{s_r=-\infty}^{\infty} A_{s_1,\dots ,s_r} \lambda_1^{s_1} \cdots \lambda_r^{s_r} := \sum_{s_1=0}^\infty \cdots \sum_{s_r=0}^{\infty} A_{s_1,\dots ,s_r},$$ where the domain of the \(A_{s_1,\dots ,s_r}\) is the field of rational functions over \(\mathbb{C}\) in several complex variables and \{\lambda_i\) are restricted to a neighborhood of the circle \(|\lambda_i|=1.\)
Note that the effect of the operator \(\Omega_\ge\) is to set any term which has at least one factor \(\lambda_i^{s_i} \) with \( s_i < 0 \) equal to 0, and to set any term \(A_{s_1,\dots ,s_r}\lambda_1^{s_1} \cdots \lambda_r^{s_r}\) with all \(s_i \geq 0\) equal to \(A_{s_1,\dots ,s_r}\) (or alternatively, in the case all \(s_i \geq 0\) , each \(\lambda_i\) is set equal to 1) .

See the page on MacMahon’s Omega Calculus for more on this topic.

Srinivasa Ramanujan also made a number of important contributions to the theory of partitions. He observed a number of partition congruences from studying a table of values of the partition function. For example, if \(n\) is an integer in the arithmetic progression \(4,9,14,19,24,29,34,\dots\), then \(p(n)\) is a multiple of 5. This is illustrated in the following table: $$ \begin{array}{c|c|c} n&5n+4&p(5n+4)\\ \hline 0 & 4 & 5 =5\times 1 \\ 1 & 9 & 30 =5\times 6 \\ 2 & 14 & 135 =5\times 27 \\ 3 & 19 & 490 =5\times 98 \\ 4 & 24 & 1575 =5\times 315 \\ 5 & 29 & 4565 =5\times 913 \\ 6 & 34 & 12310 =5\times 2462 \\ 7 & 39 & 31185 =5\times 6237 \\ 8 & 44 & 75175 =5\times 15035 \\ 9 & 49 & 173525 =5\times 34705 \\ 10 & 54 & 386155 =5\times 77231 \\ \end{array} $$ This observation may be written, using congruence notation, as $$ p(5k+4)\equiv 0 (\mod 5), \,\,\forall k\geq 0. $$ Ramanujan also discovered two other congruences: \begin{align*} p(7k+5)\equiv 0 (\mod 7), \,\,\forall k\geq 0,\\ p(11k+6)\equiv 0 (\mod 11), \,\,\forall k\geq 0. \end{align*} These two partition congruences are illustrated in the following table: $$ \begin{array}{c||c|c||c|c} n&7n+5&p(7n+5)&11n+6&p(11n+6)\\ \hline 0 & 5 & 7 =7\times 1 & 6 & 11 =11\times 1 \\ 1 & 12 & 77 =7\times11 & 17 & 297 =11\times 27 \\ 2 & 19 & 490 =7\times70 & 28 & 3718 =11\times 338 \\ 3 & 26 & 2436 =7\times348 & 39 & 31185 =11\times 2835 \\ 4 & 33 & 10143 =7\times 1449 & 50 & 204226 =11\times 18566 \\ 5 & 40 & 37338 =7\times 5334 & 61 & 1121505 =11\times 101955 \\ 6 & 47 & 124754 =7\times 17822 & 72 & 5392783 =11\times 490253 \\ 7 & 54 & 386155 =7\times55165 & 83 & 23338469 =11\times 2121679 \\ 8 & 61 & 1121505 =7\times160215 & 94 & 92669720 =11\times 8424520 \\ 9 & 68 & 3087735 =7\times441105 & 105 & 342325709 =11\times 31120519 \\ 10 & 75 & 8118264 =7\times1159752 & 116 & 1188908248 =11\times 108082568 \\ \end{array} $$ As can be seen from Table 1. above, the partition function grows very fast. There is no simple function for \(p(n)\) that shows how fast it grows, and instead one could ask for a simple formula that gives a good estimate of \(p(n)\) and at the same time indicates the order of growth of \(p(n)\). Such an approximation formula was give by Hardy and Ramanujan, who showed that $$ p(n)\sim \frac{1}{4n\sqrt{3}}\exp \left( \pi \sqrt{\frac{2n}{3}} \right) \text{ as } n \to \infty. $$ alternatively, $$ \lim_{n \to \infty} \frac{p(n)}{\frac{1}{4n\sqrt{3}}\exp \left( \pi \sqrt{\frac{2n}{3}} \right)}=1. $$ If $$ pp(n):=\frac{1}{4n\sqrt{3}}\exp \left( \pi \sqrt{\frac{2n}{3}} \right) $$ denotes the approximation to \(p(n)\) above, the following table shows that while the ratio of \(p(n)\) and \(pp(n)\) tends to 1, the difference between the two functions becomes arbitrarily large: $$ \begin{array}{c|c|c|c} n &p(n)/pp(n)&p(n)&p(n)-pp(n)\\ \hline 10 & 0.873103 & 42. & -6.10431 \\ 100 & 0.956285 & 1.90569\times 10^8 & -8.7116\times 10^6 \\ 1000 & 0.986045 & 2.40615\times 10^{31} & -3.40528\times 10^{29} \\ 10000 & 0.995573 & 3.61673\times 10^{106} & -1.60807\times 10^{104} \\ 100000 & 0.998598838736 & 2.749351056977570\times 10^{346} & -3.857689446807\times 10^{343} \\ 1000000 & 0.999556775923 & 1.471684986358223\times 10^{1107} & -6.52575456347\times 10^{1103} \\ 10000000 & 0.999859826425 & 9.20271755026045\times 10^{3514} & -1.29015866096\times 10^{3511} \\ 100000000 & 0.99995567184 & 1.760517045946249\times 10^{11131} & -7.8043940224\times 10^{11126} \\ 1000000000 & 0.99998598207 & 1.604535084280967\times 10^{35218} & -2.2492577894\times 10^{35213} \\ 10000000000 & 0.9999955671 & 1.052394346110649\times 10^{111390} & -4.665149022\times 10^{111384} \\ \end{array} $$ Thus it is clear that the approximation function \(pp(n)\) is not accurate enough to obtain exact values for \(p(n)\) for large values of \(n\). Rademacher later derived an infinite series that converges very rapidly to \(p(n)\), and in fact converges so rapidly that it can be used effectively to compute the exact value of \(p(n)\) for large \(n\). This, and similar series for other partition functions, are known as Hardy–Ramanujan-Rademacher-type series , and more information may be found on the Hardy–Ramanujan-Rademacher-type Series page.

The rank of a partition was a concept introduced by Freeman Dyson in 1944 to provide a combinatorial explanation for the Ramanujan congruences \(5k+4\equiv 0(\mod 5)\) and \(7k+5\equiv 0(\mod 7)\). The rank of a partition $$ n=\lambda_k+\lambda_{k-1}+\dots + \lambda_2+\lambda_1,\qquad \lambda_k\geq \lambda_{k-1}\geq \dots \geq \lambda_2\geq \lambda_1 $$ is defined to be \(\lambda_k - k\), namely, the largest part minus the number of parts. More information on the rank, and how it was used to prove the Ramanujan congruences modulo 5 and 7 may be found on the Rank of a Partition page.

The rank of a partition did not explain Ramanujan's third congruence, $$ p(11n+6)\equiv 0 (\mod 11). $$ However, Dyson postulated the existence of another partition statistic, which he termed the crank, and which would provide a combinatorial explanation of this third congruence. Such a partition statistic was found by Andrews and Garvan, and published in a paper in 1988.
Definition. For a partition \(\lambda\), let \(l(\lambda)\) denote the largest part of \(\lambda\), let \(\omega (\lambda )\) denote the number of 1's in \(\lambda\), and let \(\mu(\lambda )\) denote the number of parts in \(\lambda\) that are larger than \(\omega (\lambda )\). Then the crank \(c(\lambda)\) is defined by $$ c(\lambda) = \begin{cases} l(\lambda), & \text{ if } \omega (\lambda )=0,\\ \mu(\lambda )-\omega (\lambda ), & \text{ if } \omega (\lambda )>0. \end{cases} $$ More information on the crank, and how it was used to prove Ramanujan's congruence for the modulus 11, may be found on the Crank of a Partition page.

The topic of integer partitions continues to be of interest to mathematicians, with many new additions to our knowledge of them being made in recent years. More information about many of these new developments, as well as further discussion on some of more classical aspects of partitions described above, may be found by following the links below.

Analytic Proofs of Partition Identities
Asymptotic Formulae for Partition Functions
Colored Partitions
Combinatorial Proofs of Partition Identities
Conjugate and Self-conjugate Partitions
Crank of a Partition
Durfee Square
Euler Pairs and Partitions
Ferrers Graphs
Gap-Frequency Partitions
Gaussian Polynomials and Partitions
Generalized Frobenius Partitions
Generating Functions for Partitions
The Göllnitz-Gordon Identities
Hardy–Ramanujan-Rademacher-type Series
Hook Numbers and Partitions
Involutions for Partitions
k-Regular Partitions
Lecture Hall Partitions
MacMahon’s Omega Calculus
Multipartitions
Overpartitions
Partitions and Basic Hypergeometric Identities
Partition Congruences
Partitions with Initial Repetitions
Plane Partitions
Rank of a Partition
Recurrence Formulae for Partition Functions
Restricted Partition Functions
The Rogers-Ramanujan Identities
Smallest-parts Functions for Partitions
t-core Partitions
Weighted Partition Identitiess
Young Diagram

Books:

[1] Andrews, George E. The theory of partitions. Reprint of the 1976 original. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1998. xvi+255 pp. ISBN: 0-521-63766-X

[2] Andrews, George E.; Eriksson, Kimmo Integer partitions. Cambridge University Press, Cambridge, 2004. x+141 pp. ISBN: 0-521-84118-6; 0-521-60090-1

Online Lecture Notes:

[1] Chapter 8 Partitions (George E. Andrews, The Pennsylvania State University)

[2] Lecture Notes on the Theory of Partitions (Bruce C. Berndt, University of Illinois at Urbana-Champaign)

[3] Notes on partitions and their generating functions (Mark Haiman, University of California at Berkeley)

[4] Partition Bijections, a Survey (Igor Pak, University of California at Los Angeles)

[5] Lectures on Integer Partitions (Herbert S. Wilf, University of Pennsylvania)

References:

[E1] L. Euler, Introductio in Analysin Infinitorum, MarcunMichaelem Bousquet, Lausanne (1748). (link)

[SF1] J. J. Sylvester and F. Franklin A Constructive Theory of Partitions, Arranged in Three Acts, an Interact and an Exodion American Journal of Mathematics Vol. 5, No. 1 (1882), pp. 251-330. (.pdf)

[MM1] P. A. MacMahon, Combinatory analysis. Vol. I, II (bound in one volume). Reprint of An introduction to combinatory analysis (1920) and Combinatory analysis. Vol. I, II (1915, 1916). Dover Phoenix Editions. Dover Publications, Inc., Mineola, NY, 2004. ii+761 pp. (Internet Archive Online Texts)