2.2 Exponential Generating Functions

Exponential generating functions are powerful tools for solving counting problems involving labeled objects. They use factorials to encode information about permutations and combinations, making them ideal for problems with distinct elements.

These functions build on ordinary generating functions, adding new techniques to our problem-solving toolkit. By understanding their properties and operations, we can tackle complex combinatorial challenges involving permutations, partitions, and arrangements of labeled elements.

Ordinary vs Exponential Generating Functions

Definitions and Differences

Top images from around the web for Definitions and Differences

• 

  Graphs of Exponential Functions | College Algebra View original

  Is this image relevant?

• 

  Power Functions and Polynomial Functions – Algebra and Trigonometry OpenStax View original

  Is this image relevant?

• 

  Generating function - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Graphs of Exponential Functions | College Algebra View original

  Is this image relevant?

• 

  Power Functions and Polynomial Functions – Algebra and Trigonometry OpenStax View original

  Is this image relevant?

1 of 3

Top images from around the web for Definitions and Differences

• 

  Graphs of Exponential Functions | College Algebra View original

  Is this image relevant?

• 

  Power Functions and Polynomial Functions – Algebra and Trigonometry OpenStax View original

  Is this image relevant?

• 

  Generating function - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  Graphs of Exponential Functions | College Algebra View original

  Is this image relevant?

• 

  Power Functions and Polynomial Functions – Algebra and Trigonometry OpenStax View original

  Is this image relevant?

1 of 3

• Ordinary generating functions (OGFs) are power series where the coefficient of the nth term represents the number of combinatorial objects of size n, without regard to order or labeling
• Exponential generating functions (EGFs) are power series where the coefficient of the nth term represents the number of labelled combinatorial objects of size n, divided by n!
• OGFs are used for counting problems involving unlabelled objects, while EGFs are used for counting problems involving labelled objects
• The coefficients in an OGF grow at a slower rate compared to the coefficients in an EGF due to the absence of the n! factor in the denominator of OGFs
• EGFs often involve the exponential function $[e^x](https://www.fiveableKeyTerm:e^x)$, while OGFs typically do not

Examples and Applications

• The OGF for the number of ways to select k items from n distinct items is $(1 + x)^n$, as the number of such selections is given by the binomial coefficient $\binom{n}{k}$
• The EGF for the number of permutations of n distinct objects is given by $e^x$, as the number of permutations is n! and the coefficient of the nth term is $\frac{n!}{n!} = 1$
• OGFs can be used to solve counting problems related to integer partitions, such as the number of ways to partition a positive integer into a sum of smaller positive integers (partition function)
• EGFs can be used to solve counting problems related to set partitions, such as the number of ways to partition a set of n labelled objects into k nonempty subsets (Stirling numbers of the second kind)

Exponential Generating Functions for Labelled Objects

Developing EGFs

• To develop an EGF for a given combinatorial problem, identify the number of labelled objects of size n and divide it by n! to obtain the coefficient of the nth term
• The EGF for the number of ways to arrange n labelled objects into k cycles is given by $e^{\frac{x^k}{k}}$, as the number of such arrangements is the unsigned Stirling number of the first kind, denoted as $|s(n, k)|$
• The EGF for the number of ways to partition a set of n labelled objects into k nonempty subsets is given by $\frac{(e^x - 1)^k}{k!}$, as the number of such partitions is the Stirling number of the second kind, denoted as $S(n, k)$
• The product of two EGFs represents the convolution of their corresponding sequences, which can be used to solve counting problems involving the multiplication principle for labelled objects

Examples and Applications

• The EGF for the number of derangements (permutations where no element remains in its original position) of n objects is given by $\frac{!n}{e}$, where $!n$ represents the subfactorial of n
• The EGF for the number of ways to arrange n labelled objects into an even number of cycles is given by $\frac{e^x + e^{-x}}{2}$
• The EGF for the number of ways to partition a set of n labelled objects into an even number of nonempty subsets is given by $\frac{(e^x - 1)^n + (1 - e^x)^n}{2n!}$
• The EGF for the number of involutions (permutations that are their own inverse) of n objects is given by $e^{x + \frac{x^2}{2}}$

Solving Counting Problems with Generating Functions

Operations on EGFs

• Addition of EGFs corresponds to adding the coefficients of like terms, which can be used to solve counting problems involving the sum of two or more sets of labelled objects
• Multiplication of EGFs corresponds to the convolution of their coefficient sequences, which can be used to solve counting problems involving the multiplication principle for labelled objects
• Composition of EGFs, denoted as $A(B(x))$, can be used to solve counting problems where the structures being counted are composed of smaller labelled structures
• Differentiation of an EGF $A(x)$ with respect to x gives the EGF for the sequence $\{na_n\}$, where $a_n$ is the coefficient of the nth term in $A(x)$
• Integration of an EGF $A(x)$ with respect to x gives the EGF for the sequence $\{\frac{a_n}{n}\}$, where $a_n$ is the coefficient of the nth term in $A(x)$

Examples and Applications

• The EGF for the number of ways to distribute n distinct objects into k distinct boxes, allowing for empty boxes, is given by $(e^x)^k$, which is the product of k copies of the EGF for permutations
• The EGF for the number of ways to arrange n labelled objects into cycles, where each cycle is colored with one of k colors, is given by $e^{kx}$, which is the composition of the EGF for permutations with the function $kx$
• The EGF for the number of ways to select a subset of size k from a set of n labelled objects, where order matters, is given by $\frac{x^k}{k!}e^x$, which is the product of the EGF for k-permutations and the EGF for permutations
• The EGF for the number of ways to partition a set of n labelled objects into cycles, where each cycle has size at most m, is given by $e^{x + \frac{x^2}{2} + ... + \frac{x^m}{m}}$, which is the composition of the EGF for permutations with the polynomial $x + \frac{x^2}{2} + ... + \frac{x^m}{m}$

Coefficients of Exponential Generating Functions

Finding Coefficients

• The coefficient of the nth term in an EGF can be found by Taylor series expansion of the EGF around x = 0
• The coefficient of the nth term in an EGF can also be found by taking the nth derivative of the EGF evaluated at x = 0 and dividing by n!
• The coefficient of the nth term in the product of two EGFs can be found using the convolution formula: $[x^n](A(x)B(x)) = \sum_{k=0}^n (a_k * b_{n-k})$
• The coefficient of the nth term in the composition of two EGFs, $A(B(x))$, can be found using Faà di Bruno's formula, which involves partial Bell polynomials
• Lagrange inversion formula can be used to find the coefficients of an EGF when it is given as an implicit function

Examples and Applications

• The coefficient of the nth term in the EGF $e^x$ is $\frac{1}{n!}$, as the Taylor series expansion of $e^x$ is $\sum_{n=0}^{\infty} \frac{x^n}{n!}$
• The coefficient of the nth term in the EGF $\frac{(e^x - 1)^k}{k!}$ is the Stirling number of the second kind, $S(n, k)$, which can be found using the formula $S(n, k) = \frac{1}{k!}\sum_{i=0}^k (-1)^{k-i}\binom{k}{i}i^n$
• The coefficient of the nth term in the product of the EGFs $e^x$ and $\frac{x^k}{k!}$ is $\frac{1}{(n-k)!}$, which represents the number of ways to select a subset of size k from a set of n labelled objects, where order matters
• The coefficient of the nth term in the composition of the EGFs $e^x$ and $x + \frac{x^2}{2} + ... + \frac{x^m}{m}$ can be found using Faà di Bruno's formula and represents the number of ways to partition a set of n labelled objects into cycles, where each cycle has size at most m