Pólya enumeration theorem

From LifeWiki
Jump to navigation Jump to search
Ambox notice.png This article may require cleanup to meet LifeWiki's quality standards.

The Pólya enumeration theorem is a theorem in combinatorics, that allows the number of states of a system to be counted (given a set of actions under which they're considered equivalent) more efficiently than by iterating over all states,[n 1] that can be used to derive closed-form general equations.

Explanation

Groups

In group theory, a group is a set of actions, with a system of compositions, that behaves similarly to a multiplication table, where enacting one action followed by another corresponds with finding the action in the cell at the x position defined by the first and y position by the second.[n 2] Groups are not necessarily commutative (ie. one action followed by another doesn't always produce the same as the other way around), and for all ordered pairs of actions there exists a product in this table, for each action there exists a unique inverse, and there exists an identity element (which, when composed with other elements, returns them).[n 3] Beginning with the identity state and repeatedly enacting a single action will eventually return to the identity, after a number of iterations that is a factor of the group's 'order' (total number of elements).

The theorem

Systems of rotational and reflectional symmetry may be described by groups, by finding the full set of actions that can be obtained by composing known ones (filling in and extending the multiplication table as necessary). The square, for instance, is invariant under reflection in the x and y axes, and the x=y line of symmetry, and its full symmetry group (containing also reflection in the x=-y line, rotation by 180º, and by 90º in either direction) may be generated by enacting them after each other.

The theorem states that the number of states, with these considerations of equivalence ('under symmetry'), is equal to the average of the number of invariant states across all actions. Note that under the identity action (which is counted as a group element), every cell is its own cycle.

In binary cellular automata, to be invariant under an action, all cells in each of its cycles can either be on or off simultaneously, so the number of states is 2 to the power of the number of cycles (however, note that this is not always the case). You can imagine, for a given action, colouring a cell in one of two states, then recursively applying the action and setting each cell reached to the same colour before it returns to its initial position, then moving onto the next uncoloured cell and repeating with a new colour until all are coloured, then calculating 2 to the power of the number of colours used.

Once this list of numbers of invariant states for each action has been calculated, the number of nonequivalent states (under action of the entire group) is its average.

Example derivation

Consider a k*k bounded square simulation area in a two-state isotropic cellular automaton. We will find an expression for the function A(k) that returns the number of distinct states (equivalent to the OEIS sequence A054247(k)).

Firstly, we know that there are 2k2 states without this consideration of symmetry, and that each of the distinct states has symmetry of order 1 (if it is C1), 2 (if it is one of the D2s and C2s), 4 (D4s and C4s) or 8 (D8s). The amount by which each such state is multiplied, to get the number of different representations of it counted in the 2k2 will be 8 divided by its order of symmetry, so we know that the number is between 2k2 and 2k2/8, depending on how many states exist of each class of symmetry. This isn't very helpful, but we can find a stronger statement, because each symmetry class of order o requires about k*(o-1)/o cells to match the state determined by the k/o (ie. a fourfold one requires about three quarters of the cells to match).[n 4] Being that k*(o-1)/o grows unboundedly with k, for arbitrarily large k the proportion of states that exist under each order, about 1/2k*(o-1)/o, will tend to 0, so symmetrical states become arbitrarily rare, meaning that A(k)/2k2 will approach 1/8 for large k, providing a sanity check for any result we get.

We will begin with the generating elements of the identity, reflections in the x and y axes, and in the x=y line of symmetry. By reflecting in x, y, then x=y, we obtain a new one distinct from our existing ones, the reflection in the x=-y line, so we add it as an action. Reflecting in y then x=y yields the rotation by 90º anticlockwise, and x then x=y yields 90º clockwise, and x then y yields the inversion/rotation by 180º. All compositions of pairs of this set of eight actions can be described by single elements, so it is a group.

#C [[ Y 1 ]] #C [[ LABEL 7.5 -4 12 "identity\k" LABEL 25.5 -4 12 "horizontal reflection\nx" LABEL 43.5 -4 12 "vertical reflection\ny" LABEL 61.5 -4 12 "180º rotation\nx,y" LABEL 79.5 -4 12 "diagonal reflection\nx=y" LABEL 97.5 -4 12 "90º clockwise rotation\nx,x=y" LABEL 115.5 -4 12 "90º anticlockwise rotation\ny,x=y" LABEL 133.5 -4 12 "antidiagonal reflection\nx,y,x=y" ]] #C [[ LABEL 7.5 16 12 "C1" LABEL 25.5 16 12 "D2_+1" LABEL 43.5 16 12 "D2_+1" LABEL 61.5 16 12 "C2_1" LABEL 79.5 16 12 "D2_x" LABEL 97.5 16 12 "C4_1" LABEL 115.5 16 12 "C4_1" LABEL 133.5 16 12 "D2_x" ]] #C [[ LABEL 7.5 51.5 12 "k**2" LABEL 25.5 51.5 12 "k*(k+1)/2\nk/2+k**2/2" LABEL 43.5 51.5 12 "k*(k+1)/2\nk/2+k**2/2" LABEL 61.5 51.5 12 "k*(k-1)/2+(k+1)/2\n1/2+k**2/2" LABEL 79.5 51.5 12 "∑_(i=1)^k (i)\nk*(k+1)/2\nk/2+k**2/2" LABEL 97.5 51.5 12 "(k+1)/2*(k-1)/2+1\n3/4+k**2/4" LABEL 115.5 51.5 12 "(k+1)/2*(k-1)/2+1\n3/4+k**2/4" LABEL 133.5 51.5 12 "∑_(i=1)^k (i)\nk*(k+1)/2\nk/2+k**2/2" ]] #C [[ LABEL 7.5 72.5 12 "C1" LABEL 25.5 72.5 12 "D2_+2" LABEL 43.5 72.5 12 "D2_+2" LABEL 61.5 72.5 12 "C2_4" LABEL 79.5 72.5 12 "D2_x" LABEL 97.5 72.5 12 "C4_4" LABEL 115.5 72.5 12 "C4_4" LABEL 133.5 72.5 12 "D2_x" ]] #C [[ LABEL 7.5 111 12 "k**2" LABEL 25.5 111 12 "k**2/2" LABEL 43.5 111 12 "k**2/2" LABEL 61.5 111 12 "k**2/2" LABEL 79.5 111 12 "∑_(i=1)^k (i)\nk*(k+1)/2\nk/2+k**2/2" LABEL 97.5 111 12 "k**2/4" LABEL 115.5 111 12 "k**2/4" LABEL 133.5 111 12 "∑_(i=1)^k (i)\nk*(k+1)/2\nk/2+k**2/2" ]] x = 142, y = 108, rule = B3/S23 15o3b15o3b15o3b15o3b15o3b15o3b15o3b15o$o13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo$o13bo3bo13bo3bo3b2o8bo3bo8b2o3bo3bo5bo7bo3bo13bo3bo7bo5bo3bo13bo$o3b2o3b2o3bo3bo3b2o3b2o3bo3bo2b4o7bo3bo7b4o2bo3bo4bo3b2o3bo3bo2b3o3b2o3bo3bo3b2o3bo4bo3bo3b2o3b3o2bo$o2bo2bobo2bo2bo3bo2bo2bobo2bo2bo3bo2b4o7bo3bo7b4o2bo3bo4bo2bo2bo2bo3bob4o2bo2bo2bo3bo2bo2bo2bo4bo3bo2bo2bo2b4obo$o2bo2bobo2bo2bo3bo2bo2bobo2bo2bo3bo2b9o2bo3bo2b9o2bo3bo4bo2bo2bo2bo3bob4o2bo2bo2bo3bo2bo2bo2bo4bo3bo2bo2bo2b4obo$o3b2o3b2o3bo3bo3b2o3b2o3bo3bo11bobo3bobo11bo3bo4bo3b2o3bo3bo2b3o3b2o3bo3bo3b2o3bo4bo3bo3b2o3b3o2bo$o13bo3bo13bo3bo13bo3bo13bo3bo4bo8bo3bo4bo8bo3bo8bo4bo3bo8bo4bo$o11bobo3bobo11bo3bo3b2o3b2o3bo3bo3b2o3b2o3bo3bo2b3o3b2o3bo3bo4bo3b2o3bo3bo3b2o3b3o2bo3bo3b2o3bo4bo$o2b9o2bo3bo2b9o2bo3bo2bo2bobo2bo2bo3bo2bo2bobo2bo2bo3bob4o2bo2bo2bo3bo4bo2bo2bo2bo3bo2bo2bo2b4obo3bo2bo2bo2bo4bo$o2b4o7bo3bo7b4o2bo3bo2bo2bobo2bo2bo3bo2bo2bobo2bo2bo3bob4o2bo2bo2bo3bo4bo2bo2bo2bo3bo2bo2bo2b4obo3bo2bo2bo2bo4bo$o2b4o7bo3bo7b4o2bo3bo3b2o3b2o3bo3bo3b2o3b2o3bo3bo2b3o3b2o3bo3bo4bo3b2o3bo3bo3b2o3b3o2bo3bo3b2o3bo4bo$o3b2o8bo3bo8b2o3bo3bo13bo3bo13bo3bo13bo3bo5bo7bo3bo13bo3bo7bo5bo$o13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo$15o3b15o3b15o3b15o3b15o3b15o3b15o3b15o4$15o3b15o3b15o3b15o3b15o3b15o3b15o3b15o$o13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo$o13bo3bo13bo3bo3b2o8bo3bo8b2o3bo3bo5bo7bo3bo7b3o3bo3bo7b3o3bo3bo13bo$o3b2o3b2o3bo3bo3b2o3b2o3bo3bo2b4o2b2o3bo3bo3b2o2b4o2bo3bo3b2o3b2o3bo3bo2b3o2b4o2bo3bo2b3o2b4o2bo3bo3b2o3b3o2bo$o2bo2bobo2bo2bo3bo2bo2bobo2bo2bo3bo2b4obo2bo2bo3bo2bo2bob4o2bo3bo2bob2obo2bo2bo3bob5ob4o2bo3bob5ob4o2bo3bo2bo2bob5obo$o2bo2bobo2bo2bo3bo2bo2bobo2bo2bo3bo2b9o2bo3bo2b9o2bo3bo2bob2obo2bo2bo3bob10o2bo3bob10o2bo3bo2bo2bob5obo$o3b2o3b2o3bo3bo3b2o3b2o3bo3bo3b2o3b2obobo3bobob2o3b2o3bo3bo3b2o3b2o3bo3bob4o3b2o3bo3bob4o3b2o3bo3bo3b2o3b3o2bo$o13bo3bo13bo3bo13bo3bo13bo3bo4bo8bo3bo4bo3bo4bo3bo4bo3bo4bo3bo8bo4bo$o11bobo3bobo9bobo3bo3b2o3b2obobo3bo3b2o3b2obobo3bo2b3o3b2obobo3bo3b2o3b4obo3bo3b2o3b4obo3bo3b2o3bo2bobo$o2b9o2bo3bo2b9o2bo3bo2b9o2bo3bo2b9o2bo3bob10o2bo3bo2b10obo3bo2b10obo3bo2b9o2bo$o2b4o7bo3bo2b4ob4o2bo3bo2b4obo2bo2bo3bo2b4obo2bo2bo3bob5obo2bo2bo3bo2b4ob5obo3bo2b4ob5obo3bo2b4o2bo4bo$o2b4o7bo3bo2b4ob4o2bo3bo2b4o2b2o3bo3bo2b4o2b2o3bo3bo2b4o2b2o3bo3bo2b4o2b3o2bo3bo2b4o2b3o2bo3bo2b4o2bo4bo$o3b2o8bo3bo3b2o3b2o3bo3bo3b2o8bo3bo3b2o8bo3bo3b2o8bo3bo3b3o7bo3bo3b3o7bo3bo3b2o2bo5bo$o13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo3bo13bo$15o3b15o3b15o3b15o3b15o3b15o3b15o3b15o4$15o3b8o10b15o3b15o3b15o3b8o10b8o10b15o$15o3b8o10b15o3b15o3b14o4b8o10b8o11b14o$15o3b8o10b15o3b15o3b13o5b8o10b8o12b13o$15o3b8o10b15o3b15o3b12o6b8o10b8o13b12o$15o3b8o10b15o3b15o3b11o7b8o10b8o14b11o$15o3b8o10b15o3b15o3b10o8b8o10b8o15b10o$15o3b8o10b15o3b15o3b9o9b8o10b8o16b9o$15o3b8o10b15o3b8o10b8o17bo17bo17b8o$15o3b8o46b7o55b7o$15o3b8o46b6o57b6o$15o3b8o46b5o59b5o$15o3b8o46b4o61b4o$15o3b8o46b3o63b3o$15o3b8o46b2o65b2o$15o3b8o46bo67bo6$16o2b16o2b16o2b16o2b16o2b16o2b16o2b16o$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$o3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b2o9bo2bo9b2o3bo2bo6bo2b2o3bo2bo3b3o3b2o3bo2bo3b2o2bo6bo2bo3b2o3b3o3bo$o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b4o8bo2bo8b4o2bo2bo5bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo2bo2bo5bo2bo2bo2bo2b4o2bo$o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b4o8bo2bo8b4o2bo2bo5bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo2bo2bo5bo2bo2bo2bo2b4o2bo$o3b2o4b2o3bo2bo3b2o4b2o3bo2bo2b9o3bo2bo3b9o2bo2bo5bo3b2o3bo2bo3b3o3b2o3bo2bo3b2o3bo5bo2bo3b2o3b3o3bo$o14bo2bo14bo2bo11bo2bo2bo2bo11bo2bo5bo8bo2bo5bo8bo2bo8bo5bo2bo8bo5bo$o11bo2bo2bo2bo11bo2bo14bo2bo14bo2bo5bo8bo2bo5bo8bo2bo8bo5bo2bo8bo5bo$o2b9o3bo2bo3b9o2bo2bo3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b3o3b2o3bo2bo5bo3b2o3bo2bo3b2o3b3o3bo2bo3b2o3bo5bo$o2b4o8bo2bo8b4o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo5bo2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo5bo$o2b4o8bo2bo8b4o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo5bo2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo5bo$o3b2o9bo2bo9b2o3bo2bo3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b3o3b2o3bo2bo6bo2b2o3bo2bo3b2o3b3o3bo2bo3b2o2bo6bo$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$16o2b16o2b16o2b16o2b16o2b16o2b16o2b16o3$16o2b16o2b16o2b16o2b16o2b16o2b16o2b16o$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$o3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b2obo2b2o3bo2bo3b3obob2o3bo2bo3b3obob2o3bo2bo3b2o3b3o3bo$o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo2bo2bo2bo2b4o2b4o2bo2bo2b4o2b4o2bo2bo2bo2bo2b4o2bo$o2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo2bo2b4o2bo2bo2bo2bo2bo2bo2bo2bo2b4o2b4o2bo2bo2b4o2b4o2bo2bo2bo2bo2b4o2bo$o3b2o4b2o3bo2bo3b2o4b2o3bo2bo2b9o3bo2bo3b9o2bo2bo3b3o3b2o3bo2bo3b9o2bo2bo3b9o2bo2bo3b2o3b3o3bo$o14bo2bo14bo2bo11bo2bo2bo2bo11bo2bo5bo8bo2bo2bo2bo2bo5bo2bo2bo2bo2bo5bo2bo8bo5bo$o11bo2bo2bo2bo8bo2bo2bo11bo2bo2bo11bo2bo2bo5bo5bo2bo2bo5bo2bo2bo2bo2bo5bo2bo2bo2bo2bo8bo2bo2bo$o2b9o3bo2bo2b10o2bo2bo2b9o3bo2bo2b9o3bo2bo2b9o3bo2bo2b9o3bo2bo2b9o3bo2bo2b9o3bo$o2b4o8bo2bo2b4o2b4o2bo2bo2b4o2bo2bo2bo2bo2b4o2bo2bo2bo2bo2b4o2bo2bo2bo2bo2b4o2b4o2bo2bo2b4o2b4o2bo2bo2b4o2bo5bo$o2b4o8bo2bo2b4o2b4o2bo2bo2b4o2bo2bo2bo2bo2b4o2bo2bo2bo2bo2b4o2bo2bo2bo2bo2b4o2b4o2bo2bo2b4o2b4o2bo2bo2b4o2bo5bo$o3b2o9bo2bo3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b2o4b2o3bo2bo3b3o3b2o3bo2bo3b2obob3o3bo2bo3b2obob3o3bo2bo3b2o2bo6bo$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$o14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo2bo14bo$16o2b16o2b16o2b16o2b16o2b16o2b16o2b16o3$16o2b8o10b16o2b16o2b16o2b8o10b8o10b16o$16o2b8o10b16o2b16o2b15o3b8o10b8o11b15o$16o2b8o10b16o2b16o2b14o4b8o10b8o12b14o$16o2b8o10b16o2b16o2b13o5b8o10b8o13b13o$16o2b8o10b16o2b16o2b12o6b8o10b8o14b12o$16o2b8o10b16o2b16o2b11o7b8o10b8o15b11o$16o2b8o10b16o2b16o2b10o8b8o10b8o16b10o$16o2b8o10b16o2b16o2b9o9b8o10b8o17b9o$16o2b8o46b8o54b8o$16o2b8o46b7o56b7o$16o2b8o46b6o58b6o$16o2b8o46b5o60b5o$16o2b8o46b4o62b4o$16o2b8o46b3o64b3o$16o2b8o46b2o66b2o$16o2b8o46bo68bo! [[ THEME 6 GRID GRIDMAJOR 0 ZOOM 8 WIDTH 1136 HEIGHT 972 NOGUI ]]
diagram of actions, static symmetries invariant under them, and orbit representatives (and equations) for each parity

Here are shown geometric shapes, that will be mapped to all cells in the board by repeated application of the action. One can also find equations for counts of cells with each cycle type, divide each by the cycle's length, and check that the numerators sum to k2 (the number of cells) to ensure no errors were made. For the 1 identity, there are k2 cycles. For the 2 orthogonal reflections, there are k+(k2-k)/2 if k is odd, otherwise k2/2, for the 2 diagonal ones there are k+(k2-k)/2, for the 2 rotations there are (1+(k2-1)/4 if k is odd, otherwise k2/4, and for the 1 inversion, there are 1+(k2-1)/2 if k is odd, otherwise k2/2

We take 2 to the power of each of these actions' cycle counts (multiplying by the number of instances of each), and average these, for the expression

( 2k2+2*2k+(k2-k)/2+2*2k+(k2-k)/2+2*21+(k2-1)/4+21+(k2-1)/2
.if k is odd else
. 2k2+2*2k2/2+2*2k+(k2-k)/2+2*2k2/4+2k2/2)/8

It may be expressed in a form over both parities, where ⌈x⌉ is the ceiling operator, as (2k2+2*2k*(k+1)/2+2*2⌈k/2⌉*k+2⌈k2/2⌉+2*2⌈k2/4⌉)/8.[n 5]

Here and in the future expressions, it would be a small reduction to replace the doublings outside of powers of 2 with additions inside (ie. 2*2... to 21+...), however they are left as-is to make it easier to generalise to rules with arbitrarily many states by changing the bases of all exponentiations. Running this for k in (0,1,2,...,7) returns 1,2,6,102,8548,4211744,8590557312,70368882591744 (the width in digits growing quadratically). For both parities, every term in the numerator (apart from the 2k2 one) grows asymptotically to at most the square-root of 2k2, so will account for a diminishing part of the total sum, so it abides by the sanity check, and it always returns integer outputs for integer inputs (another sanity check). You may know of A(3)=102 through a different context, as the total number of birth and survival transitions in isotropic non-totalistic rules in Moore neighbourhoods.

Rectangular boards

For non-square x*y boards (for which there is only fourfold symmetry), it is instead[1]

((2x*y+2(x+1)*y/2+2x*(y+1)/2+2(x*y+1)/2
. if y is odd else
. 2x*y+2x*(y+1)/2+2*2x*y/2)
.if x is odd else
.(2x*y+2x*(y+1)/2+2*2x*y/2
. if y is odd else
. 2x*y+3*2x*y/2))/4

Equivalently, (2x*y+2⌈x/2⌉*y+2x*⌈y/2⌉+2⌈x*y/2⌉)/4.[n 6]

Note that this doesn't account for diagonal reflection or rotation where x=y.

Toroidal boards

Actions don't have to be reflections, but can be arbitrary permutations of elements of a list under which it's considered equivalent. This article mainly covers actions of reflections for isotropic cellular automata in bounded planes, but if they were to take place on a torus, one could begin with actions in the generating set that cyclically shift the state one cell to the right or upwards, and determine each one's cycles in the same way. (This causes the number of terms in the equation to grow quadratically with respect to the width, but can be computed in closed-form summations involving Euler's totient function, as explained in the cases with axis reflections and transposition in papers by S. N. Ethier.)

Applications

to counting states

As well as the binary-square-counting problem, some other useful closed forms are provided.

1D tapes

For k-cell-wide bounded tapes in isotropic 1-dimensional cellular automata (or transitions in range-(k-1)/2 1D INT neighbourhoods for odd k), it is A005418(k+1),

( 2k+2(k+1)/2
.if k is odd else
. 2k+2k/2)/2

Equivalently, (2k+2⌈k/2⌉)/2.

Hexagonal neighbourhoods

Range 1 2 3
hexagonal
neighbourhood
Hexagonal neighbourhood (range 1).png Hexagonal neighbourhood (range 2).png Hexagonal neighbourhood (range 3).png

In range-k (edge-length k+1) INT neighbourhoods in a hexagonal lattice, there are A003215(k) cells and

(23*k*(k+1)+1+3*2(3*k+2)*(k+1)/2+3*2⌊(3*k2+4*k+2)/2⌋+23*k*(k+1)/2+1+2*2k2+k+1+2*2k*(k+1)/2+1)/12

transitions.

Other neighbourhood enumerations, taking place in triangular and hexagonal neighbourhoods, are provided here.

If one is centred upon a vertex instead of a cell (beginning with an empty range-0 neighbourhood), there are A033428(k) cells, and

(23*k2+3*2k*(3*k+1)/2+2*2k2)/6

transitions.

By the rule for iteratively generating higher-range Moore neighbourhoods (all in a range-k+1 neighbourhood are either members of or adjacent to those in a range-k one) on a triangular tiling, there are A005448(k+1)=3*k*(k+1)/2+1 cells in a range-k one, and

(23*k*(k+1)/2+1+2*2k*(k+1)/2+1+3*2⌊3*k*(k+2)/4⌋+1)/6

transitions.

Beginning from a vertex (equivalently to the hexagon case), there are A319127(k+2) cells, and

(2⌊(k+1)2/4⌋*6+3*2(⌈3*k2/8⌉+k)*2+4*2⌊3*(k+1)2/4⌋+2*2⌊(k+1)2/2⌋+2*2⌊(k+1)2/4⌋)/12

transitions.

Diamonds/von Neumann transitions

Similarly to how nonequivalent states in (2*k+1)*(2*k+1) square boards describe the number of birth and survival INT transitions in range-k Moore neighbourhoods, those in diamonds describe them in von Neumann ones. (Here, to cover both odd and even k, they are defined as the set of cells with a Manhattan distance of ⌊k/2⌋ from the centre of a vertex-aligned k*k square.) The first few terms are shown here.

x = 34, y = 7, rule = B3/S23 22b2o6bo$10b2o4bo4b4o4b3o$2b2o2bo2b4o2b3o2b6o2b5o$ob2ob3ob4ob5ob6ob7o$6bo3b2o3b3o3b4o3b5o$16bo5b2o5b3o$30bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ LABEL 0 4 16 "A(1)=2" LABEL 2.5 4.5 16 "A(2)=6" LABEL 6 5 16 "A(3)=12" LABEL 10.5 5.5 16 "A(4)=570" LABEL 16 6 16 "A(5)=1236" LABEL 22.5 6.5 16 "A(6)=2102800" LABEL 30 7 16 "A(7)=4215840" ]]
For integer k approaching infinity, because there are A266725(k) cells, A(k) will converge to 2A266725(k)/8.
Neighbourhoods for odd k can be constructed by shifting quadrants of preceding even k with a single central cell added, so A(2*k+1)/A(2*k) will converge to 2.[n 7]
(click above to open LifeViewer)

Due to the polynomials for each cycle type having difference terms with period 4 (as can be seen in the diagonals alternating between ending in protrusions and indentations for both the odd and even cases), parity must be considered modulo 4,

( 2(k2+1)/2+2*2(k+1)2/4+2*2k*(k+1)/4+2(k2+3)/4+2*2(k2+7)/8
.if k≡3 (mod 4) else
. 2k*(k+2)/2+2*2(k+1)*(k+2)/4+3*2k*(k+2)/4+2*2k*(k+2)/8
.if k≡2 (mod 4) else
. 2(k2+1)/2+2*2(k+1)2/4+2*2(k2+k+2)/4+2(k2+3)/4+2*2(k2+7)/8
.if k≡1 (mod 4) else
. 2k*(k+2)/2+2*2k*(k+3)/4+3*2k*(k+2)/4+2*2k*(k+2)/8)/8

Though there is a smaller form in ceilings for each parity also,

( 2(k2+1)/2+2*2(k+1)2/4+2*2⌈k*(k+1)/4⌉+2⌈k2/4⌉+2*2⌈k2/8⌉
.if k≡1 (mod 2) else
. 2k*(k+2)/2+2*2⌈k*(k+3)/4⌉+3*2k*(k+2)/4+2*2k*(k+2)/8)/8

Higher dimensions

For squares and diamonds, the two axes can be exchanged (providing 2 actions) or each reflected (providing 22) for 23=8 distinct orientations (and thus group actions). More generally, for n-dimensional hypercubes (with vertices at each n-agonal displacement from the origin) and orthoplexes (the continuation of diamonds and octahedra, with vertices at each orthogonal displacement) the n axes can be permuted or each reflected independently, providing n!*2n.

Cubes

The number of nonequivalent n*n*n cubes under 48-fold symmetry is

( 2k3+9*2k2+(k3-k2)/2+9*2k+(k3-k)/2+21+(k3-1)/2+8*2k+(k3-k)/3+6*21+(k-1)/2+(k3-k)/4+6*2k+(k3-k)/4+8*21+(k-1)/2+(k3-k)/6
.if k≡1 (mod 2) else
. 2k3+6*2k2+(k3-k2)/2+13*2k3/2+8*2k+(k3-k)/3+12*2k3/4+8*2k/2+(k3-k)/6)/48

Equivalently,

(2k3+3*2⌈k/2⌉*k2+9*2⌈k2/2⌉*k+2⌈k3/2⌉+6*2k2*(k+1)/2+6*2⌈k2/4⌉*k+6*2⌈⌈k2/2⌉*k/2⌉+8*2k*(k2+2)/3+8*2⌈k*(k2+2)/6⌉)/48
Octahedra

For n-cell-wide octahedra (with the same interpolation for even widths as the diamonds (with vertex-centred corners)), describing 3D higher-range Moore neighbourhoods, there are instead 12 cases, 4 for the same reason as the diamonds in the 2D case (that it contains as orthogonal planes through its centre) times 3 (because the triagonals alternate between ending in the protruding vertice of a cell and an inner one at each of two orientations, with period 3). A reduced equation (with inline moduloes instead of all 12) is shown for brevity, they can be expanded out for a form with only elementary functions for each parity. Note that there are two locations in the odd-k case in which a balanced ternary modulo is the only way to reduce inline if statements.

( 2k*(k2+5)/6+3*2k*(k2+11)/12+3*2(k3+3*k2+5*k+3)/12+6*2(2*k3+3*k2+10*k+9)/24+6*2(k3+8*k+6-k%4*3)/12+2(k3+5*k+6)/12+8*2(k3+9*k+8*((k+1)%3-1))/18+6*2k*(k2+23)/24+6*2(k3+11*k+12)/24+8*2(k3+9*k+18+8*((k+1)%3-1))/36
.if k≡1 (mod 2) else
. 2k*(k3+6*k+8)/6+13*2k*(k2+6*k+8)/12+6*2(2*k3+15*k2+28*k+k%4*6)/24+8*2(k3+6*k2+12*k+k%3*8)/18+12*2k*(k2+6*k+8)/24+8*2((k3+6*k2+12*k+k%3*8)/36)/48
Tesseracts

For 4D hypercubes, it is

( 2k4+16*2k3+(k4-k3)/2+42*2k2+(k4-k2)/2+16*2k+(k4-k)/2+32*2k2+21+(k4-1)/2+(k4-k2)/3+96*2(k+(k2-k)/2+(k4-k2)/4+12*2k2+(k4-k2)/4+12*21+(k2-1)/2+(k4-k2)/4+12*21+(k4-1)/4+32*2k+(k2-k)/2+(k3-k)/3+(k4-k3-k2+k)/6+32*21+(k2-1)/2+(k4-k2)/6+32*2k+(k2-k)/2+(k4-k2)/6+48*21+(k4-1)/8
.if k≡1 (mod 2) else
. 2k4+12*2k3+(k4-k3)/2+12*2k2+(k4-k2)/2+51*2k4/2+32*2k2+(k4-k2)/3+48*2k+(k2-k)/2+(k4-k2)/4+84*2k4/4+96*2k2/2+(k4-k2)/6+48*2k4/8)/384

Equivalently,

(2k4+4*2⌈k/2⌉*k3+30*2⌈k2/2⌉*k2+16*2⌈k3/2⌉*k+2⌈k4/2⌉+12*2k3*(k+1)/2+12*2⌈k2/4⌉*k2+48*2⌈⌈k2/2⌉*k/2⌉*k+12*2⌈(⌈k2/2⌉*k2)/2⌉+32*2k2*(k2+2)/3+32*2⌈k/2⌉*k*(k2+2)/3+32*2⌈(k*(k2-1)/3+k)/2⌉*k+32*2⌈(k2*(k2+2)/3)/2⌉+12*2k2*(k2+1)/2+12*2⌈k4/4⌉+48*2k*(k3+k+2)/4+48*2⌈k4/8⌉)/384

The number of 2-colourings of an n-dimensional hypercube with edges k cells long is A361870(n,k).

To indexing methods

The ability to efficiently calculate numbers of states in arbitrarily large symmetrical spaces is interesting, but may not seem very useful beyond this, in and of itself. However, the program explained in Tutorials/Coding Life simulators/eightfold reducer, that emulates a structure containing all states in an n*n square grid (as explained in the first example) without storing it in memory, uses this to enumerate states preceding an inputted one (by counting those with bits fixed up to its binary representation across increasingly layers of cells of the same displacement under symmetry) to determine its index within the structure, or run this in reverse to determine states from indexes, both in optimal time complexity.

To other maths

The outputs of equations derived with the theorem are guaranteed to be integer. Because each one is a fraction, the numerator modulo the denominator is guaranteed to be zero, which allows modular congruences (identities in modular arithmetic) to be proven.

Fermat's little theorem

See also the explanation of the twofold reducer's necklace mode, which explains the generalisation of this to non-prime necklaces with Euler's totient function (and Duval's algorithm for generating them)

Consider a 1D tape (as above) with p cells (where p is prime), each of which is one of c colours, under action of rotations but not reflections. It will have p group actions, corresponding with cyclic shifts by amounts in the range (0, 1, 2, ..., p-1). In the identity, each cell is a cycle, so it has p length-1 cycles, but in each of the p-1 other actions, there are no subperiods of p for any cells to oscillate at (because p has no prime factors apart from itself), so all cells will oscillate with period p. The sum will thus be (cp+(p-1)*c)/p. Because this will always be an integer, (cp+(p-1)*c)%p=0, we can subtract p*c within the modulo's numerator (which is a multiple of p so won't change its value), so (cp-c)%p=0, so cp%p=c%p for all integer c>=1 and prime p. Because both sides of the equation are modulo'd by the same number, it's referred to in mathematical notation as a modular congruence, cp≡c (mod p).

Wilson's theorem

As mentioned above, cellular automata are only the simplest case. Though such general closed forms are not always possible, it can be used if states invariant under actions can be counted under other constraints.

For instance, consider a p*p chessboard (where p is again prime), with p rooks on it, such that no two rooks are attacking (though they are all considered the same colour, for our purposes). It is often taught there are p! permutations under the identity action (because each rook occupies a column, and as they're placed in successive columns (left-to-right), the number of positions each rook can be placed in is 1 fewer than the one before it, beginning with p and ending with 1, so the number of permutations is the product of this, the definition of the factorial).

If this chessboard is to be considered under action of toroidal scrolling, however, there are p2 actions to consider, one for each displacement (x,y) (where 0<=x<p and 0<=y<p). For a state to be invariant under each action (x,y), after the first rook is placed (at (0,0)), the cell it will be mapped to under the action, (x,y), must also contain a rook, then the cell that is mapped to, (2*x%p,2*y%p), must also, and so on. If only one of x and y is 0 (comprising p-1 actions each), this means the rook must exist within a row or column of rooks, which would cause them to be attacking each other, so these have 0 states each. Otherwise, in the (p-1)*(p-1) non-orthogonal actions, both axial displacements will oscillate with period p, so each row and column will have a single rook placed in it.

x = 69, y = 69, rule = B3ai4/S23 9o$2o6bo$o7bo$o7bo$o7bo$o7bo$o7bo$o7bo$9o2$10b9ob9ob9ob9ob9ob9o$10b2o6bob2o6bob2o6bob2o6bob2o6bob2o6bo$10bobo5bobo2bo4bobo3bo3bobo4bo2bobo5bobobo6b2o$10bo2bo4bobo4bo2bobo6b2obobo5bobo3bo3bobo5bobo$10bo3bo3bobo6b2obo2bo4bobo5bobobobo5bobo4bo2bo$10bo4bo2bobobo5bobo5bobobo2bo4bobo6b2obo3bo3bo$10bo5bobobo3bo3bobobo5bobo6b2obo4bo2bobo2bo4bo$10bo6b2obo5bobobo4bo2bobo3bo3bobo2bo4bobobo5bo$10b9ob9ob9ob9ob9ob9o2$10b9ob9ob9ob9ob9ob9o$10b2o6bob2o6bob2o6bob2o6bob2o6bob2o6bo$10bo4bo2bobobo5bobo5bobobo2bo4bobo6b2obo3bo3bo$10bobo5bobo2bo4bobo3bo3bobo4bo2bobo5bobobo6b2o$10bo5bobobo3bo3bobobo5bobo6b2obo4bo2bobo2bo4bo$10bo2bo4bobo4bo2bobo6b2obobo5bobo3bo3bobo5bobo$10bo6b2obo5bobobo4bo2bobo3bo3bobo2bo4bobobo5bo$10bo3bo3bobo6b2obo2bo4bobo5bobobobo5bobo4bo2bo$10b9ob9ob9ob9ob9ob9o2$10b9ob9ob9ob9ob9ob9o$10b2o6bob2o6bob2o6bob2o6bob2o6bob2o6bo$10bo5bobobo3bo3bobobo5bobo6b2obo4bo2bobo2bo4bo$10bo3bo3bobo6b2obo2bo4bobo5bobobobo5bobo4bo2bo$10bobo5bobo2bo4bobo3bo3bobo4bo2bobo5bobobo6b2o$10bo6b2obo5bobobo4bo2bobo3bo3bobo2bo4bobobo5bo$10bo4bo2bobobo5bobo5bobobo2bo4bobo6b2obo3bo3bo$10bo2bo4bobo4bo2bobo6b2obobo5bobo3bo3bobo5bobo$10b9ob9ob9ob9ob9ob9o2$10b9ob9ob9ob9ob9ob9o$10b2o6bob2o6bob2o6bob2o6bob2o6bob2o6bo$10bo2bo4bobo4bo2bobo6b2obobo5bobo3bo3bobo5bobo$10bo4bo2bobobo5bobo5bobobo2bo4bobo6b2obo3bo3bo$10bo6b2obo5bobobo4bo2bobo3bo3bobo2bo4bobobo5bo$10bobo5bobo2bo4bobo3bo3bobo4bo2bobo5bobobo6b2o$10bo3bo3bobo6b2obo2bo4bobo5bobobobo5bobo4bo2bo$10bo5bobobo3bo3bobobo5bobo6b2obo4bo2bobo2bo4bo$10b9ob9ob9ob9ob9ob9o2$10b9ob9ob9ob9ob9ob9o$10b2o6bob2o6bob2o6bob2o6bob2o6bob2o6bo$10bo3bo3bobo6b2obo2bo4bobo5bobobobo5bobo4bo2bo$10bo6b2obo5bobobo4bo2bobo3bo3bobo2bo4bobobo5bo$10bo2bo4bobo4bo2bobo6b2obobo5bobo3bo3bobo5bobo$10bo5bobobo3bo3bobobo5bobo6b2obo4bo2bobo2bo4bo$10bobo5bobo2bo4bobo3bo3bobo4bo2bobo5bobobo6b2o$10bo4bo2bobobo5bobo5bobobo2bo4bobo6b2obo3bo3bo$10b9ob9ob9ob9ob9ob9o2$10b9ob9ob9ob9ob9ob9o$10b2o6bob2o6bob2o6bob2o6bob2o6bob2o6bo$10bo6b2obo5bobobo4bo2bobo3bo3bobo2bo4bobobo5bo$10bo5bobobo3bo3bobobo5bobo6b2obo4bo2bobo2bo4bo$10bo4bo2bobobo5bobo5bobobo2bo4bobo6b2obo3bo3bo$10bo3bo3bobo6b2obo2bo4bobo5bobobobo5bobo4bo2bo$10bo2bo4bobo4bo2bobo6b2obobo5bobo3bo3bobo5bobo$10bobo5bobo2bo4bobo3bo3bobo4bo2bobo5bobobo6b2o$10b9ob9ob9ob9ob9ob9o! [[ THEME 6 GRID GRIDMAJOR 0 ZOOM 8 WIDTH 552 HEIGHT 552 NOGUI ]]
diagram of positions under each displacement in a 7*7 board

Note that the configuration of rooks appears identical from the perspective of each rook.

For each of these non-orthogonal actions, each of these solutions with a cell at (0,0) can be shifted by one of p2 displacements. A shift will map a single rook to a square within the first row, and all other rows' rooks' locations are determined by this, so there are p nonequivalent positions of the set of all rooks, one for each such square.

The equation is thus (p!+p*(p-1)2)/p2, meaning that (because it's integer) (p!+p*(p-1)2)%p2=0. This can be simplified by dividing both sides of the modulo by the common factor p (((p-1)!+(p-1)2)%p=0), expanding (((p-1)!+p2-2*p+1)%p=0) and subtracting a multiple of the denominator from the numerator (((p-1)!+1)%p=0), so (p-1)!≡-1 (mod p). This proves that the congruence is true if p is prime, but Wilson's full theorem states that the converse is true also, and only primes satisfy it. For n=4, (n-1)!=6, which is congruent to 2 modulo 4, but for all composite numbers (written as products of prime factors, f0e0+f1e1+...+fnen) thereafter, each prime factor fi will have appeared at least fiei-1 times prior (because the exponent necessary for each prime factor f (to ensure divisibility) increments by 1 on its fth occurrence), so (p-1)! will be divisible by p (ie. congruent to 0 modulo p) for all composite p apart from 4.

See also

Footnotes

  1. A less efficient explicit method, for the enumeration of states in cellular automata, would be to implement the actions as functions and represent states as lists or binary integers (such that there exists an ordering upon them), and (given a system with n cells), for each of the 2n states, to count it only if it is the minimum of the set of states that are obtainable from enacting the actions upon it.
  2. See this diagram of the tables for groups up to order 7.
  3. By convention, the identity is the top-left element in this table, and each action corresponds with the permutation from the initial row to the row which contains it as the leftmost element. Not all rows must be stored (no more than floor(log2(n)) for an n-element group), and more may be generated by composing the permutations represented by existing rows (and inserted such that the leftmost column (beginning with the identity) is in the same order as the first row).
  4. This approximation is exact for even k, but for odd k the cells along the central column and row are only halved, and the central cell isn't divided at all.
  5. In programming languages that only provide floor division (like C's / and Python's //), for integer p,q ceiling division may be computed as ⌈p/q⌉=⌊(p+q-1)/q⌋.
  6. For arbitrary n-dimensional oblique hypercuboids with only orthogonal lines of symmetry, where the edge lengths in each axis are given by a0,a1,...,an-1, this formula is given by f(n,a)=∑2n-1s=0(2⌈∏n-1i=0(ais>>i&1)/2⌉*∏n-1i=0(ai~s>>i&1))/2n. For a0=a1=...=an-1=2, it is equivalent to the number of boolean functions under action of mapping not to each input but not exchanging them (f(n,n*(2,))=A000231(n)), and for n=1 there are no axes to permute so it equals the form for binary tapes (f(1,(k,))=A361870(1,k)).
  7. Note that k=1 is the only value for which this ratio precisely equals 2, due to orthogonally-displaced cells in A(3) being equivalent to diagonal ones in A(2).

References

  1. calcyman (2012-01-24). Re: Any idea of the surface... (discussion thread) at the ConwayLife.com forums (note that the lengths there are given in the form 2*m or 2*m+1 for each parity instead of x for both)

External links

Programs

DroneBetter has written a Python program for applying the theorem to find numbers of nonequivalent states (in tessellations of boolean hypercubes, comprising larger hypercubes or orthoplexes) (that found many of the equations shown above, and is explained in dimensional INT enumerator), and a less optimised one for arbitrary graphs with a graphical interface.