Skip to main content
$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.1: Prelude to Generating Functions

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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.\nonumber$

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 $$\PageIndex{1}$$: Generating Function

$$f(x)$$ is a generating function for the sequence $$a_0,a_1,a_2,\ldots$$ if

$f(x)=\sum_{i=0}^\infty a_i x^i.\nonumber$

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.

## Contributors and Attributions

This page titled 3.1: Prelude to Generating Functions is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard.

• Was this article helpful?