login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

REFERENCES

N. Biggs, Algebraic Graph Theory, 2nd ed., Cambridge, 1993, p. 42.

D. M. Cvetkovic, 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

Sequence in context: A037661 A290587 A072615 * A037780 A163012 A164100

Adjacent sequences:  A020868 A020869 A020870 * A020872 A020873 A020874

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Michael Somos, Jun 27 2002

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 17:34 EST 2019. Contains 329106 sequences. (Running on oeis4.)