A054247

So, A054247. There’s a formula:

$a(n) = \frac{1}{8}(2^{n^2}+2\times 2^{n^2/4}+3\times 2^{n^2/2}+2\times 2^{(n^2+n)/2})$ if $n$ is even and

$a(n) =\frac{1}{8}(2^{n^2}+2\times 2^{(n^2+3)/4}+2^{(n^2+1)/2}+4\times 2^{(n^2+n)/2})$ if $n$ is odd.

Can we derive that?

Let’s look at the simplest nontrivial case, $n = 2$ . There are $2^{(2^2)} = 16$ possible soups. But some of these are equivalent to others under rotation or reflection… and some aren’t.

That is, define the following transformations:

r0 = I, the identity transformation
r1, 90° rotation clockwise
r2, 180° rotation
r3, 270° rotation clockwise (or 90° counterclockwise)
s0, reflection in a vertical axis
s1, 90° rotation clockwise then reflection in a vertical axis (equivalent to reflection in a NW–SE diagonal axis)
s2, 180° rotation then reflection in a vertical axis (equivalent to reflection in a horizontal axis)
s3, 270° rotation clockwise (or 90° counterclockwise) then reflection in a vertical axis (equivalent to reflection in a NE–SW diagonal axis)

Two configurations are equivalent if applying any of these transformations to one results in the other.

A configuration can have various symmetries, wherein applying one or more of these transformations to it results in the same configuration. For example, any transformation applied to the all cells dead pattern gives the same pattern back. That means that pattern isn’t equivalent to any other pattern. Likewise the all cells live pattern.

The following symmetries are possible:

r1r2r3s0s1s2s3: invariant under any of these transformations. (Everything is invariant under r0 = I so it’s not mentioned.) 2 by 2 example:A pattern with this symmetry is equivalent to no other patterns.
r1r2r3: Invariant under any rotation but not under reflection. No 2 by 2 or 3 by 3 pattern has this symmetry but here’s a 4 by 4 that does:
A pattern with this symmetry is equivalent to one other pattern (its mirror image).
r2s0s2: Invariant under 180° rotation or reflection in a vertical or horizontal axis. No 2 by 2 instances. Here is a 3 by 3:A pattern with this symmetry is equivalent to one other pattern (its 90° rotation).
r2s1s3: Invariant under 180° rotation or reflection in a diagonal axis. 2 by 2 example:A pattern with this symmetry is equivalent to one other pattern (its reflection in a vertical or horizontal axis, or its 90° rotation — both are the same).
r2: Invariant under 180° rotation. 3 by 3 example (there are no 2 by 2):A pattern with this symmetry is equivalent to three other patterns (its reflection in a vertical or horizontal axis, its 90° rotation, and its reflected 90° rotation).
s0: Invariant under reflection in a vertical axis. 2 by 2 example:A pattern with this symmetry is equivalent to three other patterns (its reflection in a horizontal axis, or its 180° rotation — both are the same — and its 90° or 270° rotations).
s1: Invariant under reflection in a NW–SE diagonal axis. 2 by 2 example:A pattern with this symmetry is equivalent to three other patterns (its 90°, 180°, or 270° rotations).
s2: Invariant under reflection in a horizontal axis. Equivalent to three other patterns.
s3: Invariant under reflection is a NE–SW diagonal axis. Equivalent to three other patterns.
I: Not invariant under any transformation. 3 by 3 example (there are no 2 by 2): Equivalent to seven other patterns (its transformation under r1, r2, r3, s0, s1, s2, or s3).

That there are no other symmetries may not be entirely obvious. But do some thinking: For instance, any pattern invariant under r1 must be invariant under r2 and r3, because the latter are just r1 done twice or three times. Likewise any pattern invariant under r1 and s0 must be invariant under s1, s2, and s3, because these are just r1 once, twice, or three times followed by s0. Similarly r2 and s0 imply s2, and r2 and s1 imply s3.

Think about a large square pattern that is invariant under r1r2r3s0s1s2s3. Under those transformations the corners map onto the other corners; the cells left of the center line on the top row map into the cells on the right of the center line on the top row as well as all the cells in the bottom row and left and right edges; and so on. Specify only the cells on or above the main diagonal in the upper left quadrant of the pattern and you’ve specified the whole thing. In an $n\times n$ pattern where $n$ is even, the number of cells you need to specify is $T(n/2)$ where $T(m) = m(m+1)/2$ is the $m$ th triangular number. Where $n$ is odd, the number of cells is $T((n+1)/2)$ . That means the number of such patterns is $2^{T(n/2)}$ or $2^{T((n+1)/2}$ . None is equivalent to any other pattern, so all are added into the number of unique patterns after reflections and rotations.

For a pattern invariant under r1r2r3, if $n$ is even you need to specify all the cells in one quadrant; there are $(n/2)^2$ such cells. For $n$ odd, r1 takes the bottom row of the top left quadrant into the right side of the same quadrant, so in that row all but the center cell of the pattern are constrained: you specify all the cells of one quadrant, except one row, except one cell: $((n+1)/2)^2-n/2+1$ cells. So there are then $2^{((n/2)^2)}$ or $2^{((n+1)/2)^2-n/2+1}$ possibilities — but they include all the r1r2r3s0s1s2s3 patterns too. The number of patterns invariant under r1r2r3 but not r1r2r3s0s1s2s3 is $2^{((n/2)^2)}-2^{T(n/2)}$ or $2^{((n+1)/2)^2-n/2+1}-2^{T((n+1)/2}$ . Each is equivalent to one other pattern, so the number added into the total after reflections and rotations is half of this.

Next is r2s0s2. This maps the left side of the top row to the right side of the top row and both sides of the bottom row, and so on. Here you have to specify all the cells in one quadrant if $n$ is even or odd. This means there are $2^{((n/2)^2)}$ or $2^{(((n+1)/2)^2)}$ possibilities, but again you have to subtract off the r1r2r3s0s1s2s3 patterns, leaving $2^{((n/2)^2)}-2^{T(n/2)}$ or $2^{(((n+1)/2)^2)}-2^{T((n+1)/2}$ . Again, divide by 2 for the contribution to the total after reflections and rotations.

And so on. For each of the symmetries you can figure out how many cells you have to specify, which tells you how many patterns there are; then you have to subtract off the number that have already been counted under higher symmetries, then divide by the number of equivalent patterns for that symmetry. Rather tedious to do all of it algebraically for general $n$ , so I won’t, but you have the ammunition if you want to. I have found the figures for 2 by 2 through 4 by 4 by hand and with a brute force Python script, and they agree:

	2×2		3×3		4×4
	Patterns	Unique	Patterns	Unique	Patterns	Unique
r1r2r3s0s1s2s3	2	2	8	8	8	8
r1r2r3					8	4
r2s0s2			8	4	8	4
r2s1s3	2	1	8	4	56	28
r2			8	2	176	44
s0	2	0.5	48	12	240	60
s1	4	1	48	12	960	240
s2	2	0.5	48	12	240	60
s3	4	1	48	12	960	240
I			288	36	62880	7860
Total	16	6	512	102	65536	8548

You can see how rapidly the number of asymmetric (I) patterns comes to dominate the total, so that the number of unique patterns after reflection and rotation approaches $2^{(n^2)}/8$ .

Edit: What the heck, I made a Google spreadsheet with the figures for square soups up to 16 by 16.

Share this:

Related

Leave a comment Cancel reply