More on Generating Functions

More on Generating Functions

Recall from the Generating Functions page that if $(a_i)_{i=0}^{\infty}$ is a sequence of real numbers then the generating function of $(a_i)_{i=0}^{\infty}$ is defined to be:

(1)
\begin{align} \quad F(x) = a_0 + a_1x + a_2x^2 + ... + a_ix^i + ... = \sum_{i=0}^{\infty} a_ix^i \end{align}

We will now look at finding some more generating functions. Consider the sequence $(a_k)_{k=0}^{\infty}$ where $a_k$ is equal to the number of nonnegative integral solutions to the equation:

(2)
\begin{align} \quad b_1 + b_2 + ... + b_n = k \end{align}

That is, $b_1, b_2, ..., b_n \geq 0$. We saw on the Nonnegative Integral Solutions to Simple Equations that the number of nonnegative integral solutions is $\displaystyle{\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}}$ (recall that this is also the same number of $k$-combinations of an $n$-element set whose repetition numbers are all infinite from the Combinations of Elements in Multisets page; and the same number of ways to distribute $k$ indistinguishable balls among $n$ urns from The Urn Problem with Indistinguishable Balls page). Therefore:

(3)
\begin{align} \quad (a_k)_{k=0}^{\infty} = \left ( \binom{n + 0 - 1}{n-1}, \binom{n + 1 - 1}{n-1}, ..., \binom{n + k - 1}{n-1}, ... \right ) \end{align}

The generating function for $(a_k)_{k=0}$ is therefore:

(4)
\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}

In the following theorem we will obtain a simplification for this generating function.

 Theorem 1: $\displaystyle{\sum_{k=0}^{\infty} \binom{n + k - 1}{n - 1} x^k = \frac{1}{(1 - x)^n}}$.
(5)
\begin{align} \quad (x + y)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k y^{\alpha - k} \end{align}
• Let $y = 1$ to get:
(6)
\begin{align} \quad (1 + x)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k \end{align}
• For the generalized binomial coefficient $\binom{\alpha}{k}$, let $\alpha = -n$ where $n \in \{1, 2, ..., n \}$. Then we have that:
(7)
\begin{align} \quad \binom{\alpha}{k} = \binom{-n}{k} = \frac{-n \cdot (-n - 1) \cdot ... \cdot(-n - k +1)}{k!} = (-1)^k \frac{n \cdot (n + 1) \cdot ... \cdot (n + k - 1)}{k!} = (-1)^k \binom{n+k-1}{k} = (-1)^k \binom{n+k-1}{n - 1} \end{align}
• Therefore we have that:
(8)
\begin{align} \quad \frac{1}{(1 + x)^n} = \sum_{k=0}^{\infty} (-1)^k \binom{n + k - 1}{n-1} x^k \end{align}
• Substituting $x$ for $- x$ gives us:
(9)
\begin{align} \quad \frac{1}{(1 - x)^n} = \sum_{k=0}^{\infty} (-1)^k \binom{n + k - 1}{n-1} (-x)^k \\ \quad \frac{1}{(1 - x)^n} = \sum_{k=0}^{\infty} (-1)^k \binom{n +k - 1}{n-1} (-1)^k x^k \\ \quad \frac{1}{(1 - x)^n} = \sum_{k=0}^{\infty} (-1)^{2k} \binom{n + k - 1}{n-1} x^k \\ \quad \frac{1}{(1 - x)^n} = \sum_{k=0}^{\infty} \binom{n + k - 1}{n-1} x^k \quad \blacksquare \end{align}

Theorem 1 above can be used to obtain generating functions for word problems. For example, suppose that we want to create a generating function for the $n$-combinations of dogs and cats where the number of dogs is odd and the number of cats is even. This number is precisely the number of nonnegative integral solutions where $b_1$ is odd and $b_2$ is even to the following equation:

(10)
\begin{align} \quad b_1 + b_2 = n \end{align}

We will use the factor $(x + x^3 + x^5 + ... )$ for the number of dogs and the factor $(1 + x^2 + x^4 + ... )$ for the number of cats. The generating function $F$ for the number of $n$-combinations of an odd number of dogs and an even number of cats is therefore

(11)
\begin{align} \quad F(x) = (x + x^3 + x^5 + ...)(1 + x^2 + x^4 + ...) \\ \quad F(x) = \left ( \sum_{i=0}^{\infty} x^{2i+1}\right ) \left ( \sum_{i=0}^{\infty} x^{2i} \right ) \end{align}

We can simplify $F$ by algebraically manipulating the infinite series factors above. Let $f_1(x) = \sum_{i=0}^{\infty} x^{2i+1}$ and let $f_2(x) = \sum_{i=0}^{\infty} x^{2i}$. Then:

(12)
\begin{align} \quad F(x) = f_1(x) \cdot f_2(x) \end{align}

We simplify both factors as follows that for $f_1(x)$:

(13)
\begin{align} \quad f_1(x) = \sum_{i=0}^{\infty} x^{2i+1} \\ \quad \frac{f_1(x)}{x} = \sum_{i=0}^{\infty} x^{2i} \\ \quad \frac{f_!(x)}{x} = \sum_{i=0}^{\infty} (x^2)^i \\ \quad \frac{f_1(x)}{x} = \frac{1}{1 - x^2} \\ \quad f_1(x) = \frac{x}{1 - x^2} \end{align}

And also for $f_2(x)$:

(14)
\begin{align} \quad f_2(x) = \sum_{i=0}^{\infty} x^{2i} \\ \quad f_2(x) = \sum_{i=0}^{\infty} (x^2)^i \\ \quad f_2(x) = \frac{1}{1 - x^2} \end{align}

Therefore we have that the generating function $F$ for our problem is:

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