Exponential Generating Functions

Combinatorics · Axiom Academy

LESSON Exponential Generating Functions Understanding EGFs and when to use them instead of ordinary generating functions An exponential generating function for a sequence (a₀, a₁, a₂, ...) is defined as: The key difference from OGFs is the factorial in the denominator. This normalization factor makes EGFs natural for counting labeled structures. The choice between OGFs and EGFs depends on whether your objects are labeled or unlabeled : Rule of thumb: If order matters and objects have distinct identities, use EGFs. If objects are interchangeable, use OGFs. 3. The Fundamental Example: eˣ The most important EGF is the exponential function itself: This EGF has aₙ = 1 for all n, meaning there is exactly 1 way to arrange n labeled objects in a sequence (the identity permutation, before we permute them). More importantly, eˣ is the EGF for sets : the number of ways to choose any subset from n labeled objects is encoded in the Taylor series of eˣ. Many important EGFs are variations of eˣ: This is the EGF for permutations of n objects (n! permutations). The EGF for derangements (permutations with no fixed points). Useful for counting structures with parity constraints.

This is the written version of the interactive lesson above. See the full Combinatorics course.