A034295 - OEIS

A034295

Number of different ways to divide an n X n square into sub-squares, considering only the list of parts.

1, 2, 3, 7, 11, 31, 57, 148, 312, 754, 1559, 3844, 7893, 17766, 37935, 83667, 170165, 369698, 743543, 1566258, 3154006, 6424822, 12629174, 25652807, 49802454, 98130924, 189175310, 368095797

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Number of ways an n X n square can be cut into integer-sided squares: collections of integers {a_i} so that squares of length a_i tile an n X n square.

This ignores the way the squares are arranged. We are only counting the lists of parts (compare A045846).

Also applies to the partitions of an equilateral triangle of length n. - Robert G. Wilson v

LINKS

Table of n, a(n) for n=1..28.

Alois P. Heinz, List of different ways to divide a 13 X 13 square into sub-squares

Alois P. Heinz, More ways to divide an 11 X 11 square into sub-squares

Holger Langenau, Squaring the square: New methods for determining the number of perfect square packings, 2018.

Jon E. Schoenfield, Table of solutions for n <= 12 (Caution: this table is missing 6 of the ways to divide an 11 X 11 square into sub-squares! Please see the Alois P. Heinz link listing those six ways. Thanks to Alois for catching this! -- Jon E. Schoenfield)

N. J. A. Sloane, Drawing to illustrate a(1)-a(4)

EXAMPLE

From Jon E. Schoenfield, Sep 18 2008: (Start)

a(3) = 3 because the 3 X 3 square can be divided into sub-squares in 3 different ways: a single 3 X 3 square, a 2 X 2 square plus five 1 X 1 squares, or nine 1 X 1 squares.

There are a(5) = 11 different ways to divide a 5 X 5 square into sub-squares:

1. 25(1 X 1)

2. 1(2 X 2) + 21(1 X 1)

3. 2(2 X 2) + 17(1 X 1)

4. 3(2 X 2) + 13(1 X 1)

5. 4(2 X 2) + 9(1 X 1)

6. 1(3 X 3) + 16(1 X 1)

7. 1(3 X 3) + 1(2 X 2) + 12(1 X 1)

8. 1(3 X 3) + 2(2 X 2) + 8(1 X 1)

9. 1(3 X 3) + 3(2 X 2) + 4(1 X 1)

10. 1(4 X 4) + 9(1 X 1)

11. 1(5 X 5)

a(9) = 312 because the 9 X 9 square can be divided into 312 different combinations of sub-squares such as three 4 X 4 squares plus thirty-three 1 X 1 squares, etc. (End)

MAPLE

b:= proc(n, l) option remember; local i, k, s;

if max(l[])>n then {} elif n=0 then {0}

elif min(l[])>0 then (t->b(n-t, map(h->h-t, l)))(min(l[]))

else for k while l[k]>0 do 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

end:

a:= n-> nops(b(n, [0$n])):

seq(a(n), n=1..9); # Alois P. Heinz, Apr 15 2013

MATHEMATICA

$RecursionLimit = 1000; b[n_, l_] := b[n, l] = Module[{i, k, m, s, t}, Which[Max[l]>n, {}, n == 0 || l == {}, {{}}, Min[l]>0, t = Min[l]; b[n-t, l-t], True, k = Position[l, 0, 1][[1, 1]]; s = {}; For[i = k, i <= Length[l] && l[[i]] == 0, i++, s = s ~Union~ Map[Function[x, Sort[Append[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_] := a[n] = b[n, Array[0&, n]] // Length; Table[Print[a[n]]; a[n], {n, 1, 12} ] (* Jean-François Alcover, Feb 18 2014, after Alois P. Heinz *)

CROSSREFS

Cf. A045846, A224239.

Cf. A014544, A129668 (these both involve cubes).

Main diagonal of A224697.

Sequence in context: A349420 A323067 A140108 * A338320 A056354 A072534

Adjacent sequences: A034292 A034293 A034294 * A034296 A034297 A034298

KEYWORD

nonn,hard,nice,more

AUTHOR

Erich Friedman, Dec 11 1999

EXTENSIONS

More terms from Sergio Pimentel, Jun 03 2008