# Number of possible unique patterns of $5$ points on an $8\times 8$ grid.

I'm after a specific answer and workings/formula for the number of possible unique patterns that $$5$$ points can have on an $$8\times 8$$ grid. The pattern must be unique and not match another pattern when it's rotated or mirrored. Can the workings be explained in laymans terms? Thanks

• Are there $64$ or $81$ possible locations for the points? (In other words, do I place the pieces like in chess or like in go?) – Parcly Taxel Mar 14 at 13:16
• As well as that, can more than one point occupy a grid space? – Parcly Taxel Mar 14 at 13:23
• Hey Parcly, its 64 like chess. only 1 point per slot. 64 available positions – Andre Mar 14 at 23:19

## 1 Answer

We solve the case of the points going into the slots between the grid, so there are $$64$$ slots. We put at most one point into one slot. We use the Polya Enumeration Theorem (PET), which requires the cycle index of the action of the symmetries on the slots. Supposing the grid is $$n\times n$$ with $$n$$ even we get for the rotations, first, the identity:

$$a_1^{n^2}.$$

Next, two rotations by $$90$$ degrees and $$270$$ degrees:

$$2 a_4^{n^2/4}.$$

The rotation by $$180$$ degrees:

$$a_2^{n^2/2}.$$

For reflections there is the horizontal and the vertical reflection:

$$2 a_2^{n^2/2}$$

and the reflection in the two diagonals:

$$2 a_1^n a_2^{(n^2-n)/2}.$$

We get the cycle index

$$Z(G) = \frac{1}{8} \left(a_1^{n^2} + 2 a_4^{n^2/4} + a_2^{n^2/2} + 2 a_2^{n^2/2} + 2 a_1^n a_2^{(n^2-n)/2}\right)$$

or

$$\bbox[5px,border:2px solid #00A000]{Z(G) = \frac{1}{8} \left(a_1^{n^2} + 2 a_4^{n^2/4} + 3 a_2^{n^2/2} + 2 a_1^n a_2^{(n^2-n)/2}\right).}$$

For an odd number of points call is $$m$$ we thus have

$$[z^m] Z(G; 1+z) \\= [z^m] \frac{1}{8} \left((1+z)^{n^2} + 2 (1+z^4)^{n^2/4} + 3 (1+z^2)^{n^2/2} + 2 (1+z)^n (1+z^2)^{(n^2-n)/2}\right) \\ = [z^m] \frac{1}{8} \left((1+z)^{n^2} + 2 (1+z)^n (1+z^2)^{(n^2-n)/2}\right).$$

This is

$$\bbox[5px,border:2px solid #00A000]{\frac{1}{8} {n^2\choose m} + \frac{1}{4} \sum_{k=0}^{n/2-1} {n\choose 2k+1} {(n^2-n)/2\choose (m-2k-1)/2}}$$

where $$n$$ is even and $$m$$ is odd.

We get for $$n=8$$ and $$m=5$$ the answer

$$\bbox[5px,border:2px solid #00A000]{954226.}$$

• Awesome thanks Marko! – Andre Mar 14 at 23:17
• Hey Marko, sorry but 1 adjustment to add a layer of complexity, what if in 2 opposing corners 2 of the points are allocated so the other 3 are left to occupy the remaining 62 positions. is it possible to work out the unique arrangements of those remaining 3 points? – Andre Mar 14 at 23:23
• These are diagonally opposed corners? – Marko Riedel Mar 15 at 14:10