Difference necklaces

zbMATH Open1502.05007arXiv2006.15250MaRDI QIDQ5094084FDOQ5094084

Authors: Richard K. Guy, Ethan P. White, Renate Scheidler 

Publication date: 2 August 2022

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2006.15250

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• An algorithm for generating necklaces of beads in two colors
• Generating necklaces
• ENUMERATING NECKLACES WITH TRANSITIONS
• Gray codes for necklaces
• Perfect necklaces

zbMATH Keywords

generating functionHamiltonian cyclerecurrence relation\(S\)-necklace

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Eulerian and Hamiltonian graphs (05C45) Other combinatorial number theory (11B75) Recurrences (11B37)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pattern containment in circular permutations

Cited In (8)

• A bijection between necklaces and multisets with divisible subset sum
• Counting colorful necklaces and bracelets in three colors
• Perfect necklaces
• The Necklace Process
• On the number of bracelets whose co-periods divide a given integer
• On the number of antipodal bicolored necklaces
• On the number of necklaces whose co-periods divide a given integer
• On the maximum and minimum areas of the necklace

Uses Software

• SageMath
• OEIS

This page was built for publication: Difference necklaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5094084)