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:

Restricted Partitions:

Odd partitions of $8$:

Partitions of $8$ with distinct parts (Non-Repeating Integers):

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

$$\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

$$p_n(r)=q_n(r)$$

$$p_n^s=p_n^t$$

$$p_n^o=p_n^d$$

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

ferrers.png

8. Statistics

We have the following 71 statistics 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 for positions in a game on Young diagrams (integer partitions).
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 in the integer partition.
The number of odd parts of the 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 $\lambda$.
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 size of the preimage of the map 'Robinson-Schensted tableau shape' from Permu....
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.

9. Maps

We have the following 5 maps in the database:

initial tableau
to Dyck path
conjugate
reading tableau
to binary word

Maps not yet considered are:

For many combinatorial statistics and bijections see [Pak02]

10. References

11. Sage examples

IntegerPartitions (last edited 2015-10-30 15:54:52 by ChristianStump)