EGF Applications

Combinatorics · Axiom Academy

Apply exponential generating functions to permutation counting, labeled structure enumeration, and derangement problems 1. Permutation Counting with EGFs The EGF for permutations is one of the most elegant applications. Consider permutations as sequences where order matters and all labels are used exactly once. The EGF for all permutations is: The coefficient of x n /n! gives us the number of permutations of n objects: n! Let's visualize how the EGF encodes permutation information through its coefficient structure: 2. Labeled Structure Enumeration via Convolution The power of EGFs emerges when we combine labeled structures. The product of two EGFs automatically handles the combinatorial selection of which labels belong to each component. For EGFs A(x) and B(x), their product gives: The binomial coefficient appears naturally, counting ways to partition n labels into two groups! Watch how EGF convolution distributes labels between two structures: A derangement is a permutation with no fixed points. Every element must move from its original position. EGFs provide an elegant formula. The EGF for derangements is derived from the permutation EGF by removing the identity term: This gives the subfactorial formula: D n = n! k=0 n (-1) k /k! See how derangements exclude fixed points through the EGF structure:

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