Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 36 ยท Recurrences and Generating Functions

Exponential Generating Functions

Use exponential generating functions to count words and arrangements where order matters: constraints per letter, derangements, Bell numbers, verified with sympy.

Ordinary generating functions count selections where order does not matter. When order does matter (words, arrangements, labeled structures), the natural tool is the exponential generating function (EGF):

A(x) = a_0 + a_1 x/1! + a_2 x^2/2! + a_3 x^3/3! + ...

so a_n is n! times the coefficient of x^n. The division by n! is what makes the product rule work for arrangements.

Why the factorial appears

Suppose you build a word of length n from two disjoint groups of positions: k positions get letters of one kind, n-k get another. The positions can be chosen in C(n,k) ways. Multiplying EGFs gives

(sum a_k x^k/k!) (sum b_j x^j/j!) with x^n/n! coefficient sum C(n,k) a_k b_{n-k}.

The binomial coefficient is exactly the "choose which positions" factor. That is why EGFs are the right language for words.

Building blocks

For one letter, the factor lists how many copies of it the word may contain, each allowed count m contributing x^m/m!:

  • any number of copies: 1 + x + x^2/2! + ... = e^x
  • an even number: cosh x = 1 + x^2/2! + x^4/4! + ...
  • an odd number: sinh x
  • at least one: e^x - 1
  • at most two: 1 + x + x^2/2

Example 1: even number of a's

Words of length n over {a, b, c} with an even number of a's: a contributes cosh x, and each of b, c contributes e^x. The EGF is cosh x * e^{2x}. Since cosh x = (e^x + e^{-x})/2, the product is (e^{3x} + e^{x})/2, so the count is (3^n + 1)/2.

Example 2: derangements

A derangement of n items has no fixed point. The EGF is e^{-x}/(1 - x): the factor 1/(1-x) is all permutations and e^{-x} is the inclusion-exclusion correction. Expanding gives D_n = n! sum (-1)^k / k!, the same formula you get from inclusion-exclusion.

Python Words and derangements from EGFs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three numbers are 365, and the derangement list is 1, 0, 1, 2, 9, 44, 265, 1854, 14833.

Example 3: several constraints at once

Count words of length 5 over {a, b, c} where a appears at most 2 times, b appears an even number of times, and c appears at least once. Multiply the three EGFs: (1 + x + x^2/2)(1 + x^2/2! + x^4/4!)(e^x - 1), then take 5! times the coefficient of x^5. The code truncates each series to degree 5 so that sympy does exact polynomial arithmetic, and compares with brute force over all 3^5 words.

Python Bounded letters and Bell numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both counts are 91. The second part computes the Bell numbers (ways to split an n-element set into blocks) from the beautiful EGF e^{e^x - 1}: 1, 1, 2, 5, 15, 52, 203, 877, 4140. The reasoning: a block of size at least 1 has EGF e^x - 1, a set of blocks is exp of that. See Stirling numbers for the refined count by number of blocks.

flowchart TD
    A["Words / labeled structures"] --> B["One EGF factor per letter or part"]
    B --> C["Multiply"]
    C --> D["n! times coefficient of x^n"]

EGFs multiply because choosing positions contributes the binomial coefficient.

OGF or EGF?

Situation Use
Selections, multisets, partitions, coin change Ordinary (OGF)
Words, arrangements, labeled objects, set partitions Exponential (EGF)

If the answer for identical objects would divide by k! (because order among copies does not matter), that 1/k! is the sign you want an EGF for the labeled version.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How is a(n) recovered from an EGF A(x)?

    The EGF is the sum of a(n) x^n / n!, so a(n) = n! [x^n] A(x).
  2. 2. Which EGF factor models a letter that must appear an even number of times?

    cosh x = 1 + x^2/2! + x^4/4! + ... contains only even powers.
  3. 3. Words of length n over {a,b,c} with an even number of a's: how many?

    cosh x * e^(2x) = (e^(3x) + e^x)/2, whose coefficient gives (3^n + 1)/2.
  4. 4. Which EGF counts set partitions (Bell numbers)?

    Each nonempty block has EGF e^x - 1; a set of blocks is the exponential of that.

Summary

  • EGF sum a_n x^n/n! is the right series for arrangements: the 1/n! supplies the binomial coefficient when multiplying.
  • Per-letter factors: e^x (any), cosh x (even), sinh x (odd), e^x - 1 (at least one), truncated polynomials for upper limits.
  • Derangements: e^{-x}/(1-x); Bell numbers: e^{e^x - 1}.
  • Always check small cases against brute force.

Next: Integer Partitions