

A028475


Total number of Hamiltonian cycles avoiding the rootedge in rooted cubic bipartite planar maps with 2n nodes.


0



1, 4, 20, 114, 712, 4760, 33532, 246146, 1867556, 14557064, 116038672, 942597638, 7781117632, 65131605840, 551825148660, 4725380142050, 40848069782932, 356094155836640, 3127831256055624, 27662285924478844
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

An algorithm for calculating these numbers is known. 2*a(n) can be interpreted as the number of pairs of nonintersecting arch configurations (over and under a straight line) connecting 2n points in the line, where all points are marked + and  alternately, every point belongs to a unique arch and the ends of every arch have different signs.


LINKS

Table of n, a(n) for n=1..20.
E. Guitter, C. Kristjansen and J. L. Nielsen, Hamiltonian cycles on random Eulerian triangulations, Nucl.Phys. B546 (1999), No.3, 731750.
James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2


EXAMPLE

n=2. There are 3 rooted cubic bipartite planar maps with 4 nodes: a quadrangular with two nonadjacent edges doubled (parallel), where one vertex and any of the edges incident to it are taken as the root. No Hamiltonian cycle can avoid the sole edge incident to the rootvertex. For the other two rootings, there are 4 rootedge avoiding Hamiltonian cycles. So a(2)=4.


CROSSREFS

Cf. A000356, A003122, A007084.
Sequence in context: A108447 A287512 A211248 * A128327 A320615 A316298
Adjacent sequences: A028472 A028473 A028474 * A028476 A028477 A028478


KEYWORD

nonn


AUTHOR

Valery A. Liskovets, Apr 29 2002


STATUS

approved



