A220777 Number A(n,k) of tilings of a k X n rectangle using integer-sided rectangular tiles of equal area; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 6, 6, 3, 1, 1, 2, 9, 4, 9, 2, 1, 1, 4, 11, 20, 20, 11, 4, 1, 1, 2, 21, 7, 49, 7, 21, 2, 1, 1, 4, 24, 54, 115, 115, 54, 24, 4, 1, 1, 3, 43, 12, 343, 4, 343, 12, 43, 3, 1, 1, 4, 62, 190, 850, 1225, 1225, 850, 190, 62, 4, 1

Offset

0,8

Links

Alois P. Heinz, Antidiagonals n = 0..26, flattened

Example

A(3,5) = 7, because there are 7 tilings of a 5 X 3 rectangle using integer-sided rectangular tiles of equal area:
  ._____. ._____. ._____. ._____. ._____. ._____. ._____.
  |     | | | | | |_____| |_____| |_____| | | | | |_|_|_|
  |     | | | | | |_____| |_____| | | | | | | | | |_|_|_|
  |     | | | | | |_____| | | | | | | | | |_|_|_| |_|_|_|
  |     | | | | | |_____| | | | | |_|_|_| |_____| |_|_|_|
  |_____| |_|_|_| |_____| |_|_|_| |_____| |_____| |_|_|_|
Square array A(n,k) begins:
  1,  1,  1,   1,    1,     1,      1,       1,        1, ...
  1,  1,  2,   2,    3,     2,      4,       2,        4, ...
  1,  2,  4,   6,    9,    11,     21,      24,       43, ...
  1,  2,  6,   4,   20,     7,     54,      12,      190, ...
  1,  3,  9,  20,   49,   115,    343,     850,     2401, ...
  1,  2, 11,   7,  115,     4,   1225,       7,    15242, ...
  1,  4, 21,  54,  343,  1225,   7104,   31777,   169952, ...
  1,  2, 24,  12,  850,     7,  31777,       4,  1300180, ...
  1,  4, 43, 190, 2401, 15242, 169952, 1300180, 13036591, ...
  ...

Maple

b:= proc(n, l, d) option remember; local i, k, m, q, s, 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), d)
    else for k do if l[k]=0 then break fi od; s, m:=0, nops(l);
         for i from k to m while l[i]=0 do if irem(d, 1+i-k, 'q')=0
           and q<=n then s:= s+ b(n, [l[j]$j=1..k-1, q$j=k..i,
           l[j]$j=i+1..m], d) fi od; s
      fi
    end:
A:= (n, k)-> `if`(n<k, A(k, n), `if`(k=0, 1,
              add(b(n, [0$k], d), d=numtheory[divisors](n*k)))):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

$RecursionLimit = 1000; b[n_, l_, d_] := b[n, l, d] = Module[{i, k, m, q, s, t}, Which[ Max[l] > n, 0, n == 0 || l == {}, 1, Min[l] > 0, t = Min[l]; b[n-t, l-t, d], True, k = Position[l, 0, 1][[1, 1]]; {s, m} = {0, Length[l]}; For[i = k, i <= m && l[[i]] == 0, i++, If[(Mod[d, 1+i-k]) == 0 && (q = Quotient[d, 1+i-k]) <= n, s = s + b[n, Join[l[[1 ;; k-1]], Table[q, {j, k, i}], l[[i+1 ;; m]]], d] ] ]; s ] ]; a[n_, k_] := a[n, k] = If[n < k, a[k, n], If[k == 0, 1, Sum[b[n, Array[0&, k], d], {d, Divisors[n*k]}]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Crossrefs

Columns (or rows) k=0-10 give: A000012, A000005, A220768, A220769, A220770, A220771, A220772, A220773, A220774, A220775, A220776.

Main diagonal gives: A220778.

Sequence in context: A075402 A373270 A276696 * A088855 A034851 A172453

Adjacent sequences: A220774 A220775 A220776 * A220778 A220779 A220780

Keyword

nonn,tabl

Author

Alois P. Heinz, Dec 19 2012

Status

approved