ISI2012-PCB-CS-4

Question

A fan of order $n$ is a graph on the vertices $\{0, 1, \dots, n\}$ with $2n − 1$ edges defined as follows: vertex $0$ is connected by an edge to each of the other $n$ vertices, and vertex $i$ is connected by an edge to vertex $i + 1$, for $1 \leq i \leq n − 1$.

Let $f_n$ denote the number of spanning trees of the fan of order $n$.

1. Calculate $f_4$.
2. Write a recurrence for $f_n$.
3. Solve for fn using ordinary generating functions.