A221640 Number T(n,k) of different numbers of square parts in the set of partitions of an n X k rectangle into squares with integer sides, considering only the list of parts; triangle T(n,k), 1 <= k <= n, read by rows.

1, 1, 2, 1, 2, 3, 1, 3, 4, 7, 1, 3, 5, 9, 11, 1, 4, 7, 12, 18, 23, 1, 4, 8, 15, 23, 30, 34, 1, 5, 10, 20, 27, 37, 43, 52, 1, 5, 12, 22, 32, 42, 50, 58, 68, 1, 6, 14, 27, 36, 47, 57, 68, 76, 87, 1, 6, 16, 30, 42, 54, 64, 75, 85, 96, 105

Offset

1,3

Links

Alois P. Heinz, Rows n = 1..14, flattened

Christopher Hunt Gribble, C++ program

Example

The triangle begins:
. k  1    2    3    4    5    6    7    8
n
1    1
2    1    2
3    1    2    3
4    1    3    4    7
5    1    3    5    9   11
6    1    4    7   12   18   23
7    1    4    8   15   23   30   34
8    1    5   10   20   27   37   43   52
...
T(4,3) = 4 because there are 4 partitions of a 4 X 3 rectangle into integer-sided squares with different numbers of parts:
  Partition                           Number of parts
  12 1 X 1 squares                           12
   8 1 X 1 squares, 1 2 X 2 square            9
   4 1 X 1 squares, 2 2 X 2 squares           6
   3 1 X 1 squares, 1 3 X 3 square            4

Maple

b:= proc(n, l) option remember; local i, k, s, t;
      if max(l[])>n then {} elif n=0 or l=[] then {0}
    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(v->v+1, 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:
T:= (n, k)-> nops(b(max(n, k), [0$min(n, k)])):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 08 2013

Mathematica

b[n_, l_List] := b[n, l] = Module[{i, k, s, t}, Which[Max[l] > n, {}, n == 0 || l == {}, {0}, Min[l] > 0, t = Min[l]; b[n - t, l - t], True, For[k = 1, k <= Length[l], k++, If [l[[k]] == 0 , Break[]]]; s = {}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s  ~Union~ Map[#+1&, b[n, Join[ l[[1 ;; k-1]], Array[1+i-k&, i-k+1], l[[i+1 ;; Length[l]]]]]]]; s]]; T[n_, k_] := Length[b[Max[n, k], Array[0&, Min[n, k]]]]; Table[Table[ T[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 24 2016, after Alois P. Heinz *)

Crossrefs

Diagonal = A226937.

Cf. A224697, A227998.

Sequence in context: A330661 A091438 A011794 * A073300 A104468 A293003

Adjacent sequences: A221637 A221638 A221639 * A221641 A221642 A221643

Keyword

nonn,tabl

Author

Christopher Hunt Gribble, Aug 08 2013

Extensions

More terms from Alois P. Heinz, Aug 08 2013

Status

approved