OFFSET
0,13
LINKS
Alois P. Heinz, Antidiagonals n = 0..75, flattened
Eric Weisstein's World of Mathematics, Perfect Matching
Wikipedia, FKT algorithm
Wikipedia, Matching (graph theory)
EXAMPLE
A(3,3) = 4, because there are 4 domino tilings of the 3 X 3 grid with upper left corner removed:
. .___. . .___. . .___. . .___.
._|___| ._|___| ._| | | ._|___|
| |___| | | | | | |_|_| |___| |
|_|___| |_|_|_| |_|___| |___|_|
Array begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 2, 3, 5, 8, 13, ...
1, 1, 3, 4, 11, 15, 41, ...
1, 1, 5, 11, 36, 95, 281, ...
1, 1, 8, 15, 95, 192, 1183, ...
1, 1, 13, 41, 281, 1183, 6728, ...
MAPLE
with(LinearAlgebra):
A:= proc(m, n) option remember; local i, j, s, t, M;
if m=0 or n=0 then 1
elif m<n then A(n, m)
else s:= irem(n*m, 2);
M:= Matrix(n*m-s, shape=skewsymmetric);
for i to n do
for j to m do
t:= (i-1)*m+j-s;
if i>1 or j>1 or s=0 then
if j<m then M[t, t+1]:= 1 fi;
if i<n then M[t, t+m]:= 1-2*irem(j, 2) fi
fi
od
od;
isqrt(Determinant(M))
fi
end:
seq(seq(A(m, d-m), m=0..d), d=0..15);
MATHEMATICA
A[1, 1] = 1; A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2]; M[i_, j_] /; j < i := -M[j, i]; M[_, _] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i-1)*m+j-s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t+1] = 1]; If[i < n, M[t, t+m] = 1-2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m-s, n*m-s}]]]]]; Table[Table[A[m, d-m], {m, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Dec 26 2013, translated from Maple *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Apr 15 2011
STATUS
approved