Given n squares, in how many ways can they be contiguously arranged into a single shape?

Question

Context: At school today, a friend of mine ripped up a piece of paper he had written on. I was considering the number of possible ways I could rearrange these individual pieces to try to reconstruct the whole, and the runtime complexity of such a de-rearrangement. However, that’s a question for the theoretical CS StackExchange, not here.

What I’m interested in is a more simplified problem: If some polygon in a Euclidean space which only contains right-angles is cut into equally-sized individual squares, into how many possible configurations can these squares be rearranged, allowing only rotation and translation, and no reflections (since a reflection of an actual piece of paper would imply flipping over whatever text is written on it)?

I thought of using graph theory to analyze this–that is, each square node can be in 4 possible states, because it can be rotated into 4 separate states ($4^{n}$ possible rotational states overall) and each node can have at most 4 edges extending from it (since equally-sized squares can touch at most 4 others).

However, note that if you have square-nodes A, B, and C, and they are connected in a line from left to right like ABC, that is a different configuration from CBA even though each individual letter has an edge connecting it to the same other nodes, which doesn’t align with the way that graph theory equates any two such graphs regardless of their physical representation. ABC is the same thing, however, to CBA with each node rotated twice if I’m not mistaken, if you wish to think of all rotations of the overall structure as the same thing.

I’m thinking that maybe each edge can also be labeled with a number 1-4 that represents the direction in which the contact between the two squares occurs, but at this point I’m stuck because I have no formal training in graph theory. This certainly seems like a problem within combinatorics, in which I have very minor experience (I learned a little bit for Academic Decathlon last year). I think the problem will be more easily represented by looking at a few cases.

Case 1: 1 square

Result: Either 1 or 4 ways, depending on whether you wish to consider rotations of the entire structure to be the same thing. From now on, for simplicity’s sake, I will say that every rotation of the entire structure is a separate structure.

Case 2: 2 squares

Result: Let’s call these squares A and B. A can connect to B’s left, right, top, or bottom side. A being on B’s left is the same as B being on A’s right. There are thus 4 connection states, and for each square, there are 4 rotation states. That’s $4^2 = 16$ rotation states overall, multiplied by the 4 connection states, giving $4^3 = 64$ states overall.

Case 3: 3 squares

Result: Let’s call these squares A, B, and C. I think that each outcome might be able to be represented by a tree, where at each point I choose whether to include or exclude a square from the next side.

Each time I make a choice to include another square, I have one fewer squares to choose from. I must, however, choose every square, because I’m not making a discontinuous or incomplete shape here. Note that if two squares touch the same other square, they do not touch each other, so contact is never transitive. However, if the difference between the sides chosen on a given square (A) for two other squares (B and C) has an absolute value of 1, then a fourth square (D) is able to touch both B and C. This makes a tree very confusing to deal with.

So, at square A, I can choose either B or C to go on either side 1, 2, 3, or 4. Once I place 1 of those 2 squares, I have only 1 square left to choose from that can go on 1 of the 3 remaining sides of the other two squares, giving me 6 choices. If I choose B the first time around, then that gives me 4 possible position-configurations, and then after placing C I can actualize the next 6 possible configurations one step down the line. This gives $4*6 = 24$ possible position configurations when choosing B first.

The same follows with C, meaning that there are actually $4*6*2 = 48$ possible position-configurations.

With the 4 possible rotations for each square, I have $4^3 = 64$ rotation-states for the figure, giving $64*48 = 3,072$ possible configuration states for the three squares in the image.

If, hypothetically (though not applicable in my usage case), we were allowed to reflect each of these squares as well, you would have to consider the 4 axes of symmetry on each of the squares, giving another $4^3 = 64$ reflection states for the shape, which when multiplied by our previous $3,072$ states gives $196,608$ possible states for the image. I’m not sure which sets of rotations or reflections would be equivalent (I’d have to learn some group theory to predict that), but that’s a lot for 3 squares.

Case 4: 4 squares

Results: This one is a bit harder. Since the first three squares can be placed in an L-shape, the fourth square can be placed to fill in the corner, which can be reached two separate ways by placing the square on one side of two separate squares respectively. I don’t know how to calculate this one.

Overall: I think it would be nice if anyone could tell me of a more general view of this problem and its solution (for example, using any polygon as the decomposed shape which can be arranged into a gapless tiling like a triangle, square, or hexagon, and considering the options based on its number of sides and its number of symmetries).

Edit: I just realized that in the case of the three squares, I can also perform a similar process of choice starting with each of the three squares individually rather than the others. This means that I have a separate set of $3,072$ configurations starting with each square, giving me $3*3072 = 9,216$ arrangements with rotation, and $9,216*64 = 589,824$ reflection-allowing states.

Answer 1

This is a partial result. Just an upper bound.

You can describe your problem as follows:

• Draw a path from $(0,0)$ to $(a_n,b_n)\in \Bbb Z\times\Bbb Z$, with vertical or horizontal segments of length $1$, that doesn't cut itself. (Or equivalently, give a $n$-tuple of different pairs of integers $\{(a_k,b_k)\}_{k=1}^n$ such that $(a_1,b_1)=(0,0)$ and $|a_k-a_{k-1}|+|b_k-b_{k-1}|=1$, for $2\le k\le n$). The number $n$ is, of course, the number of pieces of paper.
• If for two such sequences $S_1$ and $S_2$, there is a translation that maps $S_1$ to $S_2$ they are considered the same. Since the first and the last point of the sequence are crearly different from the others, you can make that just dividing by $2$ if $n>1$.
• IMPORTANT EDIT: Yesterday, I didn't realize that two shapes are considered the same if one of them can be rotated to get the other. Fortunately, no shape remains unchanged after a rotation of $90$, $180$ or $270$ degrees. BUT a path could be mapped to another by rotation or by translation: for example, the path $(0,0)-(1,0)-(2,0)$ can be mapped into $(0,0)-(-1,0)-(-2,0)$ by a translation $(-2,0)$ or by rotation of $180^o$. This does not happens with every path, only with paths that have central symmetry.
• Multiply the number of sequences by $4^n$, because each piece of paper can be put in four different ways.
• Multiply again by $n!$ to account the order of the pieces.

The hardest part of the problem seems to be avoiding to count the paths that cut themselves. Let call, for brevity simple paths the paths that don't cut themselves. For example, if the four first points are $(0,0)$, $(1,0)$, $(1,1)$, $(0,1)$ we have two choices for the fifth, but if they are $(0,0)$, $(1,0)$, $(2,0)$ and $(3,0)$ we have three. Of course, the number of paths for $n\ge 2$ is equal or lesser than $4\cdot 3^{n-2}$ (you can't go back). So the number of configurations for $n\ge 2$ would be $$4^nn!\frac{\text{number of simple paths that have no central symmetry}+\dfrac12\text{number of simple paths that have central symmetry}}{2}\le\dfrac{4^{n+1}3^{n-2}n!}{2}=2^{2n+1}3^{n-2}n!$$