11 Generating Functions
11.1 Definition
Let \(L\) be a subset of strings. These is also called a language. Let \(f\) be a weight function. We define the (ordinary) generating function of \(L\) or OGF as
\[ \Phi_L(x) = \Phi_L^f(x) = \sum_{s \in L} x^{f(s)}. \]
It is common in mathematical definitions to write something like \[ \Phi_L(x) = \Phi_L^f(x) = \cdots. \] This means that I am calling attention to the fact that \(\Phi\) depends on \(f\) but also saying that because \(f\) isn’t going to change much, we are going to drop the \(f\) from the notation most or all of the time.
It is also common to call generating functions by other letters, like \(A(x)\) but this needs to be introduced first by saying that \(A\) is the OGF wheras \(\Phi_L\) means this implicitly.
Example 11.1 Let \(L\) be the subset \(\{01, 1110, 11, 0, 1, 111000, \varepsilon\}\) of binary strings. Let \(f\) be the length weight. The OGF of \(L\) is \[\begin{align*} \Phi_L(x) &= x^{f(01)} + x^{f(1110)} + x^{f(11)} + x^{f(0)} + x^{f(1)} + x^{f(111000)} + x^{f(\varepsilon)} \\ &= x^2 + x^4 + x^2 + x^1 + x^1 + x^6 + x^0 \\ &= 1 + 2x + 2x^2 + x^4 + x^6 \end{align*}\]
11.2 Monomials
Inside \(\Phi_L(x)\), each monomial \(a_nx^n\) (after collecting terms) represents that \(L\) has \(a_n\) strings where \(f\) equals \(n\) (e.g. the length equals \(n\)).
Example 11.2 For the language \(L\) of Example 11.1 above, we have for instance, \(2\) strings of legnth \(1\), represented by the monomial \(2x^1\). We have \(1\) string of length \(6\) represented by the monomial \(1x^6\). We have no strings of length \(5\), represented by the lack of a monomial with \(x^5\). We could also say that the coefficient of \(x^5\) is \(0\).
Exercise 11.1 Let \(L\) be the set of all binary strings of length \(\le 5\) which have no \(11\).
- for \(n = 0, 1, 2, 3, 4, 5\), list all the strings with no \(11\)
- write down the generating function with respect to the length weight
- write down the generating function with respect to the “number of 1s” weight
11.2.1 Using generating functions to count
The monomials \(a_nx^n\) are created by adding up all the words in \(L\) of weight \(n\). So another way to describe the generating function is \[ \Phi_L(x) = \sum_{s \in L} x^{f(s)} = \sum_{n = 0}^\infty \#\{s \in L : f(s) = n\} x^n. \tag{11.1}\] This means the general strategy for getting an answer from a generating function is to—by some process—write it as as a power series \(\sum a_n x^n\) making sure that it’s \(x^n\). Then \(a_n\) is the answer to the question: how many strings of weight \(n\) are there where (whatever conditions we set).
Theorem 11.1 (Addition Theorem) If \(L\) and \(L'\) are disjoint, then \(\Phi_{L \cup L'}(x) = \Phi_{L}(x) + \Phi_{L'}(x)\).
Proof. To say that \(L\) and \(L'\) are disjoint implies that \[ \#\{s \in L \cup L' : f(s) = n\} = \#\{s \in L : f(s) = n\} + \#\{s \in L' : f(s) = n\}. \] Substituting this into Equation 11.1 yields \[\begin{align*} \Phi_{L \cup L'}(x) &= \sum_{n = 0}^\infty \#\{s \in L : f(s) = n\} x^n + \sum_{n = 0}^\infty \#\{s \in L' : f(s) = n\} x^n \\ &= \Phi_{L}(x) + \Phi_{L'}(x). \end{align*}\]
11.3 Infinite series
We’ve looked at examples where \(L\) is a finite set. In many examples, \(L\) will be an infinite set. For instance consider the infinite set of all strings of \(0\)s. I.e. \(\{\varepsilon, 0, 00, 000, 0000, \dots\}\). For this language, we have the generating function \[ A = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x}. \]
To prove this formula, we take \(A\) and multiply everything by \(x\) because that creates a lot of similar terms: \[\begin{align*} A &= 1 + x + x^2 + x^3 + \cdots \\ xA &= \phantom{1+{}}x + x^2 + x^3 + \cdots \\ A - xA &= 1 \end{align*}\] From which we solve for \(A = \dfrac{1}{1 - x}\).
Example 11.3 Let \(L\) is the language of all binary strings, i.e. \(L = \{\varnothing, 0, 1, 00, 01, 10, 11, 000, \dots\}\). We know that there are \(2^n\) binary strings of length \(n\) so the OGF of \(L\) is \[ \Phi_L(x) = \sum_{n = 0}^\infty 2^nx^n = \sum_{n = 0}^\infty (2x)^n = \frac{1}{1 - 2x}. \]
In a calculus or analysis course, we would want to specify here that \(|x| < \frac12\) for this series to converge. In combinatorics, we treat these series purely algebraically. That means as an infinite list of monomials without care whether or not the series converges. People use the term formal power series to refer to this concept.
11.3.1 When do we care about convergence?
For the most part, we don’t. Meaning an infinite series is still valid even if it doesn’t converge other than when \(x = 0\). However, there are arguements using analysis which only apply to convergent power series. For instance, the fact that the series \[ 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \cdots = \frac{1}{1 - x - x^2} \] converges for \(|x| < \frac{1}{\phi}\) where \(\varphi = \frac{1 + \sqrt5}{2}\) is connected to the fact that the Fibonnaci numbers are approximately \(c \varphi^n\) for some constant \(c\).
Exercise 11.2 In fact, one can show that \[ \mathrm{Fib}_n = \operatorname{round}\left( \frac{\varphi^n}{\sqrt 5} \right). \] Use a calculator or a computer to check this works!