|
| |
|
|
A020871
|
|
Number of spanning trees in a Moebius ladder M_n with 2n vertices.
|
|
2
| |
|
|
0, 3, 16, 81, 392, 1815, 8112, 35301, 150544, 632043, 2620880, 10759353, 43804824, 177105279, 711809392, 2846259405, 11330543648, 44929049811, 177540878736, 699402223137, 2747583822760, 10766828545767, 42095796462896
(list; graph; refs; listen; history; 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.
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.
|
|
|
LINKS
| Eric Weisstein's World of Mathematics, Moebius Ladder
Eric Weisstein's World of Mathematics, Spanning Tree
|
|
|
FORMULA
| G.f.: (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).
|
|
|
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
|
|
|
PROG
| (PARI) a(n)=n+n*real((2+quadgen(12))^n) (Somos)
|
|
|
CROSSREFS
| Sequence in context: A037773 A037661 A072615 * A037780 A163012 A164100
Adjacent sequences: A020868 A020869 A020870 * A020872 A020873 A020874
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Michael Somos, Jun 27 2002
|
| |
|
|
