两个问题，一种方法

这一讲处理两个看起来无关的问题：

1. $n$ 个顶点的标号树有多少棵？
2. 怎样把一整列计数问题变成可以机械计算的代数？

第一个问题的答案出奇简单：$n^{n-2}$。证明的关键是把同一类对象用两种方式数一遍——这正是上一讲反复训练的技巧。

第二个问题是生成函数。它把序列 $a_0,a_1,a_2,\dots$ 打包成一个幂级数，于是「组合」变成「代数运算」：不交并变成相加，笛卡尔积变成相乘，而求导可以给每一项乘上它的下标。

时间轴

凯莱树定理

陈述与小的情形

定理（Cayley）。 $n$ 个标号顶点的树共有 $n^{n-2}$ 棵。

先看几个小值（标号是 $1,\dots,n$）：

$n=4$ 可以手工核对：路径型 $1-2-3-4$ 的标号方式有 $4!/2=12$ 种（左右对称导致除以 $2$），星型（一个中心接三个叶子）有 $4$ 种（只选中心），合计 $16$。

$n=5$ 时，课程同样分类相加得到 $125$，于是规律浮现。

证明策略：把对象升级，再数两次

直接数标号树很难。策略是先数一类更容易构造的对象：标号有根树、且给边排了序。

设 $T_n$ 为 $n$ 个顶点的标号树数量。考虑

$$\text{标号} + \text{选一个根} + \text{给 } n-1 \text{ 条边排序}$$

这一类对象。

第一种数法。 从一棵标号树出发：根可以任选（$n$ 种），$n-1$ 条边可以任意排序（$(n-1)!$ 种）。所以总数是

$$T_n\cdot n\cdot (n-1)! .$$

第二种数法。 换一个构造顺序：从 $n$ 个孤立顶点（即 $n$ 棵单点树构成的森林）出发，每次把一个连通块挂到另一个连通块上。

第 $k$ 步（$k=0,1,\dots,n-2$）开始时还剩 $n-k$ 棵树：

• 从 $n$ 个顶点中任选一个作为挂载点：$n$ 种；
• 选另一棵树（不能是挂载点所在的那棵）：$n-k-1$ 种；
• 把那棵树的根接到挂载点上，边记为第 $k+1$ 条。

每一步减少一棵树，共走 $n-1$ 步，最后只剩一棵，得到标号有根树，且边带有添加顺序。总数为

$$\prod_{k=0}^{n-2} n\,(n-k-1) =n^{\,n-1}\cdot (n-1)! .$$

其中 $n$ 出现了 $n-1$ 次，而 $(n-k-1)$ 从 $n-1$ 一路乘到 $1$。

为什么这是双射

第二种构造是可逆的：给定一棵带边序的标号有根树，看最后添加的那条边，把它剪断，就唯一地还原出「两棵树」的森林，以及此前所有步骤留下的结构。反复执行，直到回到 $n$ 个孤立顶点。

因为正反两个方向都唯一，所以第二种数法数出的正是同一类对象。于是

$$T_n\cdot n\cdot (n-1)!=n^{n-1}(n-1)!,$$

两边约去 $n(n-1)!$：

$$T_n=n^{n-2}. \qquad\square$$

这个证明的美感在于：没有直接数树，而是数「树 + 根 + 边序」。多加的结构让构造变得容易，两边再一起约掉。

课程顺带提到，也可以构造标号树与长度 $n-2$、取值 $1..n$ 的序列之间的双射（Prüfer 序列），但那个双射相当复杂、直觉上不友好，所以这里走双重计数的路线。

生成函数：把序列变成一个函数

定义

给定数列 $a_0,a_1,a_2,\dots$，它的生成函数是形式幂级数

$$F(x)=\sum_{i=0}^{\infty}a_i x^i .$$

这里 $x$ 不是数，也不必赋予任何值。它的唯一作用是记录下标：$a_i$ 与 $x^i$ 绑定在一起，从而把「第 $i$ 项」与「第 $j$ 项」区分开。

既然是形式幂级数，就可以像多项式一样做加法、乘法、求导、代入，而不必担心收敛。这些代数操作会对应到组合意义，这正是它的价值。

例一：二项式系数

取 $a_n=\binom kn$（当 $n>k$ 时记作 $0$）。则

$$F(x)=\sum_{n=0}^{k}\binom kn x^n=(1+x)^k .$$

这正是二项式定理。逐项解释：把 $(1+x)^k$ 看成 $k$ 个 $(1+x)$ 相乘，要得到 $x^n$，必须从其中 $n$ 个括号里取 $x$、其余取 $1$——选择方式有 $\binom kn$ 种，所以 $x^n$ 的系数就是 $\binom kn$。

生成函数把「组合选择」编码成了「代数展开」。

例二：有偏硬币

抛一枚有偏硬币 $k$ 次，每次正面概率 $p$、反面概率 $q=1-p$。令 $a_n$ 为恰好出现 $n$ 次正面的概率：

$$a_n=\binom kn p^n q^{k-n}.$$

其生成函数为

$$A(x)=\sum_{n=0}^{k}\binom kn p^n q^{k-n}x^n=(q+px)^k,$$

同样由二项式定理得到。这里 $x$ 的作用只是标记「正面次数」，不含概率意义。

生成函数的运算

不交并：相加

设 $A,B$ 是不交的对象类，$C=A\sqcup B$。若按「大小」分层，大小为 $n$ 的对象在 $C$ 中有

$$c_n=a_n+b_n$$

个。于是

$$C(x)=\sum_n (a_n+b_n)x^n=A(x)+B(x).$$

组合上的「或者」对应代数上的「加」。

笛卡尔积：相乘

设 $A,B$ 是两类对象，$A\times B$ 中的对象形如 $(a,b)$，其大小定义为两者之和。则大小为 $n$ 的对象有

$$c_n=\sum_{k=0}^{n}a_k\,b_{n-k}$$

个：第一分量大小为 $k$、第二分量大小为 $n-k$，对所有 $k$ 求和。这正是多项式乘法的系数公式，所以

$$C(x)=A(x)\,B(x).$$

组合上的「先选一个、再选一个，大小相加」对应代数上的「乘」。

例三：两枚骰子的和

一枚六面骰（$1$–$6$）的生成函数是

$$A(x)=x+x^2+x^3+x^4+x^5+x^6,$$

一枚八面骰（$1$–$8$）的生成函数是

$$B(x)=x+x^2+\cdots+x^8 .$$

两枚骰子之和的分布就是乘积

$$C(x)=A(x)B(x).$$

看 $x^{10}$ 的系数：它数的是满足 $a+b=10$、$1\le a\le6$、$1\le b\le8$ 的有序对

$$(2,8),\ (3,7),\ (4,6),\ (5,5),\ (6,4),$$

共 $5$ 种。展开乘积确实给出 $5x^{10}$。

注意这里是有序对：$(6,4)$ 与 $(4,6)$ 被算作两种，因为第一枚和第二枚骰子是不同的。

例四：找零

有限枚数。 有 $6$ 枚 1 分、$1$ 枚 5 分、$2$ 枚 10 分，凑出 $n$ 分有多少种方法？

每种硬币的选择对应一个因子：

$$C(x)=(1+x+x^2+\cdots+x^6)(1+x^5)(1+x^{10}+x^{20}).$$

第一个因子表示「用 $0$ 到 $6$ 枚 1 分」，第二个表示「用 $0$ 或 $1$ 枚 5 分」，第三个表示「用 $0$、$1$ 或 $2$ 枚 10 分」。展开后 $x^n$ 的系数就是凑出 $n$ 分的方法数。

看 $x^{21}$ 的系数。能凑出 $21$ 的组合只有两种：

$$6+5+10=21, \qquad 1+20=21 .$$

所以答案是 $2$。（$6$ 枚 1 分加 $1$ 枚 5 分加 $1$ 枚 10 分；或 $1$ 枚 1 分加 $2$ 枚 10 分。）

无限枚数。 如果 1 分、5 分、10 分都取之不尽，则每个因子变成无穷级数：

$$C(x)=\left(\sum_{i\ge0}x^i\right)\left(\sum_{i\ge0}x^{5i}\right)\left(\sum_{i\ge0}x^{10i}\right) =\frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}} .$$

这里用了几何级数

$$1+x+x^2+\cdots=\frac{1}{1-x}.$$

于是「凑零钱」这个组合问题，被转化成了有理函数的系数提取问题。

用生成函数计算求和

目标

计算

$$S=\sum_{k=0}^{n}k\binom nk .$$

第一步：写出已知的生成函数

由二项式定理，

$$F(x)=\sum_{k=0}^{n}\binom nk x^k=(1+x)^n .$$

第二步：求导

对两边求导，左边每一项 $x^k$ 变成 $kx^{k-1}$：

$$F'(x)=\sum_{k=0}^{n}k\binom nk x^{k-1}=n(1+x)^{n-1}.$$

第三步：代入 $x=1$

左边变成 $\sum_k k\binom nk$，右边变成 $n\cdot 2^{n-1}$。于是

$$\sum_{k=0}^{n}k\binom nk=n\,2^{n-1}.$$

技巧总结： 要让生成函数的第 $k$ 项乘上 $k$，就对它求导，再乘以 $x$（若最终代入 $x=1$，乘以 $x$ 这一步可省）。这个操作在后面处理期望与递推时会反复用到。

双重计数验证

同一个和也可以用组合意义算出来：数「从 $n$ 个元素中选出一个 $k$ 元子集，并在其中指定一个特殊元素」。

• 先选特殊元素：$n$ 种；
• 剩下的 $n-1$ 个元素各自决定是否加入子集：$2^{n-1}$ 种。

所以总数是 $n\,2^{n-1}$。

两种方法结果一致，但生成函数的路线不需要想出一个巧妙的组合解释——只需要机械地求导、代入。这正是课程强调的优势：创意可以换成代数。

本节结论

• 凯莱定理：$n$ 个标号顶点的树有 $n^{n-2}$ 棵。
• 证明方法是数「标号有根树 + 边序」两类方式：$T_n\cdot n\cdot(n-1)!$ 与 $n^{n-1}(n-1)!$，相等即得结论。
• 生成函数 $F(x)=\sum a_i x^i$ 把序列编码成形式幂级数，$x$ 只起标记作用。
• $\sum_n\binom knx^n=(1+x)^k$；有偏硬币对应 $(q+px)^k$。
• 不交并 ⟹ 生成函数相加；笛卡尔积（大小相加）⟹ 生成函数相乘。
• 两枚骰子之和的分布是两者生成函数之积；有限枚硬币的找零问题对应多项式，无限枚对应有理函数 $\frac{1}{(1-x)(1-x^5)(1-x^{10})}$。
• 求导技巧：给第 $k$ 项乘 $k$ 相当于求导，于是 $\sum_k k\binom nk=n2^{n-1}$。

理解检验

1. 用凯莱公式验证 $n=5$ 的情形，并说明 $n=4$ 时路径型与星型各有多少种标号。

参考答案：公式给出 $5^{5-2}=125$。$n=4$ 时：路径型 $1-2-3-4$ 的标号方式为 $4!/2=12$（左右镜像被视为同一棵树，故除以 $2$）；星型（一个中心连三个叶子）只需选定中心，共 $4$ 种。合计 $12+4=16=4^{4-2}$，与公式一致。

2. 在凯莱定理的第二种数法中，第 $k$ 步为什么有 $n(n-k-1)$ 种选择？

参考答案：第 $k$ 步开始时森林里有 $n-k$ 棵树。先选挂载点：$n$ 个标号顶点中的任意一个，共 $n$ 种。再选一棵要挂上去的树：不能选挂载点所在的那一棵（否则不构成加边），所以有 $n-k-1$ 种。把该树的根接到挂载点上，这一步就唯一确定了。于是每步有 $n(n-k-1)$ 种，$k$ 从 $0$ 到 $n-2$ 连乘，得到 $n^{n-1}(n-1)!$。

3. 为什么「逐个加边」的构造是可逆的？请描述逆过程。

参考答案：给定最终的标号有根树以及边的添加顺序，逆过程是：找到最后添加的那条边并剪断，于是得到两棵树——原来被挂上去的那棵（其根就是这条边的下端）和剩下的那棵。这就唯一还原了上一步的森林，以及所有更早的边。重复执行直到剩下 $n$ 个孤立顶点。因为正向的每一步都由「选挂载点 + 选被挂的树」唯一确定，逆过程也唯一确定，所以这是双射。

4. 写出六面骰与八面骰之和的生成函数，并解释 $x^{10}$ 的系数为什么是 $5$。

参考答案：

$$C(x)=(x+x^2+\cdots+x^6)(x+x^2+\cdots+x^8).$$

$x^{10}$ 的系数统计满足 $a+b=10$、$1\le a\le6$、$1\le b\le8$ 的有序对 $(a,b)$：$(2,8),(3,7),(4,6),(5,5),(6,4)$，共 $5$ 个。乘积展开时，$x^{10}$ 项由所有「第一个因子取 $x^a$、第二个因子取 $x^{10-a}$」的乘法贡献，每个可行对恰好贡献一次，所以系数是 $5$。

5. 用生成函数证明 $\sum_{k=0}^n k\binom nk=n2^{n-1}$，并说明求导为什么能达到「乘 $k$」的效果。

参考答案：由 $(1+x)^n=\sum_k\binom nk x^k$，两边求导得

$$n(1+x)^{n-1}=\sum_k k\binom nk x^{k-1}.$$

令 $x=1$，右边为 $\sum_k k\binom nk$，左边为 $n\cdot2^{n-1}$，故等式成立。求导之所以能乘 $k$：$x^k$ 的导数是 $kx^{k-1}$，每一项的指数系数被提到了前面；若需要保留 $x^k$ 的形式，再乘以 $x$ 即可（代入 $x=1$ 时两者相同）。

6. 用 $6$ 枚 1 分、$1$ 枚 5 分、$2$ 枚 10 分凑 $21$ 分，有几种方法？写出对应的生成函数并说明理由。

参考答案：生成函数为

$$C(x)=(1+x+\cdots+x^6)(1+x^5)(1+x^{10}+x^{20}).$$

三个因子分别记录 1 分、5 分、10 分的枚数选择，展开后 $x^n$ 的系数就是凑出 $n$ 分的方法数。$x^{21}$ 的系数：可行组合只有 $6+5+10=21$ 与 $1+20=21$，所以答案是 $2$。

与前后课的关系

这一讲完成了计数单元的两条主线：双重计数（凯莱定理）与生成函数（把计数机械化）。生成函数目前还只是雏形——只用了加法、乘法与求导。下一讲会用它处理递推关系，尤其是斐波那契数列；再往后，卡特兰数的公式也会从一个二次方程里解出来，而不必再依赖那个漂亮的反射双射。

一句话概括：当计数问题能被写成「结构的组合」，它就能被写成「函数的代数」；此后只需算代数，不必再想组合。

Two questions, one method

This lecture handles two seemingly unrelated problems:

1. How many labelled trees are there on $n$ vertices?
2. How can a whole family of counting problems be turned into mechanical algebra?

The first answer is surprisingly clean: $n^{n-2}$. The proof counts the same class of objects two ways — precisely the technique drilled in the previous lecture.

The second topic is generating functions. They pack a sequence $a_0,a_1,a_2,\dots$ into a power series, so that "combining structures" becomes "algebra": disjoint union becomes addition, Cartesian product becomes multiplication, and differentiation multiplies the $k$-th term by $k$.

Timeline

Cayley's tree theorem

Statement and small cases

Theorem (Cayley). The number of trees on $n$ labelled vertices is $n^{n-2}$.

Small values (labels $1,\dots,n$):

For $n=4$ a hand check works: the path $1-2-3-4$ has $4!/2=12$ labellings (dividing by $2$ for left-right symmetry), and the star with one centre has $4$ labellings (choose the centre), totalling $16$.

For $n=5$, the lecture sums the cases to $125$, and the pattern becomes visible.

Strategy: upgrade the objects, then count twice

Counting labelled trees directly is hard. The strategy is to count an easier-to-construct class first: rooted labelled trees with an ordering on their edges.

Let $T_n$ be the number of labelled trees on $n$ vertices. Consider objects consisting of

$$\text{labelled tree} + \text{a chosen root} + \text{an ordering of its } n-1 \text{ edges}.$$

First count. Start from a labelled tree: choose any root ($n$ ways), then order the $n-1$ edges in any way ($(n-1)!$ ways). The total is

$$T_n\cdot n\cdot (n-1)! .$$

Second count. Build the same objects by construction: start from $n$ isolated vertices (a forest of $n$ one-vertex trees), and repeatedly attach one component to another.

At step $k$ ($k=0,1,\dots,n-2$) there are $n-k$ trees left:

• choose one of the $n$ vertices as the attachment point: $n$ ways;
• choose a different tree (not the one containing that vertex): $n-k-1$ ways;
• attach the root of that tree to the attachment point, labelling this the $(k+1)$-st edge.

Each step reduces the number of trees by one; after $n-1$ steps a single tree remains, labelled and rooted, with its edges ordered by insertion. The total is

$$\prod_{k=0}^{n-2} n\,(n-k-1) =n^{\,n-1}\cdot (n-1)! ,$$

since $n$ appears $n-1$ times and $(n-k-1)$ runs from $n-1$ down to $1$.

Why this is a bijection

The construction is reversible. Given a rooted labelled tree with ordered edges, look at the edge added last, cut it, and the two resulting components uniquely recover the previous forest together with all earlier structure. Repeating returns to the $n$ isolated vertices.

Because both directions are unique, the second count enumerates the same class. Hence

$$T_n\cdot n\cdot (n-1)!=n^{n-1}(n-1)!,$$

and cancelling $n(n-1)!$ gives

$$T_n=n^{n-2}. \qquad\square$$

The elegance lies in not counting trees directly, but counting "tree + root + edge order". The extra structure makes construction easy, and it cancels at the end.

The lecture notes that one could instead build a bijection between labelled trees and sequences of length $n-2$ over $\{1,\dots,n\}$ (Prüfer sequences), but that bijection is complicated and unintuitive, so the double-counting route is taken instead.

Generating functions: turning a sequence into a function

Definition

Given a sequence $a_0,a_1,a_2,\dots$, its generating function is the formal power series

$$F(x)=\sum_{i=0}^{\infty}a_i x^i .$$

Here $x$ is not a number and need not be assigned any value. Its only job is to record the index: $a_i$ is tied to $x^i$, which keeps the $i$-th and $j$-th terms distinct.

Being formal, the series can be added, multiplied, differentiated and substituted without any convergence worries. Each algebraic operation then corresponds to a combinatorial one — that is the point.

Example one: binomial coefficients

Take $a_n=\binom kn$ (with $a_n=0$ for $n>k$). Then

$$F(x)=\sum_{n=0}^{k}\binom kn x^n=(1+x)^k .$$

This is the binomial theorem. Term by term: view $(1+x)^k$ as $k$ copies of $(1+x)$ multiplied together. To obtain $x^n$ one must take $x$ from exactly $n$ factors and $1$ from the rest — there are $\binom kn$ ways — so the coefficient of $x^n$ is $\binom kn$.

The generating function encodes a choice problem as an algebraic expansion.

Example two: a biased coin

Flip a biased coin $k$ times, heads with probability $p$ and tails with probability $q=1-p$. Let $a_n$ be the probability of exactly $n$ heads:

$$a_n=\binom kn p^n q^{k-n}.$$

Its generating function is

$$A(x)=\sum_{n=0}^{k}\binom kn p^n q^{k-n}x^n=(q+px)^k,$$

again by the binomial theorem. Here $x$ only marks the number of heads and carries no probabilistic meaning.

Operations on generating functions

Disjoint union: add

Let $A,B$ be disjoint classes and $C=A\sqcup B$. Stratified by size, the number of size-$n$ objects in $C$ is

$$c_n=a_n+b_n,$$

so

$$C(x)=\sum_n (a_n+b_n)x^n=A(x)+B(x).$$

Combinatorial "or" becomes algebraic addition.

Cartesian product: multiply

Let $A,B$ be two classes and let $A\times B$ consist of pairs $(a,b)$ with size defined as the sum of the sizes. Then the number of size-$n$ objects is

$$c_n=\sum_{k=0}^{n}a_k\,b_{n-k},$$

counting first components of size $k$ paired with second components of size $n-k$, summed over $k$. This is exactly the coefficient rule for multiplying polynomials, so

$$C(x)=A(x)\,B(x).$$

Combinatorial "choose one, then another, sizes add" becomes algebraic multiplication.

Example three: the sum of two dice

A six-sided die ($1$–$6$) has generating function

$$A(x)=x+x^2+x^3+x^4+x^5+x^6,$$

and an eight-sided die ($1$–$8$) has

$$B(x)=x+x^2+\cdots+x^8 .$$

The distribution of the sum is the product

$$C(x)=A(x)B(x).$$

Look at the coefficient of $x^{10}$: it counts ordered pairs with $a+b=10$, $1\le a\le6$, $1\le b\le8$:

$$(2,8),\ (3,7),\ (4,6),\ (5,5),\ (6,4),$$

five in total. Expanding the product indeed gives $5x^{10}$.

The pairs are ordered: $(6,4)$ and $(4,6)$ count separately because the two dice are distinct.

Example four: making change

Finitely many coins. With $6$ pennies, $1$ nickel and $2$ dimes, in how many ways can $n$ cents be made?

Each coin type contributes a factor:

$$C(x)=(1+x+x^2+\cdots+x^6)(1+x^5)(1+x^{10}+x^{20}).$$

The first factor records "use $0$ to $6$ pennies", the second "use $0$ or $1$ nickel", the third "use $0$, $1$ or $2$ dimes". After expansion, the coefficient of $x^n$ is the number of ways to make $n$ cents.

Consider the coefficient of $x^{21}$. Only two combinations work:

$$6+5+10=21, \qquad 1+20=21 .$$

So the answer is $2$ (six pennies, one nickel and one dime; or one penny and two dimes).

Unlimited coins. If pennies, nickels and dimes are unlimited, each factor becomes an infinite series:

$$C(x)=\left(\sum_{i\ge0}x^i\right)\left(\sum_{i\ge0}x^{5i}\right)\left(\sum_{i\ge0}x^{10i}\right) =\frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot\frac{1}{1-x^{10}} .$$

This uses the geometric series

$$1+x+x^2+\cdots=\frac{1}{1-x}.$$

So "making change" becomes the problem of extracting coefficients from a rational function.

Using generating functions to evaluate a sum

The target

Compute

$$S=\sum_{k=0}^{n}k\binom nk .$$

Step one: write the known generating function

By the binomial theorem,

$$F(x)=\sum_{k=0}^{n}\binom nk x^k=(1+x)^n .$$

Step two: differentiate

Differentiating term by term turns $x^k$ into $kx^{k-1}$:

$$F'(x)=\sum_{k=0}^{n}k\binom nk x^{k-1}=n(1+x)^{n-1}.$$

Step three: substitute $x=1$

The left side becomes $\sum_k k\binom nk$ and the right becomes $n\cdot2^{n-1}$. Hence

$$\sum_{k=0}^{n}k\binom nk=n\,2^{n-1}.$$

The trick: to multiply the $k$-th term of a generating function by $k$, differentiate, then multiply by $x$ (and if the final substitution is $x=1$, the extra $x$ may be omitted). This operation recurs whenever expectations or recurrences are handled.

Double-counting check

The same sum can be computed combinatorially: count "choose a $k$-element subset of $n$ elements and mark one special element inside it".

• Choose the special element: $n$ ways.
• Each of the remaining $n-1$ elements independently decides membership: $2^{n-1}$ ways.

The total is $n\,2^{n-1}$.

Both routes agree, but the generating-function route does not require inventing a clever combinatorial story — only differentiating and substituting. That is the advantage the lecture stresses: creativity can be traded for algebra.

What this lecture establishes

• Cayley's theorem: $n$ labelled vertices support $n^{n-2}$ trees.
• The proof counts "rooted labelled trees with ordered edges" two ways: $T_n\cdot n\cdot(n-1)!$ and $n^{n-1}(n-1)!$; equating gives the result.
• A generating function $F(x)=\sum a_i x^i$ encodes a sequence as a formal power series; $x$ is a marker.
• $\sum_n\binom knx^n=(1+x)^k$; a biased coin corresponds to $(q+px)^k$.
• Disjoint union adds generating functions; Cartesian product (sizes adding) multiplies them.
• The sum of two dice is the product of their generating functions; finite coin-change problems give polynomials, unlimited ones give $\frac{1}{(1-x)(1-x^5)(1-x^{10})}$.
• Differentiation multiplies the $k$-th term by $k$, giving $\sum_k k\binom nk=n2^{n-1}$.

Comprehension check

1. Check Cayley's formula at $n=5$, and count the labelled path-type and star-type trees at $n=4$.

Reference answer: The formula gives $5^{5-2}=125$. For $n=4$: the path $1-2-3-4$ has $4!/2=12$ labellings (mirror images are the same tree, hence the division by $2$); the star, with one centre joined to three leaves, has $4$ labellings (choose the centre). Total $12+4=16=4^{4-2}$, matching the formula.

2. In the second count for Cayley's theorem, why are there $n(n-k-1)$ choices at step $k$?

Reference answer: At the start of step $k$ the forest has $n-k$ trees. First choose the attachment point among the $n$ labelled vertices: $n$ ways. Then choose a tree to attach: it cannot be the tree containing the attachment point (that would not add an edge), leaving $n-k-1$ choices. Attaching the chosen tree's root to the attachment point determines the step uniquely. Multiplying from $k=0$ to $n-2$ gives $n^{n-1}(n-1)!$.

3. Why is the "add one edge at a time" construction reversible? Describe the inverse.

Reference answer: Given the final rooted labelled tree with its edge order, find the edge added last and cut it. This splits the tree into two components: the subtree that was attached (its root is the lower endpoint) and the remainder. This uniquely recovers the previous forest and all earlier edges. Iterating returns to $n$ isolated vertices. Since every forward step was determined by "attachment point + chosen tree", the inverse is unique as well, so the map is a bijection.

4. Write the generating function for the sum of a six-sided and an eight-sided die, and explain why the coefficient of $x^{10}$ is $5$.

Reference answer:

$$C(x)=(x+x^2+\cdots+x^6)(x+x^2+\cdots+x^8).$$

The coefficient of $x^{10}$ counts ordered pairs $(a,b)$ with $a+b=10$, $1\le a\le6$, $1\le b\le8$: $(2,8),(3,7),(4,6),(5,5),(6,4)$, five pairs. On expansion, $x^{10}$ receives exactly one contribution from each feasible pair — first factor $x^a$, second factor $x^{10-a}$ — so the coefficient is $5$.

5. Use generating functions to prove $\sum_{k=0}^n k\binom nk=n2^{n-1}$, and explain why differentiation multiplies by $k$.

Reference answer: From $(1+x)^n=\sum_k\binom nk x^k$, differentiate both sides:

$$n(1+x)^{n-1}=\sum_k k\binom nk x^{k-1}.$$

At $x=1$ the right side is $\sum_k k\binom nk$ and the left is $n\cdot2^{n-1}$. Differentiation multiplies by $k$ because the derivative of $x^k$ is $kx^{k-1}$, pulling the exponent down as a coefficient; multiplying by $x$ afterwards restores the power $x^k$, which is unnecessary when substituting $x=1$.

6. With $6$ pennies, $1$ nickel and $2$ dimes, how many ways are there to make $21$ cents? Write the generating function and justify it.

Reference answer:

$$C(x)=(1+x+\cdots+x^6)(1+x^5)(1+x^{10}+x^{20}).$$

The three factors record the choices of $0$–$6$ pennies, $0$–$1$ nickel and $0$–$2$ dimes respectively; the coefficient of $x^n$ after expansion counts the ways to make $n$ cents. For $x^{21}$ the only working combinations are $6+5+10=21$ and $1+20=21$, so the answer is $2$.

Relation to neighbouring lectures

This lecture closes the counting unit along two lines: double counting (Cayley's theorem) and generating functions (mechanising counting). Generating functions are still in embryo — only addition, multiplication and differentiation have been used. The next lecture applies them to recurrences, especially Fibonacci numbers; later, the Catalan formula comes out of a quadratic equation, without needing the elegant reflection bijection.

One sentence to keep: once a counting problem can be written as a combination of structures, it can be written as the algebra of functions — afterwards one computes algebra instead of inventing combinatorics.