# 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)We then proved that a closed form of $F$ was:

(2)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)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)Find a power series for $F$ is rather difficult for this particular $F$. We instead use a power series calculator and obtain that:

(5)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)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)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)Therefore the coefficient on $x^3$ is $2$.