2
$\begingroup$

I want to find an explicit formula for the number of spanning trees in the wheel graph. The answer, is

$\tau(W_n) = \left(\frac{3+\sqrt{5}}{2}\right)^n + \left(\frac{3-\sqrt{5}}{2}\right)^n - 2$

My approach is to find a set of recurrence relations, and then solve these to find the explicit formula. A set of recurrence relations for this problem, is

$w_n = a_n+b_{n−1}$

$a_n = d_{n−1}+w_{n−1}$

$b_n = e_n+b_{n−1}$

$d_n = d_{n−1}+e_{n−1}$

$e_n = d_n+e_{n−1} =e_{n−1}+b_{n−1}$

By looking at this, I can see that a solution for these recurrence relations is

$w_n−4w_{n−1}+4w_{n−2}−w_{n−3}=0$

and when I have this recurrence relation, I can solve it to obtain the formula stated above. My problem is, to solve the 5 coupled recurrence relations to obtain

$w_n−4w_{n−1}+4w_{n−2}−w_{n−3}=0$

I have tried to simply isolate and substitute the equations many times, and I have tried working with generating functions, but none of those give me the answer.

  • 0
    Oh, I see. Write all of the equations in a form with $x_n$ on the LHS for one of the sequences $x$ and only terms involving $x_{n-1}$ for some sequences $x$ on the RHS, then write the whole thing as a matrix equation $v_n = A v_{n-1}$ where $A$ is a $5 \times 5$ matrix and $v$ is a vector of all of the sequences. Then find the characteristic polynomial of $A$.2011-05-29

1 Answers 1

1

In the page you link to, there is just such a derivation, by eta oin shrdlu. Quoting:

Your last two recursions give $(d_n−d_{n−1})−(d_{n−1}−d_{n−2})=e_{n−1}−e_{n−2}=d_{n−1}$ and so $0=d_n−3d_{n−1}+d_{n−2}.$ Now $a_n=d_{n−1}+w_{n−1}=a_{n−1}+2d_{n−1}$ and so $0=2(d_{n−1}−3d_{n−2}+d_{n−3})=(a_n−a_{n−1})−3(a_{n−1}−a_{n−2})+(a_{n−2}−a_{n−3}).$ So both $a_n$ and $d_n$ satisfy the recursion $0=x_n−4x_{n−1}+4x_{n−2}−x_{n−3}$, and hence so does their sum $a_n+d_n=w_n$.

  • 0
    I marked your answer as correct, as the comments you made on it was what I was looking for.2011-05-30