login
Array T(m,n) read by antidiagonals: number of domino tilings of the m X n grid (m>=0, n>=0).
13

%I #63 Aug 06 2022 07:23:59

%S 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,

%T 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,

%U 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

%N Array T(m,n) read by antidiagonals: number of domino tilings of the m X n grid (m>=0, n>=0).

%C A099390 supplemented by an initial row and column of 1's.

%C See A099390 (the main entry for this array) for further information.

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

%D R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.

%H Alois P. Heinz, <a href="/A187596/b187596.txt">Antidiagonals n = 0..80, flattened</a>

%H James Propp, <a href="http://arxiv.org/abs/math/9904150">Enumeration of Matchings: Problems and Progress</a>, arXiv:math/9904150 [math.CO], 1999.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChebyshevPolynomialoftheSecondKind.html">Chebyshev Polynomial of the second kind</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciPolynomial.html">Fibonacci Polynomial</a>.

%F From _Peter Bala_, Apr 30 2014: (Start)

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

%F 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)

%e Array begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...

%e 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

%e 1, 0, 3, 0, 11, 0, 41, 0, 153, 0, 571, ...

%e 1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, ...

%e 1, 0, 8, 0, 95, 0, 1183, 0, 14824, 0, 185921, ...

%e 1, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133, ...

%e 1, 0, 21, 0, 781, 0, 31529, 0, 1292697, 0, 53175517, ...

%p with(LinearAlgebra):

%p T:= proc(m,n) option remember; local i, j, t, M;

%p if m<=1 or n<=1 then 1 -irem(n*m, 2)

%p elif irem(n*m, 2)=1 then 0

%p elif m<n then T(n,m)

%p else M:= Matrix(n*m, shape=skewsymmetric);

%p for i to n do

%p for j to m do

%p t:= (i-1)*m+j;

%p if j<m then M[t, t+1]:= 1 fi;

%p if i<n then M[t, t+m]:= 1-2*irem(j, 2) fi

%p od

%p od;

%p sqrt(Determinant(M))

%p fi

%p end:

%p seq(seq(T(m, d-m), m=0..d), d=0..14); # _Alois P. Heinz_, Apr 11 2011

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

%Y Cf. A099390.

%Y See A187616 for a triangular version, and A187617, A187618 for the sub-array T(2m,2n).

%Y See also A049310, A053117.

%K nonn,tabl

%O 0,13

%A _N. J. A. Sloane_, Mar 11 2011