cp's OEIS Frontend

A340532 Number of domino tilings of a 16 X n rectangle.

%I A340532 #33 Jan 12 2021 19:18:50
%S A340532 1,1,1597,29681,9475901,366944287,69289288909,3710708201969,
%T A340532 540061286536921,34741645659770711,4337452956682508609,
%U A340532 313196612952258199679,35457442115448212075033,2764079753958605286860951,293251198441417290172509377,24080184063411167042923575793
%N A340532 Number of domino tilings of a 16 X n rectangle.
%C A340532 Basically, for n = 1, 2, ..., 513, the terms a(n) are calculated by the double product formula in the program below, with the help of the authors' C# program using the BigInteger and BigFloat classes. (The computer calculations took 44 hours to complete.)
%C A340532 Alternatively, the value of a(513) is calculated by the homogeneous linear recurrence relation of order 256; the thus calculated value coincides with the one obtained by the classical double product formula. Furthermore, using the recurrence relation, the values of a(514), a(515), ..., a(10240) are also calculated. (The computer calculations took 4 minutes to complete.)
%D A340532 A. M. Magomedov, T. A. Magomedov, S. A. Lawrencenko, Mutually-recursive formulas for enumerating partitions of the rectangle (Russian, English summary), Prikl. Diskr. Mat., 46 (2019), 108-121.
%H A340532 Alois P. Heinz, <a href="/A340532/b340532.txt">Table of n, a(n) for n = 0..514</a>
%H A340532 M. E. Fisher, <a href="https://doi.org/10.1103/PhysRev.124.1664">Statistical mechanics of dimers on a plane lattice</a>, Phys. Rev. 124 (1961) 1664-1672.
%H A340532 P. W. Kasteleyn, <a href="https://doi.org/10.1016/0031-8914(61)90063-5">The statistics of dimers on a lattice</a>, Physica 27 (1961), 1209-1225.
%H A340532 P. W. Kasteleyn, <a href="https://doi.org/10.1063/1.1703953">Dimer statistics and phase transitions</a>, J. Math. Phys., 4 (1963), 287-293.
%H A340532 Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet, <a href="https://doi.org/10.1016/j.tcs.2020.04.007">NP-completeness of the game Kingdomino(TM)</a>, Theoretical Computer Science (2020) Vol. 822, 23-35. See also <a href="https://arxiv.org/abs/1909.02849">arXiv:1909.02849</a>, [cs.CC], 2019.
%F A340532 The sequence is completely defined by the following formula, which is a special case of a classical double product formula (A099390): a(n) = Product_{j=1..8} (Product_{k=1..floor(n/2)} (4*(cos(j*Pi/17))^2 + 4*(cos(k*Pi/(n+1)))^2)). In addition, a homogeneous linear recurrence relation of order 256 with constant coefficients is obtained to generate the sequence.
%F A340532 a(n) = A187596(16,n) = A187596(n,16). - _Alois P. Heinz_, Jan 10 2021
%e A340532 a(1) = 1, since there is only one domino tiling of the 16 X n rectangle, which consists entirely of horizontal tiles.
%e A340532 a(2) = 1597 = F(17), since the number of domino tilings of the m X 2 rectangle is the Fibonacci number F(m+1).
%e A340532 Note that the terms a(16) and a(33) are even. More generally, for m even, the numbers of domino tilings of the m X m square and of the m X (2m+1) rectangle are even.
%p A340532 b:= proc(n, l) option remember; local k;
%p A340532       if n=0 then 1
%p A340532     elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
%p A340532     else for k while l[k]>0 do od; `if`(n>1, b(n, subsop(k=2, l)), 0)+
%p A340532          `if`(k<nops(l) and l[k+1]=0, b(n, subsop(k=1, k+1=1, l)), 0)
%p A340532       fi
%p A340532     end:
%p A340532 a:= n-> b(n, [0$16]):
%p A340532 seq(a(n), n=0..15);  # _Alois P. Heinz_, Jan 12 2021
%t A340532 Do[
%t A340532 P = 1; m = 16;
%t A340532 Do[
%t A340532   P = N[P*(4*Cos[Pi*i/(n + 1)]^2 + 4*Cos[Pi*j/(m + 1)]^2), 1020],
%t A340532   {i, 1, n/2}, {j, 1, m/2}];
%t A340532 Print["P=", N[P, 1020], " n=", n, " m=", m],
%t A340532 {n, 1, 20}
%t A340532 ]
%Y A340532 Subsequence of A099390.
%Y A340532 Cf. A000045, A187596.
%K A340532 nonn
%O A340532 0,3
%A A340532 A. M. Magomedov and _Serge Lawrencenko_, Jan 10 2021