login
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, 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
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.
Sequence in context: A330661 A091438 A011794 * A073300 A104468 A293003
KEYWORD
nonn,tabl
AUTHOR
EXTENSIONS
More terms from Alois P. Heinz, Aug 08 2013
STATUS
approved