A226906 Triangle read by rows: T(n,k) is the total number of parts of size k^2, 1 <= k <= n, in the set of partitions of an n X n square lattice into squares, considering only the list of parts.

1, 4, 1, 14, 1, 1, 47, 10, 1, 1, 134, 16, 4, 1, 1, 415, 82, 24, 6, 1, 1, 1102, 165, 60, 16, 6, 1, 1, 3076, 621, 169, 90, 22, 8, 1, 1, 7986, 1361, 577, 194, 80, 28, 8, 1, 1, 20930, 4254, 1464, 643, 294, 114, 35, 10, 1, 1, 50755, 9494, 3667, 1491, 858, 297, 148, 41, 10, 1, 1

Offset: 1

Author

Christopher Hunt Gribble, Jun 21 2013

Keywords

• nonn
• hard
• tabl

Comments

The sequence was derived from the documents in the Links section. The documents are first specified in the Links section of A034295.

The triangle is presented below.

\ k 1 2 3 4 5 6 7 8 9 10 11 12 13

n

1 1

2 4 1

3 14 1 1

4 47 10 1 1

5 134 16 4 1 1

6 415 82 24 6 1 1

7 1102 165 60 16 6 1 1

8 3076 621 169 90 22 8 1 1

9 7986 1361 577 194 80 28 8 1 1

10 20930 4254 1464 643 294 114 35 10 1 1

11 50755 9494 3667 1491 858 297 148 41 10 1 1

12 129977 27241 10474 4858 2239 1272 454 203 51 12 1 1

13 305449 60086 24702 11034 5918 2874 1474 592 249 58 12 1 1

Examples

			For n = 3, the partitions are:
Square side 1 2 3
            9 0 0
            5 1 0
            0 0 1
Total      14 1 1
So T(3,1) = 14, T(3,2) = 1, T(3,3) = 1.
		

Links

• Christopher Hunt Gribble, Rows n = 1..13, flattened
• Jon E. Schoenfield, Table of solutions for n <= 12
• Alois P. Heinz, More ways to divide an 11 X 11 square into sub-squares
• Alois P. Heinz, List of different ways to divide a 13 X 13 square into sub-squares

Crossrefs

Row sums give: A226897.

Cf. A034295.

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-> seq(coeff(add(j, j=b(n, [0$n])), x, i), i=1..n):
seq(T(n), n=1..10);  # Alois P. Heinz, Jun 21 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_] := Table[Coefficient[Sum[j, {j, b[n, Array[0 &, n]]}], x, i], {i, 1, n}]; Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 24 2016, after Alois P. Heinz *)

Formula

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