A230505 T(n,k,s) is the number of parts of each size in the set of partitions of an n X k rectangle into integer-sided squares with side s, considering only the list of parts; irregular triangle T(n,k,s), n >= k >= s >= 1, read by rows.

1, 2, 4, 1, 3, 8, 1, 14, 1, 1, 4, 12, 3, 27, 3, 1, 47, 10, 1, 1, 5, 18, 3, 41, 4, 2, 85, 13, 3, 1, 134, 16, 4, 1, 1, 6, 24, 6, 62, 7, 4, 135, 27, 5, 3, 250, 40, 13, 3, 1, 415, 82, 24, 6, 1, 1, 7, 32, 6, 87, 9, 5, 204, 34, 8, 4, 381, 53, 18, 5, 3, 717, 127, 45, 13, 4, 1

Offset: 1

Author

Christopher Hunt Gribble, Oct 22 2013

Keywords

• nonn
• tabf

Examples

			T(5,4,2) = 13 because there are 13 2 X 2 squares in the 9 partitions of a 5 X 4 rectangle into integer-sided squares.  The partitions are:
.         Square side
.         1  2  3  4
1        20  0  0  0
2        16  1  0  0
3        12  2  0  0
4         8  3  0  0
5         4  4  0  0
6        11  0  1  0
7         7  1  1  0
8         3  2  1  0
9         4  0  0  1
Total    85 13  3  1
The irregular triangle begins:
n,k          Square Side (s)
.       1   2   3   4   5   6   7 ...
1,1     1
2,1     2
2,2     4   1
3,1     3
3,2     8   1
3,3    14   1   1
4,1     4
4,2    12   3
4,3    27   3   1
4,4    47  10   1   1
5,1     5
5,2    18   3
5,3    41   4   2
5,4    85  13   3   1
5,5   134  16   4   1   1
6,1     6
6,2    24   6
6,3    62   7   4
6,4   135  27   5   3
6,5   250  40  13   3   1
6,6   415  82  24   6   1   1
7,1     7
7,2    32   6
7,3    87   9   5
7,4   204  34   8   4
7,5   381  53  18   5   3
7,6   717 127  45  13   4   1
7,7  1102 165  60  16   6   1   1
		

Links

• Alois P. Heinz, Rows n = 1..78, flattened (Rows 1..42 from Christopher Hunt Gribble)
• Christopher Hunt Gribble, C++ program

Crossrefs

Cf. A034295, A224697, A225622.

Programs

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+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:
T:= (n, k)->(p->seq(coeff(p, x, v), v=1..k))(add(h, h=b(n, [0$k]))):
seq(seq(T(n, k), k=1..n), n=1..9);  # Alois P. Heinz, Oct 24 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[# + x^(1 + i - k)&, b[n, Join[l[[1 ;; k - 1]], Array[1 + i - k&, i - k + 1], l[[i + 1 ;; Length[l]]]]]]]; s]]; T[n_, k_] := Function[p, Table[Coefficient[p, x, v], {v, 1, k}]][b[n, Array[0&, k]] // Total]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 9}] // Flatten (* Jean-François Alcover, Jan 24 2016, after Alois P. Heinz *)

Formula

Sum_{s=1..k} T(n,k,s) = A225622(n,k).

Sum_{s=1..k} T(n,k,s)*s^2 = n*k*A224697(n,k).