Integer Partitions

# 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 126 statistics on Integer partitions in the database:

The number of standard Young tableaux of the partition.
The length of the partition.
The largest eigenvalue of the random to random operator acting on the simple modu....
The multinomial of the parts of a partition.
The number of set partitions whose sorted block sizes correspond to the partition....
The number of linear extensions of a certain poset defined from a partition \la....
The row sums of the character table of the symmetric group.
The number of partitions contained in the given partition.
The Grundy value of an integer partition.
The number of even parts of a partition.
The maximal repeated part of a partition.
The Dyson rank of a partition.
The Andrews-Garvan crank of a partition.
The largest part of an integer partition.
The number of odd parts of a partition.
The number of cells of the partition whose leg is zero and arm is odd.
The floored half-sum of the multiplicities of a partition.
The number of different parts of an integer partition.
Multiplicity of the smallest part of $\lambda$.
Degree of the polynomial counting the number of semistandard Young-tableaux of sh....
Product of hook lengths.
The number of permutations whose cycle type is the given integer partition.
The size of the Durfee Square of a partition.
The size of the centralizer of any permutation of given cycle type.
The weighted size of a partition.
Number of non-integral Gelfand-Tsetlin polytopes with prescribed top row and part....
Number of non-integral Gelfand-Tsetlin polytopes with prescribed top row and inte....
Number of integral Gelfand-Tsetlin polytopes with prescribed top row and integer ....
Number of integral Gelfand-Tsetlin polytopes with prescribed top row and integer ....
Number of standard Young tableaux for an integer partition such that no two conse....
Difference between largest and smallest parts in a partition.
The size of a partition.
The number of parts from which one can substract 2 and still get an integer parti....
The number of distinct parts of a partition that occur at least twice.
Number of permutations whose sorted list of non zero multiplicities of the Lehmer....
The size of the preimage of the map 'to partition' from Integer compositions to I....
The Plancherel distribution on integer partitions.
The number of addable cells of the Ferrers diagram of an integer partition.
The spin of an integer partition.
The dinv adjustment of an integer partition.
The number of integer partitions of n that are dominated by an integer partition.....
The number of refinements of a partition.
The number of coarsenings of a partition.
The dinv defect of an integer partition.
The diagonal inversion number of an integer partition.
Half the perimeter of the largest rectangle that fits inside the diagram of an in....
The maximal part of the shifted composition of an integer partition.
The hook length of the base cell of a partition.
The hook length of the last cell along the main diagonal of an integer partition.....
The number of parts of a partition that are strictly bigger than the number of on....
Dyson's crank of a partition.
The number of parts equal to 1 in a partition.
The weight of a partition according to Alladi.
Another weight of a partition according to Alladi.
The number of lower covers of a partition in dominance order.
The number of upper covers of a partition in dominance order.
The number of standard desarrangement tableaux of shape equal to the given partit....
The diagonal index (content) of a partition.
The number of invariant oriented cycles when acting with a permutation of given c....
The number of invariant subsets when acting with a permutation of given cycle typ....
The number of invariant subsets of size 3 when acting with a permutation of given....
The number of invariant subsets of size 2 when acting with a permutation of given....
The number of invariant simple graphs when acting with a permutation of given cyc....
The number of invariant set partitions when acting with a permutation of given cy....
The Kreweras number of an integer partition.
The number of ways to place as many non-attacking rooks as possible on a Ferrers ....
The total number of rook placements on a Ferrers board.
The maximal number of non-attacking rooks on a Ferrers shape.
The number of even non-empty partial sums of an integer partition.
The number of different non-empty partial sums of an integer partition.
The number of odd partial sums of an integer partition.
The number of ways to select a row of a Ferrers shape and two cells in this row.
The sum of the products of all pairs of parts.
The number of self-evacuating tableaux of given shape.
The number of standard tableaux of shape equal to the given partition such that t....
The number of standard tableaux of shape equal to the given partition such that t....
The number of graphs with given frequency partition.
The greatest common divisor of the parts of the partition.
The least common multiple of the parts of the partition.
The Grundy value of Chomp on Ferrers diagrams.
The number of 3-rim hooks removed from an integer partition to obtain its associa....
The number of 2-rim hooks removed from an integer partition to obtain its associa....
The number of semistandard tableaux on a given integer partition with minimal max....
The number of semistandard tableaux on a given integer partition of n with maxima....
The product of the factorials of the multiplicities of an integer partition.
The product of the factorials of the parts.
The product of the parts of an integer partition.
The number of semistandard Young tableau of given shape, with entries at most 4.
The dimension of the irreducible representation of Sp(4) labelled by an integer p....
The number of semistandard Young tableau of given shape, with entries at most 2.
The number of semistandard Young tableau of given shape, with entries at most 3.
The dimension of the irreducible representation of Sp(6) labelled by an integer p....
The smallest integer d such that the restriction of the representation correspond....
The Grundy value for the game 'Couples are forever' on an integer partition.
The number of real roots of the characteristic polynomial of a linear recurrence ....
The smallest missing part in an integer partition.
The major index of an integer partition when read from bottom to top.
The number of proper colouring schemes of a Ferrers diagram.
The maximal number of occurrences of a colour in a proper colouring of a Ferrers ....
The maximum of the length and the number of parts of an integer partition.
The sum of the entries in the column specified by the partition of the change of ....
The sum of the entries in the column specified by the partition of the change of ....
The sum of the entries in the column specified by the partition of the change of ....
The number of zero-one matrices with weakly decreasing column sums and row sums g....
The sum of the entries in the column specified by the partition of the change of ....
The number of semistandard Young tableaux of partition weight of given shape.
The minimal difference in size when partitioning the integer partition into two s....
The sum of the hook lengths in the first column of an integer partition.
The sum of the hook lengths of an integer partition.
The product of the hook lengths of the diagonal cells in an integer partition.
The number of different multiplicities of parts of an integer partition.
The cube of the number of standard Young tableaux with shape given by the partiti....
The number of ways to refine the partition into singletons.
The alternating sum of the coefficients of the character polynomial of an integer....
The sum of the coefficients of the character polynomial of an integer partition.
The constant term of the character polynomial of an integer partition.
The number of multipartitions of sizes given by an integer partition.
The 2-degree of an integer partition.
The number of ordered refinements of an integer partition.
The number of even values of the symmetric group character corresponding to the p....
The number of positive values of the symmetric group character corresponding to t....
The number of zeros of the symmetric group character corresponding to the partiti....
The number of characters of the symmetric group whose value on the partition is p....
The number of characters of the symmetric group whose value on the partition is z....
The number of characters of the symmetric group whose value on the partition is e....
The 3-degree of an integer partition.

# 9. Maps

We have the following 16 maps in the database:

to bounded partition
to partition
to partition
to partition of connected components
to partition
initial tableau
to Dyck path
conjugate
Robinson-Schensted tableau shape
shape
shape
shape
to binary word
cycle type
Greene-Kleitman invariant

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).