math.CO math.NT
Difference Necklaces. An (a,b) difference necklace of length n is a circular arrangement of the integers 0, 1, 2, ldots , 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.