A245013 Number A(n,k) of tilings of a k X n rectangle using 1 X 1 squares and 2 X 2 squares; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 5, 5, 5, 1, 1, 1, 1, 8, 11, 11, 8, 1, 1, 1, 1, 13, 21, 35, 21, 13, 1, 1, 1, 1, 21, 43, 93, 93, 43, 21, 1, 1, 1, 1, 34, 85, 269, 314, 269, 85, 34, 1, 1, 1, 1, 55, 171, 747, 1213, 1213, 747, 171, 55, 1, 1

Offset: 0

Author

Alois P. Heinz, Sep 16 2014

Keywords

• nonn
• tabl

Examples

			A(3,3) = 5:
  ._._._.  .___._.  ._.___.  ._._._.  ._._._.
  |_|_|_|  |   |_|  |_|   |  |_|_|_|  |_|_|_|
  |_|_|_|  |___|_|  |_|___|  |_|   |  |   |_|
  |_|_|_|  |_|_|_|  |_|_|_|  |_|___|  |___|_| .
Square array A(n,k) begins:
  1, 1,  1,  1,   1,    1,     1,      1, ...
  1, 1,  1,  1,   1,    1,     1,      1, ...
  1, 1,  2,  3,   5,    8,    13,     21, ...
  1, 1,  3,  5,  11,   21,    43,     85, ...
  1, 1,  5, 11,  35,   93,   269,    747, ...
  1, 1,  8, 21,  93,  314,  1213,   4375, ...
  1, 1, 13, 43, 269, 1213,  6427,  31387, ...
  1, 1, 21, 85, 747, 4375, 31387, 202841, ...
		

Links

• Liang Kai, Antidiagonals n = 0..80, flattened (antidiagonals n = 0..45 from Alois P. Heinz)
• Kai Liang, Independent Set Enumeration in King Graphs by Tensor Network Contractions, arXiv:2505.12776 [math.CO], 2025. See p. 4.
• R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016.
• Johan Nilsson, On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.

Crossrefs

Columns (or rows) k=0+1,2-10 give: A000012, A000045(n+1), A001045(n+1), A054854, A054855, A063650, A063651, A063652, A063653, A063654.

Main diagonal gives A063443.

Programs

Maple

b:= proc(n, l) option remember; local m, k; m:= min(l[]);
      if m>0 then b(n-m, map(x->x-m, l))
    elif n=0 then 1
    else for k while l[k]>0 do od; b(n, subsop(k=1, l))+
         `if`(n>1 and k `if`(min(n, k)<2, 1, b(max(n, k), [0$min(n, k)])):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

b[n_, l_] := b[n, l] = Module[{m=Min[l], k}, If[m>0, b[n-m, l-m], If[n == 0, 1, k=Position[l, 0, 1, 1][[1, 1]]; b[n, ReplacePart[l, k -> 1]] + If[n>1 && k 2, k+1 -> 2}]], 0]]]]; A[n_, k_] := If[Min[n, k]<2, 1, b[Max[n, k], Table[0, {Min[n, k]}]]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 11 2014, after Alois P. Heinz *)