论文标题
差异项链
Difference Necklaces
论文作者
论文摘要
$（a，b）$ - 长度$ n $的差异项链是整数的通函安排$ 0、1、2，\ ldots，n-1 $，因此任何两个邻居都有绝对差异$ a $ a $ a $ a $ a或$ b $。我们证明，在$ a $ a和$ b $的某些条件下，存在此类安排，并为$（a，b）$ - 差异项链提供$（a，b）=（a，b）=（1，2）$，$（1，3）$，$（2，2，2，3）$（1，3）$和$（1，4）$的重复关系。使用类似于某些图形家庭中列举哈密顿周期的技术，我们获得了这些明确的复发关系，并证明$（a，b）$ - 长度$ n $的差异项链满足所有允许值$ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $和$ b $的差异。我们的方法推广到允许任意数量差异的项链。
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.
