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