A224697 Number A(n,k) of different ways to divide an n X k rectangle into subsquares, considering only the list of parts; 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, 2, 2, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 1, 4, 5, 7, 5, 4, 1, 1, 1, 1, 4, 7, 9, 9, 7, 4, 1, 1, 1, 1, 5, 8, 14, 11, 14, 8, 5, 1, 1, 1, 1, 5, 10, 17, 20, 20, 17, 10, 5, 1, 1
Offset: 0
Examples
A(4,5) = 9 because there are 9 ways to divide a 4 X 5 rectangle into subsquares, considering only the list of parts: [20(1 X 1)], [16(1 X 1), 1(2 X 2)], [12(1 X 1), 2(2 X 2)], [11(1 X 1), 1(3 X 3)], [8(1 X 1), 3(2 X 2)], [7(1 X 1), 1(2 X 2), 1(3 X 3)], [4(1 X 1), 4(2 X 2)], [4(1 X 1), 1(4 X 4)], [3(1 X 1), 2(2 X 2), 1(3 X 3)]. There is no way to divide this rectangle into [2(1 X 1), 2(3 X 3)]. 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, 2, 2, 3, 3, 4, 4, 5, 5, ... 1, 1, 2, 3, 4, 5, 7, 8, 10, 12, ... 1, 1, 3, 4, 7, 9, 14, 17, 24, 29, ... 1, 1, 3, 5, 9, 11, 20, 26, 36, 48, ... 1, 1, 4, 7, 14, 20, 31, 47, 71, 95, ... 1, 1, 4, 8, 17, 26, 47, 57, 102, 143, ... 1, 1, 5, 10, 24, 36, 71, 102, 148, 238, ... 1, 1, 5, 12, 29, 48, 95, 143, 238, 312, ...
Links
- Alois P. Heinz and Christopher Hunt Gribble, Antidiagonals n = 0..27, flattened (first 25 antidiagonals from Alois P. Heinz)
Crossrefs
Programs
-
Maple
b:= proc(n, l) option remember; local i, k, s, t; if max(l[])>n then {} elif n=0 or l=[] then {[]} 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:={}; for i from k to nops(l) while l[i]=0 do s:=s union map(x->sort([x[], 1+i-k]), b(n, [l[j]$j=1..k-1, 1+i-k$j=k..i, l[j]$j=i+1..nops(l)])) od; s fi end: A:= (n, k)-> `if`(n>=k, nops(b(n, [0$k])), nops(b(k, [0$n]))): seq(seq(A(n, d-n), n=0..d), d=0..12); -
Mathematica
b[n_, l_] := b[n, l] = Module[{i, k, m, s, t}, Which[Max[l] > n, {}, n == 0 || l == {}, {{}}, Min[l] > 0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; s = {}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s ~Union~ Map[Function[x, Sort[Append[x, 1+i-k]]], b[n, Join[l[[1 ;; k-1]], Array[1+i-k&, i-k+1], l[[i+1 ;; -1]] ] ]]]; s]]; a[n_, k_] := If[n >= k, Length @ b[n, Array[0&, k]], Length @ b[k, Array[0&, n]]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 19 2013, translated from Maple *)