OFFSET
0,2
REFERENCES
N. Biggs, Algebraic Graph Theory, 2nd ed., Cambridge, 1993, p. 42.
D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs: Theory and application, Academic Press, 1980.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
R. K. Guy and F. Harary, On the Moebius ladders, Canad. Math. Bull. 10 1967 493-496.
J. P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164.
W.-J. Tzeng and F. Y. Wu, Spanning trees on hypercubic lattices and nonorientable surfaces, Appl. Math. Lett., 13 (2000), 19-25.
Eric Weisstein's World of Mathematics, Moebius Ladder
Eric Weisstein's World of Mathematics, Spanning Tree
Fuji Zhang and Weigen Yan, Enumerating spanning trees of graphs with an involution, Journal of Combinatorial Theory, Series A, Volume 116, Issue 3, April 2009, Pages 650-662.
Index entries for linear recurrences with constant coefficients, signature (10,-35,52,-35,10,-1).
FORMULA
G.f.: x*(3 - 14*x + 26*x^2 - 14*x^3 + 3*x^4)/((1-x)*(1 - 4*x + x^2))^2.
a(n) = (n/2)*(2 + (2+sqrt(3))^n + (2-sqrt(3))^n).
a(n) = n * A121401(n), n > 0. - R. J. Mathar, Jul 17 2013
EXAMPLE
If n=2 then Moebius ladder is complete graph with 4^2 = 16 spanning trees.
MATHEMATICA
Table[(n/2) (2 + (2 + Sqrt[3])^n + (2 - Sqrt[3])^n), {n, 0, 20}] // Expand
LinearRecurrence[{10, -35, 52, -35, 10, -1}, {0, 3, 16, 81, 392, 1815}, 30] (* Vincenzo Librandi, Jul 24 2015 *)
Table[n (ChebyshevT[n, 2] + 1), {n, 0, 20}] (* Eric W. Weisstein, Mar 31 2017 *)
PROG
(PARI) a(n)=n+n*real((2+quadgen(12))^n) /* Michael Somos, Jun 27 2002 */
(PARI) concat(0, Vec(x*(3-14*x+26*x^2-14*x^3+3*x^4)/((1-x)*(1-4*x+x^2))^2 + O(x^50))) \\ Colin Barker, Jul 24 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
More terms from Michael Somos, Jun 27 2002
a(23)-a(24) from Vincenzo Librandi, Jul 24 2015
STATUS
approved