A269869 -id:A269869 - cp's OEIS frontend

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

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

A288852 Number T(n,k) of matchings of size k in the n X n X n triangular grid; triangle T(n,k), n>=0, 0<=k<=floor(n*(n+1)/4), read by rows.

Original entry on oeis.org

1, 1, 1, 3, 1, 9, 15, 2, 1, 18, 99, 193, 108, 6, 1, 30, 333, 1734, 4416, 5193, 2331, 240, 1, 45, 825, 8027, 45261, 151707, 298357, 327237, 180234, 40464, 2238, 1, 63, 1710, 26335, 255123, 1629474, 6995539, 20211423, 38743020, 47768064, 35913207, 15071019

Offset: 0

Alois P. Heinz, Jun 18 2017

The n X n X n triangular grid 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.

			Triangle T(n,k) begins:
  1;
  1;
  1,  3;
  1,  9,  15,    2;
  1, 18,  99,  193,   108,      6;
  1, 30, 333, 1734,  4416,   5193,   2331,    240;
  1, 45, 825, 8027, 45261, 151707, 298357, 327237, 180234, 40464, 2238;

Alois P. Heinz, Rows n = 0..17, flattened
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Wikipedia, Matching (graph theory)
Wikipedia, Triangular grid graph

Columns k=0-1 give: A000012, A045943(n-1) for n>0.
Row sums give A269869.
Last elements of rows give A271610.
Cf. A000217, A011848, A271612, A271614, A271616.

b:= proc(l) option remember;  local n, k; n:= nops(l);
      if n=0 then 1
    elif min(l)>0 then b(subsop(-1=NULL, map(h-> h-1, l)))
    else for k to n while l[k]>0 do od; b(subsop(k=1, l))+
         expand(x*(`if`(k1 and l[k-1]=1, b(subsop(k=1, k-1=2, l)), 0)))
      fi
    end:
T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(b([0$n])):
seq(T(n), n=0..10);

b[l_] := b[l] = Module[{n = Length[l], k}, Which[n == 0, 1, Min[l] > 0, b[ReplacePart[l - 1, -1 -> Nothing]], True, For[k = 1, k <= n && l[[k]] > 0, k++]; b[ReplacePart[l, k -> 1]] + x*Expand[If[k < n, b[ReplacePart[l, k -> 2]], 0] + If[k < n && l[[k + 1]] == 0, b[ReplacePart[l, {k -> 1, k + 1 -> 1}]], 0] + If[k > 1 && l[[k - 1]] == 1, b[ReplacePart[l, {k -> 1, k - 1 -> 2}]], 0]]]];
T[n_] := Table[Coefficient[#, x, i], {i, 0, Exponent[#, x]}]&[b[Table[0, n] ]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, May 24 2018, translated from Maple *)

T(n,floor(n*(n+1)/4)) = A271610(n).
Sum_{i=0..1} T(n,floor(n*(n+1)/4)-i) = A271612(n).
Sum_{i=0..2} T(n,floor(n*(n+1)/4)-i) = A271614(n).
Sum_{i=0..3} T(n,floor(n*(n+1)/4)-i) = A271616(n).

A039907 Number of perfect matchings in triangle graph with n nodes per side.

Original entry on oeis.org

1, 0, 0, 2, 6, 0, 0, 2196, 37004, 0, 0, 2317631400, 216893681800, 0, 0, 2326335506123418128, 1208982377794384163088, 0, 0, 2220650888749669503773432361504, 6408743336016148761893699822360672, 0, 0, 2015895925780490675949731718780144934779733312

Offset: 0

N. J. A. Sloane

nonn

J. Propp, Enumeration of matchings: problems and progress, pp. 255-291 in L. J. Billera et al., eds, New Perspectives in Algebraic Combinatorics, Cambridge, 1999 (see Problem 17).

Alois P. Heinz, Table of n, a(n) for n = 0..60
J. Propp, Twenty open problems in enumeration of matchings, arXiv:math/9801061 [math.CO], 1998-1999.
J. Propp, Updated article
J. Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics

Cf. A071093, A269869, A178446.

with(LinearAlgebra): a:= proc(n) option remember; local l, ll, i, j, h0, h1, M; if n=0 then return 1 fi; if n<0 or member(irem(n, 4), [1, 2]) then return 0 fi; l:= []; for j from 1 to n-1 do h0:= j*(j-1)/2+1; h1:= j*(j+1)/2+1; for i from 1 to j do l:= [l[], [h1, h1+1]]; if irem(i, 2)=1 then l:= [l[], [h1, h0]]; h1:= h1+1; l:=[l[], [h1, h0]]; h0:=h0+1 else l:= [l[], [h0, h1]]; h1:= h1+1; l:=[l[], [h0, h1]]; h0:=h0+1 fi od od; M:= Matrix((n+1)*n/2); for ll in l do M[ll[1], ll[2]]:= 1; M[ll[2], ll[1]]:= -1 od: isqrt(Determinant(M)) end: seq(a(n), n=0..20); # Alois P. Heinz, May 08 2010

a[n_] := a[n] = Module[{l, ll, i, j, h0, h1, M}, If[n == 0 , Return[1]]; If[n < 0 || MemberQ[{1, 2}, Mod[n, 4]], Return[0]]; l = {}; For[j = 1, j <= n-1, j++, h0 = j*(j-1)/2+1; h1 = j*(j+1)/2+1; For[i = 1, i <= j, i++, l = Join[l, {h1, h1+1}]; If[Mod [i, 2] == 1, l = Join[l, {h1, h0}]; h1 = h1+1; l = Join[l, {h1, h0}]; h0 = h0+1, l = Join[l, {h0, h1}]; h1 = h1+1; l = Join[l, {h0, h1}]; h0 = h0+1]]]; M[, ] = 0; Do[M[ll[[1]], ll[[2]]] = 1; M[ll[[2]], ll[[1]]] = -1, {ll, Partition[l, 2]}]; Sqrt[Det[Array[M, {n*(n+1)/2, n*(n+1)/2}]]]]; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Apr 17 2014, after Alois P. Heinz *)

a(n) = A178446(n) if A000217(n) is even, a(n) = 0 otherwise. - Andrew Howroyd, Mar 06 2016

a(17)-a(20) from Alois P. Heinz, May 08 2010

a(21)-a(23) from Alois P. Heinz, Jan 12 2014

A287230 Number of matchings in the n-triangular honeycomb acute knight graph.

Original entry on oeis.org

1, 1, 8, 64, 1331, 64000, 6400075, 1404928000, 677298787768, 712186032947200, 1635557819719974912, 8209592592625295700893, 90036881979773511965369428, 2157454308508779392217680572439, 112955975573487831948842897960075264, 12921763288870998051759383983484279183072, 3229803978189426975602886931834056243712000000

Offset: 1

Eric W. Weisstein, May 22 2017

Stan Wagon, Graph Theory Problems from Hexagonal and Traditional Chess, The College Mathematics Journal, Vol. 45, No. 4, September 2014, pp. 278-287.
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching

Cf. A289143, A287204, A289904, A287228, A269869.

a(11) from Eric W. Weisstein, Jun 25 2017
a(12)-a(14) from Andrew Howroyd, Jul 17 2017
a(15)-a(17) from Eric W. Weisstein, Sep 02 2025

A071093 Number of perfect matchings in triangle graph with n nodes per side as n runs through numbers congruent to 0 or 3 mod 4.

Original entry on oeis.org

1, 2, 6, 2196, 37004, 2317631400, 216893681800, 2326335506123418128, 1208982377794384163088, 2220650888749669503773432361504, 6408743336016148761893699822360672, 2015895925780490675949731718780144934779733312, 32307672245407537492814937397129549558917000333504

Offset: 0

N. J. A. Sloane

nonn

James Propp, Enumeration of matchings: problems and progress, pp. 255-291 in L. J. Billera et al., eds, New Perspectives in Algebraic Combinatorics, Cambridge, 1999 (see Problem 17).

Alois P. Heinz, Table of n, a(n) for n = 0..44
James Propp, Twenty open problems in enumeration of matchings, arXiv:math/9801061 [math.CO], 1998-1999.
James Propp, Updated article
James Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics
James Propp, Some 2-Adic Conjectures Concerning Polyomino Tilings of Aztec Diamonds, Integers (2023) Vol. 23, Art. A30.

Cf. A039907, A178446, A269869.

with(LinearAlgebra): b:= proc(n) option remember; local l, ll, i, j, h0, h1, M; if n=0 then return 1 fi; if n<0 or member(irem(n, 4), [1, 2]) then return 0 fi; l:= []; for j from 1 to n-1 do h0:= j*(j-1)/2+1; h1:= j*(j+1)/2+1; for i from 1 to j do l:= [l[], [h1, h1+1]]; if irem(i, 2)=1 then l:= [l[], [h1, h0]]; h1:= h1+1; l:=[l[], [h1, h0]]; h0:=h0+1 else l:= [l[], [h0, h1]]; h1:= h1+1; l:=[l[], [h0, h1]]; h0:=h0+1 fi od od; M:= Matrix((n+1)*n/2); for ll in l do M[ll[1], ll[2]]:= 1; M[ll[2], ll[1]]:= -1 od: isqrt(Determinant(M)); end: a:= n-> b(2*n +irem(n, 2)): seq(a(n), n=0..10); # Alois P. Heinz, May 08 2010

b[n_] := b[n] = Module[{l, ll, i, j, h0, h1, M}, If[n == 0 , Return[1]]; If[n<0 || MatchQ[Mod[n, 4], 1|2] , Return[0]]; l = {}; For[j = 1, j <= n-1, j++, h0 = j*(j-1)/2+1; h1 = j*(j+1)/2+1; For[i = 1, i <= j, i++, AppendTo[l, {h1, h1+1}]; If[Mod[i, 2] == 1, AppendTo[l, {h1, h0}]; h1++; AppendTo[l, {h1, h0}]; h0++ , AppendTo[l, {h0, h1}]; h1++; AppendTo[l, {h0, h1}]; h0++ ]]]; M[, ] = 0; (M[#[[1]], #[[2]]] = 1; M[#[[2]], #[[1]]] = -1)& /@ l; Sqrt[Det[Array[M, {n*(n+1)/2, n*(n+1)/2}]]]]; a[n_] := b[2*n + Mod[n, 2]]; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 29 2014, after Alois P. Heinz *)

a(2n) = A039907(4n) = A178446(4n), a(2n+1) = A039907(4n+3) = A178446(4n+3). - Andrew Howroyd, Mar 06 2016

a(9)-a(10) from Alois P. Heinz, May 08 2010

a(11)-a(12) from Alois P. Heinz, Jan 12 2014

A297061 Number of edge covers in the n X n triangular grid graph.

Original entry on oeis.org

0, 4, 198, 84682, 281721996, 7392711987818, 1528658402287559670, 2490983667363798650708788, 31987702603596066902310936860946, 3237032742135065575663156511653859260726, 2581445727611992619431296420645395411748335733438

Offset: 0

Eric W. Weisstein, Dec 24 2017

nonn

Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Triangular Graph

Cf. A269869.

a(5)-a(10) from Andrew Howroyd, Dec 27 2017

A297485 Number of maximal matchings in the n-triangular grid graph.

Original entry on oeis.org

1, 3, 11, 86, 1318, 36149, 1905037, 185934481, 34000082535, 11612664144891, 7414832091145015

Offset: 0

Eric W. Weisstein, Dec 30 2017

Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A269869, A297061.

a(6)-a(10) from Andrew Howroyd, Dec 30 2017

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

A288852 Number T(n,k) of matchings of size k in the n X n X n triangular grid; triangle T(n,k), n>=0, 0<=k<=floor(n*(n+1)/4), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A039907 Number of perfect matchings in triangle graph with n nodes per side.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A287230 Number of matchings in the n-triangular honeycomb acute knight graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A071093 Number of perfect matchings in triangle graph with n nodes per side as n runs through numbers congruent to 0 or 3 mod 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A297061 Number of edge covers in the n X n triangular grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A297485 Number of maximal matchings in the n-triangular grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions