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
Examples
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.
Links
- Alois P. Heinz, Antidiagonals n = 1..23, flattened (Antidiagonals n = 1..14 from Christopher Hunt Gribble)
- Christopher Hunt Gribble, C++ program
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: 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 *)