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
We have the following 107 statistics in the database:
9. Maps
We have the following 5 maps in the database:
Maps not yet considered are:
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