\chapter{Generating functions}



\section{Motivation for generating functions}

Generating functions are interesting curiosities to beginners, however their use is often not understood; we'll require some motivating examples and observations to lay strong foundations for this chapter. Recall the binomial theorem taught in Elementary Algebra.
\[(x+y)^n = \sum^{n}_{k=0} \binom{n}{k}x^{k}y^{n-k} \]

Even though this result is taught as a method in algebra to quickly calculate binomial expansions, the common proof for this result relies on basic combinatorics.

The idea is that we think of as strings.

\[(x+y)^5\]

\[xxxyy,xxyxy,xyxxy,yxxxy,xxyyx,xyxyx,yxxyx,xyyxx,yxyxx,yyxxx\]




\begin{example}
You want to buy a Gameboy that costs \$80, but the seller will only accept notes (5,10,20,50,100). How many possible ways are there to pay the seller with no change by using distinct note combinations?
\end{example}

It is the coefficient of $x^{80}$ in the following polynomial.
\[(\sum^{16}_{k=1}x^{5k})(\sum^{8}_{k=1}x^{10k})(\sum^{4}_{k=1}x^{20k})(\sum^{1}_{k=1}x^{50k})\]

To calculate this coefficient in a more efficient manner than a complete direct expansion, we can consider the closed form for partial sums of a geometric series.


Since we can reduce coefficients of polynomials. This is really the bijection principle in action; calculation coefficients of multiplied polynomials can be put in bijection to many combinatorial problems, in the case of the binomial theorem, coefficients of exponentiated binomials have a bijective relationship to permutations of $k$ amount of $x$es and $n-k$ amount of $y$s. 

If we can encode our problem by means of polynomials, we can invoke results from mathematical analysis relating to polynomials to solve combinatorial problems. The moral is that the bijection principle is truly the heart of combinatorics; translating our problem into equivalent structures that are easier to calculate!




\section{Ordinary generating functions}


Since polynomial encodings are so important, it is useful to tabulate some frequent encodings for common combinatorial problems. We standardize this by the notion of a \emph{generating funtion}, the most fundamental being the ordinary generating function.


\begin{definition}[Ordinary generating function]
\[ \sum^{\infty}_{k=0}S_k x^k\]
\end{definition}

\section{Exponential generating functions}

Often generating functions have a trivial factor known to occur in every coefficient.

\[ \sum^{\infty}_{k=0}S_k \frac{x^k}{k!}\]