\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\frametitle{Lecture 17 \ Generating Functions }
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi Chapter 9 Generating Functions

\vspace{2cm}
A new powerful way of counting.

\vspace{10cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
The binomial coefficient $n \choose k$ counts different objects:

\medskip
\begin{tabular}{ccl}
$\ds n \choose \ds k$& = & the number of subsets of $\{1,2,\dots,n\}$ of size $k$ \\
                 & = & the number of binary strings of length $n$ with $k$ 1's \\
                 & = & the coefficient of $x^k y^{n-k}$ in the expansion of $(x+y)^n$
\end{tabular}

\medskip
Example \ $\ds \color{blue} (1+x)^3 = $

\vspace{6cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[coefficient]
If $P(x)$ is a polynomial we denote by $[x^k] P(x)$ the
coefficient of $x^k$ in $P(x)$.
\end{definition}
Example 1 How many integer solutions $a_1+a_2+a_3 = 7$ have if $0 \le a_i \le 3$?


\vspace{10cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 2  Suppose we roll two dice.  If we add the values of the dice,
how many ways can we get 6?

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 3  How many integer solutions does 
$$\color{blue} a_1 + a_2 + a_3 = 9$$ 
have if $2 \le a_1 \le 4, 1 \le a_2 \le 5, 3 \le a_3 \le 7$ ?

\bigskip
\bigskip
$[x^9] P(x)$ where $P(x) = $

\vspace{2cm}

Exercise: What if $a_1$ is odd, $a_2$ is even and $a_3 \in \{0,3,6\}$ ?

\bigskip
\bigskip
$[x^9] P(x)$ where $P(x) = $
\vspace{4cm}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 4.  How many integer solutitions does
$$ a_1 + a_2 + a_3 = n ~~~~{\rm have~if~} a_i \ge 0 ~ ? $$

\vspace{12cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}
The {\bf generating function} for an infinite sequence $a_0,a_1,a_2,\dots$
is the series
$$ A(x) = a_0 + a_1 x + a_2 x^2 + \dots = \sum_{n=0}^{\infty} a_i x^i.$$
\end{definition}

\medskip
We are interested in the coefficients of $A(x)$ not the values of $A(x)$.

Example 5.  What is the generating function for $1,1,1,\dots$ ?
\vspace{8cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example 6.  What is the generating function for the sequence $1,2,3,4,5,\dots$ ?

\vspace{8cm}

\end{frame}
