A formula for the number of structures composed of n squares

In summary, the conversation discusses a problem involving symmetrical structures made by joining squares, and the search for a formula to determine the number of structures that can be made with a given number of squares. The conversation explores different approaches and strategies, including looking at the problem as a sequence and searching for patterns, but ultimately concludes that a nice formula is unlikely due to the complexity of the problem. Various resources and terms, such as polyplets, pseudo-polyominoes, and OEIS, are mentioned as potential sources of information and patterns.
  • #1
73
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: 424
Mathematics news on Phys.org
  • #3
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.
 
  • #4
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.
 

Suggested for: A formula for the number of structures composed of n squares

Replies
2
Views
968
Replies
5
Views
590
Replies
7
Views
1K
Replies
14
Views
810
Replies
3
Views
658
Replies
4
Views
680
Back
Top