Burnside's lemma

The number of orbits is the AVERAGE number of fixed points, \(|X/G| = |G|^{-1} \sum_g |X^g|\), and for colourings of positions \(|X^g| = k^{c(g)}\) with \(c(g)\) the number of cycles.

Usage

morie_burnside_orbit_count(group_permutations, n_colours)

Arguments

group_permutations

A list of integer vectors, each a permutation of 0:(n-1), matching the Python mirror's 0-based convention.

n_colours

Number of colours.

Value

A list with orbits, fixed_points, cycle_counts, sum_fixed, naive_division, naive_is_wrong, divides_exactly.

Details

The lemma is often stated as "divide by the symmetry", which is wrong whenever some arrangements have extra symmetry of their own. naive_division is returned to make the gap visible: two-colour necklaces of length 4 have 16 colourings and 4 rotations but 6 orbits, not 4.

Examples

group_permutations <- list(c(0, 1, 2), c(1, 2, 0), c(2, 0, 1))
morie_burnside_orbit_count(group_permutations, n_colours = 2)
#> $orbits
#> [1] 4
#> 
#> $estimate
#> [1] 4
#> 
#> $exact
#> [1] "4"
#> 
#> $fixed_points
#> [1] 8 2 2
#> 
#> $cycle_counts
#> [1] 3 1 1
#> 
#> $sum_fixed
#> [1] 12
#> 
#> $group_order
#> [1] 3
#> 
#> $total_colourings
#> [1] 8
#> 
#> $naive_division
#> [1] 2.666667
#> 
#> $naive_is_wrong
#> [1] TRUE
#> 
#> $divides_exactly
#> [1] TRUE
#> 
#> $n
#> [1] 3
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Burnside's lemma"
#>