A020871 Number of spanning trees in a Moebius ladder M_n with 2n vertices.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Examples

			If n=2 then Moebius ladder is complete graph with 4^2 = 16 spanning trees.
		

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

Programs

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 *)

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

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

Extensions

More terms from Michael Somos, Jun 27 2002

a(23)-a(24) from Vincenzo Librandi, Jul 24 2015