74 views

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