A178446 - OEIS

%I #38 Feb 16 2025 08:33:12

%S 1,1,1,2,6,28,200,2196,37004,957304,38016960,2317631400,216893681800,

%T 31159166587056,6871649018572800,2326335506123418128,

%U 1208982377794384163088,964503557426086478029152,1181201363574177619007442944,2220650888749669503773432361504,6408743336016148761893699822360672

%N 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.

%C 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.

%C 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.

%H Alois P. Heinz, <a href="/A178446/b178446.txt">Table of n, a(n) for n = 0..100</a>

%H James Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), <a href="http://www.msri.org/publications/books/Book38/contents.html">New Perspectives in Algebraic Combinatorics</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectMatching.html">Perfect Matching</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_graph#Other_kinds">Triangular grid graph</a>

%e 4 example graphs:                         o

%e                                          / \

%e                              o          o---o

%e                             / \        / \ / \

%e                    ( )     o---o      o---o---o

%e                           / \ / \    / \ / \ / \

%e               ( ) o---o  o---o---o  o---o---o---o

%e   n:           1    2        3            4

%e   Vertices:    0    2        6           10

%e   Edges:       0    1        9           18

%e   Matchings:   1    1        2            6

%p with(LinearAlgebra):

%p a:= proc(n) option remember; local i, j, h0, h1, M, s, t;

%p       if n<2 then 1

%p     else s:= `if`(member(irem(n, 4), [1, 2]), 1, 0);

%p          M:= Matrix((n+1)*n/2 -s, shape=skewsymmetric);

%p          if s=1 then M[1,2]:=1 fi;

%p          for j from 1+s to n-1 do

%p            h0:= j*(j-1)/2 +1-s;

%p            h1:= h0+j;

%p            t:= 1;

%p            for i from 1 to j do

%p              M[h1, h1+1]:= 1;

%p              M[h1, h0]:= t;

%p              h1:= h1+1;

%p              M[h1, h0]:= t;

%p              h0:= h0+1;

%p              t:= -t

%p            od

%p          od;

%p          sqrt(Determinant(M))

%p       fi

%p     end:

%p seq(a(n), n=0..15);

%t 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]]]]];

%t Table[a[n], {n, 0, 15}] (* _Jean-François Alcover_, Sep 23 2022, after _Alois P. Heinz_ *)

%Y Cf. A039907, A071093, A182797.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Dec 24 2010