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)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)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)The generating function for $(a_k)_{k=0}$ is therefore:
(4)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}}$. |
- Proof: From Newton's Generalization of the Binomial Theorem we have that for $\alpha$ as a real number and for $0 \leq \mid x \mid < \mid y \mid$ that then:
- Let $y = 1$ to get:
- For the generalized binomial coefficient $\binom{\alpha}{k}$, let $\alpha = -n$ where $n \in \{1, 2, ..., n \}$. Then we have that:
- Therefore we have that:
- Substituting $x$ for $- x$ gives us:
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)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)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)We simplify both factors as follows that for $f_1(x)$:
(13)And also for $f_2(x)$:
(14)Therefore we have that the generating function $F$ for our problem is:
(15)