Generating Functions

Definition

The generating function for the sequence $a_0,a_1,\dots ,a_k,\dots$ of real numbers is the infinite series

$$G(x)=a_0+a_{1}x+\cdots +a_k{x}^k+\cdots$$

If the sequence is finite, such as $a_0,a_1,\dots ,a_n$, then we could let $a_{n+1}=a_{n+2}=\cdots =0$. Here the generating function becomes a finite series.

Power Series

If $f(x)={\sum }_{k=0}^{\infty }{a}_k{x}^k$ and $g(x)={\sum }_{k=0}^{\infty }{b}_k{x}^k$. Then

$$f(x)+g(x)=\sum _{k=0}^{\infty }(a_k+b_k)x^l$$

and

$$f(x)g(x)=\sum _{k=0}^{\infty }\left(\sum _{j=0}^k{a}_j{b}_{k-j}\right)x^k$$

See also: Power Series

Extended Binomial Theorem

Extended Binomial Coefficient

Let $u$ be a real number and $k$ a non-negative integer. Then the extended binomial coefficient $\left(\genfrac{}{}{0ex}{}{u}{k}\right)$ is defined by

$$\left(\genfrac{}{}{0ex}{}{u}{k}\right)=\{\begin{array}{ll}u(u-1)\cdots (u-k+1)/k!,& \text{if}k>0\\ 1,& \text{if}k=0\end{array}$$

When the top parameter is a negative integer, the extended binomial coefficient can be expressed in terms of an ordinary binomial coefficient:

$$\left(\genfrac{}{}{0ex}{}{-n}{r}\right)=(-1{)}^r(\genfrac{}{}{0ex}{}{n+r-1}{r})$$

The Extended Binomial Theorem

Let $x$ be a real number with $\left|x\right|<1$ and let $u$ be a real number. Then

$$(1+x{)}^u=\sum _{k=0}^{\infty }(\genfrac{}{}{0ex}{}{u}{k})x^k$$

Using this, we can find the generating function of $(1+x{)}^{-n}$, which is

$$(1+x{)}^{-n}=\sum _{k=0}^{\infty }(\genfrac{}{}{0ex}{}{-n}{k})x^k=\sum _{k=0}^{\infty }(-1{)}^k\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)x^k$$

Useful Generating Functions

$G(x)$	$a_k$
$(1+x{)}^n$	$C(n,k)$
$(1+ax{)}^n$	$C(n,k)a^k$
$(1+x^r{)}^n$	$C(n,k/r)$ if $r\mid k$; 0 otherwise
$\frac{1-x^{n+1}}{1-x}$	1 if $k\le n$; 0 otherwise
$\frac{1}{1-x}$	1
$\frac{1}{1-ax}$	$a^k$
$\frac{1}{1-x^r}$	1 if $r\mid k$; 0 otherwise
$\frac{1}{(1-x{)}^2}$	$k+1$
$\frac{1}{(1-x{)}^n}$	$C(n+k-1,k)=C(n+k-1,n-1)$
$\frac{1}{(1+x{)}^n}$	$(-1{)}^{k}C(n+k-1,k)=(-1{)}^{k}C(n+k-1,n-1)$
$\frac{1}{(1-ax{)}^n}$	$C(n+k-1,k)a^k=C(n+k-1,n-1)a^k$
$e^x$	$\frac{1}{k!}$
$\ln (1+x)$	$\frac{(-1{)}^{k+1}}{k}$

Counting Problems and Generating Functions

Number of Solutions for Linear Equation

Find the number of solutions of

$$e_1+e_2+e_3=17$$

where $e_1,e_2$ and $e_3$ are non-negative integers with $2\le e_1\le 5,3\le e_2\le 6$ and $4\le e_3\le 7$.

The number of solutions with the indicated constraints is the coefficient of $x^{17}$ in the expansion of

$$(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)$$

This follows because we obtain a term equal to $x^{17}$ in the product by picking a term in the first sum $x^{e_1}$, a term in the second sum $x^{e_2}$, and a term in the third sum $x^{e_3}$. It is not hard to see that the coefficient of $x^{17}$ in this product is $3$.

Ways to Insert Tokens into a Vending Machine

Determine the number of ways to insert tokens worth $1, $2 and $5 into a vending machine to pay for an item that costs $r$ dollars in both cases

1. when the order in which the tokens are inserted does not matter
2. when the order does matter

First we consider the case when the order in which the tokens are inserted does not matter. The answer is the coefficient of $x^r$ in the generating function

$$(1+x+x^2+\cdots )(1+x^2+x^4+\cdots )\cdots (1+x^5+x^{10}+\cdots )$$

When the order does matter, the number of ways to insert exactly $n$ tokens to procure a total of $r$ dollars is the coefficient of $x^r$ in

$$(x+x^2+x^5{)}^n$$

So the total number is the coefficient of $x^r$ in

$$\sum _{n=0}^{\infty }(x+x^2+x^5{)}^n=\frac{1}{1-x-x^2-x^5}$$

Using Generating Functions to Solve Recurrence Relations

Solve the recurrence relation $a_k=3a_{k-1}$ for $k=1,2,3,\dots$ and initial condition $a_0=2$. Let $G(x)$ be the generating function for the sequence $\left\{a_k\right\}$, that is, $G(x)={\sum }_{k=0}^{\infty }{a}_k{x}^k$. First note that

$$xG(x)=\sum _{k=0}^{\infty }{a}_k{x}^{k+1}=\sum _{k=1}^{\infty }{a}_{k-1}{x}^k$$

Using the recurrence relations, we see that

$$\begin{array}{rl}G(x)-3xG(x)& =\sum _{k=0}^{\infty }{a}_k{x}^k-3\sum _{k=1}^{\infty }{a}_{k-1}{x}^k\\ & =a_0+\sum _{k=1}^{\infty }\left(a_k-3a_{k-1}\right)x^k\\ & =2\end{array}$$

because $a_0=2$ and $a_k=3a_{k-1}$. Thus

$$G(x)-3xG(x)=2⟹G(x)=\frac{2}{1-3x}$$

Using the identity $\frac{1}{1-ax}=\sum _{k=0}^{\infty }{a}^k{x}^k$, therefore $a_k=2\cdot 3^k$ As another example, to solve the recurrence relation

$$a_n{x}^n=8a_{n-1}+10^{n-1},a_0=1$$

We still have

$$G(x)-8xG(x)=\sum _{k=0}^{\infty }{a}_k{x}^k-8\sum _{k=1}^{\infty }{a}_{k-1}{x}^k=1+\sum _{k=1}^{\infty }10^{k-1}{x}^k=\frac{9}{10}+\frac{1}{10}\frac{1}{1-10x}$$

Therefore

$$G(x)=\frac{1}{1-8x}\frac{9(1-10x)+1}{10(1-10x)}=\frac{1-9x}{(1-8x)(1-10x)}=\frac{1}{2}\left(\frac{1}{1-8x}+\frac{1}{1-10x}\right)$$

This leads to

$$a_k=\frac{1}{2}\left(8^n+10^n\right)$$

Proving Identities via Generating Function

To show

$$\sum _{k=0}^n{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

First we note that by the binomial theorem $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ is the coefficient of $x^n$ in $(1+x{)}^{2n}$

$$(1+x{)}^{2n}={\left[\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)x+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)x^n\right]}^2$$

The coefficient of $x^n$ in this expression is

$$\left(\genfrac{}{}{0ex}{}{n}{0}\right)\left(\genfrac{}{}{0ex}{}{n}{n}\right)+\left(\genfrac{}{}{0ex}{}{n}{1}\right)\left(\genfrac{}{}{0ex}{}{n}{n-1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)\left(\genfrac{}{}{0ex}{}{n}{0}\right)$$

This equals ${\sum }_{k=0}^n{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2$, because $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$.

Exponential Generating Function

For sequence $\left\{a_k\right\}$, its exponential generating function (e.g.f.) is defined as

$$A(x)=\sum _{n=0}^{\infty }\frac{a_n{x}^n}{n!}$$

E.g.f.s are particularly useful for sequences where the order of elements is significant, such as permutations or labeled structures, and allow for operations like addition and multiplication similar to ordinary generating functions

To find an exponential generating function for the number of permutations with repetition of length $n$ of the set $\left\{a,b,c\right\}$, in which there are an odd number of $a$ s, an even number of $b$ s, and any number of $c$ s, we consider the following function

$$\sum _{i=0}^{\infty }\frac{x^{2i+1}}{(2i+1)!}\sum _{i=0}^{\infty }\frac{x^{2i}}{(2i)!}\sum _{i=0}^{\infty }\frac{x^i}{i!}$$

We already know if we have 3 $a$ s, 4 $b$ s, and 2 $c$ s, there are $\left(\genfrac{}{}{0ex}{}{9}{342}\right)$ such permutations. Let us consider the coefficient of $x^9/9!$ of the product above. One way to get an $x^9$ term is

$$\frac{x^3}{3!}\frac{x^4}{4!}\frac{x^2}{2!}=\frac{9!}{3!4!2!}\frac{x^9}{9!}=\left(\genfrac{}{}{0ex}{}{9}{342}\right)\frac{x^9}{9!}$$

That is, this one term counts the number of permutations in which there are 3 $a$ s, 4 $b$ s, and 2 $c$ s. The ultimate coefficient of $x^9/9!$ will be the sum of many such terms, counting the contributions of all possible choices of an odd number of $a$ s, and even number of $b$ s, and any number of $c$ s.

Notice that

$$\sum _{i=0}^{\infty }\frac{x^i}{i!}=e^x,\sum _{i=0}^{\infty }\frac{x^{2i}}{(2i)!}=\frac{1}{2}\sum _{i=0}^{\infty }\frac{x^i+(-x{)}^i}{i!}=\frac{e^x+e^{-x}}{2}$$

And similarly

$$\sum _{i=0}^{\infty }\frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2}$$

Thus, the generating function we seek is

$$\frac{e^x-e^{-x}}{2}\frac{e^x+e^{-x}}{2}{e}^x=\frac{1}{4}\left(e^{3x}-e^{-x}\right)$$