Exponential Generating Functions

Master EGFs for labeled structures, derangements, and exponential series.

23 min read
Advanced

Introduction

When objects are labeled (distinguishable), Ordinary GFs fail us. Exponential Generating Functions (EGFs) handle permutations and labeled structures by dividing by factorials.

Learning Objectives:

  • Understand when to use EGFs vs OGFs
  • Work with exponential series
  • Apply EGFs to derangements and labeled problems

Exponential Generating Functions

For sequence {an}\{a_n\}, the EGF is:

G^(x)=∑n=0∞anxnn!\hat{G}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}

Key difference from OGF: coefficients are ann!\frac{a_n}{n!} instead of ana_n.

Why EGFs?

Labeled objects: When arranging nn labeled items, there are n!n! permutations. EGFs automatically handle this by incorporating factorials.

Example: Permutations of nn objects (an=n!a_n = n!)

G^(x)=∑n=0∞n!⋅xnn!=∑n=0∞xn=11−x\hat{G}(x) = \sum_{n=0}^{\infty} n! \cdot \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}

The EGF is simple despite an=n!a_n = n! growing rapidly!

python
import math

def egf_coefficient(a_n, n):
    """Extract coefficient from EGF: a_n / n!"""
    return a_n / math.factorial(n)

# Permutations: a_n = n!
print("EGF for permutations (a_n = n!):")
print("\nCoefficients a_n / n!:")
for n in range(6):
    a_n = math.factorial(n)
    coef = egf_coefficient(a_n, n)
    print(f"  n={n}: {a_n} / {math.factorial(n)} = {coef}")

print("\nSum equals 1/(1-x) for |x| < 1")

Derangements

Application: Derangements

A derangement is a permutation where no element stays in its original position.

EGF for derangements:

D(x)=e−x1−xD(x) = \frac{e^{-x}}{1-x}

Number of derangements of nn objects: Dn=n![xnn!]e−x1−xD_n = n! \left[ \frac{x^n}{n!} \right] \frac{e^{-x}}{1-x}

Formula: Dn=n!∑k=0n(−1)kk!≈n!eD_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{n!}{e}

python
import math

def derangements(n):
    """Count derangements using inclusion-exclusion"""
    result = 0
    for k in range(n + 1):
        result += ((-1) ** k) * math.factorial(n) // math.factorial(k)
    return result

print("Derangements D_n:")
for n in range(1, 11):
    d_n = derangements(n)
    perm = math.factorial(n)
    ratio = d_n / perm
    print(f"  D_{n} = {d_n:>7,} / {perm:>9,} = {ratio:.6f}")

print(f"\nAs n→∞, ratio approaches 1/e ≈ {1/math.e:.6f}")

Key Takeaways

  1. EGF: Use for labeled structures, G^(x)=∑anxnn!\hat{G}(x) = \sum a_n \frac{x^n}{n!}
  2. vs OGF: OGFs for unlabeled, EGFs for labeled
  3. Derangements: D(x)=e−x1−xD(x) = \frac{e^{-x}}{1-x}, Dn≈n!eD_n \approx \frac{n!}{e}
  4. Exponential series: ex=∑xnn!e^x = \sum \frac{x^n}{n!}

Next Module: Recurrence Relations and how to solve them!

🎲

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.