Generating functions · Definition

Exponential generating function

enumerative combinatoricsgenerating functions

Ordinary generating functions work well for unordered selections, but they fail when elements are labeled and rearranged. The exponential version divides each term by a factorial to absorb those permutations.

Definition

The exponential generating function of a sequence \(a_0, a_1, \ldots\) is the formal power series \(A(x)\) whose coefficient of \(x^n\) is \(a_n/n!\).

\[A(x)=\sum_{n\ge 0}\frac{a_n}{n!}x^n\]

If \(A(x)\) and \(B(x)\) are the exponential generating functions of \(a_n\) and \(b_n\), their product has coefficients \(\sum_k \binom{n}{k}a_k b_{n-k}\) after multiplying by \(n!\). This binomial convolution is the main reason for its usefulness. Moreover, \(e^x=\sum_{n\ge 0} x^n/n!\) is the generating function of the constant sequence equal to 1.

Consider partitions of an \(n\)-element set into nonempty unordered blocks, that is, the Bell numbers \(B_n\). Since \(\exp(e^x-1)\) encodes these partitions, extracting the coefficient of \(x^3\) and multiplying by \(3!\) gives \(B_3=5\). The example shows how the exponential generates set structures without listing each partition.

A typical mistake is treating the exponential generating function as if its coefficients were simply \(a_n\), forgetting to divide by \(n!\). This produces wrong sums in products. Always remember that the factorial denominator is part of the definition.

Think about it

Why does dividing by \(n!\) make the product of two series encode labeled subsets?

Because the coefficient of \(x^n/n!\) in the product is \(\sum_k \binom{n}{k}a_k b_{n-k}\), which splits the n labeled elements between two structures.

Exercises 10

  1. What is the exponential generating function of the constant sequence \(a_n=1\)?
  2. If \(a_n=n!\), what is the exponential generating function?
  3. Which coefficient of \(x^n\) defines the exponential generating function of \(a_n\)?
  4. What is the series of \(e^x\) written as a sum?
  5. Which sequence has exponential generating function \(e^{2x}\)?
  6. Compute \(a_3\) for the sequence whose exponential generating function is \(\frac{1}{1-x}\).
  7. If \(A(x)=e^{3x}\), what is the coefficient of \(x^2\) in \(A(x)\)?
  8. Which sequence \(a_n\) has exponential generating function \(x e^x\)?
  9. Let \(A(x)=e^{2x}\) and \(B(x)=e^{3x}\). What is \(c_4\), where \(C(x)=A(x)B(x)\) and \(c_n\) is the sequence associated with \(C\)?
  10. Let \(A(x)=\exp(e^x-1)\), which counts set partitions. What is the Bell number \(B_4\)?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.