What is a generating function and what does it encode?

A generating function is a formal power series F(x) = sum_{n≥0} a_n x^n that encodes a sequence a_n. The coefficient a_n counts objects of size n, turning counting problems into algebraic manipulations.

What is the difference between ordinary generating functions and exponential generating functions, and when should you use each?

Ordinary generating functions (OGFs) have F(x) = sum a_n x^n and are used for unlabeled structures or when order doesn't matter. Exponential generating functions (EGFs) have F(x) = sum a_n x^n / n! and are used for labeled structures. Use OGFs for many counting problems with indistinguishable components; use EGFs when labels matter and factorials arise in counting.

How can generating functions help count sequences like compositions or partitions? Can you give a simple example?

For compositions with parts 1 or 2, the ordinary generating function is 1/(1 − x − x^2). The coefficient of x^n equals F_{n+1}, the (n+1)th Fibonacci number, giving the number of ways to sum to n using 1s and 2s.

How do you extract counts from a generating function and what does multiplying generating functions do?

To get counts, expand the series or extract coefficients. The product A(x)B(x) has coefficient x^n equal to sum_{k=0}^n a_k b_{n−k}, representing the combination of independent choices. This helps build complex counts from simpler pieces.