EGF Problem Examples

Combinatorics · Axiom Academy

Master exponential generating functions through five step-by-step worked examples Excellent work! You've completed five EGF examples. Here's what we learned: EGF fundamentals: For labeled structures, use exponential generating functions where the coefficient of x^n/n! gives the count for n elements. Product principle: When combining independent labeled structures, multiply their EGFs. The factorial in the denominator accounts for all possible labelings. Restrictions and constraints: Handle restrictions by adjusting the EGF terms. For example, excluding certain sizes means omitting those terms from the series. Derangements: The EGF for derangements is e^(-x)/(1-x) , which gives the classic formula D_n = n! Σ(-1)^k/k! for k from 0 to n. Coefficient extraction: Always remember to multiply by n! when extracting the coefficient of x^n/n! to get the actual count. These techniques form the foundation for solving complex counting problems with labeled objects. Practice identifying when to use EGFs versus OGFs!

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