Necklaces are the equivalence classes of words under the action of the cyclic group. Let a transition in a word be any change between two adjacent letters modulo the word’s length. We present a closed-form solution for the enumeration of necklaces in n beads, k colours and t transitions. We show that our result provides a more general solution to the problem of counting alternating (proper) colourings of the vertices of a regular n-gon.
Enumerating necklaces with transitions
Francesco Bianconi
;
2021
Abstract
Necklaces are the equivalence classes of words under the action of the cyclic group. Let a transition in a word be any change between two adjacent letters modulo the word’s length. We present a closed-form solution for the enumeration of necklaces in n beads, k colours and t transitions. We show that our result provides a more general solution to the problem of counting alternating (proper) colourings of the vertices of a regular n-gon.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
