3.1: Prelude to Generating Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
As we have seen, a typical counting problem includes one or more parameters, which of course show up in the solutions, such as (nk), P(n,k), or the number of derangements of [n]. Also recall that
(x+1)n=n∑k=0(nk)xk.
This provides the values (nk) as coefficients of the Maclaurin expansion of a function. This turns out to be a useful idea.
f(x) is a generating function for the sequence a0,a1,a2,… if
f(x)=∞∑i=0aixi.
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.