A071093 -id:A071093 - cp's OEIS frontend

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

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

A178446 Number of perfect matchings in the n X n X n triangular grid, reduced by the spire vertex if n mod 4 equals 1 or 2.

Original entry on oeis.org

1, 1, 1, 2, 6, 28, 200, 2196, 37004, 957304, 38016960, 2317631400, 216893681800, 31159166587056, 6871649018572800, 2326335506123418128, 1208982377794384163088, 964503557426086478029152, 1181201363574177619007442944, 2220650888749669503773432361504, 6408743336016148761893699822360672

Offset: 0

Alois P. Heinz, Dec 24 2010

nonn

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.

In order to be able to find matchings the n X n X n triangular grid is reduced by the spire vertex (one vertex in row 1) and the incident edges if n mod 4 is in {1, 2}. The resulting graph has an even number of vertices.

			4 example graphs:                         o
                                         / \
                             o          o---o
                            / \        / \ / \
                   ( )     o---o      o---o---o
                          / \ / \    / \ / \ / \
              ( ) o---o  o---o---o  o---o---o---o
  n:           1    2        3            4
  Vertices:    0    2        6           10
  Edges:       0    1        9           18
  Matchings:   1    1        2            6

Alois P. Heinz, Table of n, a(n) for n = 0..100
James Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, Triangular grid graph

Cf. A039907, A071093, A182797.

with(LinearAlgebra):
a:= proc(n) option remember; local i, j, h0, h1, M, s, t;
      if n<2 then 1
    else s:= `if`(member(irem(n, 4), [1, 2]), 1, 0);
         M:= Matrix((n+1)*n/2 -s, shape=skewsymmetric);
         if s=1 then M[1,2]:=1 fi;
         for j from 1+s to n-1 do
           h0:= j*(j-1)/2 +1-s;
           h1:= h0+j;
           t:= 1;
           for i from 1 to j do
             M[h1, h1+1]:= 1;
             M[h1, h0]:= t;
             h1:= h1+1;
             M[h1, h0]:= t;
             h0:= h0+1;
             t:= -t
           od
         od;
         sqrt(Determinant(M))
      fi
    end:
seq(a(n), n=0..15);

a[n_] := a[n] = Module[{i, j, h0, h1, M, s, t}, If[n<2, 1, s = If[1 <= Mod[n, 4] <= 2, 1, 0]; M = Array[0&, {(n+1)n/2 - s, (n+1)n/2 - s}]; If[s == 1, M[[1, 2]] = 1]; For[j = 1+s, j <= n-1, j++, h0 = j(j-1)/2 + 1 - s; h1 = h0+j; t = 1; For[i = 1, i <= j, i++, M[[h1, h1+1]] = 1; M[[h1, h0]] = t; h1 = h1+1; M[[h1, h0]] = t; h0 = h0+1; t = -t]]; Sqrt[Det[M-Transpose[M]]]]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Sep 23 2022, after Alois P. Heinz *)

cp's OEIS Frontend

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions