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,2

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

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

Formula

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

Example

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.

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 *)

Crossrefs

Row sums give: A226897.

Cf. A034295.

Sequence in context: A051928 A347486 A335337 * A327352 A050156 A191584

Adjacent sequences: A226903 A226904 A226905 * A226907 A226908 A226909

Keyword

nonn,hard,tabl

Author

Christopher Hunt Gribble, Jun 21 2013

Status

approved