First off, Permutation Groups are collection of permutaion operations (element swapping) on the elements of a set. They can be denoted by cycle decompositions of the swaps being made. For instance;
| A 2-element swap on a 6 element Set |
| 123456 |
| 153426 |
| = |
| (1)(3)(4)(6)(25) |
While
| Rotation on the same 6 element Set |
| 123456 |
| 234561 |
| = |
| (123456) |
Polya's enumeration theorem uses equivalent decompositions, i.e. (1)(2)(3)(4)(56) and (1)(3)(4)(5)(26) having 4 1 elements cycles and 1 2 element cycles are equivalent, to
create the generating function. Each permutation operation is weighted according to the number of equivalents and then the average is taken.
As an example the number of distinct ways to add edges to a 3 vertice graph can be found as follows. The permutations on a 3 element set is (second example);
[1 2 3] = (1)(2)(3)
[1 3 2] = (1)(2 3)
[2 1 3] = (1 2)(3)
[2 3 1] = (1 2 3)
[3 1 2] = (1 3 2)
[3 2 1] = (1 3)(2)
Which creates the function; 1/6 ( x1^3 + 3 a1 a2 + 2 a3 ). The translation is that there is one equivalent of 1-cycle * 1-cycle * 1-cycle plus three equivalents of 1-cycle * 2-cycle plus two of 3-cycle operations.
The generating function is then created using (z+1), where z denotes an edge and 1 denotes no edge. This produces ((z+1)^3 +3 (z+1)(z^2+1)+(z^3+1))/6.
Or rather, z^3 + z^2 + z^1 + 1. Which can be read as there is only one way to add three edges to the graph, only one way to add 2 edges, only one way to add 1 edge and only one way to add no edges. Only considering rotations will procude the same results.
For Mu Torere, only the rotation permutations will be used. This allows us to equate, for instance, all swaps that are 2 places apart. Ignoring teh central location, means that only 8 locations need be considered. From this, the permutaion groups are;
[12345678] = (1)(2)(3)(4)(5)(6)(7)(8)
[23456781] = (12345678)
[34567812] = (1357)(2468)
[45678123] = (14725836)
[56781234] = (15)(26)(37)(48)
[67812345] = (16385274)
[78123456] = (1753)(1864)
[81234567] = (18765432)
Being 4 permutations 8-element cycles, 1 permutation group of 1-element cycles, 1 permutation group of 2-element cycles, and 2 groups of 4-element cycles. This gives the preliminary function of 1/8 (g1^8 + g2^4 + 2 g4^2 + 4 g8).
For the generating function, we will use (c+u+1) where c will denote a piece owned by the Computer, u will denote one owned by the User, and 1 will be a empty location. This creates the generating function ((c+u+1)^8 + (c^2+u^2+1)^4 + 2 (c^4+u^4+1)^2 + 4(c^8+u^8+1))/8.
HomeWork: What terms will we need to examine? And what will be final number?
Update:
The terms to examine are C^4 U^4, C^4 U^3, and C^3 U^4.
The numbers are 10, 35, and 35, which totals 80.
