A226444 Number A(n,k) of tilings of a k X n rectangle using 1 X 1 squares and L-tiles; 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, 6, 5, 1, 1, 1, 1, 8, 13, 13, 8, 1, 1, 1, 1, 13, 28, 42, 28, 13, 1, 1, 1, 1, 21, 60, 126, 126, 60, 21, 1, 1, 1, 1, 34, 129, 387, 524, 387, 129, 34, 1, 1, 1, 1, 55, 277, 1180, 2229, 2229, 1180, 277, 55, 1, 1

Offset: 0

Author

Alois P. Heinz, Jun 06 2013

Keywords

• nonn
• tabl

Comments

An L-tile is a 2 X 2 square with the upper right 1 X 1 subsquare removed and no rotations are allowed.

Examples

			A(3,3) = 6:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |_|_|_|  | |_|_|  |_|_|_|  |_| |_|  |_|_|_|  |_| |_|
  |_|_|_|  |___|_|  | |_|_|  |_|___|  |_| |_|  | |___|
  |_|_|_|  |_|_|_|  |___|_|  |_|_|_|  |_|___|  |___|_|.
Square array A(n,k) begins:
  1, 1,  1,   1,    1,     1,      1,       1,        1, ...
  1, 1,  1,   1,    1,     1,      1,       1,        1, ...
  1, 1,  2,   3,    5,     8,     13,      21,       34, ...
  1, 1,  3,   6,   13,    28,     60,     129,      277, ...
  1, 1,  5,  13,   42,   126,    387,    1180,     3606, ...
  1, 1,  8,  28,  126,   524,   2229,    9425,    39905, ...
  1, 1, 13,  60,  387,  2229,  13322,   78661,   466288, ...
  1, 1, 21, 129, 1180,  9425,  78661,  647252,  5350080, ...
  1, 1, 34, 277, 3606, 39905, 466288, 5350080, 61758332, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..44, flattened

Crossrefs

Columns (or rows) k=0+1,2-10 give: A000012, A000045(n+1), A002478, A105262, A219737(n-1) for n>2, A219738 (n-1) for n>2, A219739(n-1) for n>1, A219740(n-1) for n>2, A226543, A226544.

Main diagonal gives A066864(n-1).

See A219741 for an array with very similar entries. - N. J. A. Sloane, Aug 22 2013

Cf. A322494.

Programs

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=1, l))+
        `if`(k b(max(n, k), [0$min(n, k)]):
seq(seq(A(n, d-n), n=0..d), d=0..14);
[Zeilberger gives Maple code to find generating functions for the columns - see links in A228285. - N. J. A. Sloane, Aug 22 2013]

Mathematica

b[n_, l_] := b[n, l] = Module[{k, t}, Which[Max[l] > n, 0, n == 0 || l == {}, 1, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; b[n, ReplacePart[l, k -> 1]] + If[k < Length[l] && l[[k+1]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 2}]], 0] ] ]; a[n_, k_] := b[Max[n, k], Array[0&, Min[n, k]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 18 2013, translated from Maple *)

Formula

The k-th column satisfies a recurrence of order Fibonacci(k+1) [Zeilberger] - see links in A228285. - N. J. A. Sloane, Aug 22 2013