A225622 A(n,k) is the total number of parts in the set of partitions of an n X k rectangle into integer-sided squares, considering only the list of parts; square array A(n,k), n>=1, k>=1, read by antidiagonals.

1, 2, 2, 3, 5, 3, 4, 9, 9, 4, 5, 15, 16, 15, 5, 6, 21, 31, 31, 21, 6, 7, 30, 47, 59, 47, 30, 7, 8, 38, 73, 102, 102, 73, 38, 8, 9, 50, 101, 170, 156, 170, 101, 50, 9, 10, 60, 142, 250, 307, 307, 250, 142, 60, 10, 11, 75, 185, 375, 460, 529, 460, 375, 185, 75, 11

Offset

1,2

Links

Alois P. Heinz, Antidiagonals n = 1..23, flattened (Antidiagonals n = 1..14 from Christopher Hunt Gribble)

Christopher Hunt Gribble, C++ program

Formula

A(n,1) = A000027(n) = n.

A(n,2) = A195014(n) = (n+1)(5n+3)/8 when n is odd

and 5n(n+2)/8 when n is even.

Example

The square array starts:
1    2    3    4    5    6    7    8    9   10   11   12 ...
2    5    9   15   21   30   38   50   60   75   87  105 ...
3    9   16   31   47   73  101  142  185  244  305  386 ...
4   15   31   59  102  170  250  375  523  726  962 ...
5   21   47  102  156  307  460  711 1040 1517 ...
6   30   73  170  307  529  907 1474 2204 ...
7   38  101  250  460  907 1351 2484 ...
8   50  142  375  711 1474 2484 ...
9   60  185  523 1040 2204 ...
...
A(3,2) = 9 because there are 9 parts overall in the 2 partitions of a 3 X 2 rectangle into squares with integer sides.  One partition comprises 6 1 X 1 squares and the other 2 1 X 1 squares and 1 2 X 2 square giving 9 parts in total.

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:
A:= (n, k)-> add(coeff(add(j, j=b(max(n, k),
            [0$min(n, k)])), x, i), i=1..n):
seq(seq(A(n, 1+d-n), n=1..d), d=1..15); # Alois P. Heinz, Aug 04 2013

Mathematica

$RecursionLimit = 1000; 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, True, k++, If[l[[k]] == 0, Break[]]]; s = {}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s ~Union~ Map[Function[{v}, v + 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_] := Sum[Coefficient[Sum[j, {j, b[Max[n, k], Array[0&, Min[n, k]]]}], x, i], {i, 1, n}]; Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 15}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

Crossrefs

Diagonal = A226897.

Cf. A034295, A224697, A225542.

Sequence in context: A252829 A014430 A360196 * A196436 A197199 A295120

Adjacent sequences: A225619 A225620 A225621 * A225623 A225624 A225625

Keyword

nonn,tabl

Author

Christopher Hunt Gribble, Aug 04 2013

Status

approved