12 Multiplication of Generating Functions
Suppose \(L, L'\) are two languages. We define the concatenated language \(LL'\) by concatenating a string from \(L\) and a string from \(L'\) in all possible ways:
\[ LL' = \{uv : u \in L, v \in L'\}. \]
The utility of this is that many common languages of strings can be written as concatenations of smaller, more simpler languages. And, it will turn out, we can compute the OGF of the more complex language out of the OGFs for the simpler languages.
12.1 Multiplication of Monomials
Suppose we have a language \(L\) which consists of \(10\) strings, each of length \(5\). Suppose we also have a language \(L'\) consisting of \(6\) strings, each of length \(7\). Concatenating any pair of strings will always yield a string of length \(12\) and there are \(60\) such pairs. This computation is represented by the following multiplication of generating functions: \[ (10x^5) \cdot (6x^7) = 60x^{12}. \]
12.2 A step further
Now suppose \(L\) is the same as before: \(10\) strings of length \(5\), and this time \(L'\) consists of \(3\) strings of length \(4\) and \(7\) strings of length \(8\). Now if we concatenate to form \(LL'\) we are either combining a string of length \(5\) with one of length \(4\) (in \(10 \cdot 3\) ways) or a string of length \(5\) with one of length \(8\) (in \(10 \cdot 7\) ways). Again, this computation is reflected in the product of polynomials \[ 10x^5 \cdot (3x^4 + 7x^8) = 30x^9 + 70x^{13}. \]
Exercise 12.1 Suppose \(L\) consists of \(3\) strings of length \(4\) and \(8\) of length \(6\). Suppose \(L'\) consists of \(2\) strings of length \(1\) and \(5\) strings of length \(4\). What will \(LL'\) consist of?
12.3 Multiplication theorem
Theorem 12.1 (Multiplication Theorem) Let \(L\) and \(L'\) be two different languages. Let \(f\) be a common weight function like the length of a string. Then \[ \Phi_{LL'}(x) = \Phi_L(x)\Phi_{L'}(x). \]
Proof. We have \[\begin{align*} \Phi_{LL'}(x) &= \sum_{w \in LL'} x^{f(w)} \\ &= \sum_{u \in L} \sum_{v \in L'} x^{f(uv)} \\ &= \sum_{u \in L} \sum_{v \in L'} x^{f(u)}x^{f(v)} \end{align*}\] using Section 10.2.1. Continuing, we get \[\begin{align*} \phantom{\Phi_{LL'}(x)} &= \sum_{u \in L} x^{f(u)} \sum_{v \in L'} x^{f(v)} \\ &= \Phi_L(x) \Phi_{L'}(x). \end{align*}\]
One might wonder whether \(\sum a_i \sum b_j\) means \((\sum a_i)(\sum b_j)\) or \(\sum \left(a_i \sum b_j \right)\). It turns out these are the same, and it is explained by the distributive property of multiplication. For example, \[ (a_1 + a_2 + a_3)(b_1 + b_2) = a_1(b_1 + b_2) + a_2(b_1 + b_2) + a_3(b_1 + b_2). \]
12.4 Strings with 0s followed by 1s
Let \(L\) be the language of strings with only \(0\)s and let \(L'\) be the language of strings with only \(1\)s. In Section 11.3, we saw that these languages have generating functions \(\frac{1}{1 - x}\) (weighting by length). By theorem Theorem 12.1, the language \(LL'\) of all strings of \(0\)s followed by \(1\)s has generating function \[ \frac{1}{(1 - x)^2}. \]
We can compute this in a couple ways. First, we ask the question: “how many strings are there of length \(n\) consisting of a string of \(0\)s followed by a string of \(1\)s?” E.g. for \(n = 4\) there are \(5\) such strings: \[ 0000, 0001, 0011, 0111, 1111. \] We can look at this as: there are either \(0, 1, 2, 3, 4\) ones. In general, there will be \(n + 1\) strings of length \(n\) (corresponding to the monomial \((n + 1)x^n\)). Therefore \[ \frac{1}{(1 - x)^2} = \sum_{n = 0}^\infty (n + 1)x^n = 1 + 2x + 3x^2 + 4x^3 + \cdots. \]
12.4.1 Calculus?
The monomials we’ve just computed look suspiciously like derivatives: \(1\) is the derivative of \(x\), \(2x\) is the derivative of \(x^2\), \(3x^2\) is the derivative of \(x^3\), and so on. I.e., we have \[ \frac{1}{(1 - x)^2} = \sum_{n = 0}^\infty \frac{d}{dx} x^n. \]
The sums \(\sum nx^{n-1}\) and \(\sum (n + 1)x^n\) are equal. In words: each sum is adding up all monomials whose coefficient is exactly \(1\) more than the exponent. Algebraically, we can transform the first sum to the second by letting \(m = n - 1\) and \(n = m + 1\). Then \[ \sum nx^{n-1} = \sum (m + 1)x^m. \] When working with OGFs, we often want to make such tranformations so that the question of “how many strings of length \(n\)” can be read directly from the summand \(a_nx^n\): there are \(a_n\) strings of length \(n\).
In our calculus courses, we learn that we can often take the derivative of a series term-by-term. Or in other words, we can safely move the derivative operator from inside the term to outside and vice versa: \[ \sum_{n = 0}^\infty \frac{d}{dx} x^n = \frac{d}{dx} \sum_{n = 0}^\infty \sum_{n = 0}^\infty x^n. \] This we recognize as the geometric series from Section 11.3. So that means we should expect \[ \frac{1}{(1 - x)^2} = \frac{d}{dx} \frac{1}{1-x}. \] Indeed, that is the case.
The following is a result of analysis that is very potent for many OGF problems.
Theorem 12.2 If \(\sum a_n x^n\) converges to a function \(f(x)\) (and the radius of convergence is not zero), then \[ \sum \frac{d}{dx} a_n x^n = f'(x) \] (and the radius of convergence is preserved).
In Section 11.3.1, we said that these generating functions are still valid even when they don’t converge. But there is utility here in that if we have an expression to represent an infinite sum like how \(\frac{1}{1-x}\) represents the geometric series, then we can compute the derivative of the expression and of the infinite series.
Example 12.1 Given that \[ \frac{1}{(1 - x)^2} = 1 + 2x + 3x^2 + 4x^3 + \dots = \sum nx^{n-1}, \] we can compute the derivative on both sides to obtain \[ \frac{2}{(1 - x)^3} = 2 + 6x + 12x^2 + 20x^3 + \cdots = \sum n(n-1)x^{n-2}. \] If we divide by \(2\) we might recognize this as \[ \frac{1}{(1 - x)^3} = \sum \frac{n(n-1)}{2}x^{n-2} = \sum \binom{n}2x^{n - 2} = \sum \binom{n + 2}{2} x^n. \]