Difference necklaces

MaRDI QIDQ5094084zbMATH OpenFDO

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

Publication date 2 August 2022

Full work available at URL https://arxiv.org/abs/2006.15250, https://cs.uwaterloo.ca/journals/JIS/VOL25/White/white2.html

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 927054 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Pattern containment in circular permutations
• Restricted permutations

Cited in

(8)

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

Describes a project that uses

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)