Positive Integer Partitions

# Positive Integer Partitions

We will now look at a specific and relatively simple counting problem that can be solved with a generating function. We first look at a definition relevant to this problem.

 Definition: If $n$ is a positive integer then a Partition of $n$ is a submultiset $P$ of $\{ \infty \cdot 1, \infty \cdot 2, ..., \infty \cdot n \}$ such that the sum of the elements in $P$ equals $n$. The number of partitions of $n$ is denoted by $P_n$

For example, if $n = 6$ then $\{ 6 \cdot 1 \} = \{1, 1, 1, 1, 1, 1 \}$ is said to be a partition of $6$. Furthermore, $\{ 3 \cdot 2 \} = \{2, 2, 2 \}$ and $\{2 \cdot 1, 2 \cdot 2 \} = \{1, 1, 2, 2 \}$ are also both partitions of $6$.

Suppose that we want to determine $P_n$ for some $n \in \{1, 2, ... \}$. For small $n$ it is relatively simply to find all partitions of $n$ and count them. Like with many counting problems though, the value of $P_n$ grows exceedingly fast as $n$ grows only moderately.

We will instead exhibit a way to determine $P_n$ using generating functions. For each $n \in \{ 1, 2, ... \}$ we can construct the number $n$ as a finite sum of positive integers less than or equal to $n$. The generating function $F$ for this problem is:

(1)
\begin{align} \quad F(x) = (1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ...)...(1 + x^k + x^{2k} + ...)... \\ \quad F(x) = \sum_{i=0}^{\infty} (x^i) \cdot \sum_{i=0}^{\infty} (x^{2i}) \cdot \sum_{i=0}^{\infty} (x^{3i}) \cdot ... \cdot \sum_{i=0}^{\infty} (x^{ki}) \cdot ...\\ \quad F(x) = \prod_{k=1}^{\infty} \left ( \sum_{i=0}^{\infty} x^{ki}\right ) \end{align}

Note that for each $n \in \{ 1, 2, ... \}$ that the coefficient on the term $x^n$ will be the number of ways that $n$ can be formed by positive integers less or equal to $n$.

Suppose that we want to compute $P_5$, i.e., the coefficient on the term $x^5$. This can be accomplished by finding the exponent on $x^5$ of the expansion of the finite expression:

(2)
\begin{align} \quad (1 + x + x^2 + x^3 + x^4 + x^5)(1 + x^2 + x^4)(1 +x^3)(1 + x^4)(1 + x^5) \\ \quad = 1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + ... \end{align}

Therefore the number of positive integer partitions of $5$ is $P_5 = 7$.