Integer Partitions
Contents
1. Definition
An Integer Partition of $n \in \mathbf{N}$ is a unique way of writing n as the sum of integers. Partitions that differ in the order only are considered to be the same partition. Restricted partitions is a partition that is restricted under specified conditions.
2. Notation
By $\mathbf{P}_n$, we denote the collection of all integer partitions of $n$. We usually write $\lambda \in \mathbf{P}_n$ as $\lambda = (\lambda_1,\lambda_2, \ldots)$.
3. Examples
Partitions:
$\mathbf{P}_1 = \{ [1]\}$
$\mathbf{P}_2 = \{ [2],[1,1]\}$
$\mathbf{P}_3 = \{ [3],[2,1],[1,1,1]\}$
$\mathbf{P}_4 = \{ [4],[3,1],[2,2], [2,1,1], [1,1,1,1]\}$
Restricted Partitions:
Odd partitions of $8$:
$7+1$
$5+3$
$5+1+1+1$
$3+3+1+1$
$3+1+1+1+1+1$
$1+1+1+1+1+1+1+1$
Partitions of $8$ with distinct parts (Non-Repeating Integers):
$8$
$7+1$
$6+2$
$5+3$
$5+2+1$
$4+3+1$
4. Partition Function
The Partition Function $P(n)$ represents the number of partitions of the integer n. The first few values of $P(n)$ are $1,1,2,3,5,7,11,15,22,30,42,$ and so on (A000041 in OEIS)
$Q(n)$ is denoted as the number of partitions of distinct parts and of odd partitions. The first few values of $Q(n)$ are $1,1,1,2,3,4,5,6,7,8,10$ (A000009 in OEIS)
5. Generating Function
$|\mathbf{P}_n| = p(n)$ counts the number of ways n can be partitioned. Hans Rademacher provided a way to determine $p(n)$ by introducing a series called Rademacher's series:
$$\displaystyle \sum_{n=0}^\infty p(n) x^n = \prod_{k=1}^\infty \frac{1}{1-x^k}$$ which can be expanded to $$(1 + x + x^2 + x^3 + ....)(1 + x^2 + x^4 + x^6 + ....)....$$ This is also known as the Euler's generating function which allows $p(n)$ to be calculated for any $n$. [Wil00]
6. Properties
Let $p_n(r)$ be the number of partitions of $n$ in which the largest part is $r$. Let $q_n(r)$ be the number of partitions of $n-r$ which no part is greater than r. Then
$$p_n(r)=q_n(r)$$
Let $p_n^s$ denote the number of self conjugate partitions of n and let $p_n^t$ be the number of partitions of n into distinct odd parts. Then
$$p_n^s=p_n^t$$
Let $p_n^o$ be the number of partitions of n into odd parts, and let $p_n^d$ be the number of partitions of n into distinct parts. Then
$$p_n^o=p_n^d$$
- [Bru10]
The elements of $\mathbf{P}_n$ index the number of irreducible representations of the symmetric group $\mathbf{S}_n$ over a field of characteristic $0$.
The number of non-isomorphic abelian groups of order $n=\sum_ip_i^{j_i}$ where $p_i$ are distinct primes and $j_i$ are positive integers is given by $\prod_ip(j_i)$ A000688
Congruence partitions are partitions that are similar under modulation. For example: $$p(5k+4)= 0 (mod\text{ }5)$$ $$p(7k+5)= 0 (mod\text{ }7)$$ $$p(11k+6)=0 (mod\text{ }11)$$ are just a couple examples proven by Srinivasa Ramanujan.
The approximation formula for p(n): $$\displaystyle p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right) \mbox { as } n\rightarrow \infty$$
7. Ferrer and Young diagrams
A very useful way to represent partitions is by the means of Ferrers diagram. Ferrers diagram, named after Norman Macleod Ferrers, is constructed by stacking left-justified rows of cells, where the number of cells in each row corresponds to the size of a part. The first row corresponds to the largest part, the second row corresponds to the second largest part and so on.
For example, partition $\lambda = (5,4,2,1)$ can be shown as
- The Young diagram is similar to the Ferrer diagram. Instead of dots, boxes are used. instead of ordering by rows, it is ordered by columns. The first columns corresponds to the largest part, the second columns corresponds to the second largest part and so on.
In this example, the Young diagram is $\lambda = (4,3,2,2,1)$
A bijection can be created between either diagram into one with a unique diagram with distinct parts. Taking the above example we take the outside L dots/boxes and create a new row. The same thing for the second row and so on. The new diagram will have a Young diagram where $\lambda = (9,4)$
8. Statistics
St000159: The number of different parts of a partition (number of corners).
St000148: The number of odd parts of a partition.
St000142: The number of even parts of a partition.
St000147: The largest part in the integer partition.
St000143: The maximal repeated part of a partition.
St000010: The length of the partition.
St000185: The weighted size of a partition.
St000160: Multiplicity of the smallest part of a partition.
St000175: Degree of the polynomial corresponds to semi-standard Young-tableaux of shape $k\lambda$.
St000150: The floored half-sum of the multiplicities of a partition.
St000149: The number of cells of the partition whose leg is zero and arm is odd.
St000137: The Grundy value for positions in a game on Young diagrams (integer partitions).
St000108: The number of partitions contained in the given partition.
St000088: The row sums of the character table of the symmetric group.
St000049: The number of set partitions whose sorted block sizes correspond to the partition.
St000048: The multinomial of the parts of a partition.
St000046: The largest eigenvalue of the random to random operator acting on the simple module corresponding to the given partition.
St000063: The number of linear extensions of a certain poset defined from a partition $\lambda$.
St000184: The Size of centralizer.
St000183: The size of Durfee square.
St000182: The size of conjugacy class.
St000179: Product of Hook lengths.
St000146: The Andrews-Garvan crank of a partition.
St000145: The Dyson rank of a partition.
St000003: The number of standard Young tableaux of the partition.
9. Combinatorial Maps
- The conjugate partition
The conjugate partition of the partition $\lambda$ of $n$ is the partition $\lambda^*$ whose Ferrers diagram is obtained from the diagram of $\lambda$ by interchanging rows with columns. [Bru10]
- Initial tableau
This is the same as standard Young tableau which has the numbers $1, 2, \ldots, n$ where $n$ is the size of the integer partition entered in order from left to right along the rows of each component, where the components are ordered from left to right.
- Reading tableau
Reading tableau is the RSK recording tableau of the reading word of the (standard) tableau $T$ labeled down each column to the shape of the corresponding Ferrers diagram.
- Partition to minimal Dyck word
This corresponds to the unique Dyck path whose complement is the partition for which the partition touches the diagonal. If $w$ is a $n$-Dyck word, then the Dyck path corresponding to $w$ can be regarded as a lattice path in the northeastern half of an $n \times n$-square. The region to the northeast of this Dyck path can be regarded as a partition. It is called the partition corresponding to the Dyck word $w$. For every partition $\lambda$ and every non-negative integer $n$, there exists at most one $n$-Dyck word $w$ such that the partition corresponding to $w$ is $\lambda$. This method computes this $w$ for a given $\lambda$ and $n$. If $n$ is not specified, this method computes the $w$ for the smallest possible $n$ for which such an $w$ exists.
For example minimal dyck word of partition $\lambda = (5,4,2,1)$ is $(1,1,0,1,0,1,0,0,1,0,1,0)$
For many combinatorial statistics and bijections see [Pak02]
10. References
- [Bru10] R. Brualdi, Partition numbers, Combinatorics Fifth Edition (2010).
- [Pak02] I. Pak, Partition bijections, a survey, Ramanujan J. 12(1) (2006) p. 5-75.
- [Wil00] S. Wilf, Basic generating functions, Lectures on Integer Partitions, (2000).
11. Sage examples