%I #40 Sep 05 2021 18:20:49
%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,40,28,13,1,1,1,1,21,60,117,117,60,21,1,1,1,1,34,129,
%U 348,472,348,129,34,1,1,1,1,55,277,1029,1916,1916,1029,277,55,1,1
%N Number A(n,k) of tilings of a k X n rectangle using integer-sided square tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%C For drawings of A(1,1), A(2,2), ..., A(5,5) see A224239.
%H Alois P. Heinz, <a href="/A219924/b219924.txt">Antidiagonals n = 0..30, flattened</a>
%H Steve Butler, Jason Ekstrand, Steven Osborne, <a href="https://doi.org/10.1007/978-3-030-37853-0_5">Counting Tilings by Taking Walks in a Graph</a>, A Project-Based Guide to Undergraduate Research in Mathematics, Birkhäuser, Cham (2020), see page 169.
%e A(3,3) = 6, because there are 6 tilings of a 3 X 3 rectangle using integer-sided squares:
%e ._____. ._____. ._____. ._____. ._____. ._____.
%e | | | |_| |_| | |_|_|_| |_|_|_| |_|_|_|
%e | | |___|_| |_|___| |_| | | |_| |_|_|_|
%e |_____| |_|_|_| |_|_|_| |_|___| |___|_| |_|_|_|
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 2, 3, 5, 8, 13, 21, ...
%e 1, 1, 3, 6, 13, 28, 60, 129, ...
%e 1, 1, 5, 13, 40, 117, 348, 1029, ...
%e 1, 1, 8, 28, 117, 472, 1916, 7765, ...
%e 1, 1, 13, 60, 348, 1916, 10668, 59257, ...
%e 1, 1, 21, 129, 1029, 7765, 59257, 450924, ...
%p b:= proc(n, l) option remember; local i, k, s, 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; s:=0;
%p for i from k to nops(l) while l[i]=0 do s:=s+
%p b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
%p od; s
%p fi
%p end:
%p A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
%p seq(seq(A(n, d-n), n=0..d), d=0..14);
%p # The following is a second version of the program that lists the actual dissections. It produces a list of pairs for each dissection:
%p b:= proc(n, l, ll) local i, k, s, t;
%p if max(l[])>n then 0 elif n=0 or l=[] then lprint(ll); 1
%p elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l), ll)
%p else for k do if l[k]=0 then break fi od; s:=0;
%p for i from k to nops(l) while l[i]=0 do s:=s+
%p b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)],
%p [ll[],[k,1+i-k]])
%p od; s
%p fi
%p end:
%p A:= (n, k)-> b(k, [0$n], []):
%p A(5,5);
%p # In each list [a,b] means put a square with side length b at
%p leftmost possible position with upper corner in row a. For example
%p [[1,3], [4,2], [4,2], [1,2], [3,1], [3,1], [4,1], [5,1]], gives:
%p ._____.___.
%p | | |
%p | |___|
%p |_____|_|_|
%p | | |_|
%p |___|___|_|
%t b[n_, l_List] := b[n, l] = Module[{i, k, s, 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]]; s = 0; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s + b[n, Join[l[[1;; k-1]], Table[1+i-k, {j, k, i}], l[[i+1;; -1]] ] ] ]; s]]; a[n_, k_] := If[n >= k, b[n, Array[0&, k]], b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Dec 13 2013, translated from 1st Maple program *)
%Y Columns (or rows) k=0+1, 2-10 give: A000012, A000045(n+1), A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
%Y Main diagonal gives A045846.
%Y Cf. A113881, A226545.
%K nonn,tabl
%O 0,13
%A _Alois P. Heinz_, Dec 01 2012