Exponential Generating Functions

Notes

Trotter Chapter 8

Also see: Generating Functions#Trotter Chapter 8: Generating Functions

In the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do we do if we have a problem in which order matters?

In these situations we want to use exponential generating functions. We define an analogous function to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{1-x}} to generate the sequence 1,1,1,1,...: we use the series expansion

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^x = \sum_{n \geq 0} \dfrac{x^n}{n!} }

which gives a basic exponential generating function of:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E(x) = \sum_{n \geq 0} \dfrac{x^n}{n!} }

As before, we will seek to put all functions/sequences of interest in terms of this base function.

Examples

Counting Ternary Strings

Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an even number of 0s.

Solving this problem can be done with the following procedure:

FIRST: Determine the generating function for each of our possible choices. In this case, a ternary string can be 0, 1, or 2. Each discrete choice has its own generating function.

SECOND: Multiply the generating functions together to get the overall generating function.

Generating functions for choices

Start by writing generating functions for each possible choice.

For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} E_1(x) &=& e^x \\ E_1(x) &=& \sum_{n \geq 0} \dfrac{x^n}{n!} \end{align} }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} E_2(x) &=& e^x \\ E_2(x) &=& \sum_{n \geq 0} \dfrac{x^n}{n!} \end{align} }

For the 0s, we can only have an even number of terms, so we need the series

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_0(x) = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots }

Unlike with linear generating functions, where complex numbers eliminate particular terms, exponential functions make this a little easier to do.

Start by writing out the exponential sequence that we are using:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^{x} = 1 + \dfrac{x}{1!} + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \dfrac{x^4}{4!} + \dots }

then substitute -x for x, to get a slightly different series:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle e^{-x} = 1 - \dfrac{x}{1!} + \dfrac{x^2}{2!} - \dfrac{x^3}{3!} + \dfrac{x^4}{4!} - \dots }

If we add these two series together, the odd terms will cancel out, and we will have precisely the terms we want. This identity can be written:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{e^x + e^{-x}}{2} = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots }

Now we have the generating function for the 0 digit:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle E_0(x) = \dfrac{e^x + e^{-x}}{2} = \sum_{k \geq 0} \dfrac{x^{2k}}{(2k)!} }

Overall generating function

The overall generating function is obtained by multiplying all of the above generating functions together.

Now the overall generating function becomes:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} E(x) &=& E_0(x) E_1(x) E_2(x) \\ &=& (e^x) (e^x) \left( \dfrac{e^x+e^{-x}}{2} \right) \\ &=& \dfrac{e^{3x} + e^x}{2} \end{align} }

Now the exponential functions can be converted to infinite series, and the series can be combined and simplified to yield the series form of the generating function.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} \dfrac{e^{3x}+e^x}{2} &=& \dfrac{1}{2} \left( \sum_{n \geq 0} \dfrac{(3x)^n}{n!} + \sum_{k \geq 0} \dfrac{(x)^n}{n!} \right) \\ &=& \dfrac{1}{2} \left( \sum_{k \geq 0} \dfrac{ 3^n x^n + x^n}{n!} \right) \\ &=& \dfrac{1}{2} \left( \sum_{k \geq 0} (3^n + 1) \dfrac{x^n}{n!} \right) \end{align} }

What this means, in the end, is that the coefficient of the nth term of the infinite series expansion of our generating function is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \dfrac{3^n+1}{n!} }

and we can obtain a closed-form expression for the total number of ternary strings of length n having an even number of 0s. It is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3^n + 1 }