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
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
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).
Comments