Using Generating Functions to Solve Counting Problems

Recall from the More on Generating Functions page that if $(a_k)_{k=0}^{\infty}$ is defined such that each $a_k$ is the number of nonnegative integral solutions to the equation $b_1 + b_2 + ... + b_n = k$ then from the Nonnegative Integral Solutions to Simple Equations page we noted that $a_k = \binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$. We also noted that the generating function $F$ for $(a_k)_{k=0}^{\infty}$ was given by:

(1)

\begin{align} \quad F(x) = \sum_{k=0}^{\infty} \binom{n + k - 1}{n - 1}x^k = \binom{n + 0 - 1}{n - 1} + \binom{n + 1 - 1}{n - 1}x + \binom{n + 2 - 1}{n - 1}x^2 + ... + \binom{n + k - 1}{n - 1}x^k + ... \end{align}

We then proved that a closed form of $F$ was:

(2)

\begin{align} \quad F(x) = \frac{1}{(1 - x)^n} \end{align}

We also looked at some examples of Determining Generating Functions. We will now see how we can use these generating functions to solve certain counting problems - in particular, counting problems that arise from the need to find nonnegative integral solutions $b_1, b_2, ..., b_n \geq 0$ to equations of the form $b_1 + b_2 + ... + b_n = k$.

For example, suppose that we want to determine the number of boxes containing $n$ vegetables which we select from: potatoes, carrots, onions, tomatoes, and broccoli such that the following criterion are met:

• The number of potatoes $p$ in the box is either $0$ or $1$, i.e., $p = 0, 1$.

• The number of carrots $c$ in the box is an even number, i.e., $c = 0, 2, 4, ...$.

• The number of onions $o$ in the box is either $0$, $1$ or $2$, i.e., $o = 0, 1, 2$.

• The number of tomatoes $t$ in the box is an odd number, i.e., $t = 1, 3, 5, ...$.

• The number of broccoli bunches $b$ is some multiple of $3$, i.e., $b = 0, 3, 6, ...$.

We will find a generating function to try to obtain a sequence $(a_i)_{i=0}^{\infty}$ where $a_i$ tells us the number of ways be can place these five types of vegetables in the box under the criterion above such that the total number of vegetables is $n$, that is, $a_i$ will tell us the number of $n$-combinations of these five types of vegetables with the criterion above exist.

For each of $p, c, o, t, b$ we create a factor of the generating function $F$:

(3)

\begin{align} \quad F(x) = \underbrace{(1 + x)}_{\mathrm{for} \: p = 0, 1}\underbrace{(1 + x^2 + x^4 + ...)}_{\mathrm{for} \: c = 0, 2, 4, ...} \underbrace{(1 + x + x^2)}_{\mathrm{for} \: o = 0, 1, 2}\underbrace{(x + x^3 + x^5 + ...)}_{\mathrm{for} \: t = 1, 3, 5, ...}\underbrace{(1 + x^3 + x^6 + ... )}_{\mathrm{for} \: b = 0, 3, 6, ...} \end{align}

The terms finite factors $1 + x + x^2 + ... + x^n$ in $F(x)$ can be compressed into the form $\frac{1 - x^{n+1}}{1 - x}$. The factor $1 + x^2 + x^4 + ... =\frac{1}{1 - x^2}$ for $\mid x \mid < 1$ and the factor $x + x^3 + x^5 + ... = \frac{x}{1 - x^2}$ for $\mid x \mid < 1$ as we saw earlier. The factor $1 + x^3 + x^6 + ... = \frac{1}{1 - x^3}$ for $\mid x \mid < 1$ which can be verified by algebraic manipulation of the geometric series. Therefore:

(4)

\begin{align} \quad F(x) = \frac{1 - x^2}{1 - x} \cdot \frac{1}{1 - x^2} \cdot \frac{x}{1 - x^2} \cdot \frac{1 - x^3}{1 - x} \cdot \frac{1}{1 - x^3} = \frac{x(1 - x^2)(1 - x^3)}{(1 - x)^2 (1 - x^2)^2 (1 - x^3)} = \frac{x}{(1 - x)^2(1 - x^2)} \end{align}

Find a power series for $F$ is rather difficult for this particular $F$. We instead use a power series calculator and obtain that:

(5)

\begin{align} \quad F(x) = 0 + x + 2x^2 + 4x^3 + 6x^4 + 9x^5 + 12x^6 + 16x^7 + 20x^8 + 25x^9 + 30x^{10} + ... \end{align}

The set of coefficients in front of each of the terms in $F$ is our sequence $(a_i)_{i=0}^{\infty}$ where $a_i$ tells us the number of $i$-combinations of potatoes, carrots, onions, tomatoes, and broccolis we have given our criterion, so:

(6)

\begin{align} \quad (a_i)_{i=0}^{\infty} = (0, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, ...) \end{align}

Let's try to verify at least one of the terms in this sequence, say $a_4 = 6$. This coefficient says that there are $6$ many $4$-combinations that satisfy the criterion above. They are precisely:

$\{ p, c, c, t \}$

$\{c, c, o, t \}$

$\{p, t, t, t\}$

$\{ o, t, t, t \}$

$\{t, b, b, b \}$

$\{p, o, o, t \}$

Remark 1: Once we have obtained a generating function $F$ for a problem - there are two approaches we can use in order to determine the coefficients of a certain term $x^k$. If possible, we may be able to write the generating function $F$ as a power series of the form $\sum_{i=0}^{\infty} a_ix^i$ in which for $a_k$ is the coefficient attached to $x_k$. For most problems this is extremely difficult though. In other cases, we may have to partially expand $F$ and simplify our partial expansion in a brute-force sort of method to determine the coefficient of $x^k$.

If we want to compute the coefficient on $x^k$ with brute force then we do not need to consider terms of any factor whose exponent is greater than $k$. For example, consider the generating function:

(7)

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

Suppose that we want to determine the coefficient on $x^3$. We can truncate the factor $(1 + x^2 + x^4 + ...)$ to be $(1 + x^2)$ and similarly, we truncate $(1 + x + x^2 + x^3 + x^4 + x^5)$ to $(1 + x + x^2 + x^3)$. We do this because all exponents are nonnegative and so multiplication by any exponent larger than $k = 3$ will now result to an increase in the coefficient of $x^k$. We get:

(8)

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

Therefore the coefficient on $x^3$ is $2$.