Lecture 5: More Counting and Generating Functions

Quick Overview

Peter Shor proves Cayley's tree theorem, stating there are $n^{n-2}$ labeled trees on $n$ vertices, by counting labeled rooted trees with ordered edges in two different ways, which ultimately leads to the formula $Tn = n^{n-2}$, and then introduces generating functions by defining them as $F(x) = \sum ai x^i$ and demonstrating their application in binomial coefficients and calculating combinations for sums of dice rolls and change-making problems.

Key Points: The Cayley tree theorem states that there are $n^{n-2}$ ways of labeling a tree on $n$ vertices, demonstrated by checking initial values: $n=2$ has 1 way, $n=3$ has 3 ways, and $n=4$ leads to a sum resulting in $4^2 = 16$ (for specific tree shapes), summing up to $125$ for $n=5$ (which is $5^3$). Shor proves the theorem by counting labeled rooted trees with ordered edges in two ways: first, $Tn \times n \times (n-1)!$, where $Tn$ is the number of labeled trees; the second way establishes the count as $n^{n-1} (n-1)!$, leading to $Tn = n^{n-2}$. The second counting method involves constructing the tree iteratively by adding one-vertex trees to existing trees in a labeled rooted forest, reducing the number of trees by one at each step over $n-1$ steps. A generating function $F(x)$ for a sequence $a0, a1, a2, \dots$ is defined as $F(x) = \sum ai x^i$, where $x$ is a tool for keeping track of the index $i$. The generating function for binomial coefficients $\binom{k}{n}$ is shown to be $(1+x)^k$, derived from the binomial theorem. The generating function for the sum of outcomes of two dice (6-sided and 8-sided) is found by multiplying their individual generating functions, $C(x) = (x + x^2 + \dots + x^6)(x + x^2 + \dots + x^8)$. The summation $\sum{k=0}^{n} \binom{n}{k} k$ is solved using generating functions by differentiating $F(x) = (1+x)^n$ and then setting $x=1$, resulting in $n \cdot 2^{n-1}$, which is verified by a combinatorial argument involving choosing a special element from a subset.

Context: The lecture begins with Peter Shor explaining and proving the Cayley tree theorem, which determines the number of distinct labelings for a tree structure on $n$ vertices. After establishing this result using a double-counting argument for labeled rooted trees with ordered edges, the lecture transitions to the second major topic: generating functions. Generating functions are introduced as an algebraic tool used to count combinatorial objects, contrasting them with more intuitive but sometimes difficult direct counting proofs.