The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A112676 Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side. 9
 1, 1, 1, 3, 26, 474, 17214, 1371454, 231924780, 82367152914, 61718801166402, 97482824713311442, 323896536556067453466, 2262929852279448821099932, 33231590982432936619392054662, 1025257090790362187626154669771934, 66429726878393651076826663971376589034 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS This sequence counts cycles in a triangular region of the familiar 2-dimensional lattice in which each point has 6 neighbors (sometimes called either the "triangular" or the "hexagonal" lattice), visiting every vertex of the region exactly once and returning to the starting vertex. Cycles differing only in orientation or starting point are not considered distinct. LINKS Andrey Zabolotskiy, Table of n, a(n) for n = 1..20 [from Pettersson's tables] AndrĂ¡s Kaszanyitzky, Triangular fractal approximating graphs and their covering paths and cycles, arXiv:1710.09475 [math.CO], 2017. See Table 1. Ville Pettersson, Graph Algorithms for Constructing and Enumerating Cycles and Related Structures, Dissertation, Aalto, Finland, 2015. Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014. Eric Weisstein's World of Mathematics, Hamiltonian Cycle Eric Weisstein's World of Mathematics, Triangular Grid Graph FORMULA For n>1, a(n) = A174589(n)/2. EXAMPLE a(3) = 1, the only Hamiltonian cycle being the obvious one running around the edge of the triangle. PROG (Python) # Using graphillion from graphillion import GraphSet def make_n_triangular_grid_graph(n):     s = 1     grids = []     for i in range(n + 1, 1, -1):         for j in range(i - 1):             a, b, c = s + j, s + j + 1, s + i + j             grids.extend([(a, b), (a, c), (b, c)])         s += i     return grids def A112676(n):     if n == 1: return 1     universe = make_n_triangular_grid_graph(n - 1)     GraphSet.set_universe(universe)     cycles = GraphSet.cycles(is_hamilton=True)     return cycles.len() print([A112676(n) for n in range(1, 12)])  # Seiichi Manyama, Nov 30 2020 CROSSREFS Cf. A003763, A112675, A174589, A266513. Sequence in context: A049088 A089041 A059511 * A103112 A064941 A112612 Adjacent sequences:  A112673 A112674 A112675 * A112677 A112678 A112679 KEYWORD nonn AUTHOR Gareth McCaughan (gareth.mccaughan(AT)pobox.com), Dec 30 2005 EXTENSIONS a(11)-a(16) from Andrew Howroyd, Nov 03 2015 a(17) from Pettersson by Andrey Zabolotskiy, May 23 2017 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.

Last modified June 25 08:27 EDT 2021. Contains 345453 sequences. (Running on oeis4.)