login
A020871
Number of spanning trees in a Moebius ladder M_n with 2n vertices.
3
0, 3, 16, 81, 392, 1815, 8112, 35301, 150544, 632043, 2620880, 10759353, 43804824, 177105279, 711809392, 2846259405, 11330543648, 44929049811, 177540878736, 699402223137, 2747583822760, 10766828545767, 42095796462896, 164244726238389, 639620518118448
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
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.
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
Sequence in context: A372324 A290587 A072615 * A037780 A163012 A164100
KEYWORD
nonn,easy
EXTENSIONS
More terms from Michael Somos, Jun 27 2002
a(23)-a(24) from Vincenzo Librandi, Jul 24 2015
STATUS
approved