Basics

In number theory and combinatorics, a partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. - Wikipedia

As addition is commutative, the order of the summands is arbitrary and may be rearranged so that they appear in decreasing order. For example, we may partition the integer $5$ in the following seven distinct ways:

  • $5$
  • $4 + 1$
  • $3 + 2$
  • $3 + 1 + 1$
  • $2 + 2 + 1$
  • $2 + 1 + 1 + 1$
  • $1 + 1 + 1 + 1 + 1$

With this in mind, we begin with the following definitions:

First Definitions

A partition is a finite nonincreasing sequence of positive integers, often denoted by symbols such as $\lambda$, $\mu$, or $p$.

In other words, if $\lambda$ is a partition, then it can be viewed as a function $\lambda:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ such that $\lambda(i)\ge\lambda(j)$ for all $i\le j$, and there is some $M\in\mathbb{Z}_{>0}$ such that $\lambda(i)=0$ for all $i\ge M$.

We may express the data stored in a partition by writing out the finite sequence as $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ with $\lambda_{1}\ge\lambda_{2}\ge\ldots\ge\lambda_{k}>0$. These $\lambda_{i}$ are called the parts of the partition $\lambda$.

We define the size of a partition $\lambda$ to be the sum of its parts. That is, $\mathrm{size}(\lambda):=\sum_{i=1}^{\infty}\lambda(i)=\sum_{i=1}^{k}\lambda_{i}$. We say that $\lambda$ is a partition of $n$, and write $\lambda\vdash n$, where $n=\mathrm{size}(\lambda)$.

We define the length of a partition $\lambda$ to be the number of nonzero parts in $\lambda$. That is, $\mathrm{length}(\lambda):=\max\{i\in\mathbb{Z}_{>0}|\lambda(i)\ne0\}$. For $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ with $\lambda_{1}\ge\lambda_{2}\ge\ldots\ge\lambda_{k}>0$, we have $\mathrm{length}(\lambda)=k$.

Exercise

The SageMath mathematics software system has some functionality for working with partitions built in.

We can create a partition $p=(6,3,1)$ with the following command (case sensitive):

p = Partition([6,3,1])

We can calculate $\mathrm{size}(p)=6+3+1=10$ and $\mathrm{length}(p)=3$ using the size() and length() methods respectively. These actually just make use of the built in functions sum and len for Python lists.

p.size() # Equal to sum(p)
p.length() # Equal to len(p)

We can access the parts of a partition in the same way we would for a Python list, either by indexing or slicing, or we can use the get_part() method. Note that in Python/SageMath indices are $0$-based (i.e. indices start from $0$ instead of $1$).

mu = Partition([6,4,4,2,1])
mu.get_part(0), mu.get_part(1), mu.get_part(2), mu.get_part(3), mu.get_part(4), mu.get_part(5)
# (6, 4, 4, 2, 1, 0)
mu[1:4] # Slice from index 1 (inclusive) to index 4 (exclusive)
# [4, 4, 2]

You can practice executing SageMath and Python code in the SageMathCell below.