A364457 Number A(n,k) of tilings of a k X n rectangle using dominoes and trominoes (of any shape); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 6, 1, 1, 1, 2, 17, 30, 17, 2, 1, 1, 2, 43, 145, 145, 43, 2, 1, 1, 3, 108, 733, 1294, 733, 108, 3, 1, 1, 4, 280, 3540, 12109, 12109, 3540, 280, 4, 1, 1, 5, 727, 17300, 110017, 215905, 110017, 17300, 727, 5, 1

Offset

0,13

Links

Alois P. Heinz, Antidiagonals n = 0..25, flattened

Wikipedia, Domino (mathematics)

Wikipedia, Tromino

Formula

A(n,k) = A(k,n).

Example

A(3,2) = A(2,3) = 6:
  .___.   .___.   .___.   .___.   .___.   .___.
  | | |   |___|   | | |   |___|   | ._|   |_. |
  | | |   |___|   |_|_|   | | |   |_| |   | |_|
  |_|_|   |___|   |___|   |_|_|   |___|   |___|  .
.
Square array A(n,k) begins:
  1, 1,   1,     1,       1,        1,          1,            1, ...
  1, 0,   1,     1,       1,        2,          2,            3, ...
  1, 1,   2,     6,      17,       43,        108,          280, ...
  1, 1,   6,    30,     145,      733,       3540,        17300, ...
  1, 1,  17,   145,    1294,    12109,     110017,      1014847, ...
  1, 2,  43,   733,   12109,   215905,    3710880,     64589501, ...
  1, 2, 108,  3540,  110017,  3710880,  118624712,   3899306587, ...
  1, 3, 280, 17300, 1014847, 64589501, 3899306587, 239677657279, ...

Maple

b:= proc(n, l) option remember; local k, t;
      if max(l[])>n then 0 elif n=0 or l=[] then 1
    elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
    else for k do if l[k]=0 then break fi od; b(n, subsop(k=2, l))+
         `if`(k>1 and l[k-1]=1, b(n, subsop(k=2, k-1=2, l)), 0)+
         `if`(k<nops(l) and l[k+1]=1, b(n, subsop(k=2, k+1=2, l)), 0)+
         `if`(k<nops(l) and l[k+1]=0, b(n, subsop(k=1, k+1=1, l))+
            b(n, subsop(k=1, k+1=2, l))+b(n, subsop(k=2, k+1=1, l)), 0)+
         `if`(k+1<nops(l) and l[k+1]=0 and l[k+2]=0,
            b(n, subsop(k=2, k+1=2, k+2=2, l))+
            b(n, subsop(k=2, k+1=2, k+2=1, l)), 0)+
         `if`(k+1<nops(l) and l[k+1]=0 and l[k+2]=0, b(n, subsop(k=1,
              k+1=1, k+2=1, l)), 0)+b(n, subsop(k=3, l))
      fi
    end:
A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[n_, l_] := b[n, l] = Module[{k, t, RP = ReplacePart}, Which[Max[l] > n,  0, n == 0 || l == {}, 1, Min[l] > 0, t = Min[l]; b[n - t, l - t], True, For[k = 1, True, k++, If[l[[k]] == 0, Break[]]]; b[n, RP[l, k -> 2]] + If[k > 1 && l[[k - 1]] == 1, b[n, RP[l, {k -> 2, k - 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 1, b[n, RP[l, {k -> 2, k + 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 0, b[n, RP[l, {k -> 1, k + 1 -> 1}]] + b[n, RP[l, {k -> 1, k + 1 -> 2}]] + b[n, RP[l, {k -> 2, k + 1 -> 1}]], 0] + If[k + 1 < Length[l] && l[[k + 1]] == 0 && l[[k + 2]] == 0, b[n, RP[l, {k -> 2, k + 1 -> 2, k + 2 -> 2}]] + b[n, RP[l, {k -> 2, k + 1 -> 2, k + 2 -> 1}]], 0] + If[k + 1 < Length[l] && l[[k + 1]] == 0 && l[[k + 2]] == 0, b[n, RP[l, {k -> 1, k + 1 -> 1, k + 2 -> 1}]], 0] + b[n, RP[l, k -> 3]]]];
A[n_, k_] := If[n >= k, b[n, Table[0, {k}]], b[k, Table[0, {n}]]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Aug 28 2023, after Alois P. Heinz *)

Crossrefs

Columns (or rows) k=0-10 give: A000012, A182097(n) = A000931(n+3), A019439, A364460, A364155, A364556, A364616, A364617, A364632, A364638, A364640.

Main diagonal gives A364504.

Cf. A219866, A219987, A233320.

Sequence in context: A275062 A247005 A174215 * A305567 A134744 A260875

Adjacent sequences: A364454 A364455 A364456 * A364458 A364459 A364460

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 25 2023

Status

approved