login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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

      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.

License Agreements, Terms of Use, Privacy Policy. .

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