Exponential Generating Functions
Trotter Chapter 8
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 to generate the sequence 1,1,1,1,...: we use the series expansion
which gives a basic exponential generating function of:
As before, we will seek to put all functions/sequences of interest in terms of this base function.
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:
For the 0s, we can only have an even number of terms, so we need the series
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:
then substitute -x for x, to get a slightly different series:
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:
Now we have the generating function for the 0 digit:
Overall generating function
The overall generating function is obtained by multiplying all of the above generating functions together.
Now the overall generating function becomes:
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.
What this means, in the end, is that the coefficient of the nth term of the infinite series expansion of our generating function is
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:
Combinatorial Structures - Order Does Not Matter
Ordinary generating functions
Labelled Structures - Order Matters
Enumerating Permutations: String Permutations
Flags · Template:CombinatoricsFlag · e
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e