Journal of Integer Sequences, Vol. 25 (2022), Article 22.5.3

Difference Necklaces

Ethan P. White
Department of Mathematics
Room 121, 1984 Mathematics Road
Vancouver, BC V6T 1Z2

Richard K. Guy

Renate Scheidler
Department of Mathematics and Statistics
University of Calgary
2500 University Drive NW
Calgary, AB T2N 1N4


An S-necklace of length n is a circular arrangement of the integers 0, 1, 2, ..., n – 1 such that the absolute difference of two neighbors always belongs to S. Focusing in particular on the case |S| = 2, we prove that, subject to certain conditions on the two elements in S, the number of S-necklaces obeys a linear homogeneous recurrence relation. We give an algorithm for computing the corresponding generating function and compute generating functions and explicit recurrence relations for several small sets S. Our methods extend to sets S of any size.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A003520 A017899 A079977.)

Received February 22 2022; revised version received June 12 2022. Published in Journal of Integer Sequences, June 13 2022.

Return to Journal of Integer Sequences home page