ALTERNATING COLOURINGS OF THE VERTICES OF A REGULAR POLYGON

Let n, r; k epsilon N. An r-colouring of the vertices of a regular n-gon is any mapping chi : Z(n) -> {1, 2, ... r}. Two colourings are equivalent if one of them can be obtained from another by a rotation of the polygon. An r-ary necklace of length n is an equivalence class of r-colourings of Z(n). We say that a colouring is k-alternating if all k consecutive vertices have pairwise distinct colours. We compute the smallest number r for which there exists a k-alternating r-colouring of Z(n) and we count, for any r, 2-alternating r-colourings of Z(n) and 2-alternating r-ary necklaces of length n.