A formula for the number of structures composed of n squares

Click For Summary

Discussion Overview

The discussion revolves around the problem of determining the number of unique structures that can be formed by joining squares either side to side or corner to corner. It explores the complexity of this combinatorial problem, particularly in relation to symmetry and classification of structures. Participants seek insights and potential formulas related to this topic.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant describes the challenge of finding a formula for the number of structures composed of n squares, acknowledging the complexity of partition problems.
  • Another participant suggests considering the problem as a sequence and questions how to derive ##a_{n+1}## from ##a_n##.
  • A different participant mentions the possibility of extensive casework being necessary and expresses skepticism about finding a simple formula.
  • Another contribution references terminology from Wolfram MathWorld and Wikipedia, noting that there are various sequences in the OEIS related to the problem, but no established formula exists.
  • It is noted that the literature on polyominoes, which only allow edge-connections, is more extensive than that on the structures being discussed.

Areas of Agreement / Disagreement

Participants express uncertainty regarding the existence of a formula and acknowledge the complexity of the problem. There are competing views on how to approach the problem, with no consensus reached on a specific method or solution.

Contextual Notes

The discussion highlights the limitations of existing approaches, including the dependence on definitions of symmetry and structure, as well as the unresolved nature of deriving a formula for the number of structures.

ddddd28
Messages
73
Reaction score
4
Hello,
The problem I came up with deals with the structures that can be obtained by joining squares side to side or corner to corner. Specifically to this problem, structures, that are symmetrical to each other, are regarded the same.
Ideally, I am looking for a formula that will tell how many structures can be made with n given squares. However, I am aware of the problem's complexity (this is the nature of partition problems...), so,at least, it will be comforting, if someone comes up with an insight about what happens "behind the scenes" in the problem.
One can easily observe that the n+1 structures can be generated from the n structures. By applying this principle, I was able to draw all the unique structures up to n=5. Then, I tried to classify them by the minimal rectangle that encloses the structure, and still lead to no progress.
I ran out of new strategies for a solution, and I am asking for another perspective on the problem.
 

Attachments

  • IMG-20180623-WA0007.jpeg
    IMG-20180623-WA0007.jpeg
    32.6 KB · Views: 513
Mathematics news on Phys.org
Try thinking of it as a sequence given ##a_n## what is ##a_{n+1}## ?
 
You have 5 numbers - did you search for the beginning of the sequence on OEIS?

These problems often end up in a lot of casework done by a computer.
jedishrfu said:
Try thinking of it as a sequence given ##a_n## what is ##a_{n+1}## ?
I would be very surprised if you get a nice formula for that.
 
Wolfram mathworld calls it a polyplet and Wikipedia a pseudo-polyomino or polyking. The OEIS also has various sequences, depending on wether rotations and/or reflections will result in the same figure, and what to do with holes. No one has any formula.
There's much more literature on poliyominoes, that only allow edge-connections.
 
  • Like
Likes   Reactions: mfb

Similar threads

  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 13 ·
Replies
13
Views
13K
  • · Replies 17 ·
Replies
17
Views
7K
  • · Replies 29 ·
Replies
29
Views
6K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 6 ·
Replies
6
Views
3K