Give every edge weight one and delete the row and column for $v_n$ from the out-Laplacian. Expanding the resulting banded determinant along its last available row gives
$$
a_n=a_{n-1}+2a_{n-2},
\qquad a_2=1,\quad a_3=3.
$$
The characteristic roots are $2$ and $-1$, and the initial values give
$$
a_n=\frac{2^n-(-1)^n}{3}.
$$
By the directed <matrix-tree theorem>, this determinant is exactly the number of directed spanning trees rooted towards $v_n$.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 145 / 1 / b / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-145/1/b/solution