2.4 Applications of Generating Functions

Generating functions are powerful tools for solving combinatorial problems and analyzing sequences. They encode sequences as formal power series, allowing us to manipulate and derive closed-form expressions for complex patterns.

These mathematical objects bridge the gap between discrete and continuous mathematics. By applying operations like addition, multiplication, and composition to generating functions, we can model and solve a wide range of counting problems and probability distributions.

Modeling with Generating Functions

Encoding Sequences with Generating Functions

Top images from around the web for Encoding Sequences with Generating Functions

• 

  Generating function - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Generating function - Wikipedia, the free encyclopedia View original

  Is this image relevant?

1 of 1

Top images from around the web for Encoding Sequences with Generating Functions

• 

  Generating function - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Generating function - Wikipedia, the free encyclopedia View original

  Is this image relevant?

1 of 1

• Generating functions are formal power series used to encode sequences of numbers
  • The coefficients of the series correspond to the terms of the sequence
• Ordinary generating functions (OGFs) have the form $G(x) = a₀ + a₁x + a₂x² + ...$
  • The coefficient $aₙ$ represents the $n$th term of the sequence
• Exponential generating functions (EGFs) have the form $G(x) = a₀ + a₁x/1! + a₂x²/2! + ...$
  • The coefficient $aₙ$ represents the $n$th term of the sequence divided by $n!$

Modeling Combinatorial Problems

• Combinatorial problems can be modeled using generating functions
  • Express the problem in terms of a sequence
  • Find the corresponding generating function
• Operations on generating functions correspond to certain combinatorial operations
  • Addition corresponds to union
  • Multiplication corresponds to Cartesian product
  • Composition corresponds to substitution
• The generating function for the sum of two sequences is the sum of their individual generating functions
• The generating function for the Cartesian product of two sequences is the product of their individual generating functions

Deriving Closed-Form Expressions

Manipulating Generating Functions

• Closed-form expressions for sequences can be obtained by manipulating the generating function
  • Use techniques such as partial fraction decomposition, differentiation, and integration
• The generating function can be expanded using Taylor series or the binomial theorem to obtain the coefficients of the sequence
• Partial fraction decomposition can be used to break down a rational generating function into simpler terms
  • The simpler terms can then be expanded to find the coefficients

Deriving Expressions for Specific Sequences

• Differentiation and integration of generating functions can be used to derive closed-form expressions for related sequences
• The generating function for the sequence of powers of a fixed number $a$ is $1/(1-ax)$
• The generating function for the sequence of Fibonacci numbers is $x/(1-x-x²)$
• The generating function for the sequence of Catalan numbers is $(1-√(1-4x))/(2x)$

Counting with Generating Functions

Partitions and Compositions

• Partitions of a positive integer $n$ are the ways of writing $n$ as a sum of positive integers
  • The order of the summands does not matter
• The generating function for the number of partitions of $n$ is the infinite product $∏ₖ₌₁^∞ (1/(1-xᵏ))$
• Compositions of a positive integer $n$ are the ways of writing $n$ as a sum of positive integers
  • The order of the summands matters
• The generating function for the number of compositions of $n$ is $1/(1-x)^n$

Combinatorial Structures

• The generating function for the number of ways to partition a set of $n$ elements into $k$ non-empty subsets is the Stirling number of the second kind
  • It has the exponential generating function $(e^x - 1)^k/k!$
• The generating function for the number of permutations of $n$ elements with $k$ cycles is the unsigned Stirling number of the first kind
  • It has the exponential generating function $(log(1+x))^k/k!$

Applications in Probability and Statistics

Probability Distributions

• Generating functions can be used to find the probability distribution and moments of discrete random variables
• The probability generating function (PGF) of a discrete random variable $X$ is defined as $G_X(s) = E[s^X] = ∑ₓ P(X=x)s^x$
  • The coefficient of $s^x$ represents the probability $P(X=x)$
• The PGF of the sum of independent random variables is the product of their individual PGFs
• The PGF of the binomial distribution with parameters $n$ and $p$ is $(ps + (1-p))^n$
• The PGF of the Poisson distribution with parameter $λ$ is $e^(λ(s-1))$

Moments of Random Variables

• The moment generating function (MGF) of a random variable $X$ is defined as $M_X(t) = E[e^(tX)] = ∑ₓ P(X=x)e^(tx)$
  • It can be used to find the moments of $X$ by differentiating and evaluating at $t=0$
• The MGF of the normal distribution with mean $μ$ and variance $σ²$ is $e^(μt + (σ²t²)/2)$