login
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.
9

%I #35 Dec 12 2018 11:56:42

%S 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,

%T 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,

%U 387,524,387,129,34,1,1,1,1,55,277,1180,2229,2229,1180,277,55,1,1

%N 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.

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

%H Alois P. Heinz, <a href="/A226444/b226444.txt">Antidiagonals n = 0..44, flattened</a>

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

%e A(3,3) = 6:

%e ._____. ._____. ._____. ._____. ._____. ._____.

%e |_|_|_| | |_|_| |_|_|_| |_| |_| |_|_|_| |_| |_|

%e |_|_|_| |___|_| | |_|_| |_|___| |_| |_| | |___|

%e |_|_|_| |_|_|_| |___|_| |_|_|_| |_|___| |___|_|.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

%e 1, 1, 3, 6, 13, 28, 60, 129, 277, ...

%e 1, 1, 5, 13, 42, 126, 387, 1180, 3606, ...

%e 1, 1, 8, 28, 126, 524, 2229, 9425, 39905, ...

%e 1, 1, 13, 60, 387, 2229, 13322, 78661, 466288, ...

%e 1, 1, 21, 129, 1180, 9425, 78661, 647252, 5350080, ...

%e 1, 1, 34, 277, 3606, 39905, 466288, 5350080, 61758332, ...

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

%p if max(l[])>n then 0 elif n=0 or l=[] then 1

%p elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))

%p else for k do if l[k]=0 then break fi od; b(n, subsop(k=1, l))+

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

%p fi

%p end:

%p A:= (n, k)-> b(max(n, k), [0$min(n, k)]):

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%p [Zeilberger gives Maple code to find generating functions for the columns - see links in A228285. - _N. J. A. Sloane_, Aug 22 2013]

%t 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 *)

%Y 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.

%Y Main diagonal gives A066864(n-1).

%Y See A219741 for an array with very similar entries. - _N. J. A. Sloane_, Aug 22 2013

%Y Cf. A322494.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Jun 06 2013