Skip to main content
Contents Embed Dark Mode Prev Up Next \(\require{physics}\require{upgreek}\everymath{\displaystyle}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\inv}{^{-1}}
\newcommand{\DS}{\displaystyle}
\newcommand{\eps}{\varepsilon}
\newcommand{\tsub}[1]{_{\mathrm{#1}}}
\newcommand{\ee}{\mathrm{e}}
\newcommand{\ii}{\mathrm{i}}
\newcommand{\limit}[1]{\lim\limits_{#1}}
\newcommand{\resid}[1]{\underset{#1}{\Res}}
\DeclareMathOperator{\sinc}{sinc}
\DeclareMathOperator{\sgn}{sgn}
\newcommand{\pii}{\pi}
\DeclareMathOperator{\Prob}{P}
\DeclareMathOperator{\EV}{E}
\DeclareMathOperator{\Var}{Var}
\newcommand{\bv}[1]{\boldsymbol{#1}}
\newcommand{\uv}[1]{\hat{\bv{#1}}}
\newcommand{\cl}[1]{\mathcal{#1}}
\newcommand{\bb}[1]{\mathbb{#1}}
\DeclareMathOperator{\Cis}{cis}
\DeclareMathOperator{\RE}{Re}
\DeclareMathOperator{\IM}{Im}
\newcommand{\xd}{\mathbf{d}}
\newcommand{\seq}[3]{{#1}_{#2},\cdots,{#1}_{#3}}
\newcommand{\psup}[1]{^{(#1)}}
\newcommand{\hypext}{{}^*}
\DeclareMathOperator{\st}{st}
\newcommand{\set}[1]{\left\{#1\right\}}
\DeclareMathOperator{\Sin}{Sin}
\DeclareMathOperator{\Cos}{Cos}
\DeclareMathOperator{\Tan}{Tan}
\DeclareMathOperator{\Sec}{Sec}
\DeclareMathOperator{\Csc}{Csc}
\DeclareMathOperator{\Cot}{Cot}
\DeclareMathOperator{\Log}{Log}
\DeclareMathOperator{\Arg}{Arg}
\DeclareMathOperator{\Ln}{Ln}
\DeclareMathOperator{\Grad}{grad}
\DeclareMathOperator{\Div}{div}
\DeclareMathOperator{\Curl}{curl}
\newcommand{\rd}{\textstyle\mathop{}\!\mathrm{d}^{\!\!\!-}\hspace{-0.0555 em}}
\newcommand{\rpd}{\textstyle\mathop{}\!\partial^{\hspace{-0.5 em}-}\hspace{-0.1666 em}}
\newcommand{\rdv}[2]{\frac{\rd{#1}}{\rd{#2}}}
\newcommand{\rpdv}[2]{\frac{\rpd{#1}}{\rpd{#2}}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 10.5 Generating functions
Objectives
Understand the concept of generating functions and how they can be used to encode sequences.
Manipulate generating functions to find closed-form expressions for sequences.
Use generating functions to solve counting problems.
A generating function is a formal power series in which the coefficients correspond to terms in a sequence. For a sequence \({a_n}\text{,}\) the generating function is
\begin{equation*}
G(x) = \sum_{n=0}^{\infty} a_n x^n.
\end{equation*}
Generating functions can be manipulated algebraically to find closed-form expressions for sequences. For example, if we have a sequence defined by a recurrence relation, we can express it as a generating function and solve for it.
Binomial series:
\begin{equation*}
(1+x)^r = \sum_{n=0}^{\infty} \binom{r}{n} x^n
\end{equation*}
where \(\DS\binom{r}{n} = \frac{r(r-1)(r-2)\cdots(r-n+1)}{n!}\text{.}\)
Example combinatorics problem: counting the number of ways to distribute \(n\) identical balls into \(k\) distinct boxes. The generating function for this problem is
\begin{equation*}
G(x) = \left( \frac{1}{1-x} \right)^k = \sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n.
\end{equation*}
