A112676
Number of (undirected) Hamiltonian cycles on a triangular grid, n vertices on each side.
Original entry on oeis.org
1, 1, 1, 3, 26, 474, 17214, 1371454, 231924780, 82367152914, 61718801166402, 97482824713311442, 323896536556067453466, 2262929852279448821099932, 33231590982432936619392054662, 1025257090790362187626154669771934, 66429726878393651076826663971376589034
Offset: 1
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
-
# 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
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
a(1) = 6:
: o : o : o : o : o : o
: : / : \ : / \ : \ : /
: o---o : o o : o o : o o : o---o : o---o .
A174579
Number of spanning trees in the n-triangular grid graph.
Original entry on oeis.org
1, 3, 54, 5292, 2723220, 7242690816, 98719805835000, 6861326937782575104, 2423821818614367091537296, 4342290918217084382837760000000, 39389085041906366256386454778172877408, 1807026244113880332171608161401397806958116864
Offset: 0
-
with(LinearAlgebra):
tr:= n-> n*(n+1)/2:
a:= proc(n) local h, i, M;
if n=0 then 1 else
M:= Matrix(tr(n+1), shape=symmetric);
for h in [seq(seq([[i, i+j], [i, i+j+1], [i+j, i+j+1]][],
i=tr(j-1)+1 .. tr(j-1)+j), j=1..n)]
do M[h[]]:= -1 od;
for i to tr(n+1) do M[i, i]:= -add(M[i, j], j=1..tr(n+1)) od;
Determinant(DeleteColumn(DeleteRow(M, 1), 1))
fi
end:
seq(a(n), n=0..12);
-
tr[n_] := n*(n + 1)/2;
a[0] = 1; a[n_] := Module[{T, M}, T = Table[Table[{{i, i+j}, {i, i+j+1}, {i + j, i+j+1}}, {i, tr[j-1]+1, tr[j-1] + j}], {j, 1, n}] // Flatten[#, 2]&; M = Array[0&, {tr[n+1], tr[n+1]}]; Do[{i, j} = h; M[[i, j]] = -1, {h, T}]; M = M + Transpose[M]; For[i = 1, i <= tr[n+1], i++, M[[i, i]] = -Sum[M[[i, j]], {j, 1, tr[n+1]}]]; Det[Rest /@ Rest[M]]];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Jun 02 2018, from Maple *)
-
# 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 A174579(n):
if n == 0: return 1
universe = make_n_triangular_grid_graph(n)
GraphSet.set_universe(universe)
spanning_trees = GraphSet.trees(is_spanning=True)
return spanning_trees.len()
print([A174579(n) for n in range(8)]) # Seiichi Manyama, Nov 30 2020
A297671
Number of chordless cycles in the n-triangular grid graph.
Original entry on oeis.org
0, 0, 0, 1, 7, 41, 260, 1930, 17463, 200008, 3026192, 62212319, 1742874972, 65794989216, 3314857545154, 222226981778153, 19858056830333695, 2371636836808937036, 378993965527624639893
Offset: 0
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
Showing 1-5 of 5 results.
Comments