Generating Functions

For coverage of generating functions specific to Donald Knuth's Art of Computer Programming, see AOCP/Generating Functions.

Notes

Sedgewick Flajolet: Analysis of Algorithms

Ordinary Generating Functions

Definition: define an ordinary generating function using the relation:

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 G(z) = \sum_{k \geq 0} a_k z^k }

Notation for denoting a particular coefficient:

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 \left[ z^n \right] G(z) = \mbox{coefficient of }z^N }

To add coefficeints raised to the N power, add a coefficient to z:

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 G(cz) = \sum_{k \geq 0} a_k c^k z^k = a_0 + c a_1 + c^2 a_2 + \dots }

For example, powers of 2 coefficients are given by 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 \dfrac{1}{1 - 2z} = 1 + 2 z + 4 z^2 + 8 z^3 + \dots }

Can also perform operations on generating function.

Addition

To add generating functions together:

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} G_1 &=& \sum_{k \geq 0} a_k z^k \\ G_2 &=& \sum_{k \geq 0} b_k z^k \end{align} }

then:

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 G_1 + G_2 = (a_0 + b_0) + (a_1 + b_1) z + (a_2 + b_2) z^2 + \dots }

Differentiation

Can also take derivative of series to get:

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 z G'(z) = \sum_{k \geq 1} k a_k z^k = 0 + 1 a_1 z + 2 a_2 z^2 + 3 a_3 z^3 + \dots }

Also note that the derivative of the basic generating function is given by:

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{d}{dx} \left( \dfrac{1}{1-z} \right) = \dfrac{z}{(1 - z)^2} }

This operation can be performed an arbitrary number of times:

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-z} = \sum_{k \geq 0} z^k \rightarrow 1, 1, 1, 1, \dots }

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{z}{(1-z)^2} = \sum_{k \geq 1} k z^k \rightarrow 0, 1, 2, 3, 4, 5, \dots }

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{z^2}{(1-z)^3} = \sum_{k \geq 2} \binom{k}{2} z^k \rightarrow 0, 0, 1, 3, 6, 10, \dots }

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{z^m}{(1-z)^{m+1}} = \sum_{k \geq m} \binom{k}{m} z^k \rightarrow 0, \dots, 1, M+1, (M+2)(M+1)/2, \dots }

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-z)^{m+1}} = \sum_{k \geq 0} \binom{k + m}{m} z^k \rightarrow 1, (M+1), (M+2)(M+1)/2, \dots }

Integration

Can also integrate generating functions. Suppose we have a 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 G(z) = \sum_{k \geq 0} a_k z^k }

then

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 \int_0^{z} G(t) dt = \sum_{k \geq 1} \dfrac{a_{n-1}}{n} z^n = 0 + a_0 z + \dfrac{a_1}{2} z^2 + \dfrac{a_2}{3} z^3 + \dots + \dfrac{ a_{k-1} }{k} z^k + \dots }

For example:

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 \ln \left( \dfrac{1}{1-z} \right) = \sum_{k \geq 1} \dfrac{z^k}{k} \rightarrow 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \dots }

Partial Sum Of Prior Terms

A more exotic operation is a partial sum - this allows us to write a sequence that is the sum of each prior term in the sequence. For example, suppose we start with our usual generating function G(z):

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 G(z) = \sum_{k \geq 0} a_k z^k \rightarrow a_0, a_1, a_2, \dots, a_k, \dots }

Now we can multiply the generating function by itself to get:

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-z} G(z) \rightarrow a_0, (a_0 + a_1), (a_0 + a_1 + a_2), \dots }

This can be obtained via the following operations:

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{1}{1-z} G(z) &=& \sum_{k \geq 0} z^k \sum_{m \geq 0} a_m z^m \\ &=& \sum_{k \geq 0} \sum_{m \geq 0} a_m z^{m+k} \\ &=& \sum_{k \geq 0}{m \geq k} a_{m-k} z^{m} \end{align} }

(note that the last step there is just switching m for m-k.) Continuing:

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{1}{1-z} G(z) &=& \sum_{m \geq 0} \left( \sum_{0 \leq k \leq m} a_{m-k} \right) z^m \\ &=& \sum_{m \geq 0} \left( \sum_{0 \leq k \leq m} a_k \right) z^m \end{align} }

Some examples of this: start with the log generating function, as before,

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{1}{1-z} &=& \sum_{k \geq 0} z^k \qquad \rightarrow \qquad 1, 1, 1, 1,1 ,1, \dots \\ \ln \left( \dfrac{1}{1-z} \right) &=& \sum_{k \geq 1} \dfrac{z^k}{k} \qquad \rightarrow \qquad 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots \\ \frac{1}{1-z} \ln \left( \frac{1}{1-z} \right) &=& \sum_{k \geq 1} H_k z^k \qquad \rightarrow \qquad 1, 1 + \frac{1}{2}, 1 + \frac{1}{2} + \frac{1}{3}, 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}, \dots \end{align} }

Multiplication

Multiplying two generating functions is called the convolution of two OGFs. Given two generating functions:

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\begin{aligned}G_{1}(z)&=&\sum _{k\geq 0}a_{k}z^{k}\\G_{2}(z)&=&\sum _{k\geq 0}b_{k}z^{k}\end{aligned}}}

Now the product of these two gives 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 \begin{align} G_1(z) G_2(z) &=& \sum_{k \geq 0} a_k z^k \sum_{m \geq 0} b_m z^m \\ &=& \sum_{k \geq 0} \sum_{m \geq 0} a_k b_m z^{k+m} \\ &=& \sum_{k \geq 0} \sum_{m \geq k} a_k b_{m-k} z^m \\ &=& \sum_{m \geq 0} \sum_{0 \leq k \leq m} a_k b_{m-k} z^m \end{align} }

This gives us 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 G_1(z) G_2(z) \qquad \rightarrow \qquad a_0 b_0, (a_1 b_0 + a_1 b_0), (a_2 b_0 + a_1 b_1 + a_0 b_2), \dots }

Example:

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-z} \qquad \rightarrow \qquad 1, 1, 1, 1, 1, \dots }

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-z)^2} = \dfrac{1}{1-z} \dfrac{1}{1-z} = \sum_{k \geq 0} (k+1) z^k \qquad \rightarrow \qquad 1, 2, 3, 4, 5, \dots }

Expanding Generating Function

Expanding a generating function is the process of expressing unknown generating function as power series.

Typically using Taylor Theorem to expand a function in terms of its derivatives, or using a known generating function (OGF or EGF)

Example: Two-Term Recurrence

Suppose we have the recurrence:

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 a_n = 5 a_{n-1} - 6 a_{n-2} \qquad a_0 = 0, a_1 = 1, n \geq 2 }

then we can write this recurrence as:

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 a_n = 5 a_{n-1} - 6 a_{n-2} + \delta_{n1} }

Now multiply by 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 z^n} , and sum over all n

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 G(z) = 5 z G(z) - 6 z^2 G(z) + z }

Solving this for G,

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 G(z) = \dfrac{z}{1 - 5z + 6z^2} }

Now using partial fractions gives

$G(z)={\dfrac {1}{1-3z}}-{\dfrac {1}{1-2z}}$

(where the partial fractions expansion results in +1 and -1 as the numerators.)

Expanding this gives:

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a_{n}=3^{n}-2^{n}}

Example: Three-Term Recurrence

Suppose we have the recurrence:

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a_{n}=5a_{n-1}-8a_{n-2}+4a_{n-3}\qquad n\geq 3,a_{0}=0,a_{1}=1,a_{2}=4}

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G(z)={\dfrac {z-z^{2}}{1-5z+8z^{2}-4z^{3}}}\ dfrac{z(1-z)}{(1-z)(1-2z)^{2}}={\dfrac {z}{(1-2z)^{2}}}}

Expanding and obtaining an expression for the nth term:

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a_{n}=n2^{n-1}}

Note that if we had a term in the denominator with a higher multiplicity, say a multiplicity of p, we would end up with $n^{p-1}\beta ^{n+p-3}$

Example: Imaginary Roots

Suppose we have an irreducible quadratic in our simplified/combined 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 a_n = 2 a_{n-1} - a_{n-2} + 2 a_{n-3} \qquad n \geq 3, a_0 = 1, a_1 = 0, a_2 = -1 }

Recurrence:

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 a_n = 2 a_{n-1} - a_{n-2} + 2 a_{n-3} + \delta_{n0} - 2 \delta_{n1} }

Now multiply by 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 z^n} :

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 G(z) = 2 z G(z) - z^2 G(z) + 2 z^3 G(z) + 1 - 2 z }

Expanding/solving/simplifying:

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 G(z) = \frac{1-2z}{1 -2 z + z^2 - 2z^3} }

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 G(z) = \dfrac{1}{(1 + z^2)} }

Now we have an irreducible quadratic. Expanding this using partial fractions yields:

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 G(z) = \dfrac{1}{2} \left( \dfrac{1}{1 - iz} + \dfrac{1}{1 + iz} \right) }

Now the nth term of the series can be written as:

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 a_n = \dfrac{1}{2} \left( i^n + (-i)^n \right) = \dfrac{1}{2} i^n \left(1 + (-1)^n \right) \qquad \rightarrow \qquad 1, 0, -1, 0, 1, 0, -1, 0, 1, \dots }

Example: Quicksort Recurrence

Consider the recurrence relation for quicksort.

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 C_n = n + 1 + \dfrac{2}{n} \sum_{ 1 \leq k \leq n } C_{k-1} }

To solve this, we can turn each term in the recurrence into a generating function. Start by multiplying both sides by 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 z^n} and then sum over all n:

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 n c_n = n(n+1) + 2 \sum_{1 \leq k \leq n} C_{k-1} z^n }

now summing over n:

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 \sum_{n \geq 1} n C_n z^n = \sum_{n \geq 1} n (n+1) z^n + 2 \sum_{n \geq 1} \sum_{1 \leq k \leq n} C_{k-1} z^n }

Looking at each term and turning it into a generating function, we can see the first term (left hand side) is the derivative of our usual 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 C'(z) = \dfrac{2}{(1-z)^3} + 2 \dfrac{C(z)}{1-z} }

Note that this is a differential equation, which can be solved using an integrating factor:

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 \rho^{\prime}(z) = \dfrac{ 2 \rho(z) }{ 1-z } \qquad \rightarrow \qquad \rho(z) = \dfrac{1}{(1-z)^2} }

This leads to a solution for the differential equation:

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 \left( (1-z)^2 C(z) \right)^{\prime} = (1-z)^2 C'(z) - 2(1-z)C(z) }

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 \left( (1-z)^2 C(z) \right)^{\prime} = (1-z)^2 \left( C'(z) - 2 \dfrac{C(z)}{1-z} \right) = \dfrac{2}{1-z} }

Now we have our solution:

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 C(z) = \dfrac{2}{(1-z)^2} \ln \left( \dfrac{1}{1-z} \right) }

Finally, we get a expression for the nth term in 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 C_n = \left[ z^n \right] \dfrac{2}{(1-z)^2} \ln \left( \dfrac{1}{1-z} \right) = 2 (n+1) (H_{n+1} - 1) }

Trotter Chapter 8: Generating Functions

Alternative Generating Functions Introduction

To approach generating functions: consider the problem of distributing apples among children.

We can even boil it down to a super simple case: distributing n apples among n children.

In this case, if there are no apples, the coeff is 0. If there is 1 apple, 1 way to distribute. If 2 apples, 1 way to distribute. Etc.

This makes 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 x + x^2 + x^3 + \dots = x ( 1 + x + x^2 + x^3 + \dots) }

And this is, as we already know, equivalent 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{x}{1-x} = x + x^2 + x^3 + \dots = x ( 1 + x + x^2 + x^3 + \dots ) }

Now consider the case where there are two children. Now, each child has an independent scenario in which it gets a particular number of apples. To cover all of these combinations we can multiply two copies of the generating function together:

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 (x + x^2 + x^3 + \dots ) ( x + x^2 + x^3 + \dots ) }

Now in this case, there is no leading term (no zero-apples case), but there is also no one-apples case, either, since there is no way to obtain an x term. This corresponds to the scenario we have set up, in which each child must have one apple.

That is, when we defined the generating function, we defined the generating function such that if there are no apples, there are no possible configurations. This means that any child getting zero apples is not a possible configuration.

If we went back and changed the generating 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 1 + z + z^2 + z^3 + \dots }

then we would end up with one possible configuration when a given child has zero apples. This would carry through, so that when there are two children, there is one possible configuration when there are zero apples (z = 0; the leading constant term is 1), and there are also two possible configurations (z + z = 2z) for the case when there is one apple (z = 1; the 2z term gives us 2 configurations).

So, as mentioned 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 \sum_{k \geq 0} z^k} contains no terms for the 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 k=0} case, because each child must have 1 apple.

If we extend this to n children, we will multiply n copies of the original series. Consider the 5-child case:

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 (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) }

Here, the smallest term 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 z^5} which corresponds to a single possible configuration when there are five apples.

If we look at the term 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 z^n} this represents the number of ways we can distribute n apples among a certain number of children (the number of children determines the final form of the function, i.e., the structure of the problem; n just determines which coefficient of the function we're asking for, i.e., the size of the problem).

Therefore, the coefficient 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 x^n} in our generating function represents the number of ways that we can combine the number of apples each child gets (indexed by k):

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 k_1 + k_2 + k_3 + \dots + k_i = n }

Suppose we have 6 apples. Then we are asking, how many ways can we distribute 6 apples among 5 children? This is a relatively easy question, one that can be answered with the binomial coefficient. What we are asking is, how many ways can we combine 5 different k values (one for each child, indicating how many apples they get, or the exponent on the z term) to get a total of 6, which is the total number of apples available.

For five children,

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 (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) (z + z^2 + z^3 + \dots ) }

To combine 6 z terms together to get z^6, with the restriction that one z must come from each group, results in the following sets of choices:

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 \{ z, z, z, z, z^2 \}, \{ z, z, z, z, z^2, z \}, \{ z, z, z, z^2, z, z \}, \dots }

which is 5 choose 1, or 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 \binom{5}{1} = \binom{5}{4} = }

We could also get this result through a little bit ore advanced use of calculus and derivatives: suppose that we replace the long expanded generating function with the shorter version, to get a generating function for the one-child case:

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 G_1 (z) = \dfrac{z}{1-z} }

and for the five-child case:

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 G_5(z) = \dfrac{z^5}{(1-z)^5} = z^5 \dfrac{1}{(1-z)^5} }

Now we can observe that the denominator can be obtained via:

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{d^n}{dz^n} \left( \dfrac{1}{1-z} \right) = \dfrac{n!}{(1-z)^{n+1}} }

so that

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{z^5}{(1-z)^5} = z^5 \left( \dfrac{1}{4!} \dfrac{d^4}{dz^4} \left( \dfrac{1}{1-z} \right) \right) }

now this can be simplified 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{z^5}{4!} \left( \dfrac{d^4}{dz^4} \left( z + z^2 + z^3 + \dots \right) \right) }

Almost finished. Now we can use

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{d^4 G(z)}{d z^4} &=& \dfrac{d^4}{dz^4} \left( \sum_{n=1}^{\infty} z^n \right) \\ &=& \dfrac{d^4}{dz^4} \left( z + z^2 + z^3 + \dots \right) \\ &=& (n)(n-1)(n-2)(n-3)z^{n-4} \end{align} }

Just to take this example one step further, let's suppose we decide that no child can get more than 4 apples. Then the generating function for each child will terminate after 4 terms (any term beyond that represents the case where a child has more than 4 apples and therefore we do not have any possibilities) and will be:

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 G(z) = z + z^2 + z^3 + z^4 }

While this latter calculus approach looks hairy, with practice it becomes much easier to spot how to combine and simplify series. (See exercises below.)

EXAMPLE Colored Marbles with Complicated Restrictions

Let's look at an example that uses less trivial restrictions.

Suppose we are preparing cans of marbles. Each can of marbles will have 20 red, blue, or green marbles. How many different outcomes are there if we require each jar have at least 1 red marble, no more than three blue marbles, any number of yellow marbles, and the number of green marbles must be a multiple of 4?

We begin this problem by starting with an easier problem: let's count the number of outcomes if we put n marbles into each can. We'll create a generating function whose coefficients give this number, and we can then find the 20th coefficient. As with the generating functions above, the term 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 z^6} corresponds to six marbles in each can, and the coefficient indicates the number of different ways that our three k values 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 k_{r}, k_{b}, k_{y}, k_{g}} can be combined to get 6.

Now, to write the generating functions for each marble, given our various restrictions:

Start with red, which is easiest - we require at least one red marble, so the case 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 z^0} must correspond to 0 outcomes for red.

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} G_{r}(z) &=& z + z^2 + z^3 + z^4 + \dots \\ G_{r}(z) &=& z ( 1+z+z^2+\dots) \\ G_{r}(z) &=& z \left( \dfrac{1}{1-z} \right) \end{align} }

so finally we get our generating function for red:

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 G_{r}(z) = \dfrac{z}{1-z} }

Next, for blue, we require that we have no more than three blue marbles, so any terms larger than 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 z^3} will be 0:

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 G_{b}(z) = 1 + z + z^2 + z^3 }

Yellow marbles can be any number:

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 G_{y}(z) = 1 + z + z^2 + z^3 + \dots }

Green marbles are a bit more tricky - we require they only occur in multiples of four, which means the coefficients of the generating function are nonzero only when the degree is divisible by 4:

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 G_{g}(z) = 1 + z^4 + z^8 + z^{12} + \dots }

Notice that we can do a variable transformation 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 u = z^4} , and this becomes 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 G_{g}( \sqrt[4]{u} ) = 1 + u + u^2 + u^3 + \dots }

Now, this 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 G_{g}( \sqrt[4]{u} ) = \dfrac{1}{1-u} }

and undoing our substitution 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 u = z^4} gives:

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 G_{g}(z) = \dfrac{1}{1 - z^4} }

Now the generating function for the entire lot 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 G(z) = G_r G_b G_y G_g = \dfrac{z}{1-z} \left( 1 + z + z^2 + z^3 \right) \dfrac{1}{1-z^4} \dfrac{1}{1-z} }

Simplifying with Mathematica or Wolfram Alpha:

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 G(z) = \dfrac{z}{(1-z)^3} }

Analysis of Generating Function

One step, at this point, is to find the Taylor Series expansion of this expression, which would give us our coefficients and the counts of different configurations. We will do that in the next section. However, we can do further analysis to get expressions for the coefficients analytically.

First, we can associate the 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 (1-z)^3} on the bottom to the sum $1+x+x^{2}+\dots$ via the derivative:

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{d^2}{dx^2} \left( \dfrac{1}{1-x} \right) = \dfrac{2}{(1-x)^3} }

and recall that this gives us a link to an infinite series, because 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} = 1 + x + x^2 + \dots} , as we have seen many times thus far.

So, we can replace the derivative term with an infinite sum:

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{d^2}{dx^2} \left( \dfrac{1}{1-x} \right) = \sum_{n=0}^{\infty} n (n-1) x^{n-2} }

and this gives us the generating function in terms of a sum:

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 G(z) = \dfrac{x}{2} \sum_{n=0}^{\infty} n (n-1) x^{n-2} }

Why do all of this? The next steps give us the payoff: we get a closed form for the coefficients.

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 G(z) = x \sum_{n=0}^{\infty} \dfrac{n(n-1)}{2} x^{n-2} }

Notice the triangle number 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{n(n-1)}{2}} , which we will see crop up in the next section. The triangle number in that form, 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{n(n-1)}{2}} , rather than its usual form ${\frac {n(n+1)}{2}}$ (which gives the sum of the integers from 1 to n), indicates that this is a binomial coefficient. Recall from AOCP/Binomial Coefficients that:

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 \binom{n}{2} = \dfrac{n(n-1)}{2} }

Thus, if we bring the x inside the infinite sum and simplify the expression, we get:

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 G(z) = \sum_{n=0}^{\infty} \binom{n}{2} x^{n-1} }

Last, we do a variable shift with the infinite series, shift n up by one, which pops out a 0 term, and write:

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 G(z) = \sum_{n=1}^{\infty} \binom{n+1}{2} x^{n} }

or equivalently,

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 G(z) = \sum_{n=1}^{\infty} \binom{n+1}{2} x^{n} }

Now we can give the closed-form answer to the question: How many fruit baskets are there? (n+1) choose 2. For a can of 20 marbles, that's:

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 21 \mbox{ choose } 2 = 210 }

Indeed, this is a lot nicer than just using Mathematica, but Mathematica certainly scales better:

Taylor Series Analysis

Now, we can use this generating function to explore the possibilities in our system. Here's the Taylor Series expansion to the first 10 terms:

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 G(z) = z+3 z^2+6 z^3+10 z^4+15 z^5+21 z^6+28 z^7+36 z^8+45 z^9+55 z^{10}+O\left(z^{11}\right) }

We can actually verify the first few terms.

The case of the z term (k=1 marbles). Let us first examine the z term (k=1 marble). When we have a single marble, there is only one configuration that works, and that is the case of a single red marble. No other marbles are required, strictly speaking. Thus the coefficient is 1.

The case of the z^2 term (k=2 marbles). The case of 2 marbles is more interesting: one slot has to be occupied by a red marble, so the remaining slot can be occupied by a red marble, a blue marble, a yellow marble, or a green marble. But green marbles can only occur in multiples of 4, so they're out. That leaves 3 possible configurations:

RR, RB, RY

The case of the z^3 term (k=3 marbles). If we have 3 marbles, we must have one slot occupied by a red marble. The remaining slots can be occupied by red, blue, or yellow marbles. Green marbles are still out. This gives 3 additional possibilities, added to the prior 3 possibilities, for 6 total:

RRR
RRB
RRY

RBB
RBY

RYY

Notice the way that the configurations are arranged - in groups of size 3, 2, 1. The total possibilities are 3 + 2 + 1 = 6, which is a triangle number.

Another way to think about this is, we are selecting from a set of 3 colored marbles, which one to put in each spot. Each spot sees the same set of 3 colored marbles, so this is different from saying 3 marbles (RYB) are going into two slots. It is actually like saying, when we choose what color to put into the first slot we are choosing from three marbles (RYB), and when we choose what color to put into the second slot we are also choosing from three marbles (RYB).

The case of the z^4 term (k=4 marbles). This configuration has 10 possibilities. 10 is a triangle number - just like 6.

RRRR
RRRB
RRRY

RRBB
RRBY

RRYY

RBBB
RBBY

RBYY

RYYY

Again, notice the configuration arrangements: (3 + 2 + 1) + (2 + 1) + (1) = 4 + 3 + 2 + 1

These numbers are coming from the term in the Taylor Series analysis we did above:

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 \sum_{n=0}^{\infty} \binom{n+1}{2} x^n }

If we have a term like k-choose-2, that will result in the (k-1)th triangle number. In this case, we have a term (n-1)-choose-2, which will give us the nth triangle numbers. That's why, when we had 3 marbles, we got the 3rd triangle number, when we had 4 marbles, we had the 4th triangle number, etc.

Exponential Generating Functions

What we've seen so far is pretty cool. But 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.

EXAMPLE 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.

To solve this problem, we apply a formulaic procedure:

First, we determine the generating function for each of the possible choices (0, 1, 2 in this case).

Then, we multiply the generating functions together to get the overall generating function.

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 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)!} }

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 }

Trotter: Chapter 8 Exercises

Problem 3

In problem 3, we're given some generating functions, and asked to find a closed form for the nth term.

Part a

Find nth term of 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 G(x) = (1 + x)^{10} }

Solving this one is as simple as applying the binomial theorem:

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} (1+x)^n &=& \sum_{k=1}^{n} \binom{n}{k} x^k \\ (x+y)^n &=& \sum_{k=1}^{n} \binom{n}{k} x^k y^{n-k} \end{align} }

So the nth term will be:

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 \binom{10}{n} }

Part b

Find nth term of 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 G(x) = \dfrac{1}{1-x^4} }

This one is easy to do, intuitively, since the fourth power means we have a normal generating function that generates every fourth term. It is relatively easy to do by hand, therefore, but more complicated to do formally. Here's the formal approach.

Start by factoring this as 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 (1-x^4) = (1-x)(1+x)(1+x^2)} , then do a partial fractions decomposition:

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}{4} \left( \dfrac{1}{1-x} \right) + \dfrac{1}{4} \left( \dfrac{1}{1+x} \right) + \dfrac{1}{2} \left( \dfrac{1}{1+x^2} \right) }

Now the goal is to combine these terms into a single series by re-expressing each expression with x in it in terms 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 \dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \dots = \sum_{k \geq 0} x^k} , using various tricks shown above and from calculus.

The first term is simple enough:

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}{4} \left( \dfrac{1}{1-x} \right) = \dfrac{1}{4} \left( \sum_{k \geq 0}{x^k} \right) }

The second term can be written as a series in (-x):

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}{4} \left( \dfrac{1}{1+x} \right) = \dfrac{1}{4} \left( \dfrac{1}{1-(-x)} \right) = \dfrac{1}{4} \left( 1 + (-x) + (-x)^2 + (-x)^3 + \dots \right) = \dfrac{1}{4} \left( \sum_{k \geq 0} (-1)^k x^k \right) }

The last term is a bit challenging. I used Wolfram Alpha to get a series expansion for this function. Here 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 \dfrac{1}{1+x^2} = 1 - x^2 + x^4 - x^6 + x^8 - \dots }

Converting this to a series expression requires some imaginary numbers to eliminate the odd terms of the series. We have:

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^2} = \sum_{k \geq 0} \dfrac{1}{2} x^k ((-i)^k + i^k) }

where 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 i = \sqrt{-1}} .

These three terms can now be combined:

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 G(x) = \dfrac{1}{1-x^4} = \dfrac{1}{4} \left( \sum_{k \geq 0} x^k + \sum_{k \geq 0} (-1)^k x^k + \sum_{k \geq 0} x^k ((-i)^k + (i)^k) \right) }

which 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 G(x) = \dfrac{1}{4} \left( \sum_{k \geq 0}{ \left( 1 + (-1)^k + ((-i)^k + (i)^k) \right) x^k } \right) }

(This is technically the final answer.)

Let's interpret this result a bit more.

Notice that the imaginary terms 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 ((-i)^k+(i)^k)} ensure the series has no odd values of k. For even values of k, the term has an alternating value of +2 or -2. Specifically, if k is divisible by 4 (0 mod 4), we have a value of +2, and if k is 2 mod 4, we have a value of -2.

The term 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 1 + (-1)^k} will be +2 when k is even and 0 otherwise, so this contributes no odd terms to the series.

Since there are no odd terms and the values of k that are 2 mod 4 cancel out, we are left with:

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 G(x) = \sum_{k \geq 0} x^{4k} }

So the entire series looks like:

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 G(x) = 1 + x^4 + x^8 + x^{12} + x^{16} + \dots }

Part c

Again, we're given a generating function and asked to find the nth term.

In part c we have the complement function to part b, so hold on to your hats.

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 G(x) = \dfrac{x^3}{1-x^4} = \dfrac{x^3}{(1-x)(1+x)(1+x^2)} }

The first two terms of the partial fraction expansion are the same as in part b:

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{x^3}{(1+x)(1-x)(1+x^2)} = \dfrac{1}{4} \left( \dfrac{1}{1-x} \right) - \dfrac{1}{4} \left( \dfrac{1}{1+x} \right) - \dfrac{x}{2(1+x^2)} }

The first two terms become:

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}{4} \left( \dfrac{1}{1-x} \right) - \dfrac{1}{4} \left( \dfrac{1}{1+x} \right) = \dfrac{1}{4} \left( \sum_{k \geq 0} \left( 1 - (-1)^k \right) x^k \right) }

The last term is a series that, analogous to the one from part b, has only odd terms. This time we'll take a shortcut and write the series expansion as:

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{x}{1+x^2} = x-x^3+x^5-x^7+x^9-x^{11}+x^{13} - \dots }

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{x}{1 + x^2} = \sum_{k \geq 0} (-1)^{k} x^{2k+1} }

Still struggling to glue this all together, but basically the two terms 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 (1-(-1)^k)} and 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 (-1)^k} will cancel out with each other for odd k, and will cancel out with the imaginary term for even k, for a final series solution that skips every other odd term:

Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\dfrac {x^{3}}{1-x^{4}}}=x^{3}+x^{7}+x^{11}+x^{15}+O\left(x^{16}\right)}

Related Pages

AOCP/Generating Functions