|
|
A187596
|
|
Array T(m,n) read by antidiagonals: number of domino tilings of the m X n grid (m>=0, n>=0).
|
|
13
|
|
|
1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 2, 0, 1, 1, 1, 3, 3, 1, 1, 1, 0, 5, 0, 5, 0, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 0, 13, 0, 36, 0, 13, 0, 1, 1, 1, 21, 41, 95, 95, 41, 21, 1, 1, 1, 0, 34, 0, 281, 0, 281, 0, 34, 0, 1, 1, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 1, 1, 0, 89, 0, 2245, 0, 6728, 0, 2245, 0, 89, 0, 1, 1, 1, 144, 571, 6336
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,13
|
|
COMMENTS
|
A099390 supplemented by an initial row and column of 1's.
See A099390 (the main entry for this array) for further information.
If we work with the row index starting at 1 then every row of the array is a divisibility sequence, i.e., the terms satisfy the property that if n divides m then a(n) divide a(m) provided a(n) != 0. Row k satisfies a linear recurrence of order 2^floor(k/2) (Stanley, Ex. 36 p. 273). - Peter Bala, Apr 30 2014
|
|
REFERENCES
|
R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k)^2 = absolute value of Product_{b=1..k} Product_{a=1..n} ( 2*cos(a*Pi/(n+1)) + 2*i*cos(b*Pi/(k+1)), where i = sqrt(-1). See Propp, Section 5.
Equivalently, working with both the row index n and column index k starting at 1 we have T(n,k)^2 = absolute value of Resultant (F(n,x), U(k-1,x/2)), where U(n,x) is a Chebyshev polynomial of the second kind and F(n,x) is a Fibonacci polynomial defined recursively by F(0,x) = 0, F(1,x) = 1 and F(n,x) = x*F(n-1,x) + F(n-2,x) for n >= 2. The divisibility properties of the array entries mentioned in the Comments are a consequence of this result. (End)
|
|
EXAMPLE
|
Array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
1, 0, 3, 0, 11, 0, 41, 0, 153, 0, 571, ...
1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, ...
1, 0, 8, 0, 95, 0, 1183, 0, 14824, 0, 185921, ...
1, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133, ...
1, 0, 21, 0, 781, 0, 31529, 0, 1292697, 0, 53175517, ...
|
|
MAPLE
|
with(LinearAlgebra):
T:= proc(m, n) option remember; local i, j, t, M;
if m<=1 or n<=1 then 1 -irem(n*m, 2)
elif irem(n*m, 2)=1 then 0
elif m<n then T(n, m)
else M:= Matrix(n*m, shape=skewsymmetric);
for i to n do
for j to m do
t:= (i-1)*m+j;
if j<m then M[t, t+1]:= 1 fi;
if i<n then M[t, t+m]:= 1-2*irem(j, 2) fi
od
od;
sqrt(Determinant(M))
fi
end:
|
|
MATHEMATICA
|
t[m_, n_] := Product[2*(2+Cos[2*j*Pi/(m+1)]+Cos[2*k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}]; t[_?OddQ, _?OddQ] = 0; Table[t[m-n, n] // FullSimplify, {m, 0, 13}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 07 2014, after A099390 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|