Sign in to save

Bookmark this page so you can find it later.

Sign in to save

Bookmark this page so you can find it later.

Ordinary vs Exponential Generating Functions Reference cheat sheet - grade college

Click image to open full size

Math Grade college

Ordinary vs Exponential Generating Functions Reference Cheat Sheet

A printable reference covering ordinary generating functions, exponential generating functions, coefficient extraction, products, composition, and labeled versus unlabeled structures for college.

TopicsCountingFunctionsAlgebraPatternsStudy GuideMathematics
Download PNG

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Ordinary and exponential generating functions turn sequences into formal power series so that counting problems can be solved with algebra. This cheat sheet compares when to use an ordinary generating function and when to use an exponential generating function. It is useful for recurrence relations, combinatorial classes, coefficient extraction, and enumerating objects with or without labels.

An ordinary generating function stores a sequence as A(x)=∑n≥0anxnA(x)=\sum_{n\ge 0} a_n x^n, while an exponential generating function stores it as A^(x)=∑n≥0anxnn!\widehat{A}(x)=\sum_{n\ge 0} a_n \frac{x^n}{n!}. Products usually model splitting a size into parts, but the binomial factors appear naturally in exponential generating functions. The main skill is choosing the correct model, manipulating the series, and extracting the coefficient with [xn]A(x)[x^n]A(x) or n![xn]A^(x)n![x^n]\widehat{A}(x).

Key Facts

  • The ordinary generating function for a sequence {an}n≥0\{a_n\}_{n\ge 0} is A(x)=∑n≥0anxnA(x)=\sum_{n\ge 0} a_n x^n.
  • The exponential generating function for a sequence {an}n≥0\{a_n\}_{n\ge 0} is A^(x)=∑n≥0anxnn!\widehat{A}(x)=\sum_{n\ge 0} a_n \frac{x^n}{n!}.
  • Coefficient extraction for an ordinary generating function is an=[xn]A(x)a_n=[x^n]A(x).
  • Coefficient extraction for an exponential generating function is an=n![xn]A^(x)a_n=n![x^n]\widehat{A}(x).
  • If A(x)=∑anxnA(x)=\sum a_n x^n and B(x)=∑bnxnB(x)=\sum b_n x^n, then [xn]A(x)B(x)=∑k=0nakbn−k[x^n]A(x)B(x)=\sum_{k=0}^{n} a_k b_{n-k}.
  • If A^(x)=∑anxnn!\widehat{A}(x)=\sum a_n \frac{x^n}{n!} and B^(x)=∑bnxnn!\widehat{B}(x)=\sum b_n \frac{x^n}{n!}, then n![xn]A^(x)B^(x)=∑k=0n(nk)akbn−kn![x^n]\widehat{A}(x)\widehat{B}(x)=\sum_{k=0}^{n}\binom{n}{k}a_k b_{n-k}.
  • Use ordinary generating functions most often for unlabeled objects, integer partitions, tilings, and recurrences indexed only by size.
  • Use exponential generating functions most often for labeled objects, permutations, set constructions, and structures where choosing labels contributes factors such as (nk)\binom{n}{k}.

Vocabulary

Ordinary generating function
An ordinary generating function represents a sequence by the formal power series A(x)=∑n≥0anxnA(x)=\sum_{n\ge 0}a_n x^n.
Exponential generating function
An exponential generating function represents a sequence by the formal power series A^(x)=∑n≥0anxnn!\widehat{A}(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}.
Coefficient extraction
Coefficient extraction uses notation such as [xn]A(x)[x^n]A(x) to mean the coefficient of xnx^n in the series A(x)A(x).
Cauchy product
The Cauchy product is the multiplication rule [xn]A(x)B(x)=∑k=0nakbn−k[x^n]A(x)B(x)=\sum_{k=0}^{n}a_k b_{n-k} for ordinary generating functions.
Labeled structure
A labeled structure is a combinatorial object built on distinguishable labels, often counted naturally by exponential generating functions.
Formal power series
A formal power series is an algebraic series such as ∑n≥0anxn\sum_{n\ge 0}a_n x^n manipulated by coefficients rather than by analytic convergence.

Common Mistakes to Avoid

  • Using an ordinary generating function for a labeled product is wrong when the labels must be distributed among components. Exponential generating functions include the needed factor (nk)\binom{n}{k} automatically.
  • Forgetting the factor n!n! when extracting from an exponential generating function gives coefficients that are too small. If A^(x)=∑anxnn!\widehat{A}(x)=\sum a_n\frac{x^n}{n!}, then an=n![xn]A^(x)a_n=n![x^n]\widehat{A}(x).
  • Multiplying exponential generating functions as if they used the ordinary Cauchy product loses the label-choice factor. The correct coefficient rule is ∑k=0n(nk)akbn−k\sum_{k=0}^{n}\binom{n}{k}a_k b_{n-k}.
  • Treating convergence as necessary in every generating function problem can distract from the main argument. In enumerative combinatorics, A(x)A(x) and A^(x)\widehat{A}(x) are often formal power series.
  • Confusing 11−x\frac{1}{1-x} and exe^x leads to the wrong constant sequence model. The series 11−x=∑n≥0xn\frac{1}{1-x}=\sum_{n\ge 0}x^n is an ordinary generating function for an=1a_n=1, while ex=∑n≥0xnn!e^x=\sum_{n\ge 0}\frac{x^n}{n!} is the exponential generating function for an=1a_n=1.

Practice Questions

  1. 1 For the sequence an=2na_n=2^n, find the ordinary generating function A(x)A(x) and the exponential generating function A^(x)\widehat{A}(x).
  2. 2 If A(x)=11−3xA(x)=\frac{1}{1-3x}, compute [x5]A(x)[x^5]A(x).
  3. 3 If A^(x)=e4x\widehat{A}(x)=e^{4x}, compute a6a_6 where A^(x)=∑n≥0anxnn!\widehat{A}(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}.
  4. 4 A counting problem builds labeled objects by splitting an nn-element label set into two parts and placing one structure on each part. Explain why an exponential generating function product is usually the natural choice.

Understanding Ordinary vs Exponential Generating Functions Reference

The product rule comes from a bookkeeping choice. Suppose an object is built from a left part and a right part. If its total size is n, the left part may have size zero through n.

For ordinary generating functions, each split contributes one count from the left sequence multiplied by one count from the right sequence. Adding over all possible splits gives the familiar convolution. This is useful for coin change and tiling problems.

A tile arrangement can begin with one allowed tile, leaving a smaller board. That direct size split often turns a recurrence into a product or a simple equation for a generating function.

Labels change the bookkeeping because a structure of size n has n distinct names available. If one component receives k labels, there are n choose k ways to decide which labels it gets. The remaining labels go to the other component.

This choice explains the extra binomial factor in an exponential generating function product. Think about arranging students into two named groups, then building a different structure inside each group. The group sizes alone are not enough.

The identities of the students matter. Factorials in exponential generating functions package all those label choices so that multiplication still works cleanly.

Composition needs even more care. In an ordinary setting, composition often represents an ordered sequence of components. For example, a path can be assembled from steps, where each step has a size.

In an exponential setting, composition usually represents replacing every element of an outer labeled structure by a nonempty labeled inner structure. The word nonempty matters. If empty inner structures were allowed, a fixed set of labels could produce infinitely many invisible replacements.

Students should first state what a single component is, what counts as its size, and whether order or labels matter. This prevents using a correct algebra rule for the wrong combinatorial model.

Differentiation is another practical tool because it shifts sequence indices. A recurrence that relates the count at size n to the count at size n minus one can often become a differential equation for the generating function. Initial values are essential, since they determine the missing constant term after solving.

When extracting an answer, check the first few sizes by direct counting. This catches common errors such as forgetting an empty object, treating identical parts as distinct, or losing a factorial. These ideas appear beyond pure counting.

They help analyze algorithms built from smaller subproblems, count seating arrangements, describe network components, and study random permutations. The reliable habit is to build a small table of counts before trusting a series manipulation.