cp's OEIS Frontend

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.

%I A178446 #38 Feb 16 2025 08:33:12
%S A178446 1,1,1,2,6,28,200,2196,37004,957304,38016960,2317631400,216893681800,
%T A178446 31159166587056,6871649018572800,2326335506123418128,
%U A178446 1208982377794384163088,964503557426086478029152,1181201363574177619007442944,2220650888749669503773432361504,6408743336016148761893699822360672
%N 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.
%C A178446 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 A178446 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 A178446 Alois P. Heinz, <a href="/A178446/b178446.txt">Table of n, a(n) for n = 0..100</a>
%H A178446 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 A178446 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectMatching.html">Perfect Matching</a>
%H A178446 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_graph#Other_kinds">Triangular grid graph</a>
%e A178446 4 example graphs:                         o
%e A178446                                          / \
%e A178446                              o          o---o
%e A178446                             / \        / \ / \
%e A178446                    ( )     o---o      o---o---o
%e A178446                           / \ / \    / \ / \ / \
%e A178446               ( ) o---o  o---o---o  o---o---o---o
%e A178446   n:           1    2        3            4
%e A178446   Vertices:    0    2        6           10
%e A178446   Edges:       0    1        9           18
%e A178446   Matchings:   1    1        2            6
%p A178446 with(LinearAlgebra):
%p A178446 a:= proc(n) option remember; local i, j, h0, h1, M, s, t;
%p A178446       if n<2 then 1
%p A178446     else s:= `if`(member(irem(n, 4), [1, 2]), 1, 0);
%p A178446          M:= Matrix((n+1)*n/2 -s, shape=skewsymmetric);
%p A178446          if s=1 then M[1,2]:=1 fi;
%p A178446          for j from 1+s to n-1 do
%p A178446            h0:= j*(j-1)/2 +1-s;
%p A178446            h1:= h0+j;
%p A178446            t:= 1;
%p A178446            for i from 1 to j do
%p A178446              M[h1, h1+1]:= 1;
%p A178446              M[h1, h0]:= t;
%p A178446              h1:= h1+1;
%p A178446              M[h1, h0]:= t;
%p A178446              h0:= h0+1;
%p A178446              t:= -t
%p A178446            od
%p A178446          od;
%p A178446          sqrt(Determinant(M))
%p A178446       fi
%p A178446     end:
%p A178446 seq(a(n), n=0..15);
%t A178446 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 A178446 Table[a[n], {n, 0, 15}] (* _Jean-François Alcover_, Sep 23 2022, after _Alois P. Heinz_ *)
%Y A178446 Cf. A039907, A071093, A182797.
%K A178446 nonn
%O A178446 0,4
%A A178446 _Alois P. Heinz_, Dec 24 2010