A181340 Number of compound perfect squared squares of order n up to symmetries of the square and its squared subrectangles.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 16, 46, 143, 412, 941, 2788, 7941, 22413, 62273, 172330, 466508, 1239742, 3257378, 8430928

Offset: 1

Author

Stuart E Anderson, Oct 13 2010, Oct 16 2010

Keywords

• nonn
• more
• hard

Comments

A squared rectangle (which may be a square) is a rectangle dissected into a finite number, two or more, of squares. If no two of these squares have the same size, the squared rectangle is perfect. A squared rectangle is compound if it contains a smaller squared rectangle. The order of a squared rectangle is the number of constituent squares. - Geoffrey H. Morley, Oct 17 2012

The smallest perfect compound squared square was published by T. H. Willcocks in 1948, has 24 squares and has one rectangle as a sub-dissection; however, it was not until 1982 that A. J. W. Duijvestijn, P. J. Federico and P. Leeuw proved it to be the lowest-order example.

In 2010 Stuart Anderson and Ed Pegg Jr generated all 2-connected minimum degree 3 planar graphs up and including 29 edges, using B. D. McKay and G. Brinkmann's plantri software, then applied electrical node analysis to the graphs to obtain complete counts of compound perfect squares in orders 24, 25, 26, 27 and 28, along with all the members of each equivalence class of each compound square.

In 2011 S. E. Anderson and Stephen Johnson commenced order 29 CPSSs, and processed all plantri generated 2-connected minimum degree 3 planar graph embeddings with up to 15 vertices. This left the largest graph class, the 16 vertex class. In 2012 S. E. Anderson processed the remaining graphs, using the Amazon Elastic Cloud supercomputer and new software which he wrote to find a(29). - Stuart E Anderson, Nov 30 2012

In May 2013 Lorenz Milla and Stuart Anderson enumerated a(30) (CPSSs of order 30), using the same process and software as used on order 29 CPSSs, with the addition of a technique recommended by William Tutte in his writings which resulted in a 3x speed-up of the search for perfect squared squares by factoring the determinant of the Kirchhoff/discrete Laplacian matrix of a graph into a product 2fS, where f is a squarefree number and S is a square number. - Stuart E Anderson, May 26 2013

From June to September 2013, Lorenz Milla further optimized the process and software and completed the computation required to enumerate all CPSSs of order 31 and 32. A second run with enhanced software was undertaken by Milla and Anderson as there was a possibility some CPSSs could have been missed on the first run. The second run found nothing new or different and confirmed the result. - Stuart E Anderson, Sep 29 2013

In April 2014, Jim Williams wrote software and used it to complete the enumeration of CPSS orders 33, 34, 35 and 36. - Stuart E Anderson, May 02 2016

In August 2018, Jim Williams completed the enumeration of CPSS orders 37, 38 and 39. - Stuart E Anderson, Sep 17 2018.

Examples

			From _Geoffrey H. Morley_, Oct 17 2012 (Start):
See MathWorld link for an explanation of Bouwkamp code.
a(24)=1 because all four compound perfect squares of order 24 are equivalent up to symmetries. They have side 175. The Bouwkamp code for one of them is (81,56,38)(18,20)(55,16,3)(1,5,14)(4)(9)(39)(51,30)(29,31,64)(43,8)(35,2)(33). (End)
		

References

• J. D. Skinner II, Squared Squares: Who's Who & What's What, published by the author, 1993. [Includes some compound perfect squares up to order 30.]
• T. H. Willcocks, Problem 7795 & solution, Fairy Chess Review 7 (1948) 97, 106.

Links

• S. E. Anderson, Compound Perfect Squared Squares (complete to order 36).
• S. E. Anderson, Compound Perfect Squared Squares of the Order Twenties, 2013; arXiv:1303.0599 [math.CO], 2013.
• Stuart E Anderson, CPSS discoveries attributed to the person or people who found them
• G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem., 58 (2007), 323-357.
• Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph.
• Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph [Cached copy, pdf file only, no active links, with permission]
• A. J. W. Duijvestijn, P. J. Federico and P. Leeuw, Compound perfect squares, Amer. Math. Monthly 89 (1982), 15-32. [The lowest order of a compound perfect square is 24.]
• N. D. Kazarinoff and R. Weitzenkamp, On the existence of compound perfect squared squares of small order, J. Combin. Theory Ser. B 14 (1973), 163-179. [A compound perfect squared square must contain at least 22 subsquares.]
• Lorenz Milla, Depiction of all CPSS until order 31
• Eric Weisstein's World of Mathematics, Perfect Square Dissection
• Wikipedia, Squaring the square
• Index entries for squared squares

Crossrefs

Cf. A217155 (counts symmetries of subrectangles as distinct).

Cf. A006983, A181735, A217152, A217153.

Extensions

Corrected last term from 142 to 143 to include cpss 1170C, added cross reference

Corrected last term from 143 to 144 to include cpss 1224d, incorrectly excluded as a duplicate in the initial count.

Corrected last term from 144 back to 143 after a recount from the original graphs established a bijection between exactly 948 non-isomorphic graphs and 948 isomers in 143 different CPSS arrangements. Gave usual bouwkampcode notation in examples. Removed redundant word "mathematically" from comments. - Stuart E Anderson, Jan 2012

Clarified the definition of 'number' in relation to the 'number' of compound squares, included the definition of 'perfect'. Excluded the trivial dissection from the sequence count. - Stuart E Anderson, May 2012

Definition corrected and offset changed to 1 by Geoffrey H. Morley, Oct 17 2012

a(29) added by Stuart E Anderson, Nov 30 2012

a(30) added by Stuart E Anderson, May 26 2013

a(31)-a(32) added by Stuart E Anderson, Sep 29 2013

a(33)-a(36), enumeration of these orders was completed by Jim Williams in 2014, added by Stuart E Anderson, May 02 2016

a(37)-a(39), enumeration of these orders was completed by Jim Williams in 2018, added by Stuart E Anderson, Sep 17 2018