$\usepackage{textcomp}$
$\newcommand{\Av}{\operatorname{Av}}$
$\newcommand{\oc}{\Av(3124,4312)}$
$\newcommand{\pa}[1]{\left({#1}\right)}$
$\newcommand{\ds}{\displaystyle}$

[Wait 15 seconds for the page to load completely,

or the math will be messed up.]

[Navigate slides using the left and right arrow keys.]

A generating function is a clothesline on which we hang up a sequence of numbers for display.

- Herb Wilf, *Generatingfunctionology*

Take an infinite sequence (usually of integers) $\mathcal{A} = (a_0, a_1, a_2, \ldots)$, and use these as the coefficients of a formal power series.

\[A(x) = \ds\sum_{i \geq 0} a_ix^i = a_0 + a_1x + a_2x^2 + \cdots \in \mathbb{R}[[x]].\]

What's the generating function of the sequence $(0,0,2,1,0,0,\ldots)$ ?

$0 + 0x + 2x^2 + 1x^3 + 0x^4 + 0x^5 + \cdots = $ $2x^2 + x^3$

What's the generating function of the sequence $(1,1,1,1,1,1,\ldots)$ ?

$1 + x + x^2 + x^3 + x^4 + x^5 + \cdots = $ $\ds\frac{1}{1-x}$

What's the generating function of the sequence $(1,2,4,8,16,32,\ldots)$ ?

$1 + 2x + 4x^2 + 8x^3 + 16x^4 + 32x^5 + \cdots = $ $\ds\frac{1}{1-2x}$

We *don't care* about convergence. All arithmetic is

done in the ring of formal power series.

We can perform many easy operations on generating functions

to get combinatorial results. Suppose we have the sequence $\mathcal{A} = \pa{a_n}_{n \geq 0}$ with generating function $A(x)$. Then:

The sequence $\pa{0, 0, a_0, a_1, a_2, \ldots}$ has generating function \[x^2A(x) = a_0x^2 + a_1x^3 + a_2x^4 + \cdots.\]

The sequence $\pa{n\cdot a_n}_{n \geq 0}$ has generating function \[x\:A'(x) = a_1x + 2a_2x^2 + 3a_3x^3 + \cdots.\]

The sequence of partial sums has generating function \[\ds\frac{1}{1-x}\cdot A(x) = a_0 + (a_0+a_1)x + (a_0+a_1+a_2)x^2 + \cdots.\]

Start with an arbitrary (but finite) number of checkers

lined up in a grid on one side of a line.

A checker can jump over an adjacent checker (not diagonally),

and the checker that got jumped over disappears.

How many checkers do you need to start with

to get a checker $n$ steps past the line?

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 2 checkers

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 4 checkers

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 8 checkers

[To play the animation, click in the box and use the left/right arrows (not too fast!).]

[You must click outside of the box to proceed to the next slide.]

needed 20 checkers

Impossible! Weird, huh?

**Proof:** Let $P$ be a location in the $5^{\text{th}}$ row, where we're trying to get a checker.

Label each space with the monomial $x^i$, where $i$ is

the grid-distance from the space to $P$.

Let $S$ be the sum of all monomials which currently have a checker on them.

A jump can change $S$ in three ways:

- A checker can go from $x^n$ to $x^{n+2}$, setting $S := S+\pa{x^{n+2}-x^{n+1}-x^n}$.
- A checker can go from $x^{n}$ to $x^{n-2}$, setting $S := S+\pa{x^{n-2}-x^{n-1}-x^{n}}$.
- A checker can go from $x^{n}$ to $x^{n}$, setting $S := S+\pa{-x^{n-1}}$.

If we can successfully get a checker to $x^0$, then at this point, we should have

\[S = x^0 + \text{[other stuff]} = 1 + \text{[other stuff]}.\]

Consider the $n=3$ case from earlier.

\[S = x^3 + 3x^4 + 3x^5 + x^6\]

\[S = x^2 + x^3 + 2x^4 + 3x^5 + x^6\]

\[S = x^2 + x^3 + x^4 + 2x^5 + x^6\]

\[S = x + x^4 + 2x^5 + x^6\]

\[S = x + x^3 + x^4\]

\[S = x^0 = 1\]

What happens if we plug in a specific $x$-value into these polynomials?

For most $x$-values, the value of $S$ will go up and down as we jump around.

Instead, we're going to pick an $x$-value for which $S$ *doesn't change* when

we jump toward the target, and only *decreases* after other jumps.

Therefore, since we end with a value of $S=1$, we *must start*

with a configuration which has $S \geq 1$.

Recall that a jump toward the target changed $S$ by \[S := S - x^n(1-x-x^2).\]

The roots of $1-x-x^2$ are $x = \ds\frac{-1\pm\sqrt{5}}{2}$, and if we pick $\phi := \ds\frac{-1+\sqrt{5}}{2} \approx 0.62$, then jumps toward the target don't change $S$, while other jumps only decrease $S$.

Note: $\phi^2 = 1 - \phi$.

If we start with a checker in every spot with the goal of reaching the $5^{\text{th}}$ level,

what is the value of our starting configuration?

The sum of the first row is $R := \phi^5 + 2(\phi^6 + \phi^7 + \cdots)$, and the sum of the $i^{\text{th}}$ row is $\phi^{i-1}\cdot R$.

Hence, the starting configuration has value:

\[
\begin{align*}
\pa{\phi^5 + 2\pa{\phi^6 + \phi^7 + \cdots}}\pa{1 + \phi + \phi^2 + \cdots} &= \pa{\phi^5 + \ds\frac{2\phi^6}{1-\phi}}\pa{\ds\frac{1}{1-\phi}}\\
&= \ds\frac{\phi^5 - \phi^6 + 2\phi^6}{\pa{1-\phi}^2}\\
&= \ds\frac{\phi^5\pa{1+\phi}}{\pa{1-\phi}^2}\\
&= \ds\frac{\phi^5\pa{1+\phi}}{\phi^4}\\
&= \phi^2+\phi\\
&= 1.
\end{align*}
\]

Therefore, with any finite number of checkers, the starting configuration will have

value less than 1, making it impossible to reach the $5^{\text{th}}$ level. $\square$

Any questions about checker jumping?

How many ways are there to make change for $23.70

using pennies, nickels, dimes, and quarters?

We're going to build a generating function $C(x) = \sum a_nx^n$

where $a_n$ is the number of ways to make change for $n$ cents.

Let's start with an easier problem: What combinations of change

can we make if we have 4 pennies, 2 nickels, and a dime?

- GF for 4 pennies: $1+x+x^2+x^3+x^4$
- GF for 2 nickels: $1+x^5+x^{10}$
- GF for 1 dime: $1+x^{10}$

We want the generating function for all possible combinations of picking 0-4 pennies, 0-2 nickels, and 0-1 dimes. All we need to do is multiply the generating functions for each denomination together!

\[(1+x+x^2+x^3+x^4)(1+x^5+x^{10})(1+x^{10}) = x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} + 2 \, x^{14} + 2 \, x^{13}\]\[ \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+ \:2 \, x^{12} + 2 \, x^{11} + 2 \, x^{10} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1\]

Now back the original problem.

We can have any number of each type of coin.

- GF for pennies: $1+x+x^2+x^3+\cdots = \ds\frac{1}{1-x}$
- GF for nickels: $1+x^5+x^{10}+x^{15}+\cdots = \ds\frac{1}{1-x^5}$
- GF for dimes: $1+x^{10}+x^{20}+x^{30}+\cdots = \ds\frac{1}{1-x^{10}}$
- GF for quarters: $1+x^{25}+x^{50}+x^{75}+\cdots = \ds\frac{1}{1-x^{25}}$

\begin{align*}C(x) &= \frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{25}}\\& = 1 + x + x^2 + x^3 + \cdots + 1825912x^{2370} + \cdots\end{align*}

This method is easily extendable!

Want to allow 50-cent coins and all bills?

\[ \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!C(x) = \frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}}\cdot\frac{1}{1-x^{25}}\cdot\frac{1}{1-x^{50}}\cdot\frac{1}{1-x^{100}}\cdot\frac{1}{1-x^{200}}\cdot\frac{1}{1-x^{500}}\cdot\frac{1}{1-x^{1000}}\cdot\frac{1}{1-x^{2000}}\cdot\frac{1}{1-x^{5000}}\cdot\frac{1}{1-x^{10000}} \]

In a strange and foreign land which only has 2, 3, 7, and 18 cent coins?

\[ C(x) = \frac{1}{1-x^2}\cdot\frac{1}{1-x^3}\cdot\frac{1}{1-x^{7}}\cdot\frac{1}{1-x^{18}} \]

Want to keep track of *how many* coins are used?

\[ C(x) = \frac{1}{1-ux}\cdot\frac{1}{1-ux^5}\cdot\frac{1}{1-ux^{10}}\cdot\frac{1}{1-ux^{25}} \]

(A term $a_{i,j}u^ix^j$ means that there are $a_{i,j}$ ways to make $j$ cents using $i$ coins.)

Any questions about coin counting?

During graduation, a group of students throwing their hats into the air, and randomly (uniformly) catch a hat when they come down. What is the probability that nobody caught their own hat?

or

Since you don't know any of your students' names, you pass back exams at random. What is the probability that no student actually got their own exam?

or

What proportion of permutations in $S_n$ have no fixed points?

This question can be easily solved with the **Principle of Inclusion-Exclusion** (PIE), so let's start with a quick refresher.

Say that there are 100 graduate students in the department, and they play some combination of ultimate frisbee, racquetball, and basketball. If 45 play basketball (and possibly other sports), 36 play racquetball, etc, then how many students play no sports?

We start with all $100$ students, then subtract $(45+36+33)$. However, this subtracts people who play more than one sport twice, so to compensate, we add back in $(8+10+11)$. Now, we've added back in people who play all three sports twice, so we must subtract $3$.

\[100-(45+36+33)+(8+10+11)-(3) = 12.\]

We started with all students, then added/subtracted back and forth the sum of number of students who played each set of sports, even though some of these sets overlapped.

First, we're going to solve our problem using this

technique, without generating functions.

What proportion of permutations in $S_n$ have no fixed points?

Let $I \subseteq \{1,2, \ldots, n\}$. How many permutations have every point of $I$ fixed?

\[\pa{n-|I|}!\]

By PIE, the number of permutations with no fixed points is:

\[\begin{align*} \ds\sum_{I \subseteq \{1, \ldots, n\}}(-1)^{|I|}(n-|I|)! &= \ds\sum_{i=0}^n (-1)^i{n \choose i}(n-i)!\\ &= \ds\sum_{i=0}^n (-1)^i\ds\frac{n!}{i!(n-i)!}(n-i)!\\ &= n!\ds\sum_{i=0}^n \frac{(-1)^i}{i!} \approx \frac{n!}{e}. \end{align*}\]

So, the probability that no one gets their cap back approaches $\ds\frac{1}{e} \approx 36.8\%$.

Well, that was pretty easy, so why do we need generating functions?

Using the **sieve method**, we can easily find a generating function $f_n = \sum a_ix^i$ where $a_i$ is the number of permutations in $S_n$ with *exactly* $i$ fixed points.

We start by building a generating function that over-counts, by

setting $a_i$ to be ${n \choose i}(n-i)!$, just like when we used PIE.
\[
g_n(x) = \ds\sum_{i=0}^n \left[{n \choose i}(n-i)!\right]x^i.
\]

Then, the generating function we actually want (which

compensates for the over-counting) is just
\[
f_n(u) := g_n(u-1).
\]

$\begin{align*} g_{10}(x) &= \ds\sum_{i=0}^{10} \left[{10 \choose i}(10-i)!\right]x^i\\[4pt] &= x^{10} + 10x^{9} + 90x^{8} + 720 x^{7} + 5040 x^{6} + 30240 x^{5} + 151200 x^{4}\\&\qquad + 604800 x^{3} + 1814400 x^{2} + 3628800 x + 3628800 \end{align*}$

$\begin{align*} f_{10}(u) &= g_{10}(u-1)\\[4pt] &= {\left(u - 1\right)}^{10} + 10 {\left(u - 1\right)}^{9} + 90 {\left(u - 1\right)}^{8} + 720 {\left(u - 1\right)}^{7} \\&\qquad+ 5040 {\left(u - 1\right)}^{6} + 30240 {\left(u - 1\right)}^{5} + 151200 {\left(u - 1\right)}^{4} \\&\qquad + 604800 {\left(u - 1\right)}^{3} + 1814400 {\left(u - 1\right)}^{2} + 3628800 u\\[4pt] &= u^{10} + 45 \, u^{8} + 240 \, u^{7} + 1890 \, u^{6} + 11088 \, u^{5} + 55650 \, u^{4} \\&\qquad + 222480 \, u^{3} + 667485 \, u^{2} + 1334960 \, u + 1334961 \end{align*}$

Any questions about cap throwing?