|
Search: id:A020871
|
|
|
| A020871 |
|
Number of spanning trees in a Moebius ladder M_n with 2n vertices. |
|
+0
3
|
|
| 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; listen)
|
|
|
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.
|
|
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.
|
|
PROGRAM
|
(PARI) a(n)=n+n*real((2+quadgen(12))^n) (Somos)
|
|
CROSSREFS
|
Sequence in context: A037773 A037661 A072615 this_sequence A037780 A041707 A037584
Adjacent sequences: A020868 A020869 A020870 this_sequence A020872 A020873 A020874
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
More terms from Michael Somos, Jun 27 2002
|
|
|
Search completed in 0.002 seconds
|
