cp's OEIS Frontend

A112676 Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side.

%I A112676 #50 Feb 16 2025 08:32:59
%S A112676 1,1,1,3,26,474,17214,1371454,231924780,82367152914,61718801166402,
%T A112676 97482824713311442,323896536556067453466,2262929852279448821099932,
%U A112676 33231590982432936619392054662,1025257090790362187626154669771934,66429726878393651076826663971376589034
%N A112676 Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side.
%C A112676 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.
%H A112676 Andrey Zabolotskiy, <a href="/A112676/b112676.txt">Table of n, a(n) for n = 1..20</a> [from Pettersson's tables]
%H A112676 András Kaszanyitzky, <a href="https://arxiv.org/abs/1710.09475">Triangular fractal approximating graphs and their covering paths and cycles</a>, arXiv:1710.09475 [math.CO], 2017. See Table 1.
%H A112676 Ville Pettersson, <a href="https://aaltodoc.aalto.fi/handle/123456789/17688">Graph Algorithms for Constructing and Enumerating Cycles and Related Structures</a>, Dissertation, Aalto, Finland, 2015.
%H A112676 Ville H. Pettersson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
%H A112676 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H A112676 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TriangularGridGraph.html">Triangular Grid Graph</a>
%H A112676 <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>
%F A112676 For n>1, a(n) = A174589(n)/2.
%e A112676 a(3) = 1, the only Hamiltonian cycle being the obvious one running around the edge of the triangle.
%o A112676 (Python)
%o A112676 # Using graphillion
%o A112676 from graphillion import GraphSet
%o A112676 def make_n_triangular_grid_graph(n):
%o A112676     s = 1
%o A112676     grids = []
%o A112676     for i in range(n + 1, 1, -1):
%o A112676         for j in range(i - 1):
%o A112676             a, b, c = s + j, s + j + 1, s + i + j
%o A112676             grids.extend([(a, b), (a, c), (b, c)])
%o A112676         s += i
%o A112676     return grids
%o A112676 def A112676(n):
%o A112676     if n == 1: return 1
%o A112676     universe = make_n_triangular_grid_graph(n - 1)
%o A112676     GraphSet.set_universe(universe)
%o A112676     cycles = GraphSet.cycles(is_hamilton=True)
%o A112676     return cycles.len()
%o A112676 print([A112676(n) for n in range(1, 12)])  # _Seiichi Manyama_, Nov 30 2020
%Y A112676 Cf. A003763, A112675, A174589, A266513.
%K A112676 nonn
%O A112676 1,4
%A A112676 _Gareth McCaughan_, Dec 30 2005
%E A112676 a(11)-a(16) from _Andrew Howroyd_, Nov 03 2015
%E A112676 a(17) from Pettersson by _Andrey Zabolotskiy_, May 23 2017