Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
The generating function approach works. The characteristic polynomial $x^3 - 4x^2 + 4x - 1$ has root $x = 1$ by inspection. Factoring it out gives $(x - 1)(x^2 - 3x + 1)$ and the roots of the latter are precisely the two quadratic irrationals which appear in the closed formula. The rest is computation. –  Qiaochu Yuan May 29 '11 at 17:39
    
Yes, but the part I am interested in, is finding the recurrence relation to solve, not solving it. –  utdiscant May 29 '11 at 18:34
    
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$. –  Qiaochu Yuan May 29 '11 at 19:30
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
Yes. But I do not follow from "Now a_n = d_{n-1}...". –  utdiscant May 29 '11 at 19:46
1  
@utdiscant: Your last equation implies that $d_n = b_{n-1}$. Another possible pitfall is deriving $0 = d_n - 4d_{n-1} + 4d_{n-2} - d_{n-3}$ from $0 = d_n - 3d_{n-1} + d_{n-2}$: just subtract $0 = d_{n-1} - 3d_{n-2} + d_{n-3}$. –  Yuval Filmus May 29 '11 at 21:06
    
Thanks, that cleared some of the puzzle for me, but I can't make sense of $a_n=d_{n-1}+w_{n-1} = a_{n-1}+2d_{n-1}$. –  utdiscant May 29 '11 at 21:51
1  
@utdiscant: Did you try $w_{n-1} = a_{n-1} + b_{n-2} = a_{n-1} + d_{n-1}$? –  Yuval Filmus May 29 '11 at 23:52
    
I marked your answer as correct, as the comments you made on it was what I was looking for. –  utdiscant May 30 '11 at 9:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.