login
The OEIS is supported by the many generous donors 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

%I #43 Mar 01 2020 13:23:50

%S 0,3,16,81,392,1815,8112,35301,150544,632043,2620880,10759353,

%T 43804824,177105279,711809392,2846259405,11330543648,44929049811,

%U 177540878736,699402223137,2747583822760,10766828545767,42095796462896,164244726238389,639620518118448

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

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

%D D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs: Theory and application, Academic Press, 1980.

%H Colin Barker, <a href="/A020871/b020871.txt">Table of n, a(n) for n = 0..1000</a>

%H R. K. Guy and F. Harary, <a href="http://dx.doi.org/10.4153/CMB-1967-046-4">On the Moebius ladders</a>, Canad. Math. Bull. 10 1967 493-496.

%H J. P. McSorley, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00086-1">Counting structures in the Moebius ladder</a>, Discrete Math., 184 (1998), 137-164.

%H W.-J. Tzeng and F. Y. Wu, <a href="http://dx.doi.org/10.1016/S0893-9659(00)00071-9">Spanning trees on hypercubic lattices and nonorientable surfaces</a>, Appl. Math. Lett., 13 (2000), 19-25.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MoebiusLadder.html">Moebius Ladder</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>

%H Fuji Zhang and Weigen Yan, <a href="http://dx.doi.org/10.1016/j.jcta.2008.10.004">Enumerating spanning trees of graphs with an involution</a>, Journal of Combinatorial Theory, Series A, Volume 116, Issue 3, April 2009, Pages 650-662.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (10,-35,52,-35,10,-1).

%F G.f.: x*(3 - 14*x + 26*x^2 - 14*x^3 + 3*x^4)/((1-x)*(1 - 4*x + x^2))^2.

%F a(n) = (n/2)*(2 + (2+sqrt(3))^n + (2-sqrt(3))^n).

%F a(n) = n * A121401(n), n > 0. - _R. J. Mathar_, Jul 17 2013

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

%t Table[(n/2) (2 + (2 + Sqrt[3])^n + (2 - Sqrt[3])^n), {n, 0, 20}] // Expand

%t LinearRecurrence[{10, -35, 52, -35, 10, -1}, {0, 3, 16, 81, 392, 1815}, 30] (* _Vincenzo Librandi_, Jul 24 2015 *)

%t Table[n (ChebyshevT[n, 2] + 1), {n, 0, 20}] (* _Eric W. Weisstein_, Mar 31 2017 *)

%o (PARI) a(n)=n+n*real((2+quadgen(12))^n) /* _Michael Somos_, Jun 27 2002 */

%o (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

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Michael Somos_, Jun 27 2002

%E a(23)-a(24) from _Vincenzo Librandi_, Jul 24 2015

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 17:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)