Partition Number Essentials

Cheatsheet Content

Partitions of an Integer A partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers, where the order of the summands (called parts) does not matter. The parts are usually written in non-increasing order. Notation: $p(n)$ denotes the number of partitions of $n$. Example: Partitions of $n=4$: $4$ $3+1$ $2+2$ $2+1+1$ $1+1+1+1$ So, $p(4) = 5$. Generating Function The generating function for $p(n)$ is given by: $$ \sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k} $$ Conventionally, $p(0)=1$ (representing the empty sum). Recurrence Relation (Euler's Pentagonal Number Theorem) Euler's Pentagonal Number Theorem provides a recurrence relation for $p(n)$: $$ p(n) = \sum_{k \neq 0} (-1)^{k-1} p(n - g_k) $$ where $g_k = \frac{k(3k-1)}{2}$ are the generalized pentagonal numbers. The sum is over non-zero integers $k$, and $p(m)=0$ if $m Generalized Pentagonal Numbers ($g_k$): For $k=1, 2, 3, \dots$: $1, 5, 12, 22, \dots$ For $k=-1, -2, -3, \dots$: $2, 7, 15, 26, \dots$ The sequence of $g_k$ for $k = \pm 1, \pm 2, \dots$ is $1, 2, 5, 7, 12, 15, 22, 26, \dots$ Expanded Recurrence: $$ p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \dots $$ Example: $p(0) = 1$ $p(1) = p(0) = 1$ $p(2) = p(1) + p(0) = 1+1 = 2$ $p(3) = p(2) + p(1) = 2+1 = 3$ $p(4) = p(3) + p(2) - p(-1) = 3+2-0 = 5$ Ferrers Diagrams / Young Diagrams A visual representation of a partition using dots or boxes arranged in rows. Each row corresponds to a part, and the number of dots/boxes in a row is the size of the part. Rows are arranged in non-increasing order of length. Example: Partition $5+3+1$ of $n=9$: ***** *** * Conjugate Partition: Obtained by transposing the Ferrers diagram (swapping rows and columns). The conjugate of $5+3+1$ is $3+2+2+1+1$. This corresponds to reading the columns of the original diagram. Restricted Partitions Partitions with a maximum part size $k$: The number of partitions of $n$ into parts of size at most $k$ is $p(n, \text{max part } k)$. Partitions into exactly $k$ parts: The number of partitions of $n$ into exactly $k$ parts is often denoted $p_k(n)$. Theorem: The number of partitions of $n$ into exactly $k$ parts is equal to the number of partitions of $n$ whose largest part is $k$. (This can be shown by considering the conjugate of the Ferrers diagram.) Partitions into distinct parts: A partition where all parts are unique. Generating Function: $$ \prod_{k=1}^{\infty} (1+x^k) $$ Theorem (Euler): The number of partitions of $n$ into distinct parts is equal to the number of partitions of $n$ into odd parts. Example $n=5$: Distinct parts: $5$, $4+1$, $3+2$. (3 partitions) Odd parts: $5$, $3+1+1$, $1+1+1+1+1$. (3 partitions) Restricted Partitions (Continued) Partitions with parts from a specific set $A$: The generating function is $\prod_{a \in A} \frac{1}{1-x^a}$. Congruence Properties of $p(n)$ (Ramanujan) $p(5k+4) \equiv 0 \pmod{5}$ $p(7k+5) \equiv 0 \pmod{7}$ $p(11k+6) \equiv 0 \pmod{11}$ These are famous congruences discovered by Ramanujan. Asymptotic Formula (Hardy and Ramanujan) For large $n$, $p(n)$ can be approximated by: $$ p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}} $$ This formula provides a remarkably accurate estimate for the growth of $p(n)$.