This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A034295 Number of different ways to divide an n X n square into sub-squares, considering only the list of parts. 24
 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 (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 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       fi     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: A322118 A323067 A140108 * A056354 A072534 A056292 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 Corrected and extended by Jon E. Schoenfield, Sep 19 2008 Edited by N. J. A. Sloane, Apr 12 2013, at the suggestion of Paolo P. Lava a(11) corrected by Alois P. Heinz, Apr 15 2013 a(13) from Alois P. Heinz, Apr 19 2013 a(14) from Christopher Hunt Gribble, Oct 26 2013 a(15) and a(16) from Fidel I. Schaposnik, May 04 2015 a(17)-a(23) from Holger Langenau, Sep 20 2017 a(24) from Michael De Vlieger, May 04 2018, from paper written by Holger Langenau a(25) and a(26) from Holger Langenau, May 14 2018 a(27) from Holger Langenau, Apr 15 2019 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 20 10:00 EDT 2019. Contains 328257 sequences. (Running on oeis4.)