A034295 - OEIS

%I #136 Jul 31 2020 06:46:29

%S 1,2,3,7,11,31,57,148,312,754,1559,3844,7893,17766,37935,83667,170165,

%T 369698,743543,1566258,3154006,6424822,12629174,25652807,49802454,

%U 98130924,189175310,368095797

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

%C 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.

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

%C Also applies to the partitions of an equilateral triangle of length n. - _Robert G. Wilson v_

%H Alois P. Heinz, <a href="/A034295/a034295_2.txt">List of different ways to divide a 13 X 13 square into sub-squares</a>

%H Alois P. Heinz, <a href="/A034295/a034295_1.txt">More ways to divide an 11 X 11 square into sub-squares</a>

%H Holger Langenau, <a href="https://nbn-resolving.org/urn:nbn:de:bsz:ch1-qucosa-233031">Squaring the square: New methods for determining the number of perfect square packings</a>, 2018.

%H Jon E. Schoenfield, <a href="/A034295/a034295.txt">Table of solutions for n <= 12</a> (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)

%H N. J. A. Sloane, <a href="/A034295/a034295.jpg">Drawing to illustrate a(1)-a(4)</a>

%e From _Jon E. Schoenfield_, Sep 18 2008: (Start)

%e 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.

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

%e    1. 25(1 X 1)

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

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

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

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

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

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

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

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

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

%e   11.  1(5 X 5)

%e 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)

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

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

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

%p     else for k while l[k]>0 do od; s:={};

%p          for i from k to nops(l) while l[i]=0 do s:=s union

%p              map(v->v+x^(1+i-k), b(n, [l[j]$j=1..k-1,

%p                  1+i-k$j=k..i, l[j]$j=i+1..nops(l)]))

%p          od; s

%p       fi

%p     end:

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

%p seq(a(n), n=1..9);  # _Alois P. Heinz_, Apr 15 2013

%t $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_ *)

%Y Cf. A045846, A224239.

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

%Y Main diagonal of A224697.

%K nonn,hard,nice,more

%O 1,2

%A _Erich Friedman_, Dec 11 1999

%E More terms from _Sergio Pimentel_, Jun 03 2008

%E Corrected and extended by _Jon E. Schoenfield_, Sep 19 2008

%E Edited by _N. J. A. Sloane_, Apr 12 2013, at the suggestion of _Paolo P. Lava_

%E a(11) corrected by _Alois P. Heinz_, Apr 15 2013

%E a(13) from _Alois P. Heinz_, Apr 19 2013

%E a(14) from _Christopher Hunt Gribble_, Oct 26 2013

%E a(15) and a(16) from _Fidel I. Schaposnik_, May 04 2015

%E a(17)-a(23) from _Holger Langenau_, Sep 20 2017

%E a(24) from _Michael De Vlieger_, May 04 2018, from paper written by _Holger Langenau_

%E a(25) and a(26) from _Holger Langenau_, May 14 2018

%E a(27) from _Holger Langenau_, Apr 15 2019

%E a(28) from _Holger Langenau_, Jun 17 2020

%E a(28) corrected by _Holger Langenau_, Jul 31 2020