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

9. Combinatorial Maps

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

fer.png

For many combinatorial statistics and bijections see [Pak02]

10. References

11. Sage examples

IntegerPartitions (last edited 2014-05-16 01:46:44 by LahiruKariyawasam)