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

Table of contents
- Solution b

Solution

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} + 2 a_{n - 2}, a_{2} = 1, 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.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version