# Lecture 5: More Counting and Generating Functions Source: https://www.youtube.com/watch?v=HpQUVd1MGso Recap page: https://rapidrecap.app/video/HpQUVd1MGso Generated: 2025-12-17T16:37:51.537+00:00 --- ## 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 $T_n = n^{n-2}$, and then introduces generating functions by defining them as $F(x) = \sum a_i 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, $T_n \times n \times (n-1)!$, where $T_n$ is the number of labeled trees; the second way establishes the count as $n^{n-1} (n-1)!$, leading to $T_n = 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 $a_0, a_1, a_2, \dots$ is defined as $F(x) = \sum a_i 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. ## Detailed Analysis The lecture successfully proves Cayley's tree theorem, $T_n = n^{n-2}$, by relating the number of labeled trees ($T_n$) to the number of labeled rooted trees with ordered edges. The first count yields $T_n \cdot n \cdot (n-1)!$, and the second count, established by constructing the tree by sequentially adding rooted one-vertex trees to a forest, yields $n^{n-1} (n-1)!$. The lecture then pivots to generating functions, formally defining $F(x) = \sum a_i x^i$ as the function associated with a sequence $a_i$. Examples include showing the generating function for binomial coefficients $\binom{k}{n}$ is $(1+x)^k$. The additive property of generating functions ($C(x) = A(x) + B(x)$ for disjoint unions) and the multiplicative property ($C(x) = A(x)B(x)$ for Cartesian products) are demonstrated, notably for calculating the sums possible when rolling two dice. A powerful trick involving differentiation of the generating function $F(x)=(1+x)^n$ is used to evaluate $\sum_{k=0}^{n} \binom{n}{k} k$ as $n 2^{n-1}$, which Shor confirms with a separate combinatorial argument. ### Cayley Tree Theorem Proof - The number of labeled trees on $n$ vertices is $n^{n-2}$ - The proof relies on counting labeled rooted trees with ordered edges twice - The second count uses construction by adding one-vertex trees sequentially to a forest. ### Generating Function Definition and Basics - $F(x) = \sum a_i x^i$ uses $x$ as an index tracker - Addition corresponds to disjoint union of object classes ($C(x) = A(x) + B(x)$) - Multiplication corresponds to Cartesian product ($C(x) = A(x)B(x)$). ### Generating Function Examples - Binomial coefficients $\binom{k}{n}$ have GF $(1+x)^k$ - Sums of dice rolls are found by multiplying their respective GFs - Change-making problems use products of infinite geometric series, e.g., $1/(1-x)$ for pennies. ### Algebraic Manipulation Trick - To calculate $\sum k \binom{n}{k}$, differentiate $F(x)=(1+x)^n$ to get $\sum k \binom{n}{k} x^{k-1}$ - Substituting $x=1$ yields the result $n 2^{n-1}$.