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,13

Links

Alois P. Heinz and Christopher Hunt Gribble, Antidiagonals n = 0..27, flattened (first 25 antidiagonals from Alois P. Heinz)

Example

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

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 *)

Crossrefs

Columns (or rows) k=0+1, 2-5 give: A000012, A008619, A001399, A008763(n+4), A187753.

Main diagonal gives: A034295.

Cf. A225622.

Sequence in context: A119963 A057790 A350889 * A052307 A067059 A049704

Adjacent sequences: A224694 A224695 A224696 * A224698 A224699 A224700

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 15 2013

Status

approved