A112675 -id:A112675 - cp's OEIS frontend

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

1, 1, 1, 3, 26, 474, 17214, 1371454, 231924780, 82367152914, 61718801166402, 97482824713311442, 323896536556067453466, 2262929852279448821099932, 33231590982432936619392054662, 1025257090790362187626154669771934, 66429726878393651076826663971376589034

Offset: 1

Gareth McCaughan, Dec 30 2005

nonn

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.

			a(3) = 1, the only Hamiltonian cycle being the obvious one running around the edge of the triangle.

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
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A112675, A174589, A266513.

# 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

For n>1, a(n) = A174589(n)/2.

a(11)-a(16) from Andrew Howroyd, Nov 03 2015

a(17) from Pettersson by Andrey Zabolotskiy, May 23 2017

A266513 Number of undirected cycles in a triangular grid graph, n vertices on each side.

Original entry on oeis.org

0, 1, 11, 110, 2402, 128967, 16767653, 5436906668, 4406952731948, 8819634719356421, 43329348004927734247, 522235268182347360718818, 15436131339319739257518081878, 1117847654274955574635482276231683, 198163274851163063009517020867737770265

Offset: 1

Andrew Howroyd, Apr 06 2016

nonn

			Of the 11 cycles in the triangular grid with 3 vertices per side, 4 have length 3, 3 have length 4, 3 have length 5 and 1 has length 6.
4 basic cycle shapes on a(3):
                                      o
                                     / \
        o       o---o    o---o      o   o
       / \     /   /    /     \    /     \
      o---o   o---o    o---o---o  o---o---o

Ed Wynn, Table of n, a(n) for n = 1..17
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A112676, A112675, A140517, A269869.

# 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 A266513(n):
    if n == 1: return 0
    universe = make_n_triangular_grid_graph(n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A266513(n) for n in range(1, 12)])  # Seiichi Manyama, Nov 30 2020

A288148 Number of (undirected) paths in the n-triangular grid graph.

Original entry on oeis.org

0, 6, 108, 2598, 123750, 12994248, 3114709914, 1730766715308, 2248937669398650, 6877862090075063484, 49790967547432817528562, 857275977287938332061154856, 35233501393224883314185777947590

Offset: 0

Eric W. Weisstein, Jun 05 2017

Paths of length zero are not counted here.

			a(1) = 6:
:    o    :    o    :    o    :    o    :    o    :    o
:         :   /     :     \   :   / \   :     \   :   /
:  o---o  :  o   o  :  o   o  :  o   o  :  o---o  :  o---o  .

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A020874, A266513, A112675, A112676.

a(7)-a(12) from Andrew Howroyd, Jun 07 2017

A112683 For each positive integer n, consider the ternary sequence given initially by x(i) = 0 if 1 <= i < n, x(n) = 1; and thereafter determined by the quadratic recurrence x(i) = x(i-1) + x(i-n)^2 mod 3. Define a(n) to be the smallest positive integer N for which x(N+i) = x(i) for all sufficiently large i.

Original entry on oeis.org

1, 4, 4, 9, 19, 4, 4, 22, 36, 4, 4, 45, 64, 4, 4, 102, 182, 213, 4, 188, 272, 4, 412, 225, 202, 4, 4, 1444, 512, 4, 4, 840, 1237, 4, 1138, 362, 1263, 4, 4, 1536, 672, 1786, 4, 701, 741, 4, 4, 2098, 3921, 5400, 178, 1183, 2348, 4, 7698, 6042, 5091, 4, 4

Offset: 1

N. J. A. Sloane, Dec 31 2005

nonn

			For example, if n=4, then N=9, since the first 60 terms of x are:
0 0 0 1 1 1 1 2 0 1
2 0 0 1 2 2 2 0 1 2
0 0 1 2 2 2 0 1 2 0
0 1 2 2 2 0 1 2 0 0
1 2 2 2 0 1 2 0 0 1
2 2 2 0 1 2 0 0 1 2

Terms computed by Bob Harder.

Steven R. Finch, Periodicity in Sequences Mod 3 [Broken link]
Steven R. Finch, Periodicity in Sequences Mod 3 [From the Wayback machine]

Cf. A112684, A112675.

period[lst_List] := Catch[lg = If[Length[lst] <= 5, 2, 40]; lst1 = lst[[1 ;; lg]]; km = Length[lst] - lg; Do[ If[lst1 == lst[[k ;; k+lg-1]], Throw[k-1]]; If[k == km, Throw[0]], {k, 2, km}]]; a[n_] := (ClearAll[x]; x[i_ /; 1 <= i < n] = 0; x[n] = 1; x[i_] := x[i] = Mod[x[i-1] + x[i-n]^2, 3]; xx = Table[x[i], {i, 1, 20000}]; period[xx // Reverse]); Table[a[n], {n, 1, 59}] (* Jean-François Alcover, Nov 30 2012 *)

A343307 a(n) is the number of self-avoiding paths connecting consecutive corners of an n X n triangular grid.

Original entry on oeis.org

1, 2, 10, 108, 2726, 168724, 25637074, 9454069104, 8461610420420, 18438745892175008, 97929194419509169380, 1267379450261470833222676, 39964658780097197018058705552, 3071011528804416058638501563820092, 575150143830631835000028468717331605240

Offset: 1

Rémy Sigrist, Apr 11 2021

We use unit moves parallel to the triangle edges.

			For n = 3:
- we have the following paths:
.                         .
.
.                       .   .
.
.                     o---o---o
.
.
.          .              .              .
.
.        o   .          o   o          .   o
.       / \            / \ / \            / \
.      o   o---o      o   o   o      o---o   o
.
.
.          .              .              .
.
.        o---o          o---o          o---o
.       /   /          /     \          \   \
.      o   o---o      o   .   o      o---o   o
.
.
.          o              o              o
.         / \            / \            / \
.        o   o          o   o          o   o
.       /   /          /     \          \   \
.      o   o---o      o   .   o      o---o   o
- so a(3) = 10.

Rémy Sigrist, Python program for A343307
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Index entries for sequences related to walks

Cf. A007764, A112675, A288148, A308144, A343310.

Python
```
# See Links section.
```

a(14)-a(15) from Andrew Howroyd, Feb 04 2022

A308144 Number of (undirected) Hamiltonian paths on the triangular grid with n vertices on each side.

Original entry on oeis.org

1, 3, 12, 114, 1968, 66312, 4381020, 578266212, 153350225268, 82409298702462, 90180040305841212, 201800030110625440248, 926548406689594565864346, 8752381854153235620928637604

Offset: 1

Eric W. Weisstein, May 14 2019

nonn

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A112675, A112676, A266513, A288148.

a(n) = A112675(n)/2 for n > 1.

a(1) corrected by Andrew Howroyd, Jan 19 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A266513 Number of undirected cycles in a triangular grid graph, n vertices on each side.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

A288148 Number of (undirected) paths in the n-triangular grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A343307 a(n) is the number of self-avoiding paths connecting consecutive corners of an n X n triangular grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A308144 Number of (undirected) Hamiltonian paths on the triangular grid with n vertices on each side.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions