The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A340532 Number of domino tilings of a 16 X n rectangle. 2
1, 1, 1597, 29681, 9475901, 366944287, 69289288909, 3710708201969, 540061286536921, 34741645659770711, 4337452956682508609, 313196612952258199679, 35457442115448212075033, 2764079753958605286860951, 293251198441417290172509377, 24080184063411167042923575793 (list; graph; refs; listen; history; text; internal format)



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.)

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.)


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.


Alois P. Heinz, Table of n, a(n) for n = 0..514

M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Phys. Rev. 124 (1961) 1664-1672.

P. W. Kasteleyn, The statistics of dimers on a lattice, Physica 27 (1961), 1209-1225.

P. W. Kasteleyn, Dimer statistics and phase transitions, J. Math. Phys., 4 (1963), 287-293.

Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet, NP-completeness of the game Kingdomino(TM), Theoretical Computer Science (2020) Vol. 822, 23-35. See also arXiv:1909.02849, [cs.CC], 2019.


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.

a(n) = A187596(16,n) = A187596(n,16). - Alois P. Heinz, Jan 10 2021


a(1) = 1, since there is only one domino tiling of the 16 X n rectangle, which consists entirely of horizontal tiles.

a(2) = 1597 = F(17), since the number of domino tilings of the m X 2 rectangle is the Fibonacci number F(m+1).

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.


b:= proc(n, l) option remember; local k;

      if n=0 then 1

    elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))

    else for k while l[k]>0 do od; `if`(n>1, b(n, subsop(k=2, l)), 0)+

         `if`(k<nops(l) and l[k+1]=0, b(n, subsop(k=1, k+1=1, l)), 0)



a:= n-> b(n, [0$16]):

seq(a(n), n=0..15);  # Alois P. Heinz, Jan 12 2021



P = 1; m = 16;


  P = N[P*(4*Cos[Pi*i/(n + 1)]^2 + 4*Cos[Pi*j/(m + 1)]^2), 1020],

  {i, 1, n/2}, {j, 1, m/2}];

Print["P=", N[P, 1020], " n=", n, " m=", m],

{n, 1, 20}



Subsequence of A099390.

Cf. A000045, A187596.

Sequence in context: A068263 A078954 A117745 * A189456 A084427 A260245

Adjacent sequences:  A340529 A340530 A340531 * A340533 A340534 A340535




A. M. Magomedov and Serge Lawrencenko, Jan 10 2021



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 4 20:58 EST 2021. Contains 341811 sequences. (Running on oeis4.)