A112676 -id:A112676 - cp's OEIS frontend

A269869 Number of matchings (not necessarily perfect) in the triangle graph of order n.

1, 4, 27, 425, 14278, 1054396, 169858667, 59811185171, 46012925161519, 77344464552678876, 284066030784415134855, 2279568155737623235728996, 39969481180418160836567285156, 1531253921482570179838977438893104, 128176575381689893022287259560629125869

Offset: 1

Andrew Howroyd, Mar 06 2016

nonn

The triangle graph of order n has n rows with i vertices in row i. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has A000217(n) vertices and 3*A000217(n-1) edges altogether.

Samuel Dittmer, Hiram Golze, Grant Molnar, and Caleb Stanford, Puzzle and Proof: A Decade of Problems from the Utah Math Olympiad, CRC Press, 2025, p. 59.

Andrew Howroyd, Table of n, a(n) for n = 1..25
Eric Weisstein's World of Mathematics, Independent Edge Set.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Triangular Grid Graph.

Cf. A000217, A028420, A039907, A112676, A178446.

Row sums of A288852.

A112675 Number of directed Hamiltonian paths on a triangular grid, n vertices on each side.

Original entry on oeis.org

1, 6, 24, 228, 3936, 132624, 8762040, 1156532424, 306700450536, 164818597404924, 180360080611682424, 403600060221250880496, 1853096813379189131728692, 17504763708306471241857275208

Offset: 1

Gareth McCaughan, Dec 30 2005

This sequence counts paths 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. The paths are not assumed to be closed. A path and its reversal are not considered equivalent.

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A112676.

a(8)-a(14) from Andrew Howroyd, Nov 02 2015

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

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

Alois P. Heinz, Nov 29 2010

nonn

The n-triangular grid graph has n+1 rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The Graph has A000217(n+1) vertices and 3*A000217(n) edges altogether.

Alois P. Heinz, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Spanning Tree
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Wikipedia, Kirchhoff's theorem

Cf. A000217, A112676, A266513.

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

Indexing changed by Alois P. Heinz, Jun 14 2017

A174589 Number of directed Hamiltonian cycles in the n X n X n triangular grid.

Original entry on oeis.org

1, 2, 2, 6, 52, 948, 34428, 2742908, 463849560, 164734305828, 123437602332804, 194965649426622884, 647793073112134906932, 4525859704558897642199864, 66463181964865873238784109324, 2050514181580724375252309339543868, 132859453756787302153653327942753178068

Offset: 1

Alois P. Heinz, Nov 29 2010

nonn

The n X n X n triangular grid has n rows with k vertices in row k. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has A000217(n) vertices and 3*A000217(n-1) edges altogether.

			For n = 4 the 4 X 4 X 4 triangular grid has 10 vertices and 18 edges. If vertices are numbered from left to right in each row and ascending with row numbers, the a(4) = 6 Hamiltonian cycles are (1,2,4,7,8,5,9,10,6,3), (1,2,4,7,8,9,10,6,5,3), (1,2,5,4,7,8,9,10,6,3), (1,3,5,6,10,9,8,7,4,2), (1,3,6,10,9,5,8,7,4,2), (1,3,6,10,9,8,7,4,5,2).

Alois P. Heinz, Table of n, a(n) for n = 1..20
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Wikipedia, Triangular grid graph

For n>1, a(n) = 2*A112676(n).

a(11)-a(16) computed from A112676 by Max Alekseyev, Jul 01 2016

a(17) via A112676 from Alois P. Heinz, Jul 31 2023

A293709 Number of Hamiltonian walks on a Sierpinski fractal.

Original entry on oeis.org

1, 2, 10, 92, 1852, 78032, 6846876, 1255156712, 482338029046, 387869817764474, 652822489612455344, 2300645402905295350788, 16976857303773016457918252

Offset: 2

Michel Marcus, Oct 25 2017

András Kaszanyitzky, The generalized Sierpinski Arrowhead Curve, arXiv:1710.08480 [math.CO], 2017.
András Kaszanyitzky, Triangular fractal approximating graphs and their covering paths and cycles, arXiv:1710.09475 [math.CO], 2017.
Jelena Stajic, Suncica Elezovic-Hadzic, Hamiltonian walks on Sierpinski and n-simplex fractals, arXiv:cond-mat/0310777 [cond-mat.stat-mech], 2003-2005.

Cf. A112676.

# 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 A293709(n):
    universe = make_n_triangular_grid_graph(n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n * (n + 1) // 2
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A293709(n) for n in range(2, 10)])  # Seiichi Manyama, Dec 05 2020

a(10)-a(14) from Seiichi Manyama, Dec 05 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

Eric W. Weisstein, Jan 02 2018

Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A112676, A266513.

a(7)-a(18) from Andrew Howroyd, Jan 08 2018

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

A379747 The number of Hamiltonian cycles with rotational symmetry of order 3 on the triangular grid, n vertices on each side.

Original entry on oeis.org

0, 1, 1, 0, 2, 6, 0, 52, 270, 0, 17130, 189154, 0, 51417622

Offset: 1

Nicolay Avilov, Jan 01 2025

If n = 3*k + 1, then the triangular grid has a central node, so for such n there are no Hamiltonian cycles and a(n) = 0.

			a(3) = 1, the only Hamiltonian cycle being the obvious one running around the edge of the triangle;
a(4) = 0 because there are no Hamiltonian cycles;
a(5) = 2 because there are exactly two Hamiltonian cycles.

Nicolay Avilov, Examples of cycles counted by a(1) - a(8).

Cf. A112676.

a(9)-a(10) from Andrey Zabolotskiy, Jan 02 2025
a(11)-a(13) from Talmon Silver, Jan 04 2025
a(14) from Talmon Silver, Jan 06 2025

cp's OEIS Frontend

A269869 Number of matchings (not necessarily perfect) in the triangle graph of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A112675 Number of directed Hamiltonian paths on a triangular grid, n vertices on each side.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A174579 Number of spanning trees in the n-triangular grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A174589 Number of directed Hamiltonian cycles in the n X n X n triangular grid.

Views

Author

Keywords

Comments

Examples

Links

Formula

Extensions

A293709 Number of Hamiltonian walks on a Sierpinski fractal.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A297671 Number of chordless cycles in the n-triangular grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions