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

Checker Jumping, Coin Counting, and Cap Throwing: Why Generating Functions are Magic!


GMA Colloquium

August 28, 2013


Jay Pantone

University of Florida


[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.]

what are generating functions?


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]].\]


That's it!

examples of generating functions


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}$

what's the point?

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.\]

checker jumping

(solution due to John Conway)


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?

checker jumping

$(n=1)$

[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

checker jumping

$(n=2)$

[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

checker jumping

$(n=3)$

[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

checker jumping

$(n=4)$

[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

checker jumping

$(n=5)$


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

checker jumping


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]}.\]

checker jumping


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\]

checker jumping


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

checker jumping


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

checker jumping


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$

checker jumping









Any questions about checker jumping?





coin counting

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\]

coin counting

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*}


coin counting

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.)

coin counting









Any questions about coin counting?





cap throwing

(the derangement problem)

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?

cap throwing

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.

cap throwing

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

cap throwing

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). \]

cap throwing

($n=10$)

$\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*}$


cap throwing









Any questions about cap throwing?





Thanks for coming!

See more about Conway's Soldiers:

http://www.chiark.greenend.org.uk/~sgtatham/solarmy/