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.

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

Offset

0,4

Comments

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.

Links

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

Example

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

Maple

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);

Mathematica

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 *)

Crossrefs

Cf. A039907, A071093, A182797.

Sequence in context: A229112 A201959 A216187 * A324126 A272662 A125812

Adjacent sequences: A178443 A178444 A178445 * A178447 A178448 A178449

Keyword

nonn

Author

Alois P. Heinz, Dec 24 2010

Status

approved