A220122 Number A(n,k) of tilings of a k X n rectangle using integer-sided rectangular tiles of area k; 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, 1, 3, 1, 1, 1, 1, 2, 2, 5, 1, 1, 1, 1, 1, 3, 3, 8, 1, 1, 1, 1, 2, 1, 9, 4, 13, 1, 1, 1, 1, 1, 4, 1, 16, 6, 21, 1, 1, 1, 1, 2, 1, 7, 2, 35, 9, 34, 1, 1, 1, 1, 1, 3, 1, 13, 3, 65, 13, 55, 1, 1, 1, 1, 2, 2, 9, 1, 46, 4, 143, 19, 89, 1, 1

Offset: 0

Author

Alois P. Heinz, Dec 05 2012

Keywords

• nonn
• tabl

Comments

Row n gives: 1 followed by period A003418(n): (1, A000045(n+1), ...) repeated; offset 0.

Examples

			A(4,4) = 9, because there are 9 tilings of a 4 X 4 rectangle using integer-sided rectangular tiles of area 4:
._._._._.  ._______.  .___.___.  ._.___._.  ._______.
| | | | |  |_______|  |   |   |  | |   | |  |_______|
| | | | |  |_______|  |___|___|  | |___| |  |   |   |
| | | | |  |_______|  |   |   |  | |   | |  |___|___|
|_|_|_|_|  |_______|  |___|___|  |_|___|_|  |_______|
._._.___.  ._______.  .___._._.  .___.___.
| | |   |  |_______|  |   | | |  |   |   |
| | |___|  |_______|  |___| | |  |___|___|
| | |   |  |   |   |  |   | | |  |_______|
|_|_|___|  |___|___|  |___|_|_|  |_______|
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,  1,   1, ...
1, 1,  2,  1,   2, 1,    2, 1,    2,  1,   2, ...
1, 1,  3,  2,   3, 1,    4, 1,    3,  2,   3, ...
1, 1,  5,  3,   9, 1,    7, 1,    9,  3,   5, ...
1, 1,  8,  4,  16, 2,   13, 1,   16,  4,   9, ...
1, 1, 13,  6,  35, 3,   46, 1,   35,  6,  15, ...
1, 1, 21,  9,  65, 4,   88, 2,   65,  9,  26, ...
1, 1, 34, 13, 143, 5,  209, 3,  250, 13,  44, ...
1, 1, 55, 19, 281, 6,  473, 4,  495, 37,  75, ...
1, 1, 89, 28, 590, 8, 1002, 5, 1209, 64, 254, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..32, flattened

Crossrefs

Columns k=0+1, 2-11, 13 give: A000012, A000045(n+1), A000930, A220123, A003520, A220124, A005709, A220125, A220126, A220127, A017905(n+11), A017907(n+13).

Rows n=0+1, 2-10 give: A000012, A040001, A220128, A220129, A220130, A220131, A220132, A220133, A220134, A220135.

Main diagonal gives: A182106.

Programs

Maple

b:= proc(n, l) option remember; local i, k, m, 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))
    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(m, 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]) fi od; s
      fi
    end:
A:= (n, k)-> b(n, [0$k]):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

b[n_, l_] := b[n, l] = Module[{i, k, m, 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, m} = {0, Length[l]}; For[ i = k , i <= m && l[[i]] == 0, i++, If[Mod[m, 1+i-k ] == 0 && (q = Quotient[m, 1+i-k]) <= n, s = s+b[n, Join[ l[[1 ;; k-1]], Array[q &, i-k+1], l[[i+1 ;; m]] ]]]]; s]]; a[n_, k_] := b[n, Array[0&, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 19 2013, translated from Maple *)

Formula

For prime p column p has g.f.: 1/(1-x-x^p) or a_p(n) = Sum_{j=0..floor(n/p)} C(n-(p-1)*j,j).