Combinatorics (home): Theory of generating functions (home)

1. Introduction and main theorems
2. Recursive equations
3. The method of snake oil
4. Problems and solutions

Theoretical Introduction to Generating Functions

When dealing with generating functions we frequently want to use different transformations and manipulations that are illegal if the generating functions are viewed as analytic functions. Therefore they will be introduced as algebraic objects in order to obtain wider range of available methods. The theory we will develop is called the formal theory of power series.

The set of natural numbers will be denoted by \(\mathbb{N}\), while \(\mathbb N_0\) will stand for the set of non-negative integers. For the sums going from \(0\) to \(+\infty\) the bounds will frequently be omitted -- if a sum is without the bounds, they are assumed to be \(0\) and \(+\infty\).

Definition A formal power series is the expression of the form \[a_0+a_1x+a_2x^2+\cdots = \sum_{i=0}^{\infty} a_ix^i.\] A sequence of integers \(\{a_i\}_0^\infty\) is called the sequence of coefficients.

Remark. We will use the other expressions also: series, generating function...

For example the series \[A(x)=1+x+2^2x^2+3^3x^3+\cdots+n^nx^n+\cdots\] converges only for \(x=0\) while, in the formal theory this is well defined formal power series with the correspongind sequence of coefficients equal to \(\{a_i\}_0^\infty, a_i=i^i\).

Remark. Sequences and their elements will be most often denoted by lower-case latin letters (\(a\), \(b\), \(a_3\) \(\cdots\)), while the power series generated by them (unless stated otherwise) will be denoted by the corresponding capital letters (\(A\), \(B\), \(\cdots\)).

Definition Two series \(A=\sum_{i=0}^{\infty} a_ix^i\) and \(B=\sum_{i=0}^{\infty} b_ix^i\) are called equal if their corresponding sequences of coefficients are equal, i.e. \(a_i=b_i\) for every \(i\in {\mathbb N_0}\).

Remark. The coefficient near \(x^n\) in the power series \(F\) will be denoted by \([x^n]F\).

We can define the sum and the difference of power series in the following way \[\sum_n a_nx^n \pm \sum_n b_nx^n=\sum_n(a_n\pm b_n)x^n\] while the product is defined by

\[\sum_n a_nx^n \sum_n b_nx^n=\sum_n c_nx^n, \qquad c_n=\sum_i a_ib_{n-i}\]

Instead of \(F\cdot F\) we write \(F^2\), and more generally \(F^{n+1}=F\cdot F^n\). We see that the neutral for addition is 0, and 1 is the neutral for multiplication. Now we can define the following term:

Definition The formal power series \(G\) is reciprocal to the formal power series \(F\) if \(FG=1\).

The generating function reciprocal to \(F\) will be usually denoted by \(1/F\). Since the multiplication is commutative we have that \(FG=1\) is equivalent to \(GF=1\) hence \(F\) and \(G\) are mutually reciprocal. We also have \((1-x)(1+x+x^2+\cdots)=1+\sum_{i=1}^\infty (1\cdot 1 - 1\cdot 1)x^i=1\) hence \((1-x)\) and \((1+x+x^2+\cdots)\) are mutually reciprocal.

Theorem 1. Formal power series \(F=\sum_n a_nx^n\) has a reciprocal if and only if \(a_0\neq0\). In that case the reciprocal is unique.

Now we can conclude that the set of power series with the above defined operation forms a ring whose invertible elements are precisely those power series with the non-zero first coefficient.

If \(F=\sum_n f_nx^n\) is a power series, \(F(G(x))\) will denote the series \(F(G(x))=\sum_n f_nG(x)^n\). This notation will be used also in the case when \(F\) is a polynomial (i.e. when there are only finitely many non-zero coefficients) or if the free term of \(G\) equals 0. In the case that the free term of \(G\) equal to 0, and \(F\) is not a polynomial, we can’t determine the particular element of the series \(F(G(x))\) in finitely many steps.

Definition A formal power series \(G\) is said to be an inverse of \(F\) if \(F(G(x))=G(F(x))=x\).

We have a symmetry here as well, if \(G\) is inverse of \(F\) than \(F\) is inverse of \(G\) as well.

Theorem 2. Let \(F\) and \(G\) be mutually inverse power series. Then \(F=f_1x+f_2x^2+\cdots\), \(G=g_1x+g_2x^2+\cdots\), and \(f_1g_1\neq 0\).

Definition The derivative of a power series \(F=\sum_n f_nx^n\) is \(F^{\prime}=\sum_n nf_nx^{n-1}\). The derivative of order \(n > 1\) is defined recursively by \(F^{(n+1)}=(F^{(n)})^{\prime}\).

Theorem 3. The following properties of the derivative hold:
  • \((F+G)^{(n)}=F^{(n)}+G^{(n)}\)
  • \((FG)^{(n)}= \sum_{i=0}^n \binom{n}{i} F^{(i)}G^{(n-i)}\)

The proof is very standard as is left to the reader.

We will frequently associate the power series with its generating sequence, and to make writing more clear we will define the the relation \(\genfrac{}{}{0pt}{}{os}{\leftrightarrow}\) in the following way:

Definition \(A \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \{a_n\}_0^\infty\) means that \(A\) is an ordinary power series which is generated by \(\{a_n\}_0^\infty\), i.e. \(A=\sum_n a_nx^n\).

Assume that \(A \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \{a_n\}_0^\infty\). Then \[\sum_n a_{n+1}x^n=\frac {1}{x}\sum_{n > 0}a_nx^n= \frac{A(x)-a_0}{x}\] or equivalently \(\{a_{n+1}\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \frac{A-a_0}{x}\). Similarly \[\{a_{n+2}\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \frac{(A-a_0)/x-a_1}{x}= \frac{A-a_0-a_1x}{x^2}.\]

Theorem 4. If \(\{a_n\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} A\) the for \(h > 0\): \[\{a_{n+h}\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \frac{A-a_0-a_1x-\cdots-a_{h-1}x^{h-1}}{x^h}.\]

We already know that \(\{(n+1)a_{n+1}\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} A^{\prime}\). Our goal is to obtain the sequence \(\{na_n\}_0^\infty\). That is exactly the sequence \(xA^{\prime}\). We will define the operator \(xD\) in the following way:

Definition \(xDA= xA^{\prime}\) i.e. \(xDA= x\frac{dA}{dx}\).

The following two theorems are obvious consequences of the properties of the derivative:

Theorem 5. Let \(\{a_n\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} A\). Then \(\{n^ka_n\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} (xD)^kA\).

Theorem 6. Let \(\{a_n\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} A\) and \(P\) be a polynomial. Then \[P(xD)A \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \{P(n)a_n\}_0^\infty.\]

Let us consider the generating function \(\frac A{1-x}\). It can be written as \(A\frac 1{1-x}\). As we have shown before the reciprocal to the series \(1-x\) is \(1+x+x^2+\cdots\), hence \(\frac A{1-x}=(a_0+a_1x+a_2x^2+\cdots)(1+x+x^2+\cdots) =a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\cdots\).

Theorem 7. If \(\{a_n\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} A\) then \[\frac A{1-x} \quad \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \quad \left\{\sum_{j=0}^na_j\right\}_{n\geq 0}.\]

Now we will introduce the new form of generating functions.

Definition We say that \(A\) is exponential generating function (or series, power series) of the sequence \(\{a_n\}_0^\infty\) if \(A\) is the usual generating function of the sequence \(\{\frac{a_n}{n!}\}_0^\infty\), or equivalently \[A=\sum_n \frac{a_n}{n!}x^n.\] If \(B\) is exponential generating function of the series \(\{b_n\}_0^\infty\) we can also write \(\{b_n\}_0^\infty \genfrac{}{}{0pt}{}{es}{\leftrightarrow} B\).

If \(B \genfrac{}{}{0pt}{}{es}{\leftrightarrow} \{b_n\}_0^\infty\), we are interested in \(B^{\prime}\). It is easy to see that \[B^{\prime}=\sum_{n=1}^\infty \frac{nb_nx^{n-1}}{n!}=\sum_{n=1}^\infty \frac{b_nx^{n-1}}{(n-1)!}=\sum_{n=0}^{\infty} \frac{b_{n+1}x^n}{n!}\] hence \(B^{\prime} \genfrac{}{}{0pt}{}{es}{\leftrightarrow} \{b_{n+1}\}_0^\infty\).

Theorem 8. If \(\{b_n\}_0^\infty \genfrac{}{}{0pt}{}{es}{\leftrightarrow} B\) then for \(h\geq 0\): \[\{b_{n+h}\}_0^\infty \quad \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \quad B^{(h)}.\]

We also have an equivalent theorem for exponential generating functions.

Theorem 9. Let \(\{b_n\}_0^\infty \genfrac{}{}{0pt}{}{es}{\leftrightarrow} B\) and let \(P\) be a polynomial. Then \[P(xD)B \genfrac{}{}{0pt}{}{es}{\leftrightarrow} \{P(n)b_n\}_0^\infty.\]

The exponential generating functions are useful in combinatorial identities because of the following property.

Theorem 10. Let \(\{a_n\}_0^\infty \genfrac{}{}{0pt}{}{es}{\leftrightarrow} A\) and \(\{b_n\}_0^\infty \genfrac{}{}{0pt}{}{es}{\leftrightarrow} B\). Then the generating function \(AB\) generates the sequence \[\left\{\sum_k \binom nk a_kb_{n-k} \right\}_{n=0}^\infty.\]

We have listed above the fundamental properties of generating functions. New properties and terms will be defined later.

Although the formal power series are defined as solely algebraic objects, we aren’t giving up their analytical properties. We will use the well-known Taylor’s expansions of functions into power series. For example, we will treat the function \(e^x\) as a formal power series obtained by expanding the function into power series, i.e. we will identify \(e^x\) with \(\sum_{n=0}^{\infty} \frac{x^n}{n!}\). We will use the converse direction also. Here we will list the Taylor expansions of most common functions.

\[\frac 1{1-x}=\sum_{n\geq0}x^n\] \[\ln\frac 1{1-x}=\sum_{n\geq1} \frac{x^n}n\] \[e^x=\sum_{n\geq0}\frac{x^n}{n!}\] \[\sin x = \sum_{n\geq0}(-1)^n \frac{x^{2n+1}}{(2n+1)!}\] \[\cos x = \sum_{n\geq0}(-1)^n \frac{x^{2n}}{(2n)!}\] \[(1+x)^\alpha=\sum_k \binom{\alpha}{k}x^k\] \[\frac1{(1-x)^{k+1}}=\sum_n \binom{n+k}{n}x^n\] \[\frac{x}{e^x-1}=\sum_{n\geq0} \frac{B_nx^n}{n!}\] \[\arctan x=\sum_{n\geq0}(-1)^n\frac{x^{2n+1}}{2n+1}\] \[\frac1{2x}(1-\sqrt{1-4x})=\sum_n \frac1{n+1}\binom{2n}{n}x^n\] \[\frac1{\sqrt{1-4x}}=\sum_n \binom{2n}{n} x^n\] \[x \cot x=\sum_{n\geq0} \frac{(-4)^nB_{2n}}{(2k)!}x^{2n}\] \[\tan x=\sum_{n\geq1}(-1)^{n-1}\frac{2^{2n}(2^{2n}-1)B_{2n}}{(2n)!}x^{2n-1}\] \[\frac x{\sin x}=\sum_{n\geq0}(-1)^{n-1}\frac{(4^n-2)B_{2n}}{(2n)!}x^{2n}\] \[\frac1{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^k=\sum_n \binom{2n+k}{n}x^n\] \[\left(\frac{1-\sqrt{1-4x}}{2x}\right)^k=\sum_{n\geq0}\frac{k(2n+k-1)!}{n!(n+k)!}x^n\] \[\arcsin x=\sum_{n\geq0}\frac{(2n-1)!!x^{2n+1}}{(2n)!!(2n+1)}\] \[e^x\sin x=\sum_{n\geq1}\frac{2^\frac n2\sin \frac{n\pi}4}{n!}x^n\] \[\ln^2\frac1{1-x}=\sum_{n\geq2}\frac{H_{n-1}}{n}x^n\] \[\sqrt{\frac{1-\sqrt{1-x}}x}=\sum_{n=0}^{\infty} \frac{(4n)!}{16^n\sqrt2(2n)!(2n+1)!}x^n\] \[\left(\frac{\arcsin x}x\right)^2=\sum_{n=0}^{\infty} \frac{4^nn!^2}{(k+1)(2k+1)!}x^{2n}\]

Remark: Here \(H_n=\sum_{i=1}^n \frac 1i\), and \(B_n\) is the \(n\)-th Bernoulli number.