|
%I #47 Nov 30 2020 10:32:14
%S 1,1,1,3,26,474,17214,1371454,231924780,82367152914,61718801166402,
%T 97482824713311442,323896536556067453466,2262929852279448821099932,
%U 33231590982432936619392054662,1025257090790362187626154669771934,66429726878393651076826663971376589034
%N Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side.
%C 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 Andrey Zabolotskiy, <a href="/A112676/b112676.txt">Table of n, a(n) for n = 1..20</a> [from Pettersson's tables]
%H 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TriangularGridGraph.html">Triangular Grid Graph</a>
%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>
%F For n>1, a(n) = A174589(n)/2.
%e a(3) = 1, the only Hamiltonian cycle being the obvious one running around the edge of the triangle.
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o def make_n_triangular_grid_graph(n):
%o s = 1
%o grids = []
%o for i in range(n + 1, 1, -1):
%o for j in range(i - 1):
%o a, b, c = s + j, s + j + 1, s + i + j
%o grids.extend([(a, b), (a, c), (b, c)])
%o s += i
%o return grids
%o def A112676(n):
%o if n == 1: return 1
%o universe = make_n_triangular_grid_graph(n - 1)
%o GraphSet.set_universe(universe)
%o cycles = GraphSet.cycles(is_hamilton=True)
%o return cycles.len()
%o print([A112676(n) for n in range(1, 12)]) # _Seiichi Manyama_, Nov 30 2020
%Y Cf. A003763, A112675, A174589, A266513.
%K nonn
%O 1,4
%A Gareth McCaughan (gareth.mccaughan(AT)pobox.com), Dec 30 2005
%E a(11)-a(16) from _Andrew Howroyd_, Nov 03 2015
%E a(17) from Pettersson by _Andrey Zabolotskiy_, May 23 2017
| 