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
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
- Liang Kai, Antidiagonals n = 0..75, flattened (antidiagonals 0..44 from Alois P. Heinz)
- Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs and Their Variants, arXiv:2507.04007 [math.CO], 2025. See p. 13.
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 -
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
Comments