Necklaces: colourings up to rotation

Burnside applied to the cyclic group gives \(n^{-1} \sum_{d \mid n} \varphi(n/d) k^d\). Computed both that way and by direct Burnside over the explicit rotations, then compared – the closed form is a shortcut, and shortcuts are where errors hide.

Usage

morie_cycle_index_necklaces(n, k)

Arguments

n

Number of beads.

k

Number of colours.

Value

A list with count, direct_burnside, agrees, divides_exactly, total_colourings.

References

Polya G (1937). Kombinatorische Anzahlbestimmungen fuer Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68, 145-254.

Examples

morie_cycle_index_necklaces(n = 5L, k = 5L)
#> $count
#> [1] 629
#> 
#> $estimate
#> [1] 629
#> 
#> $exact
#> [1] "629"
#> 
#> $direct_burnside
#> [1] 629
#> 
#> $agrees
#> [1] TRUE
#> 
#> $divides_exactly
#> [1] TRUE
#> 
#> $total_colourings
#> [1] 3125
#> 
#> $n
#> [1] 5
#> 
#> $k
#> [1] 5
#> 
#> $method
#> [1] "Cycle index of the cyclic group (Polya enumeration)"
#>