As we have seen, a typical counting problem includes one or more parameters, which of course show up in the solutions, such as $n\choose k$, $P(n,k)$, or the number of derangements of $[n]$. Also recall that $$(x+1)^n=\sum_{k=0}^n {n\choose k}x^k.$$ This provides the values ${n\choose k}$ as coefficients of the Maclaurin expansion of a function. This turns out to be a useful idea.

Definition 3.0.1 $f(x)$ is a generating function for the sequence $\ds a_0,a_1,a_2,\ldots$ if $$f(x)=\sum_{i=0}^\infty a_i x^i.$$ $\square$

Sometimes a generating function can be used to find a formula for its coefficients, but if not, it gives a way to generate them. Generating functions can also be useful in proving facts about the coefficients.

1. Newton's Binomial Theorem

2. Exponential Generating Functions

3. Partitions of Integers

4. Recurrence Relations

5. Catalan Numbers