Difference Necklaces

Abstract

An $(a,b)$-difference necklace of length $n$ is a circular arrangement of the integers $0,1,2,\dots ,n-1$ such that any two neighbours have absolute difference $a$ or $b$. We prove that, subject to certain conditions on $a$ and $b$, such arrangements exist, and provide recurrence relations for the number of $(a,b)$-difference necklaces for $(a,b)=(1,2)$, $(1,3)$, $(2,3)$ and $(1,4)$. Using techniques similar to those employed for enumerating Hamiltonian cycles in certain families of graphs, we obtain these explicit recurrence relations and prove that the number of $(a,b)$-difference necklaces of length $n$ satisfies a linear recurrence relation for all permissible values $a$ and $b$. Our methods generalize to necklaces where an arbitrary number of differences is allowed.

32 pages, 20 figures, 4 tables

References in corpus (1)

• Fibonacci Plays Billiards