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)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)Therefore the number of positive integer partitions of $5$ is $P_5 = 7$.