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 functions.
