cp's OEIS Frontend

A219924 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.

%I A219924 #40 Sep 05 2021 18:20:49
%S A219924 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 A219924 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 A219924 348,472,348,129,34,1,1,1,1,55,277,1029,1916,1916,1029,277,55,1,1
%N A219924 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 A219924 For drawings of A(1,1), A(2,2), ..., A(5,5) see A224239.
%H A219924 Alois P. Heinz, <a href="/A219924/b219924.txt">Antidiagonals n = 0..30, flattened</a>
%H A219924 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 A219924 A(3,3) = 6, because there are 6 tilings of a 3 X 3 rectangle using integer-sided squares:
%e A219924   ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
%e A219924   |     |  |   |_|  |_|   |  |_|_|_|  |_|_|_|  |_|_|_|
%e A219924   |     |  |___|_|  |_|___|  |_|   |  |   |_|  |_|_|_|
%e A219924   |_____|  |_|_|_|  |_|_|_|  |_|___|  |___|_|  |_|_|_|
%e A219924 Square array A(n,k) begins:
%e A219924   1,  1,  1,   1,    1,    1,     1,      1, ...
%e A219924   1,  1,  1,   1,    1,    1,     1,      1, ...
%e A219924   1,  1,  2,   3,    5,    8,    13,     21, ...
%e A219924   1,  1,  3,   6,   13,   28,    60,    129, ...
%e A219924   1,  1,  5,  13,   40,  117,   348,   1029, ...
%e A219924   1,  1,  8,  28,  117,  472,  1916,   7765, ...
%e A219924   1,  1, 13,  60,  348, 1916, 10668,  59257, ...
%e A219924   1,  1, 21, 129, 1029, 7765, 59257, 450924, ...
%p A219924 b:= proc(n, l) option remember; local i, k, s, t;
%p A219924       if max(l[])>n then 0 elif n=0 or l=[] then 1
%p A219924     elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
%p A219924     else for k do if l[k]=0 then break fi od; s:=0;
%p A219924          for i from k to nops(l) while l[i]=0 do s:=s+
%p A219924            b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])
%p A219924          od; s
%p A219924       fi
%p A219924     end:
%p A219924 A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
%p A219924 seq(seq(A(n, d-n), n=0..d), d=0..14);
%p A219924 # The following is a second version of the program that lists the actual dissections. It produces a list of pairs for each dissection:
%p A219924 b:= proc(n, l, ll) local i, k, s, t;
%p A219924       if max(l[])>n then 0 elif n=0 or l=[] then lprint(ll); 1
%p A219924     elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l), ll)
%p A219924     else for k do if l[k]=0 then break fi od; s:=0;
%p A219924          for i from k to nops(l) while l[i]=0 do s:=s+
%p A219924            b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)],
%p A219924             [ll[],[k,1+i-k]])
%p A219924          od; s
%p A219924       fi
%p A219924     end:
%p A219924 A:= (n, k)-> b(k, [0$n], []):
%p A219924 A(5,5);
%p A219924 # In each list [a,b] means put a square with side length b at
%p A219924 leftmost possible position with upper corner in row a.  For example
%p A219924 [[1,3], [4,2], [4,2], [1,2], [3,1], [3,1], [4,1], [5,1]], gives:
%p A219924 ._____.___.
%p A219924 |     |   |
%p A219924 |     |___|
%p A219924 |_____|_|_|
%p A219924 |   |   |_|
%p A219924 |___|___|_|
%t A219924 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 A219924 Columns (or rows) k=0+1, 2-10 give: A000012, A000045(n+1), A002478, A054856, A054857, A219925, A219926, A219927, A219928, A219929.
%Y A219924 Main diagonal gives A045846.
%Y A219924 Cf. A113881, A226545.
%K A219924 nonn,tabl
%O A219924 0,13
%A A219924 _Alois P. Heinz_, Dec 01 2012