for k in range(4):
print(binomial(1/2, k))1
1/2
-1/8
1/1614 Coefficient Extraction
In this section, we develop some techniques for extracting coefficients from generating functions. Remember that coefficient of \(x^n\) represents the number of solutions of weight \(n\). So knowing that the generating function is, for example,
\[ A(x) = \frac{x^{k - 1}(x^5 - x^{14})}{(1 - x)^k} = \sum a_n x^n, \]
our goal is to find \(a_n\). A common notation for this is \(a_n = [x^n] A(x)\).
Warning
Be careful! This is not the same thing as \(A(n)\). Plugging in \(n\) is not the way to find the coefficient. For example, the coefficient of \(x^2\) in the quadratic \(f(x) = 2x^2 + 3x + 1\) is \([x^2]f(x) = 2\) and not \(f(2)\) which equals \(15\).
14.1 Shifts
Multiplying \(A(x)\) by \(x^k\) shifts the sequence left or right (depending on whether \(k\) is positive or negative): \[ x^k \sum a_n x^n = \sum a_n x^{n + k} = \sum a_{n - k} x^n. \] The second equals sign is obtained either by substituting \(n \gets n + k\) or by noticing that the coefficient is always \(k\) less than the exponent.
Substituting inside a sum
Consider a summation like \[ \sum_{k = 2}^\infty k(k-1)x^{k - 2}. \] If we want to write this as a sum where \(x^k\) is the exponent in our summand, then we can either
- add \(2\) everywhere we see \(k\): \[ \sum_{k + 2 = 2}^\infty (k + 2)(k + 1)x^{k} = \sum_{k = 0}^\infty (k + 2)(k + 1)x^{k}, \]
- make a substitution of \(n = k - 2\) and \(k = n + 2\) to get \[ \sum_{n + 2 = 2}^\infty (n + 2)(n + 1)x^{n}. \]
Both methods are equivalent.
Putting this together, we have the following result.
Theorem 14.1 (Coefficient Shift) If \(A(x) = \sum a_nx^n\) then \[ [x^n]x^kA(x) = [x^{n - k}] A(x) = a_{n - k}. \] “The coefficient of \(x^n\) in \(x^k A(x)\) is \(a_{n - k}\).”
14.2 Sums and differences
Suppose \(A(x) = \sum a_n x^n, B(x) = \sum b_n x^n\) are two power series. Then for any constants \(\lambda, \mu\), we have \[ \lambda A(x) + \mu B(x) = \lambda \sum a_n x^n + \mu \sum b_n x^n = \sum (\lambda a_n + \mu b_n) x^n. \] In terms of our \([x^n]\) operator, we record the following result.
Theorem 14.2 (Linear Combinations) \[ [x^n](\lambda A(x) + \mu B(x)) = \lambda [x^n] A(x) + \mu [x^n] B(x). \]
14.3 Derivatives
As we saw earlier, \[ A'(x) = \sum na_nx^{n - 1} = \sum (n + 1)a_{n + 1}x^n. \]
Theorem 14.3 (Derivatives and Antiderivatives) \[ [x^n] A'(x) = (n + 1) [x^{n + 1}] A(x). \] Or for antiderivatives, \[ [x^n] A(x) = \frac{1}{n} [x^{n - 1}] A'(x). \]
14.4 Newton’s Binomial Theorem
We’ve seen the Binomial Theorem, \[ (1 + x)^n = \sum_{k = 0}^n \binom{n}{k}x^k. \] And, in the previous section, we worked out power series for \((1 - x)^{-n}\). These kinds of functions are quite common in combinatorics, and not just for integer exponents either.
Definition 14.1 The general binomial coefficient is \[ \binom{r}{k} = \frac{r(r - 1)(r - 2) \cdots (r - k + 1)}{k!} \] and we define this for any real (or complex) number \(r\).
What Newton observed, is that when you take the derivative of \(f(x) = (1 + x)^r\) a few times, you get \[ r(1+x)^{r - 1} \text{ then } r(r - 1) (1 + x)^{r - 2} \text{ then } r(r - 1)(r - 2)(1 + x)^{r - 3}, \dots \]
Theorem 14.4 (Newton’s Binomial Theorem) The Taylor series of \((1 + x)^r\) is \[ \sum_{k = 0}^\infty \binom{r}{k}x^k. \]
Proof. We’ve seen above that for \(f(x) = (1 + x)^r\), we have \[ f^{(k)}(x) = r(r-1)(r-2)\cdots(r - k + 1)(1 + x)^{r - k}. \] Plugging this into the formula for a Taylor series, \[ (1 + x)^r = \sum_{k = 0}^\infty \frac{f^{(k)}(0)}{k!} x^k = \sum_{k = 0}^\infty \frac{r(r - 1)(r - 2) \cdots (r - k + 1)}{k!} = \sum_{k = 0}^\infty \binom{r}{k}x^k. \]
Note
These series converge for at least \(|x| < 1\) (and so techniques of calculus apply to analyzing these series). Convergence for \(x = \pm 1\) depends on \(r\). And of course, if \(r\) is a whole number then the series is finite and converges everywhere.
14.5 Examples
Let’s finally get to solving the problem of Section 13.2.1. Recall that we had the generating function \[ A(x) = \frac{x^{k - 1}(x^5 - x^{14})}{(1 - x)^k} = \frac{x^{k + 4} - x^{k + 13}}{(1 - x)^k}. \] Now we’re going to combine this with the first formula from Section 13.4 to get \[\begin{align*} [x^n] \frac{x^{k + 4} - x^{k + 13}}{(1 - x)^k} &= [x^n] x^{k + 4} \frac{1}{(1 - x^k)} - [x^n] x^{k + 13} \frac{1}{(1 - x)^k} \\ &= [x^{n - k - 4}] \frac{1}{(1 - x)^k} - [x^{n - k - 13}] \frac{1}{(1 - x)^k} \\ &= \binom{(n - k - 4) + k - 1}{k - 1} - \binom{(n - k - 13) + k - 1}{k - 1} \\ &= \binom{n - 5}{k - 1} - \binom{n - 14}{k - 1}. \end{align*}\]
Coefficient extraction with the formulas
The formula from Section 13.4 says \[ \frac{1}{(1 - x)^k} = \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1}x^n. \] That means that the coefficient of \(x^n\) is \[ [x^n] \frac{1}{(1 - x)^k} = \binom{n + k - 1}{k - 1}. \] If we want to apply this to a more complex power of \(x\), we do so by substituting where we see \(n\), for example, \[ [x^{n + 1}] \frac{1}{(1 - x)^k} = \binom{(n + 1) + k - 1}{k - 1} = \binom{n + k}{k - 1}. \]
14.5.1 Negative Binomial Theorem
Comparing Theorem 14.4 and formula (a.) of Section 13.4 yields an interesting result:
\[ \frac{1}{(1 - x)^k} = \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1} x^n = \sum_{n = 0}^\infty \binom{-k}{n} (-x)^n. \tag{14.1}\] Note that we are looking at \((1 - x)^{-k}\) not \((1 + x)^{-k}\) hence the \((-x)\) on the right.
The next theorem is most often stated with \(n\) and \(k\) swapped. We also use the identity \(\binom{a + b}{a} = \binom{a + b}{b}\).
Theorem 14.5 (Negative Binomial Theorem) \[ \binom{-k}{n} (-1)^n = \binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}. \] Or, with \(n\) and \(k\) in the usual position: \[ \binom{-n}{k} (-1)^k = \binom{n + k - 1}{n - 1} = \binom{n + k - 1}{k}. \]
Like many things in combinatorics, it’s interesting to give a second proof of this beyond the generating function proof in Equation 14.1.
Proof. \[\begin{align*} \binom{-n}{k} (-1)^k &= \frac{(-n)(-n - 1)(-n - 2)\cdots(-n-k+1)}{k!} (-1)^k \\ &= \frac{(n)(n + 1)(n + 2)\cdots(n+k-1)}{k!} \\ &= \frac{(n + k - 1)(n + k - 2) \cdots (n + 1)(n)}{k!} \\ &= \binom{n + k - 1}{k}. \end{align*}\] In line 2, we distribute one \(-1\) to each of the \(k\) factors in the numerator.
14.5.2 Central Binomial Theorem
We’ve seen the binomial theorem with a whole number exponent. We’ve seen it with a negative integer exponent. The next place to go is fractions. Let’s start with \(n = \frac12\). For reference, here are the first couple values of this:
It would seem that these are \(\pm 1\) over some power of \(2\) but if we continue our computation, we find that the next value is \(-5/128\).
In order to get to the bottom of this, we need to work this out from the definition:
\[\begin{align*} \binom{1/2}{k} &= \frac{\frac12(\frac12 - 1)(\frac12 - 2)\cdots(\frac12 - k + 1)}{k!} \\ &= \frac{\frac12 (-\frac12)(-\frac32)(-\frac52) \cdots (-\frac{2k - 3}{2})}{k!} \\ &= \frac{(-\frac12)^{k-1}(1)(3)(5)\cdots(2k-3)}{2k!} \\ &= (-1)^{k-1}\frac{(1)(3)(5)\cdots(2k-3)}{2^kk!}. \\ \end{align*}\]
This is a pretty good formula. We can also write it in terms of the double factorial which is the product of all the odd numbers up to \(2k - 3\). (It’s called double because the factors decrease by \(2\) each time instead of \(1\).)
But like in the Wikipedia article, we can write double factorials in terms of more usual factorials. We do this by adding in the missing even numbers to the numerator and balancing that out in the denominator:
\[\begin{align*} \binom{1/2}{k} &= (-1)^{k-1}\frac{(1)(3)\cdots(2k-3) \cdot (2)(4) \cdots (2k - 2)}{2^kk! \cdot (2)(4) \cdots (2k - 2)} \\ &= (-1)^{k-1}\frac{(1)(2)(3)\cdots(2k-3)(2k - 2)}{2^kk! \cdot 2^{k-1} (1)(2) \cdots (k - 1)} \\ &= (-1)^{k-1}\frac{(2k - 2)!}{2^{2k-1}k!(k - 1)!} \\ &= (-1)^{k-1} \frac{1}{2^{2k - 1}k} \binom{2k-2}{k - 1} \end{align*}\]
Let’s do this once more with \(n = -1/2\) but going through the steps a bit quicker:
\[\begin{align*} \binom{-1/2}{k} &= \frac{(-\frac12)(-\frac32)(-\frac52) \cdots (-\frac{2k - 1}{2})}{k!} \\ &= (-1)^k \frac{1 \cdot 3 \cdot 5 \cdots (2k - 1)}{2^k k!} \\ &= (-1)^k \frac{(2k)!}{2^k k! \cdot (2)(4) \cdots (2k)} \\ &= (-1)^k \frac{(2k)!}{2^k k! \cdot 2^k k!} \\ &= (-1)^k \frac{1}{4^k} \binom{2k}{k}. \end{align*}\]
Let us record these results as a theorem.
Theorem 14.6 (Half Binomials) \[ \binom{1/2}{k} = (-1)^{k-1} \frac{1}{2^{2k - 1}k} \binom{2k-2}{k - 1} \text{ and } \binom{-1/2}{k} = \frac{(-1)^k}{4^k} \binom{2k}{k}. \] The first formula is only valid for \(k \ge 1\). If \(k = 0\) then we get \(\binom{1/2}{0} = 1\) (product of zero terms in the numerator equals \(1\) and the denominator is \(0! = 1\)).
Example 14.1 Take the second formula, and use it with Theorem 14.4. We will put \((-4x)^k\) instead of \(x^k\) to cancel the \((-1/4)^k\). That is, \[\begin{align*} \frac{1}{\sqrt{1 - 4x}} = (1 - 4x)^{-1/2} &= \sum_{k = 0}^\infty \binom{-1/2}{k} (-4x)^k \\ &= \sum_{k = 0}^\infty \frac{(-1)^k}{4^k} \binom{2k}{k} (-4x)^k \\ &= \sum_{k = 0}^\infty \binom{2k}{k} x^k \\ \end{align*}\]
This is a neat little result in and of itself but there is deeper implications here. Consider the number of binary strings of length \(2k\) with an equal number of \(0\)s and \(1\)s. That means there are \(k\) of each, and that gives us the formula \(\binom{2k}{k}\). These are called the central binomial coefficients because they appear right down the center of Pascal’s triangle.
For those of you who have taken computer science or mathematical linguistics, there is a concept known as a “regular language”—languages which can be parsed by a regular expresion1. For these regular languages, we will see later on, that they always yeild a rational generating function. Here we have a non-rational generating function and indeed this language of strings with equal numbers of \(0\)s and \(1\)s is not a regular language.
Going beyond regular languages, the Chomsky–Schützenberger Theorem says that if you have an unambiguous context-free grammar, then the generating function for that language is algebraic. That is what we are looking at with \(\frac{1}{\sqrt{1 - 4x}}\). This is an algebraic function because it is a square root of a rational function. Indeed, the language of strings with equal numbers of \(0\)s and \(1\)s is a context-free language.
14.5.3 Catalan Numbers
If you remember the formula for the Catalan numbers even vaguely, you’ll recognize the \(\binom{2k}{k}\). If you squint real hard, the first formula of Theorem 14.6 looks vaguely similar once you deal with the \((-1)^k\) and the \(4^k\) as we did in Example 14.1. Let’s dig into that.
First, recall the decomposition we had for Dyck paths.
In terms of “the language of Dyck paths,” what this says is that a Dyck path of length \(n\) is equal to
- a shift one step up from the diagonal
- a Dyck path of length \(k - 1\)
- a Dyck path of length \(n - k\)
Here’s the beauty of generating functions: as long as we keep track of the shifts, we don’t need to keep track of the lengths of the subwords or subpaths. So we can describe the language of Dyck paths in simpler terms: it is a shift, together with two smaller Dyck paths. Therefore, if we represent our shift by the monomial \(x\), and our Catalan generating function by \(C(x)\), what we have here is \(xC(x)^2\).
We almost have it, we just need to be careful of the edge case. If \(n = 0\), the path from \((0,0)\) to \((0,0)\) is a valid Dyck path which involves no shift. So a Dyck path is either
- this length \(0\) Dyck path, which has OGF \(x^0 = 1\)
- a shift, together with two Dyck paths, with OGF \(xC(x)^2\).
Therefore, \(C(x)\) satisfies the equation \[ C(x) = 1 + xC(x)^2. \]
If you solve this quadratic equation using the quadratic formula, we find that \[ C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}. \tag{14.2}\]
In order to get numbers out of this, we use Theorem 14.4 to expand the square root (separating the \(k = 0\) term so we can apply the formula from Theorem 14.6): \[\begin{align*} \sqrt{1 - 4x} &= 1 + \sum_{k = 1}^\infty \binom{1/2}{k}(-4x)^k \\ &= 1 + \sum_{k = 1}^\infty (-1)^{k-1} \frac{1}{2^{2k - 1}k} \binom{2k-2}{k - 1} (-4x)^k \\ &= 1 + \sum_{k = 1}^\infty \frac{-2}{k} \binom{2k-2}{k - 1} x^k. \end{align*}\]
The presence of the \(-\) sign indicates that we want to use the negative square root in Equation 14.2. Doing this, we obtain
\[\begin{align*} - \sqrt{1 - 4x} &= - 1 + \sum_{k = 1}^\infty \frac{2}{k} \binom{2k-2}{k - 1} x^k \\ 1 - \sqrt{1 - 4x} &= \sum_{k = 1}^\infty \frac{2}{k} \binom{2k-2}{k - 1} x^k \\ \frac{1 - \sqrt{1 - 4x}}{2x} &= \sum_{k = 1}^\infty \frac{1}{k} \binom{2k-2}{k - 1} x^{k - 1} \\ &= \sum_{k = 0}^\infty \frac{1}{k + 1} \binom{2k}{k} x^k \end{align*}\] (adding \(1\) to each \(k\) to get from \(k - 1\) to \(k\)).
We’ve now found another way to get our Catalan number formula.
Theorem 14.7 (Catalan OGF) The generating function for the Catalan numbers is \[ C(x) = \frac{1 - \sqrt{1 - 4x}}{2x} = \sum_{k = 0}^\infty \frac{1}{k + 1} \binom{2k}{k} x^k. \]
We’ll define many of these terms in a later section for those of you who haven’t seen them before.↩︎