2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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?) $\endgroup$ – Parcly Taxel Mar 14 at 13:16
  • $\begingroup$ As well as that, can more than one point occupy a grid space? $\endgroup$ – Parcly Taxel Mar 14 at 13:23
  • $\begingroup$ Hey Parcly, its 64 like chess. only 1 point per slot. 64 available positions $\endgroup$ – Andre Mar 14 at 23:19
0
$\begingroup$

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.}$$

$\endgroup$
  • $\begingroup$ Awesome thanks Marko! $\endgroup$ – Andre Mar 14 at 23:17
  • $\begingroup$ 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? $\endgroup$ – Andre Mar 14 at 23:23
  • $\begingroup$ These are diagonally opposed corners? $\endgroup$ – Marko Riedel Mar 15 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.