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$.
- Calculate $f_4$.
- Write a recurrence for $f_n$.
- Solve for fn using ordinary generating fuctions.