Ordinary generating functions are powerful tools for solving recurrence relations and combinatorial problems. They transform complex sequences into algebraic equations, making them easier to manipulate and solve. This technique is a game-changer in discrete mathematics.

By representing sequences as power series, we can perform operations like addition, multiplication, and composition on generating functions. This allows us to tackle a wide range of problems, from counting arrangements to finding closed-form expressions for sequence terms.

Ordinary Generating Functions

Definition and Role

• An ordinary generating function is a formal power series that encodes the terms of a sequence as coefficients of the series
• Generating functions transform recurrence relations into algebraic equations, making them easier to solve
• The coefficients of the resulting generating function provide the solution to the recurrence relation
• Ordinary generating functions are particularly useful for solving linear recurrence relations with constant coefficients

Examples of Ordinary Generating Functions

• The generating function for the sequence 1, 2, 3, 4, ... is $1 + 2x + 3x^2 + 4x^3 + ...$
• The generating function for the sequence 1, 1, 1, 1, ... is $1 + x + x^2 + x^3 + ... = \frac{1}{1-x}$
• The generating function for the Fibonacci sequence 0, 1, 1, 2, 3, 5, ... is $\frac{x}{1-x-x^2}$
• The generating function for the sequence 1, -1, 1, -1, ... is $1 - x + x^2 - x^3 + ... = \frac{1}{1+x}$

Constructing Generating Functions

Representing Sequences as Power Series

• To construct a generating function for a given sequence, represent each term of the sequence as a coefficient of a power series in a variable (usually denoted as x or z)
• The power of the variable in each term corresponds to the index of the sequence term
• For example, the sequence 1, 2, 4, 8, ... can be represented by the generating function $1 + 2x + 4x^2 + 8x^3 + ...$
• The sequence 1, 3, 6, 10, ... can be represented by the generating function $1 + 3x + 6x^2 + 10x^3 + ...$

Common Generating Functions

• Geometric sequence: a, ar, ar^2, ... has the generating function $\frac{a}{1-rx}$
• Fibonacci sequence: 0, 1, 1, 2, 3, 5, ... has the generating function $\frac{x}{1-x-x^2}$
• Exponential sequence: 1, 1, 1/2!, 1/3!, ... has the generating function $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + ...$
• Binomial sequence: 1, 1, 1, 1, ... has the generating function $\frac{1}{1-x}$

Constructing Generating Functions from Recurrence Relations or Combinatorial Problems

• Generating functions can be constructed for sequences defined by recurrence relations or combinatorial problems
• For example, the recurrence relation $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0$ and $a_1 = 1$ defines the Fibonacci sequence, and its generating function is $\frac{x}{1-x-x^2}$
• Combinatorial problems, such as counting the number of ways to arrange objects or the number of paths in a graph, can often be solved using generating functions

Manipulating Generating Functions

Operations on Generating Functions

• Addition of generating functions corresponds to term-wise addition of the sequences they represent
• Multiplication of generating functions corresponds to the convolution of the sequences they represent
• Composition of generating functions (substituting one generating function into another) can be used to solve certain types of recurrence relations or combinatorial problems
• The derivative and integral of generating functions can be used to shift indices or compute sums of sequences

Partial Fractions Decomposition

• Partial fractions decomposition can be applied to generating functions to break them down into simpler components, facilitating the extraction of coefficients
• For example, the generating function $\frac{1}{1-2x-3x^2}$ can be decomposed into $\frac{1}{3(1-3x)} - \frac{1}{3(1+x)}$
• The decomposed form makes it easier to extract the coefficients of the generating function using techniques such as Taylor series expansion or the residue theorem

Examples of Manipulating Generating Functions

• The generating function for the sequence 1, 2, 3, 4, ... can be multiplied by itself to obtain the generating function for the sequence 1, 4, 10, 20, ..., which represents the sum of the first n squares
• The generating function for the Fibonacci sequence can be decomposed using partial fractions to obtain a closed-form expression for the nth Fibonacci number: $F_n = \frac{1}{\sqrt{5}}(\phi^n - (-\phi)^{-n})$, where $\phi = \frac{1+\sqrt{5}}{2}$ is the golden ratio
• The generating function for the sequence 1, 1, 1, 1, ... can be composed with itself n times to obtain the generating function for the sequence of n-dimensional hypercube numbers: 1, 2, 4, 8, 16, ...

Solving Combinatorial Problems with Generating Functions

Combinatorial Interpretations of Coefficients

• The coefficients of a generating function often have combinatorial interpretations, such as counting the number of ways to arrange objects or the number of paths in a graph
• For example, the coefficient of $x^n$ in the generating function $\frac{1}{1-x}$ represents the number of ways to select n objects from an unlimited supply
• The coefficient of $x^n$ in the generating function $\frac{1}{(1-x)^k}$ represents the number of ways to distribute n identical objects among k distinct boxes

Extracting Coefficients from Generating Functions

• To extract the nth coefficient from a generating function, use techniques such as Taylor series expansion, partial fractions decomposition, or the residue theorem
• The snake oil method (also known as the method of undetermined coefficients) can be used to find a closed-form expression for the coefficients of a generating function by assuming a general form of the solution and solving for the unknown coefficients

Examples of Solving Combinatorial Problems with Generating Functions

• Generating functions can be used to solve problems related to integer partitions, such as counting the number of ways to partition an integer into a sum of smaller integers
• Set partitions can be enumerated using generating functions, such as the Bell numbers, which count the number of ways to partition a set into non-empty subsets
• Permutations with restricted positions, such as derangements (permutations with no fixed points), can be counted using generating functions
• The number of ways to make change for a given amount using a set of coin denominations can be determined using generating functions