Determining Generating Functions

As we have already seen on the More on Generating Functions page - certain counting problems can often be solved using generating functions. We looked at one example on that page and we will see how to take generating functions and solve certain counting problems with them on the upcoming Using Generating Functions to Solve Counting Problems page. For now, we will get a little more practice on determining a generating function for a specific counting problem.

Let's first look at some examples of determining generating functions based on word problems.

For example, suppose that we want to determine the generating function $F$ that gives us the number of solutions to integral solutions for a positive integers $x_1, x_2, x_3, x_4, k$ that satisfy $0 \leq x_1 \leq 3$, $0 \leq x_2 \leq 2$, $0 \leq x_3 \leq 5$, and $0 \leq x_4$ and:

(1)

\begin{align} \quad x_1 + x_2 + x_3 + x_4 = k \end{align}

For each restriction $0 \leq x_i \leq p$ we will have a factor $(1 + x + x^2 + … + x^p)$ in our generating function $F$. Then upon collecting like terms in the expansion and simplification of $F$, the coefficient on the term $x^k$ be equal the number of ways to choose terms from each factors such that the exponents add up to $k$, or equivalently, the number of ways for which our restrictions hold and such that the equation above is satisfied.

For our particular example, we have that $F$ is given by:

(2)

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

Of course, the rightmost factor is simply the geometric series and $1 + x + x^2 + ... = \frac{1}{1 - x}$ for $\mid x \mid < 1$, so we could instead rewrite $F$ for $\mid x \mid < 1$ as:

(3)

\begin{align} \quad F(x) = (1 + x + x^2 + x^3)(1 + x + x^2)(1 + x + x^2 + x^3 + x^4 + x^5) \left ( \frac{1}{1 - x} \right ) \\ \quad F(x) = \frac{(1 + x + x^2 + x^3)(1 + x + x^2)(1 + x + x^2 + x^3 + x^4 + x^5)}{(1 - x)} \end{align}

For a more realistic problem, suppose that we want to count the number of ways we can place $k$ many coloured balls into a box (assuming that this box can certain fit $n$ balls) where the colours we have to choose from are $r$, $y$, $g$, and $b$ which stand for red, yellow, green, and blue respectively. Suppose further that we want to restrict the number of each colour of ball in the box. Say $0 \leq r \leq 4$, $0 \leq y \leq 2$, $y = 0, 2, 4, 6, ...$ and $b = 1, 3, 5, 7, ...$. The generating function $F$ for this problem is:

(4)

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

For $\mid x \mid < 1$, the infinite factors in $F$ can be replaced and $F$ can be simplified as:

(5)

\begin{align} \quad F(x) = (1 + x + x^2 + x^3 + x^4)(1 + x + x^2)\left ( \frac{1}{1 - x^2} \right ) \left ( \frac{x}{1 - x^2} \right ) \\ \quad F(x) = \frac{x(1 + x + x^2 + x^3 + x^4)(1 + x + x^2)}{(1 - x^2)^2} \end{align}

So the coefficient on the term $x^k$ for each $k \geq 0$ tells us the number of ways in which we can place $k$ of these coloured balls into a box such that our restrictions are satisfied.