<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,recno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{url}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\renewcommand{\pmod}[1]{{\ifmmode\text{\rm\ (mod~$#1$)}\else\discretionary{}{}{\hbox{ }}\rm(mod~$#1$)\fi}}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{alg}[theorem]{Algorithm}

\numberwithin{equation}{section}
\numberwithin{table}{section}
\numberwithin{figure}{section}

\begin{center}
\vskip 1cm{\LARGE\bf
Difference Necklaces
}
\vskip 1cm
\large
Ethan P.\ White\footnote{The first author is supported by funding from NSERC and the Killam Trusts.} \\
Department of Mathematics  \\ 
Room 121, 1984 Mathematics Road \\ 
Vancouver, BC V6T 1Z2
Canada \\
\href{mailto:epwhite@math.ubc.ca}{\tt epwhite@math.ubc.ca} \\
\ \\
Richard K.\ Guy\footnote{Deceased.} \\
\ \\
Renate Scheidler\footnote{The third author is supported by NSERC Discovery Grant RGPIN-2019-04844.} \\
Department of Mathematics and Statistics \\
University of Calgary \\
2500 University Drive NW \\
Calgary, AB T2N 1N4 \\
Canada \\
\href{mailto:rscheidl@ucalgary.ca}{\tt rscheidl@ucalgary.ca}
\end{center}

\vskip .2 in

\begin{abstract}
An $S$-necklace of length $n$ is a circular arrangement of the integers $0, 1, 2, \ldots , n-1$ such that the absolute difference of two neighbors always belongs to $S$. Focusing in particular on the case $|S| = 2$, we prove that, subject to certain conditions on the two elements in $S$, the number of $S$-necklaces obeys a linear homogeneous recurrence relation. We give an algorithm for computing the corresponding generating function and compute generating functions and explicit recurrence relations for several small sets $S$. Our methods extend to sets $S$ of any size. 
\end{abstract}




\section{Introduction}


Let $n \geq 3$ be a positive integer and $[n]$ denote the set $\{0,1,\ldots,n-1\}$. A circular permutation of $[n]$ is an arrangement of the elements of $[n]$ on a circle. Two circular permutations on $[n]$ are equal if one can be obtained by rotating or flipping the other. 

Now let $S$ be a finite set of positive integers. An \emph{$S$-(difference) necklace} of length $n$ is a circular permutation of $[n]$ such  that the absolute difference between adjacent terms belongs to $S$. A $\{4,7\}$-necklace of length 11 is depicted in Figure~\ref{47}. 

\begin{figure}[ht]    
\begin{center}
\begin{tikzpicture}
{
\draw (1*360/11 :1.25 cm) node{0}; 
\draw (2*360/11 :1.25 cm) node{4}; 
\draw (3*360/11 :1.25 cm) node{8}; 
\draw (4*360/11 :1.25 cm) node{1};
\draw (5*360/11 :1.25 cm) node{5};
\draw (6*360/11 :1.25 cm) node{9};
\draw (7*360/11 :1.25 cm) node{2};
\draw (8*360/11 :1.25 cm) node{6};
\draw (9*360/11 :1.25 cm) node{10};
\draw (10*360/11 :1.25 cm) node{3};
\draw (11*360/11 :1.25 cm) node{7};}
\end{tikzpicture}
\end{center}
\caption{A $\{4,7\}$-necklace of length 11. Any two neighbors differ by $\pm 4$ or $\pm 7$.}
\label{47}
\end{figure}

Our primary goal is to analyze the count of difference necklaces of length~$n$. The problem of counting and enumerating permutations according to the containment or avoidance of particular patterns is the subject of intense research; see, for example, the seminal paper by Simion and Schmidt~\cite{RSSF} or the more recent article by Gray, Lanning, and Wang~\cite{GLW}. Most previous work on circular permutations explores relative increases and decreases of elements. In contrast, we consider the absolute difference between successive terms. It is expedient to cast difference necklaces in the language of graph theory. To that end, we define $G_S(n)$ to be the graph on $[n]$ where two vertices $x,y$ are adjacent if and only if $|x-y|  \in S$; we show an example in Figure~\ref{15graph}. Then the $S$-difference necklaces are precisely the Hamiltonian cycles of $G_S(n)$. Note that $G_S(n)$ can be obtained by deleting certain edges from the undirected Caley graph on $\mathbb{Z}/n\mathbb{Z}$ with generating set~$S$. 

Let $N_S(n)$ denote the number of difference necklaces of length $n$, or equivalently, the number of Hamiltonian cycles in $G_S(n)$. Then our main result is the following. 

\begin{theorem}\label{LRthm}
Let $S$ be a non-empty finite set of positive integers. Then the sequence $(N_S(n))_{n \in \mathbb{N}}$ obeys a homogeneous linear recurrence relation with constant coefficients. That is, there exist a positive integer $d$ and integers $c_1,c_2,\ldots,c_d$, depending on $S$, such that 
\[ 
N_S(n) = \sum_{i = 1}^d c_iN_S(n-i) .
\]
\end{theorem}

In previous work~\cite{WGS}, we presented a highly technical construction for ``growing'' $S$-necklaces via walks in a digraph, which, in particular, implies this theorem. Here, we provide a substantially streamlined and much more useful proof of Theorem~\ref{LRthm}. The key feature of our proof herein is that it offers a general algorithm for finding the generating function of $(N_S(n))_{n \in \mathbb{N}}$. We focus in particular on the case $|S| = 2$ and explicitly compute the generating functions for several two-element sets $S$ as well as the set $S = \{1, 2, 3\}$. For ease of notation, we omit set brackets in $N_S(n)$ and $G_S(n)$ when listing the elements of $S$ explicitly. For example, when $S = \{1,5\}$, we write~$N_{1,5}(n)$ and~$G_{1,5}(n)$ instead of~$N_{\{1,5\}}(n)$ and~$G_{\{1,5\}}(n)$. 


\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=1]
\node[draw][circle](1) at (0,4) {0};
\node[draw][circle](2) at (0,3) {1};
\node[draw][circle](3) at (0,2) {2};
\node[draw][circle](4) at (0,1) {3};
\node[draw][circle](5) at (0,0) {4};
\node[draw][circle](6) at (1.7,4) {5};
\node[draw][circle](7) at (1.7,3) {6};
\node[draw][circle](8) at (1.7,2) {7};
\node[draw][circle](9) at (1.7,1) {8};
\node[draw][circle](10) at (1.7,0) {9};;
\node[draw][circle, inner sep=2pt](11) at (3.4,4) {10};
\node[draw][circle, inner sep=2pt](12) at (3.4,3) {11};
\node[draw][circle, inner sep=2pt](13) at (3.4,2) {12};
\node[draw][circle, inner sep=2pt](14) at (3.4,1) {13};
\node[draw][circle, inner sep=2pt](15) at (3.4,0) {14};
\node[draw][circle, inner sep=2pt](16) at (5.1,4) {15};
\node[draw][circle, inner sep=2pt](17) at (5.1,3) {16};
\node[draw][circle, inner sep=2pt](18) at (5.1,2) {17};


\draw (1)--(2)--(3)--(4)--(5)--(6)--(7)--(8)--(9)--(10)
(10)--(11)--(12)--(13)--(14)--(15)--(16)--(17)--(18) (1)--(6)--(11)--(16) (2)--(7)--(12)--(17)
(3)--(8)--(13)--(18) (4)--(9)--(14) (5)--(10)--(15);
\end{tikzpicture}
\end{center}
\caption{The graph $G_{1,5}(18)$. Any two adjacent vertices differ by $\pm 1$ or $\pm 5$.} \label{15graph}
\end{figure}

Figure~\ref{15graph} shows the graph $G_{1,5}(18)$. The drawing bears striking resemblance to a grid graph, i.e., a graph that is the Cartesian product of two path graphs. The proof of Theorem~\ref{LRthm} and the resulting method for obtaining generating functions for $(N_S(n))_{n \in \mathbb{N}}$ bear similarities to prior literature on counting Hamiltonian cycles in grid graphs. This is a difficult problem that has received significant attention and has to date only been solved in certain special cases. The current best explicit results are due to Stoyan and Strehl~\cite{SS} who determined the generating functions for the number of Hamiltonian cycles in an $m \times k$ grid graph for $m \leq 8$. 

Berlekamp and the second author~\cite{BG} investigated permutations where the sum (as opposed to the difference) of two neighbors is a number of a particular type, such as a prime, square, cube, or triangular number. They illustrated how a search for such permutations can be facilitated by considering paths of billiard balls on a rectangular or other polygonal billiard table. Using this technique, they gave necessary and sufficient conditions for the existence of (non-circular) permutations where adjacent terms sum to a Fibonacci or Lucas number. We provide a comprehensive survey of related literature in our prior work~\cite{WGS}.




\subsection{Existence of $S$-necklaces} \label{sec:existence}

Previously, we conducted an in-depth investigation of the existence of $S$-necklaces for the case $|S| = 2$~\cite{WGS}. Put $S = \{ a, b \}$ with $0 &lt; a &lt; b$. Then $\{a,b\}$-necklaces exist only when $\gcd(a,b) = 1$, and their smallest possible length is $a+b$. For completeness, we restate the main existence result and briefly outline the road map of its proof.

\begin{prop}[{\cite[Theorem 2.4]{WGS}}] \label{exist} 
Let $a$ and $b$ be positive coprime integers with $2a \leq b$. Then $\{a,b\}$-necklaces of length $n$ exist for all sufficiently large~$n$,
unless $abn$ is odd, in which case there are no $\{a,b\}$-necklaces of length $n$.
\end{prop}

Since $G_{a,b}(n)$ is bipartite, there are no $\{a,b\}$-necklaces of odd length $n$. For $a = 1$, a Hamiltonian cycle in  $G_{1,b}(n)$ can easily be found by tracing a ``snake pattern'' through the grid. For $a \ge 2$, the proof of Proposition~\ref{exist} proceeds as follows. Firstly, the graph $G_{a,b}(a+b)$ is  readily seen to be the circulant graph on jumps $a,b$, which is a cycle and hence an $\{a,b\}$-necklace of length $a+b$. Secondly, an $\{a,b\}$-necklace of length $3a+b$ can be constructed by ``stringing together'' residue classes  modulo $a$ in a suitable manner when $2a \le b$. Thirdly, an $\{a,b\}$-necklace of length $m+n$ can be formed from two $\{a,b\}$-necklaces of respective lengths $m,n$ by ``gluing'' along a pair of suitable links. Thus, $\{a,b\}$-necklaces exist of every length $x(a+b) + y(3a+b)$ with $x,y \ge 0$. Noting that $\gcd(a+b, 3a+b) = 1$ when $\gcd(a,b) = 1$, we can invoke Frobenius' Coin Problem~\cite[Theorem 2.1.1]{JR} to infer the existence of sufficiently long $\{a,b\}$-necklaces for all integers~$a,b$ subject to the conditions of Proposition~\ref{exist}. We also provided explicit lower bounds on~$n$ that guarantee their existence~\cite{WGS}. 

The existence of $\{a,b\}$-necklaces for $2a &gt; b$ is an open problem. We conjecture that they also exist for every sufficiently large length $n$ in this case, subject to the aforementioned necessary conditions on $a$, $b$, and $n$. Unfortunately, our construction~\cite{WGS} of $\{a,b\}$-necklaces of length $3a+b$ fails when $a$ and $b$ are too close together. 

\subsection{Organization of the paper}

In Section~\ref{secrec}, we provide a constructive proof of Theorem~\ref{LRthm} which is used to obtain explicit recurrence relations for $N_S(n)$ when $S = \{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{1,4\}$, and $\{1,2,3\}$ in Section~\ref{seccount}. In Section~\ref{seccomp}, we present algorithms for computing the generating functions for $N_S(n)$ when $S = \{a,b\}$ (i.e., $S$ contains two elements), and give their explicit expressions, along with some numerical data, for several small pairs $\{a,b\}$. Some concluding remarks are offered in Section~\ref{S:conclude}.




\section{Linear recurrence for $N_{a,b}(n)$} \label{secrec}

This section contains a proof of our main result (Theorem~\ref{LRthm}), namely the fact that for every finite set~$S$ of absolute difference values, the sequence $(N_S(n))_{n \in \mathbb{N}}$ obeys a linear recurrence. We present a proof in the case $|S|=2$, but the reasoning generalizes easily to larger sets $S$; see the remarks and example in Section~\ref{sec:123}. As in Section~\ref{sec:existence}, put $S = \{a,b\}$ with $0&lt;a&lt;b$. The  proof of Theorem~\ref{LRthm} is based on two key ideas. 

\begin{enumerate}[(A)] \itemsep 0pt
\item For every graph $H$ on $[b]$, we can explicitly construct graphs $H'$, $H''$ on $[b]$ from $H$ such that the number of Hamiltonian cycles in $G_{a,b}(n)$ containing $H$ depends only on the number of Hamiltonian cycles in $G_{a,b}(n-1)$ containing $H'$ or $H''$.
\item Since there are finitely many graphs $H$ on $b$ vertices, (A) yields a finite system of coupled difference equations, one of which is satisfied by $N_{a,b}(n)$.
\end{enumerate}

\begin{defn}\label{Hnecklaces} Let $H$ be a graph with vertex set $[b]$. Define the graph $G^H_{a,b}(n)$ to have vertex set $[n]$ and edge set $E(G_{a,b}(n)) \cup E(H)$. Let $\mathcal{C}(G^H_{a,b}(n))$ denote the collection of all Hamiltonian cycles of $G^H_{a,b}(n)$ containing~$H$. 
\end{defn}



\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=1]

\filldraw

(0,0) circle (2pt)
(0,1) circle (2pt)
(1,1) circle (2pt)

(5,0) circle (2pt)
(5,1) circle (2pt)
(6,0) circle (2pt)
(6,1) circle (2pt)
(7,1) circle (2pt)

(10,0) circle (2pt)
(10,1) circle (2pt)
(11,0) circle (2pt)
(11,1) circle (2pt)
(12,1) circle (2pt);

\draw

(0,1)--(1,1)

(5,1)--(5,0)
(5,1)--(6,1)
(5,0)--(7,1)
(7,1)--(6,0)
(6,1)--(6,0)

(10,0)--(11,1)
(11,0)--(10,1)
(10,1)--(11,1)
(10,0)--(12,1)
(11,0)--(12,1);


\draw
(-0.25,1) node{\small{$0$}}
(-0.25,0) node{\small{$1$}}
(1.25,1) node{\small{$2$}};

\draw
(4.75,1) node{\small{$0$}}
(4.75,0) node{\small{$1$}}
(6.25,1) node{\small{$2$}}
(6.25,0) node{\small{$3$}}
(7.25,1) node{\small{$4$}};

\draw
(9.75,1) node{\small{$0$}}
(9.75,0) node{\small{$1$}}
(11.25,1) node{\small{$2$}}
(11.25,0) node{\small{$3$}}
(12.25,1) node{\small{$4$}};


\end{tikzpicture}
\end{center}
\caption{A graph $H$ on the left and two members of $\mathcal{C}(G^H_{1,3}(5))$ on the right.}
\label{defnpicdemo}
\end{figure}

Note that for the independent graph $I_b$,  $\mathcal{C}(G^{I_b}_{a,b}(n))$ is precisely the set of $\{a,b\}$-necklaces of length $n$. If $H$ has maximum degree exceeding 2, then $\mathcal{C}(G^H_{a,b}(n))$ is empty. Figure~\ref{defnpicdemo} depicts a graph $H$ with vertex set $[3]$ and two members of $\mathcal{C}(G^H_{1,3}(5))$. 

To prove Theorem~\ref{LRthm}, we establish a recursive property held by $|\mathcal{C}(G^H_{a,b}(n))|$. For every graph $H$ on $[b]$ with maximum degree 2, we show that there exist suitable graphs $H', H''$ with vertex set $[b]$ and maximum degree 2 such that 
\begin{equation} \label{cyclerec}
\begin{aligned}  
    |\mathcal{C}(G^H_{a,b}(n))|  &amp; =0 \quad \text{ or}  \\
    |\mathcal{C}(G^H_{a,b}(n))|  &amp; = |\mathcal{C}(G^{H'}_{a,b}(n-1))| \quad \text{ or}  \\
    |\mathcal{C}(G^H_{a,b}(n))|  &amp; =|\mathcal{C}(G^{H'}_{a,b}(n-1))| + |\mathcal{C}(G^{H''}_{a,b}(n-1))|  .  \quad 
\end{aligned} 
\end{equation}

This implies that the collection of sequences $(|\mathcal{C}(G^H_{a,b}(n))|)_{n \geq b}$ satisfies a system of coupled simultaneous linear recurrences. Applying standard techniques for decoupling linked difference equations (see~\cite{KL}, for example) produces a single linear recurrence relation for $|\mathcal{C}_{a,b}^{I_b}(n)| = N_{a,b}(n)$ as asserted in Theorem~\ref{LRthm}.

For brevity, let $\deg_G(v)$ denote the degree of a vertex $v$ in a graph $G$ and $\Delta(G)$ the maximum degree of $G$. 

\begin{proof}[Proof of Theorem~\ref{LRthm}.] Let $H$ be a graph on $[b]$. If $\Delta(H) &gt; 2$, then $\mathcal{C}(G_{a,b}^H(n))$ is empty, so assume that $\Delta(H) \le 2$. 
We consider three cases, according to the degree of vertex 0 in $H$. 

\medskip

\noindent \textbf{Case 1.} Suppose $\deg_H(0) = 0$. 
Then every $C \in \mathcal{C}(G^H_{a,b}(n))$ contains the path $a, 0, b$ and can hence contain at most one edge in $H$ incident with $a$. Thus, $|\mathcal{C}(G^H_{a,b}(n)) |= 0$ when $\deg_H(a) = 2$. So assume now that $\deg_H(a) \le 1$. We form a graph~$H'$ on the vertices in $[b]$ with $\Delta(H') \le 2$ by performing the following operations on~$H$:
\begin{itemize}
\item[(i)] add the vertex $b$ and the edge $a,b$;
\item[(ii)] delete the vertex $0$;
\item[(iii)] shift all vertex labels down by 1.
\end{itemize}
An example of this construction is depicted in Figure~\ref{case1pic}.

We establish a bijection between $\mathcal{C}(G_{a,b}^H(n))$ and $\mathcal{C}(G_{a,b}^{H'}(n-1))$. Every $C \in \mathcal{C}(G^H_{a,b}(n))$ contains the path $a,0,b$. Replacing this path with the edge $a,b$ and then shifting all vertex labels of $C$ down by 1 yields a Hamiltonian cycle in $\mathcal{C}(G_{a,b}^{H'}(n-1))$. Conversely, every $C \in \mathcal{C}(G^{H'}_{a,b}(n-1))$ contains the edge $a-1,b-1$. Shifting all vertex labels of $C$ up by 1 and then replacing the edge $a,b$ by the path $a,0,b$ in the resulting labeled cycle produces a Hamiltonian cycle in $\mathcal{C}(G^H_{a,b}(n))$.




\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=1]

\def\x{-1}

\filldraw

(-1+\x,0) circle (2pt)
(-1+\x,1) circle (2pt)
(0+\x,0) circle (2pt)
(0+\x,1) circle (2pt)

(4+\x,0) circle (2pt)
(4+\x,1) circle (2pt)
(5+\x,0) circle (2pt)
(5+\x,1) circle (2pt)
(6+\x,1) circle (2pt)

(10,0) circle (2pt)
(10,1) circle (2pt)
(11,0) circle (2pt)
(11,1) circle (2pt);

\draw

(-1+\x,0)--(0+\x,0)

(4+\x,0)--(5+\x,0)
(4+\x,1)--(4+\x,0)

(10,1)--(11,1)
(10,1)--(11,0);

\draw[dotted]
(4+\x,0)--(6+\x,1);

\draw
(4+\x,1) to [out = 30, in = 150] (6+\x,1);


\draw
(-0.5+\x,-1) node{$H$}


(10.5,-1) node{$H'$};


\draw

(2+\x,0.5) node{$\longrightarrow$}

(2+\x,0.85) node{\scriptsize{All cycles contain}}
(2+\x,0.25) node{\scriptsize{path $1,0,4$}}

(7.5,0.85) node{\scriptsize{Replace path with edge}}
(7.5,0.25) node{\scriptsize{Shift labels down}}
(7.5,0.5) node{$\longrightarrow$};


\draw
(-1.25+\x,1) node{\small{$0$}}
(-1.25+\x,0) node{\small{$1$}}
(0.25+\x,1) node{\small{$2$}}
(0.25+\x,0) node{\small{$3$}}

(-1.25+5+\x,1) node{\small{$0$}}
(-1.25+5+\x,0) node{\small{$1$}}
(0.25+5+\x,1) node{\small{$2$}}
(0.25+5+\x,0) node{\small{$3$}}
(0.25+6+\x,1) node{\small{$4$}}

(-1.25+11,1) node{\small{$0$}}
(-1.25+11,0) node{\small{$1$}}
(0.25+11,1) node{\small{$2$}}
(0.25+11,0) node{\small{$3$}};



\end{tikzpicture}
\end{center}
\caption{Example for Case 1 with $a = 1, b = 4$.}
\label{case1pic}
\end{figure}


\noindent \textbf{Case 2.} Suppose $\deg_H(0) = 1$. Let $u \in [b]$ be the neighbor of $0$ in $H$. We consider two subcases. 

\medskip

\textit{Case 2.i.} Suppose $u = a$. Then every $C \in \mathcal{C}(G^H_{a,b}(n))$ contains the path $a,0,b$ and we can construct a graph $H'$ just as in Case 1. 

\medskip

\textit{Case 2.ii.} Suppose $u\neq a$. For $x \in \{a,b\}$, define the two graphs $H_a,H_b$ on~$[b]$ by performing the following operations on $H$: 
\begin{itemize}
\item[(i)] add the edge $\{u,x\}$;
\item[(ii)] delete the vertex $0$; 
\item[(iii)] shift all vertex indices down by 1;
\item[(iv)] add vertex~$b-1$.
\end{itemize}
We will show that 
\begin{equation}\label{case2ii} 
|\mathcal{C}(G^H_{a,b}(n))| = |\mathcal{C}(G^{H_a}_{a,b}(n-1))|+|\mathcal{C}(G^{H_b}_{a,b}(n-1))|  .
\end{equation}
Partition $\mathcal{C}(G^H_{a,b}(n))$ into two sets $S_a$ and $S_b$ consisting of the cycles containing the paths $u,0,a$ and $u,0,b$, respectively. Every cycle $C \in S_a$ corresponds to a cycle in $\mathcal{C}(G^{H_a}_{a,b}(n-1))$ via the following operations:
\begin{itemize}
\item[(i)] replace the path $u,0,a$ with the edge $u,a$;
\item[(ii)] delete the vertex 0;
\item[(iii)] shift all vertex labels down by 1.
\end{itemize}
This process can be inverted, so there is a bijection between $S_a$ and $\mathcal{C}(G^{H_a}_{a,b}(n-1))$. An analogous bijection exists between $S_b$ and $\mathcal{C}(G^{H_b}_{a,b}(n-1))$, thus proving~\eqref{case2ii}. Figure~\ref{case2iipic} shows an example of this construction.

\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=1]

\filldraw

(0,0) circle (2pt)
(0,1) circle (2pt)
(1,0) circle (2pt)
(1,1) circle (2pt)

(5,0) circle (2pt)
(5,1) circle (2pt)
(6,0) circle (2pt)
(6,1) circle (2pt)

(10,0) circle (2pt)
(10,1) circle (2pt)
(11,0) circle (2pt)
(11,1) circle (2pt);

\draw

(0,0)--(1,1)
(1,0)--(0,1)

(5,1)--(5,0)
(5,1)--(6,1)

(10,1)--(10,0)
(11,1)--(11,0);

\draw
(0.5,-1) node{$H$}
(0.5,-2) node{$|\mathcal{C}(G^H_{a,b}(n))|$}

(5.5,-1) node{$H_a$}
(5.5,-2) node{$|\mathcal{C}(G^{H_a}_{a,b}(n-1))|$}

(10.5,-1) node{$H_b$}
(10.5,-2) node{$|\mathcal{C}(G^{H_b}_{a,b}(n-1))|$};

\draw

(3,0.5) node{$\longrightarrow$}
(3,0.75) node{$-1$}
(3,0.25) node{\scriptsize{Edges replace paths}}
(3,-0.05) node{\scriptsize{Labels shifted down}}

(3,-2) node{$=$}

(8,0.5) node{$+$}
(8 ,-2) node{$+$};

\draw
(-0.25,1) node{\small{$0$}}
(-0.25,0) node{\small{$1$}}
(1.25,1) node{\small{$2$}}
(1.25,0) node{\small{$3$}};

\draw
(4.75,1) node{\small{$0$}}
(4.75,0) node{\small{$1$}}
(6.25,1) node{\small{$2$}}
(6.25,0) node{\small{$3$}};

\draw
(9.75,1) node{\small{$0$}}
(9.75,0) node{\small{$1$}}
(11.25,1) node{\small{$2$}}
(11.25,0) node{\small{$3$}};

\end{tikzpicture}
\end{center}
\caption{Example for Case 2.ii with $a = 1, b = 4$.}
\label{case2iipic}
\end{figure}

Since $\Delta(H) \leq 2$ we have $\Delta(H_b)\leq 2$. Similarly, $\Delta(H_a) \le 2$ if and only if $\deg_H(a) \le 1$; if $\deg_H(a) = 2$, then $\Delta(H_a) &gt; 2$ and hence $\mathcal{C}(G^{H_a}_{a,b}(n-1))$ is empty.  

\bigskip

\noindent\textbf{Case 3.} Suppose $\deg_H(0) = 2$. Let $u,v\in [b]$ be the two neighbors of~$0$ in $H$. Build a graph $H'$ on $[b]$ by performing the following operations on $H$: 
\begin{itemize}
\item[(i)] add the edge $\{u,v\}$;
\item[(ii)] delete the vertex $0$;
\item[(iii)] shift all vertex indices down by 1 by relabeling;
\item[(iv)] add vertex $b-1$.
\end{itemize}
Similar reasoning as in the previous cases shows that there is a bijection between $\mathcal{C}(G^H_{a,b}(n))$ and $\mathcal{C}(G^{H'}_{a,b}(n-1))$ because the path $u,0,v$ in every Hamiltonian cycle of $\mathcal{C}(G^H_{a,b}(n))$ can be exchanged with the edge $u-1,v-1$ in every Hamiltonian cycle of $\mathcal{C}(G^{H_1}_{a,b}(n-1))$. 

The above construction establishes a system of simultaneous recurrence relations of the form~\eqref{cyclerec} for every graph $H$ on $[b]$. Applying this result to the special case $H = I_b$ proves that $N_{a,b}(n) = |\mathcal{C}(G_{a,b}^{I_b}(n))|$ satisfies a homogeneous linear recurrence relation. 
\end{proof}

In the next section, we explicitly construct the sequence of graphs and the system of recurrence relations of the above proof for some small pairs $\{a,b\}$ and for the set $S = \{ 1, 2, 3 \}$. The number of recurrences grows exponentially as $a,b$ increase, rendering by-hand analysis impractical even for modest values of $a,b$. We have computerized the process of building these recurrences and discuss our implementation and some numerical data in Section~\ref{seccomp}.





\section{Explicit $S$-necklace counts} \label{seccount}

In this section, we apply the technique from Section~\ref{secrec} to obtain explicit linear recurrence relations for $N_{a,b}(n)$ when $\{a,b\} \in \big \{\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{1,4\} \big \}$ and for $N_S(n)$ when $S = \{1,2,3\}$. 
To that end, we derive coupled recurrences as given in~\eqref{cyclerec} and construct graphs as described in the proof of Theorem~\ref{LRthm}. We begin each construction with $H_0 = I_b$, the independent graph with vertex set $[b]$, and let $H_1, H_2, \ldots$ denote the graphs obtained through repeated application of the constructions in the proof of Theorem~\ref{LRthm}. We use the pictorial style of Figures~\ref{case1pic} and~\ref{case2iipic} to represent these recurrences and the corresponding graphs. Not surprisingly, the recurrence diagrams become increasingly complicated as $a$ and $b$ increase; already for parameters as small as $a = 1$ and $b=4$, the process is quite involved. 

Recall that $N _{a,b}(n) = 0$ for $n &lt; a+b$, so we provide initial values for $N_{a,b}(n)$ starting at $n=a+b$. Recall also that $N_{a,b}(n) = 0$ when $abn$ is odd.



\subsection{Counting $\{1,2\}$-necklaces} \label{sec12}

We begin with $H_0 = I_1$. This is an instance of Case 1 in the proof of Theorem~\ref{LRthm}. Following the construction described there, we obtain the graph $H_1$ on $\{0,1\}$ with one edge; see Figure~\ref{12rec1}. 


\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=1]

\filldraw

(0,0) circle (2pt)
(0,1) circle (2pt)

(4,0) circle (2pt)
(4,1) circle (2pt);
\draw

(4,0)--(4,1);


\draw

(2,0.5) node{$\longrightarrow$}
(2,0.75) node{$-1$}
(2,-1) node{$=$}
(0,-1) node{$|\mathcal{C}(G_{1,2}^{H_0}(n))|$}
(4,-1) node{$|\mathcal{C}(G_{1,2}^{H_1}(n-1))|$};

\draw
(-0.25,1) node{\small{$0$}}
(-0.25,0) node{\small{$1$}};

\end{tikzpicture}
\end{center}

\caption{Recurrence diagram for $\{1,2\}$-necklaces: part 1.}
\label{12rec1}
\end{figure}


Now we apply~\eqref{cyclerec} with $H = H_1$. This is an instance of Case 2.i in the proof of Theorem~\ref{LRthm}. The construction in this case yields the graph $H_2 = H_1$, as seen in Figure~\ref{12rec2}.  

\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=1]

\filldraw

(0,0) circle (2pt)
(0,1) circle (2pt)

(4,0) circle (2pt)
(4,1) circle (2pt);
\draw
(0,0)--(0,1)
(4,0)--(4,1);


\draw

(2,0.5) node{$\longrightarrow$}
(2,0.75) node{$-1$}
(2,-1) node{$=$}
(0,-1) node{$|\mathcal{C}(G_{1,2}^{H_1}(n))|$}
(4,-1) node{$|\mathcal{C}(G_{1,2}^{H_2}(n-1))|$};

\draw
(-0.25,1) node{\small{$0$}}
(-0.25,0) node{\small{$1$}};

\end{tikzpicture}
\end{center}
\caption{Recurrence diagram for $\{1,2\}$-necklaces: part 2.}
\label{12rec2}
\end{figure}


Since $N_{1,2}(3) = 1$, we conclude that 
\[ 
N_{1,2}(n) = 1 \quad \text{for all } n \geq 3. 
\]
This result can also be obtained directly by recognizing that up to flips and rotations, the only way of constructing a $\{1,2\}$-necklace is by tracing a cycle starting at~0, moving along all the even numbers up to~$n-1$ in ascending order, followed by all the odd numbers from~$n-1$ down to~1 in descending order, and finally moving back to~0 to close the cycle. 



\subsection{Counting $\{1,3\}$-necklaces} \label{sec13}

Starting with $H_0 = I_2$, we display the sequence of identities derived from~\eqref{cyclerec} and the graphs obtained via the proof technique for Theorem~\ref{LRthm} in Figure~\ref{13rec}. 


\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=0.8]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(4,1)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,3}^{H_0}(n))|=|\mathcal{C}(G_{1,3}^{H_1}(n-1))|$};

\draw
(-0.5,1) node{\small{$0$}}
(-0.5,0) node{\small{$1$}}
(1.5,1) node{\small{$2$}};


\begin{scope}[xshift = 9cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt);


\draw
(0,1)--(1,1)
(4,0)--(4,1)
(8,0)--(9,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,3}^{H_1}(n))|= |\mathcal{C}(G_{1,3}^{H_2}(n-1))|+|\mathcal{C}(G_{1,3}^{H_3}(n-1))|$};



\end{scope}

\begin{scope}[yshift= -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,0)--(0,1)
(4,1)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,3}^{H_2}(n))|=|\mathcal{C}(G_{1,3}^{H_1}(n-1))|$};
\end{scope}

\begin{scope}[xshift = 9cm,yshift = -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt);

\draw
(0,0)--(1,1)
(4,0)--(4,1)
(4,1)--(5,1)
(8,0)--(8,1);

\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$\longrightarrow$}
(6.4,0.8) node{$-1$}
(4.5,-1) node{$|\mathcal{C}(G_{1,3}^{H_3}(n))|= |\mathcal{C}(G_{1,3}^{H_4}(n-1))|=|\mathcal{C}(G_{1,3}^{H_2}(n-2))|$};



\end{scope}

\end{tikzpicture}
\end{center}

\caption{Recurrence diagram for $\{1,3\}$-necklaces.}
\label{13rec}
\end{figure}

To obtain a recurrence relation for $N_{1,3}(n)$, note that $0$ and $1$ are adjacent in all $\{1,3\}$-necklaces, so $|\mathcal{C}(G_{1,3}^{H_0}(n))| = |\mathcal{C}(G_{1,3}^{H_2}(n))|$. From the identities in Figure~\ref{13rec} we deduce that 
\[ 
|\mathcal{C}(G_{1,3}^{H_2}(n))| = |\mathcal{C}(G_{1,3}^{H_2}(n-2))| + |\mathcal{C}(G_{1,3}^{H_2}(n-4))|.
\]
It is easy to check that $N_{1,3}(4)=1$ and $N_{1,3}(6) = 2$, so 
\[ 
N_{1,3}(n) = \begin{cases} F_{n/2}, &amp; \text{if } n \ge 4 \text{ is even;}\\ 
0, &amp; \text{if } n \ge 5 \text{ is odd,}
 \end{cases} 
\]
where $F_n$ is the $n^{\textrm{th}}$ Fibonacci number (with $F_0 = 0$ and $F_1 = 1$). The Fibonacci numbers interspersed with zeroes appear in the \emph{Online Encyclopedia of Integer Sequences} (OEIS)~\cite{NS} as~\seqnum{A079977}, a note on $\{1,3\}$-necklaces is included in this entry. 








\subsection{Counting $\{2,3\}$-necklaces} \label{sec23}

As before, we begin with $H_0 = I_3$ and show the relevant equations of the form~\eqref{cyclerec} and the corresponding graphs in Figure~\ref{23rec}.


\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=0.75]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(4,0)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{2,3}^{H_0}(n))|=|\mathcal{C}(G_{2,3}^{H_1}(n-1))|$};

\draw
(-0.5,1) node{\small{$0$}}
(-0.5,0) node{\small{$1$}}
(1.5,1) node{\small{$2$}};


\begin{scope}[xshift = 12cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,0)--(1,1)
(4,0)--(4,1)
(4,0)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{2,3}^{H_1}(n))|=|\mathcal{C}(G_{2,3}^{H_2}(n-1))|$};


\end{scope}

\begin{scope}[yshift= -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,0)--(0,1)
(0,0)--(1,1)
(4,0)--(4,1)
(4,1)--(5,1);



\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{2,3}^{H_2}(n))|=|\mathcal{C}(G_{2,3}^{H_3}(n-1))|$};
\end{scope}

\begin{scope}[xshift = 12cm,yshift = -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,0)--(0,1)
(0,1)--(1,1)
(4,0)--(4,1);



\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{2,3}^{H_3}(n))|=|\mathcal{C}(G_{2,3}^{H_4}(n-1))|$};



\end{scope}



\begin{scope}[xshift = -2cm, yshift= -6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt);

\draw
(0,0)--(0,1)
(4,0)--(4,1)
(8,1)--(9,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{2,3}^{H_4}(n))|= |\mathcal{C}(G_{2,3}^{H_4}(n-1))|+|\mathcal{C}(G_{2,3}^{H_5}(n-1))|$};




\end{scope}

\begin{scope}[xshift = 12cm,yshift = -6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,1)--(1,1)
(4,0)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{2,3}^{H_5}(n)|=|\mathcal{C}(G_{2,3}^{H_1}(n-1))|$};

\end{scope}

\end{tikzpicture}
\end{center}
\caption{Recurrence diagram for $\{2,3\}$-necklaces.}
\label{23rec}
\end{figure}


In all $\{2,3\}$-necklaces, vertices $0$ and $2$ are adjacent, so $N_{2,3}(n) = |\mathcal{C}(G_{2,3}^{H_0}(n))|$ $ = |\mathcal{C}(G_{2,3}^{H_5}(n))|$. Making the appropriate substitutions for the quantities derived in Figure~\ref{23rec}, we obtain 
\[ 
N_{2,3}(n) = N_{2,3}(n-1)+N_{2,3}(n-5).
\]
It is easy to find initial values of $N_{2,3}(n)$ by hand; they are shown in Table~\ref{23initterms}. We remark that the sequence given by $N_{2,3}(n)$ is~\seqnum{A017899} in OEIS; the entry points out the connection to $\{2,3\}$-necklaces. In addition, \seqnum{A003520} is the same sequence modulo a shift. Note that the denominator of the generating function of $N_{2,3}(n)$, given in Table~\ref{genfunc}, is irreducible. Hence $N_{2,3}(n)$ does not satisfy a linear recurrence of order less than 5. 

\begin{table} \centering
 \begin{tabular}{| c || c | c |c |} 
 \hline
         $n$  &amp; $5$ &amp; $6$ &amp; $7$ \\ 
 \hline
 $N_{2,3}(n)$ &amp; $1$ &amp; $0$ &amp; $0$  \\ 
 \hline
\end{tabular}
\caption{Initial values of $N_{2,3}(n)$.}
\label{23initterms}
\end{table}



\subsection{Counting $\{1,4\}$-necklaces} \label{sec14}

Starting with $H_0 = I_4$, Figure~\ref{14rec} shows the counts and graphs involved in deriving a recurrence relation for $N_{1,4}(n)$. 

As in the previous subsection, is possible to combine the equations in Figure~\ref{14rec} to find a recurrence relation containing  only terms in the sequence $(\mathcal{C}(G_{a,b}^{H_0}(n))_{n}$. Instead, we show a more mechanical strategy that is well suited for computer implementation. The equations in Figure~\ref{14rec} yield the transition matrix equation~\eqref{14matrix}; to reduce the notational burden, we put $T_i(n)=\mathcal{C}(G_{1,4}^{H_i}(n) )$ for $0 \leq i \leq 11$. 
\setcounter{MaxMatrixCols}{12}
\setlength{\arraycolsep}{4pt}
\begin{equation}\footnotesize\label{14matrix}
\begin{pmatrix} 
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\
0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
\end{pmatrix} \begin{pmatrix} T_0(n-1) \\ T_1(n-1) \\ T_2(n-1) \\T_3(n-1) \\T_4(n-1) \\T_5(n-1) \\T_6(n-1) \\T_7(n-1) \\T_8(n-1) \\T_9(n-1) \\T_{10}(n-1) \\T_{11}(n-1) \\ \end{pmatrix} = \begin{pmatrix} T_0(n) \\ T_1(n) \\ T_2(n) \\T_3(n) \\T_4(n) \\T_5(n) \\T_6(n) \\T_7(n) \\T_8(n) \\T_9(n) \\T_{10}(n) \\T_{11}(n) \\ \end{pmatrix} .
\end{equation}

\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=0.76]


\begin{scope}[xshift = -3cm]
\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw 
(4,1)--(5,0);




\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_0}(n))|=|\mathcal{C}(G_{1,4}^{H_1}(n-1))|$};

\draw
(-0.5,1) node{\small{$0$}}
(-0.5,0) node{\small{$1$}}
(1.5,1) node{\small{$2$}}
(1.5,0) node{\small{$3$}};
\end{scope}


\begin{scope}[xshift = 6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt)
(9,0) circle (3pt);

\draw

(0,1)--(1,0)
(4,1)--(5,1)
(9,0)--(9,1);



\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_1}(n))|= |\mathcal{C}(G_{1,4}^{H_2}(n-1))|+|\mathcal{C}(G_{1,4}^{H_3}(n-1))|$};

\end{scope}

\begin{scope}[xshift = -3cm, yshift= -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt)
(9,0) circle (3pt);

\draw

(0,1)--(1,1)
(4,0)--(4,1)
(8,0)--(9,0);




\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_2}(n))|= |\mathcal{C}(G_{1,4}^{H_4}(n-1))|+|\mathcal{C}(G_{a,b}^{H_5}(n-1))|$};


\end{scope}

\begin{scope}[xshift = 10cm,yshift = -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(1,0)--(1,1)
(4,0)--(5,1)
(4,1)--(5,0);



\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_3}(n))|=|\mathcal{C}(G_{1,4}^{H_6}(n-1))|$};


\end{scope}

\begin{scope}[xshift = -2cm,yshift= -6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(0,0)--(0,1)
(4,1)--(5,0);

\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_4}(n))|=|\mathcal{C}(G_{1,4}^{H_1}(n-1))|$};




\end{scope}

\begin{scope}[xshift = 10cm,yshift = -6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(0,0)--(1,0)
(4,1)--(5,1)
(4,1)--(5,0);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_5}(n))|=|\mathcal{C}(G_{1,4}^{H_7}(n-1))|$};

\end{scope}

\begin{scope}[xshift = -3cm,yshift= -9cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt)
(9,0) circle (3pt);

\draw
(0,1)--(1,0)
(0,0)--(1,1)
(4,0)--(4,1)
(4,1)--(5,1)
(8,0)--(8,1)
(9,0)--(9,1);




\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_6}(n))|= |\mathcal{C}(G_{1,4}^{H_8}(n-1))|+|\mathcal{C}(G_{1,4}^{H_9}(n-1))|$};


\end{scope}

\begin{scope}[xshift = 10cm,yshift = -9cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(0,1)--(1,1)
(0,1)--(1,0)
(4,0)--(5,1);




\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_7}(n))|=|\mathcal{C}(G_{1,4}^{H_{10}}(n-1))|$};

\end{scope}


\begin{scope}[xshift = -2cm,yshift= -12cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(0,0)--(0,1)
(0,1)--(1,1)
(4,0)--(4,1);




\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_8}(n))|=|\mathcal{C}(G_{1,4}^{H_4}(n-1))|$};

\end{scope}

\begin{scope}[xshift = 10cm,yshift = -12cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(0,0)--(0,1)
(1,0)--(1,1)
(4,0)--(5,1)
(4,1)--(5,0);





\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_9}(n))|=|\mathcal{C}(G_{1,4}^{H_6}(n-1))|$};

\end{scope}


\begin{scope}[xshift = -2cm,yshift= -15cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);

\draw
(0,0)--(1,1)
(4,1)--(5,0)
(4,1)--(4,0);





\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_{10}}(n))|=|\mathcal{C}(G_{1,4}^{H_{11}}(n-1))|$};




\end{scope}

\begin{scope}[xshift = 10cm,yshift = -15cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)
(1,0) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)
(5,0) circle (3pt);


\draw
(0,0)--(0,1)
(0,1)--(1,0)
(4,1)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,4}^{H_{11}}(n))|=|\mathcal{C}(G_{1,4}^{H_2}(n-1))|$};



\end{scope}




\end{tikzpicture}

\end{center}
\caption{Recurrence diagram for $\{1,4\}$-necklaces.}
\label{14rec}
\end{figure}

\begin{table} \centering
 \begin{tabular}{| c || c | c |c |c |c |c |c |c |c |c |c |} 
 \hline
          $n$  &amp; $5$ &amp; $6$ &amp; $7$ &amp; $8$ &amp; $9$ &amp; $10$ &amp; $11$ &amp; $12$ &amp; $13$ &amp; $14$ &amp; $15$\\ 
 \hline
 $N_{1,4}(n) $ &amp; $1$ &amp; $0$ &amp; $1$ &amp; $1$ &amp; $1$ &amp; $3$  &amp; $2$  &amp; $3$  &amp; $6$  &amp; $5$  &amp; $10$ \\ 
 \hline
\end{tabular}
\caption{Initial values of $N_{1,4}(n)$.}
\label{14terms}
\end{table}

The characteristic polynomial of the matrix in~\eqref{14matrix} is the characteristic polynomial of the recurrence for $N_{1,4}(n)$. The initial values $N_{1,4}(n)$, $5 \le n \le 15$, can be found by hand or by computer and are displayed in Table~\ref{14terms}. The generating function corresponding to $N_{1,4}(n)$, obtained via the technique~\cite[Theorem~4.1.1]{RS}, for example, is  
\begin{align*}
   \sum_{n = 0}^\infty N_{1,4}(n)x^n &amp;= \frac{x^5-x^{12}}{1-x^2-x^3-x^5+x^7+x^{10}} \\
    &amp;=  \frac{x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}}{1+x-x^3-x^4-2x^5-2x^6-x^7-x^8-x^9}  , 
\end{align*}
with associated linear recurrence
\begin{align*}
N_{1,4}(n) &amp; = -N_{1,4}(n-1) + N_{1,4}(n-3) + N_{1,4}(n-4) + 2N_{1,4}(n-5) \\
           &amp; \qquad + 2N_{1,4}(n-6) + N_{1,4}(n-7) + N_{1,4}(n-8) + N_{1,4}(n-9)  .
\end{align*}

Note that the generating function can be reduced to an expression with an irreducible denominator of degree 9. Therefore $N_{1,4}(n)$ satisfies a degree 9 recurrence, and 9 is the lowest order of a recurrence satisfied by $N_{1,4}(n)$.
 


\subsection{Counting $\{1,2,3\}$-necklaces} \label{sec:123}

The technique of finding a system of linear recurrences as in Theorem~\ref{LRthm} can be extended to sets of arbitrarily many differences. The underlying idea is to partition necklaces of a particular length $n$ into subsets depending on the two neighbors of vertex 0, and then shift all labels down by 1, so the count of length $n$ necklaces depends on the count on length $n-1$ necklaces. The main distinction in considering 3 or more differences instead of 2 is that there are more choices for neighbors of vertex 0. The algebraic consequence is that in the system of linear recurrences analogous to~\eqref{cyclerec}, the right-hand sides may have more than two terms. In Figure~\ref{123rec}, we explicitly give the system of recurrences and the sequence of associated graphs when the set of differences is $S = \{1,2,3\}$ . Note that in the first line of the figure, the set of all $\{1,2,3\}$-necklaces is partitioned into three subsets containing the path $1,0,2$, the path  $1,0,3$ and the path $2,0,3$, respectively. 

\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=0.73]

\def\x{-0.5}
\def\y{1}

\filldraw

(0+\x,0) circle (3pt)
(0+\x,1) circle (3pt)
(1+\x,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt)

(12+\y,0) circle (3pt)
(12+\y,1) circle (3pt)
(13+\y,1) circle (3pt);

\draw
(4,0)--(4,1)
(8,1)--(9,1)
(12+\y,0)--(13+\y,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(6.5,0.5) node{$+$}
(11,0.5) node{$+$}
(2.5,0.8) node{$-1$}
(7,-1) node{$|\mathcal{C}(G_{1,2,3}^{H_0}(n)|=|\mathcal{C}(G_{1,2,3}^{H_1}(n-1))|+ |\mathcal{C}(G_{1,2,3}^{H_2}(n-1))| + |\mathcal{C}(G_{1,2,3}^{H_3}(n-1))|$};

\draw
(-0.5+\x,1) node{\small{$0$}}
(-0.5+\x,0) node{\small{$1$}}
(1.5+\x,1) node{\small{$2$}};


\begin{scope}[xshift = 2cm, yshift= -3cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt);

\draw
(0,0)--(0,1)
(4,0)--(4,1)
(8,1)--(9,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,2,3}^{H_1}(n))|= |\mathcal{C}(G_{a,b}^{H_1}(n-1))|+|\mathcal{C}(G_{1,2,3}^{H_2}(n-1))|$};




\end{scope}




\begin{scope}[xshift = -2cm, yshift= -6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt);

\draw
(0,1)--(1,1)
(4,0)--(4,1)
(8,0)--(9,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,2,3}^{H_2}(n))|= |\mathcal{C}(G_{1,2,3}^{H_1}(n-1))|+|\mathcal{C}(G_{1,2,3}^{H_3}(n-1))|$};




\end{scope}

\begin{scope}[xshift = 12cm,yshift = -6cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,1)--(1,1)
(0,1)--(0,0)
(4,0)--(4,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,2,3}^{H_4}(n)|=|\mathcal{C}(G_{1,2,3}^{H_1}(n-1))|$};

\end{scope}


\begin{scope}[xshift = -2cm, yshift= -9cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt)

(8,0) circle (3pt)
(8,1) circle (3pt)
(9,1) circle (3pt);

\draw
(0,0)--(1,1)
(4,0)--(4,1)
(4,1)--(5,1)
(8,1)--(8,0)
(9,1)--(8,0);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(6.4,0.5) node{$+$}
(4.5,-1) node{$|\mathcal{C}(G_{1,2,3}^{H_3}(n))|= |\mathcal{C}(G_{1,2,3}^{H_4}(n-1))|+|\mathcal{C}(G_{1,2,3}^{H_5}(n-1))|$};




\end{scope}

\begin{scope}[xshift = 12cm,yshift = -9cm]

\filldraw

(0,0) circle (3pt)
(0,1) circle (3pt)
(1,1) circle (3pt)

(4,0) circle (3pt)
(4,1) circle (3pt)
(5,1) circle (3pt);

\draw
(0,1)--(0,0)
(0,0)--(1,1)
(4,0)--(4,1)
(4,1)--(5,1);


\draw

(2.5,0.5) node{$\longrightarrow$}
(2.5,0.8) node{$-1$}
(2.5,-1) node{$|\mathcal{C}(G_{1,2,3}^{H_5}(n)|=|\mathcal{C}(G_{1,2,3}^{H_4}(n-1))|$};

\end{scope}

\end{tikzpicture}
\end{center}
\caption{Recurrence diagram for $\{1,2,3\}$-necklaces.}
\label{123rec}
\end{figure}

We can find the generating function of $N_S(n) = N_{1,2,3}(n)$ by the same method used for $\{1,4\}$-necklaces. The initial values can be obtained by hand or computer search and are displayed in Table~\ref{123terms}. The generating function is
\[ 
\sum_{n=0}^\infty N_{1,2,3}(n)x^n = \frac{x^3+2x^4+2x^5+x^6}{1-x-x^2-x^4-x^5} , 
\]
and the corresponding linear recurrence is 
\[ 
N_{1,2,3}(n) = N_{1,2,3}(n-1)+N_{1,2,3}(n-2)+N_{1,2,3}(n-4)+N_{1,2,3}(n-5) .
\]
The denominator of the generating function above is irreducible, so no recurrence of order less than~5 exists for $N_{1,2,3}(n)$.


\begin{table} \centering
 \begin{tabular}{| c || c | c |c |c |c |c  |} 
 \hline
          $n$  &amp; $3$ &amp; $4$ &amp; $5$ &amp; $6$ &amp; $7$ &amp; $8$ \\ 
 \hline
 $N_{1,2,3}(n) $ &amp; $1$ &amp; $3$ &amp; $6$ &amp; $10$ &amp; $17$ &amp; $31$ \\ 
 \hline
\end{tabular}
\caption{Initial values of $N_{1,2,3}(n)$.}
\label{123terms}
\end{table}





\section{Counting $\{a,b\}$-necklaces via computer}\label{seccomp}


The process of obtaining a system of recurrences of the form~\eqref{cyclerec}, as described in the proof of Theorem~\ref{LRthm} and carried out for special cases in Section~\ref{seccount}, can be automated. In this section, we describe our algorithms for computing the numerator and denominator of the generating function 
\begin{equation} \label{eq:genfunc}
\sum_{n = 0}^{\infty} N_{a,b}(n)x^n = \frac{f_{a,b}(x)}{g_{a,b}(x)} 
\end{equation}
associated with the count of $\{a,b\}$-necklaces. Note that the polynomials $f_{a,b}(x)$ and $g_{a,b}(x)$ found by our method need not be relatively prime, as the example $\{a,b\} = \{1,4\}$ in Section~\ref{sec14} illustrates. Furthermore, $f_{a,b}(x)$ is always a multiple of $x^{a+b}$ as $N_{a,b}(n) = 0$ for $0 \le n &lt; a+b$. 

\subsection{Algorithm for finding the generating function of $N_{a,b}(n)$} \label{sec:algs}

We partition the computation of the generating function of $N_{a,b}(n)$ into four separate algorithms. Our first algorithm (Algorithm~\ref{alg:rec}) is an auxiliary routine that constructs the collection of graphs $H$ and associated recurrence relations for $|\mathcal{C}(G_{a,b}^{H}(n))|$ as described in~\eqref{cyclerec}. 

\begin{alg}[\textsc{System of Recurrences}] \label{alg:rec}
\
\begin{description} \itemsep 0pt
\item[Input:] Relatively prime positive integers $a, b$ with $a&lt;b$.

\item[Output:] A list \textsc{H\_list} consisting of pairs $(H, R_H)$ where $H$ is a graph on $[b]$ with $\Delta(H) \le 2$ and $R_H$ is the recurrence relation in~\eqref{cyclerec} satisfied by  $|\mathcal{C}(G_{a,b}^{H}(n))|$. 
\end{description}

\begin{enumerate}[Step 1:] \itemsep 0pt
\item Initialize \textsc{H\_list} with the pair $(I_b, R_{I_b})$ where $I_b$ is the independent graph on $[b]$ and $R_{I_b} =$ \texttt{unassigned}.

\item While \textsc{H\_list} contains entries $(H, R_H)$ with  $R_H =$ \texttt{unassigned}, do
\begin{enumerate}[Step \theenumi.1:]
   \item Choose the first pair $(H, R_H)$ in \textsc{H\_list} with $R_H =$ \texttt{unassigned}.
   \item Identify the correct recurrence relation for $|\mathcal{C}(G_{a,b}^{H}(n))|$ in~\eqref{cyclerec}, according to the cases in the proof of Theorem~\ref{LRthm}, and assign it to~$R_H$.
   \item If the recurrence relation for $|\mathcal{C}(G_{a,b}^{H}(n))|$ involves a graph(s) $\hat{H}$ that do not yet appear in any pair in \textsc{H\_list}, append the pair(s) $(\hat{H}, R_{\hat{H}})$ with  $R_{\hat{H}} =$ \texttt{unassigned} to \textsc{H\_list}.
\end{enumerate}
\item Return \textsc{H\_list}.
\end{enumerate}
\end{alg}

Algorithm~\ref{alg:rec} terminates because the number of pairs in \textsc{H\_list} is finite. 

The next algorithm (Algorithm~\ref{alg:den}) uses the list of graph/recurrence relation pairs obtained by Algorithm~\ref{alg:rec} and computes the transition matrix for the system of recurrences as well as the denominator of~\eqref{eq:genfunc}. As in~\eqref{14matrix}, for brevity, we put $T_i(n)=|\mathcal{C}(G_{a,b}^{H_i}(n))|$ for the $i$-th pair $(H_i, R_{H_i})$ in \textsc{H\_list}.

\pagebreak

\begin{alg}[\textsc{Denominator}] \label{alg:den}
\ 
\begin{description} \itemsep 0pt
\item[Input:] The list \textsc{H\_list} $= \big ( (H_0, R_{H_0}), \ldots , (H_r, R_{H_r}) \big)$ output by Algorithm~\ref{alg:rec}.

\item[Output:] The transition matrix $M$ for the system of recurrence relations $R_{H_i}$, $0 \le i \le r$, and the denominator polynomial $g_{a,b}(x)$ of the generating function~\eqref{eq:genfunc}.  
\end{description}

\begin{enumerate}[Step 1:]  \itemsep 0pt
\item From the sequence $R_{H_i}$, $0 \le i \le r$, construct the transition matrix $M$ such that
\[ 
\begin{pmatrix} T_0(n) \\ T_1(n) \\ \vdots \\ T_r(n) \end{pmatrix} = M \begin{pmatrix} T_0(n-1) \\ T_1(n-1) \\ \vdots \\ T_r(n-1) \end{pmatrix}  . 
\] \label{matrix}
\item Compute the characteristic polynomial $P_M(x)$ of $M$. 
\item Put $g_{a,b}(x) = x^{\deg(P_M)}P_M(1/x)$.
\item Return $M$ and $g_{a,b}(x)$.
\end{enumerate}
\end{alg}

In Step~\ref{matrix}, $M$ is a square $0,1$-matrix of dimension $r+1$ with at most two ones per row. The characteristic polynomial $P_M(x)$ of $M$ is also the characteristic polynomial of $T_0(n) = N_{a,b}(n)$, which immediately yields a recurrence relation for $N_{a,b}(n)$. 

The numerator polynomial $f_{a,b}(x)$ of the generating function is obtained using the standard technique of symbolically multiplying~\eqref{eq:genfunc} by $g_{a,b}(x)$ and comparing coefficients of the appropriate powers of $x$, as was done in Sections~\ref{sec23} and~\ref{sec14}. Specifically, if
\[ 
g_{a,b}(x) = g_0 + g_1x+ \cdots +g_dx^d  , \qquad f_{a,b}(x) =x^{a+b}(f_0+f_1x+\cdots + f_dx^d)  , 
\]
then the coefficients of $f_{a,b}(x)$ are
\begin{equation} \label{numpol}
f_k = \sum_{j=0}^k g_j N_{a,b}(a+b+k-j) \qquad (0 \le k \leq d)  . 
\end{equation}
To compute these coefficients, we require the initial values $N_{a,b}(a+b+j)$ for $0 \le j \le d$. We compute these values as combinations of the quantities $T_i(b) = |\mathcal{C}(G_{a,b}^{H_i}(b))|$, the number of Hamiltonian cycles in $G^{H_i}_{a,b}(b)$ containing~$H_i$ for $0 \le i \le r$, using the following framework.

Let $W$ be a multiset consisting of graphs from the set $\{H_0, H_1, \ldots , H_r\}$ and define 
\[ 
T_W(n) = \sum_{H_j \in W} T_j(n)  . 
\]
Writing $M = (M_{jk})_{0 \le j, k \le r}$, define a function on such multisets $W$ as
\[ 
\mathcal{S}(W) =  \bigcup_{H_j \in W} \big \{ H_k \in \{H_0, H_1, \ldots , H_r\} \mid M_{jk} = 1 \big \}  ,
\]
where the union is taken over the multiset $W$. Thus, each set under the union contains at most two graphs, indexed by those column(s) of $M$ where the $j$-th row of $M$  has `1' entries. The key relationship between $W$ and $S(W)$ is 
\begin{equation} \label{key2ini} T_W(n+1) = T_{\mathcal{S}(W)}(n)  . 
\end{equation}
\begin{example} \label{multisetexample}
Suppose \textsc{H\_list} = $\big ( (H_0, R_{H_0}), (H_1, R_{H_1}), (H_2, R_{H_2}) \big )$ with the recurrence relations
\begin{align*}
    R_{H_0}: T_0(n) &amp;= T_1(n-1)  , \\
    R_{H_1}: T_1(n) &amp;= T_0(n-1) + T_2(n-1)  , \\
    R_{H_2}: T_2(n) &amp;= T_0(n-1)  .  
\end{align*}
The associated transition matrix is
\[ 
M = \begin{pmatrix} 0 &amp; 1 &amp; 0 \\ 1 &amp; 0 &amp; 1 \\ 1 &amp; 0 &amp; 0 \end{pmatrix}  . 
\]
Now consider the multiset $W = \{ H_0, H_1, H_1, H_2 \}$. Then 
\[ 
\mathcal{S}(W) = \{ H_1 \} \cup \{ H_0, H_2 \} \cup \{ H_0, H_2 \} \cup \{ H_0 \} = \{ H_0, H_0, H_0, H_1, H_2, H_2 \}  , 
\]
and we have
\begin{align*}
    T_W(n+1) &amp;= T_0(n+1) + 2T_1(n+1) + T_2(n+1) \\
             &amp;= T_1(n) + 2 \big ( T_0(n) + T_2(n) \big ) + T_0(n) \\
             &amp;= 3T_0(n) + T_1(n) + 2T_2(n) \\ 
             &amp;= T_{\mathcal{S}(W)}(n),
\end{align*}
as asserted in~\eqref{key2ini}.
\end{example}

To compute the initial values $N_{a,b}(a+b+j)$ for $0 \le j \le d$, put $W_0= \{H_0\}$ and recursively define $W_{i+1} = \mathcal{S}(W_i)$ for $i \geq 0$. Then $N_{a,b}(b) = T_0(b) = T_{W_0}(b)$ , and from~\eqref{key2ini} we inductively obtain 
\begin{equation}\label{N2T} 
N_{a,b}(b+i) = T_{W_i}(b) \quad (i \ge 0)  . \end{equation}
It remains to determine the quantities $T_i(b)$ for $0 \le i \le r$. We prove that $T_i(b) \in \{ 0, 1 \}$, i.e., each graph $G_{a,b}^{H_i}(b)$ has at most one Hamiltonian cycle containing $H_i$. The proof is constructive and leads to a simple algorithm for computing $T_i(b)$.

\begin{lemma} \label{formcycle}
Let $H$ be a graph with vertex set $[b]$ such that $\Delta(H) \le 2$. Then $G_{a,b}^H(b)$ has at most one Hamiltonian cycle containing $H$.
\end{lemma}

\begin{proof} 
We show that there is at most one way to add successive edges to $H$ to form a Hamiltonian cycle in $G^H_{a,b}(b)$ containing~$H$. Let $C$ be a subgraph of $G^H_{a,b}(b)$ containing $H$ with $\Delta(C) \le 2$, and let $x \in [b]$ be the smallest vertex with $\deg_C(x) \le 1$. If $x &lt; a$, then the only vertex adjacent to $x$ in $G_{a,b}(b)$ is $x+a$. If $a \le x \le b-1$, then $\deg_C(x-a) = 2$, so adding the edge $x, x-a$ to~$C$ would cause the vertex $x-a$ to have degree 3 in the resulting graph. Either way, there is at most one choice of edge incident with $x$ in $G^H_{a,b}(b)$ such that $C \cup \{ e \}$ has maximum degree at most 2, namely the edge $e$ joining $x$ to $x+a$, and this edge belongs to every Hamiltonian cycle in $G^H_{a,b}(b)$.

So beginning with $C = H$, successively identify the minimal vertex $x$ of degree at most~1 and add the edge $x, x+a$ to $C$ if it does not already belong to $C$ and the degree of $x+a$ is at most~1. Continue this process until either all vertices in $C$ have degree 2, or it is not possible to add an edge in this way. This process terminates with a unique subgraph~$C$ of~$G^H_{a,b}(b)$ of maximum degree~2 containing~$H$, which may or may not be a Hamiltonian cycle in~$G^H_{a,b}(b)$.
\end{proof}

We present the process described in the proof of Lemma~\ref{formcycle} in algorithmic form as Algorithm~\ref{alg:hamcycle}.

\begin{alg}[\textsc{Hamiltonian Cycle in $G_{a,b}^H(b)$}] \label{alg:hamcycle}
\
\begin{description} \itemsep 0pt
\item[Input:] A graph $H$ on $[b]$ with $\Delta(H) \le 2$.

\item[Output:] The number of Hamiltonian cycles (0 or 1) in $G_{a,b}^{H}(b)$.
\end{description}

\begin{enumerate}[Step 1:] \itemsep 0pt  \itemsep 0pt
\item Initialize $C = H$.
\item For $x = 0, 1, \ldots , b-1$ do
   \begin{enumerate}[Step \theenumi.1:]  \itemsep 0pt
    \item If $\deg_C(x) = 0$, output 0 and quit;
    \item Else if $\deg_C(x) = 1$ and any of the following hold: i) $x+a \ge b$, ii) $(x,x+a)$ is an edge in $C$, iii) $\deg_C(x+a) = 2$, then output 0 and quit;
    \item Else if $\deg_C(x) = 1$ and $x+a &lt; b$, add the edge $x, x+a$ to $C$.
   \end{enumerate}
\item If $C$ is a Hamiltonian cycle on $[b]$, return 1, else return 0.  
\end{enumerate}
\end{alg}

We now have all the ingredients for computing the numerator polynomial $f_{a,b}(x)$ of~\eqref{eq:genfunc}, described in Algorithm~\ref{alg:num}. 

\begin{alg}[\textsc{Numerator}] \label{alg:num}
\
\begin{description} \itemsep 0pt
\item[Input:] Relatively prime positive integers $a, b$ with $a&lt;b$, the list \textsc{H\_list} $= \big ( (H_i, R_{H_i}) \mid 0 \le i \le r) \big)$ output by Algorithm~\ref{alg:rec}, the transition matrix $M = (M_{jk})_{0 \le j, k \le r}$ and the denominator polynomial $g_{a,b}(x) = g_0 + g_1x + \cdots + g_dx^d$ $(g_d \ne 0$) output by Algorithm~\ref{alg:den}.  
\item[Output:] The numerator polynomial $f_{a,b}(x)$ of the generating function~\eqref{eq:genfunc}.
\end{description}

\begin{enumerate}[Step 1.]  \itemsep 0pt
\item For $i = 0, 1, \ldots , r$, compute $T_i(b)$, the number of Hamiltonian cycles in $G_{a,b}^{H_i}(b)$, using Algorithm~\ref{alg:hamcycle}.

\item Initialize $W_0 = \{ H_0 \}$.
\item For $i = 1, 2, \ldots , d+a$ do
    \begin{enumerate}[Step \theenumi.1:]
    \item Compute $W_i = \mathcal{S}(W_{i-1}) =  \bigcup_{H_j \in W_{i-1}} \{ H_k \mid M_{jk} = 1 \}$.
    \item Compute $T_{W_i}(b) = \sum_{H_j \in W_i} T_j(b)$.
    \end{enumerate}
\item For $i = 0, 1, \ldots , d$ do \label{loop}
         \begin{enumerate}[Step \theenumi.1:]
         \item Compute $f_i = g_0 T_{W_{a+i}}(b) + g_1 T_{W_{a+i-1}}(b) + \cdots + g_iT_{W_a}(b)$.
         \end{enumerate}
\item Return $f(x) = f_0x^{a+b} + f_1 x^{a+b+1} + \cdots + f_d x^{a+b+d}$.
\end{enumerate}
\end{alg}

The coefficients computed in Step~\ref{loop} of Algorithm~\ref{alg:num} are correct by~\eqref{numpol} and~\eqref{N2T}. 



\subsection{Data on generating functions}

We implemented the algorithms of Section~\ref{sec:algs} using SageMath~\cite{sage}; our code is available from the first author upon request. In Table~\ref{genfunc} we display the (relatively prime) numerator and denominator polynomials $f_{a,b}(x)$ and $g_{a,b}(x)$ as given in~\eqref{eq:genfunc} for several small values of $a,b$. The table ends at $\{a,b\}=\{3,5\}$ because for larger pairs $a,b$, $f_{a,b}(x)$ and $g_{a,b}(x)$ contain too many terms for easy display.

\begin{table}[ht] \centering
\renewcommand{\arraystretch}{1.1}
 \begin{tabular}{| c || c |} 
 \hline
 $f_{1,2}(x)$  &amp; \small{$x^3$}  \\ 
 \hline
 $g_{1,2}(x)$ &amp; \small{$1-x$}  \\ 
 \hline
 \hline
 $f_{1,3}(x)$  &amp; \small{$x^4+x^6$}  \\ 
 \hline
 $g_{1,3}(x)$ &amp; \small{$1-x^2-x^6$}  \\ 
 \hline
 \hline
 $f_{2,3}(x)$  &amp; \small{$x^5-x^6$}  \\ 
 \hline
 $g_{2,3}(x)$ &amp; \small{$1-x-x^5$}   \\ 
 \hline
 \hline
 $f_{1,4}(x)$  &amp; \small{$x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}$} \\ 
 \hline
 $g_{1,4}(x)$ &amp; \small{${1+x-x^3-x^4-2x^5-2x^5-x^7-x^8-x^9}$}  \\ 
 \hline
 \hline
 $f_{3,4}(x)$  &amp; \small{$x^7-x^9-x^{12}-x^{13}-2x^{14}-x^{15}+x^{16}+x^{17}+x^{19}+x^{20}$}   \\ 
 \hline
 $g_{3,4}(x)$ &amp; \small{${1-x^2-x^5-x^6-3x^7-x^8+2x^9+x^{10}+2x^{12}+2x^{13}+x^{14}-x^{16}-x^{19}}$}   \\ 
 \hline
 \hline
 $f_{1,5}(x)$  &amp; \small{$x^{6}+x^{8}+x^{10}+x^{12}+2x^{14}+2x^{16}+x^{18}+x^{20}+x^{22}$}   \\ 
 \hline
 $g_{1,5}(x)$ &amp; \small{${1-x^{4}-3x^{6}-2x^{8}-3x^{10}-2x^{12}-3x^{14}-2x^{16}-x^{18}-x^{20}}$}  \\ 
 \hline
 \hline
 $f_{2,5}(x)$  &amp; \small{$x^{7}-x^{8}+x^{11}-x^{12}-2x^{14}+x^{15}-2x^{18}+x^{19}+x^{21}+x^{25}$}  \\ 
 \hline
 $g_{2,5}(x)$ &amp; \small{$1-x-x^{6}-4x^{7}+4x^{8}-x^{9}-3x^{10}+2x^{11}+x^{12}-x^{13}+5x^{14}$} \\
 &amp; \small{$-2x^{15}+x^{16}+2x^{17}-x^{19}+2x^{20}-3x^{21}+x^{24}-x^{25}+x^{28}$}  \\ 
 \hline
 \hline
  $f_{3,5}(x)$  &amp; \small{$x^{8}-x^{12}-x^{14}-5x^{16}-4x^{18}-x^{20}+3x^{24}+3x^{26}+x^{28}-x^{32}$}  \\ 
 \hline
 $g_{3,5}(x)$ &amp; \small{$1-x^{4}-x^{6}-7x^{8}-6x^{10}-x^{12}-x^{14}+7x^{16}+8x^{18}$} \\ &amp; \small{$+2x^{20}-4x^{24}-3x^{26}-x^{28}+2x^{32}$}  \\ 
 \hline
 

\end{tabular}

\caption{Generating functions for various counts $N_{a,b}(n)$.}
\label{genfunc}
\end{table}

Table~\ref{properties} lists the minimal order of a recurrence relation for $N_{a,b}(n)$, given by $\deg(g_{a,b}(x))$, for all the pairs $\{a,b\}$ from Table~\ref{genfunc} and some larger ones. The table also shows the zero(s) of $h_{a,b}(x) = x^{\deg(g_{a,b})}g_{a,b}(1/x)$ that are largest in absolute value and thus determine the exponential growth rate of $N_{a,b}(n)$. 

Recall that $N_{a,b}(n) = 0$ for all odd $n$ when $a$ and $b$ are both odd. In this case, $h_{a,b}(x)$ cannot have a unique absolutely maximal zero. Indeed, for all such pairs $a,b$ included in Table~\ref{properties}, $h_{a,b}(x)$ has two such zeros $\pm \lambda$, both real. Hence $N_{a,b}(2n)$ grows as $|2\lambda|^n$ in this case. For all the pairs~$a,b$ of opposite parity appearing in Table~\ref{properties}, $h_{a,b}(x)$ has a unique maximal positive real zero $\lambda$, so $N_{a,b}(n)$ has growth rate $\lambda^n$ here. These data supports our conjecture that $\{a,b\}$-necklaces of every sufficiently large length also exist when $2a&gt;b$. 


\begin{table}[ht] \centering
 \begin{tabular}{| c || c | r || c | c | r |} 
 \hline
 $a,b$  &amp; Order &amp; Largest zero(s) of $h_{a,b}$  &amp; $a,b$  &amp; Order &amp; Largest zero(s) of $h_{a,b}(x)$  \\ 
 \hline
 \hline
 $1,2$ &amp; 1 &amp; 1 &amp; $5,6$ &amp; 232 &amp; 1.44097085878288 \\ 
 \hline
 $1,3$  &amp; 4 &amp; $\pm 1.27201964951407$ &amp; $1,7$ &amp; 112  &amp; $\pm 1.43153399139975$  \\ 
  \hline
  $2,3$ &amp; 5 &amp; 1.32471795724475 &amp; $2,7$ &amp; 153 &amp; 1.43674405558324 \\ 
 \hline
 $1,4$  &amp; 9 &amp; 1.35393824208368 &amp; $3,7$ &amp; 154  &amp; $\pm 1.43660604737112$ \\ 
 \hline
  $3,4$ &amp; 19 &amp; 1.39439617374762 &amp; $4,7$ &amp; 293 &amp; 1.44321501158368 \\ 
 \hline
 $1,5$  &amp; 20 &amp; $\pm 1.39434068621703$ &amp; $5,7$ &amp; 346  &amp; $\pm 1.44408397641332$  \\ 
 \hline
  $2,5$ &amp; 28 &amp; 1.40714337368192 &amp; $1,8$ &amp; 304 &amp; $1.44272948175431$ \\ 
 \hline
 $3,5$  &amp; 32 &amp; $\pm 1.41001750346218$ &amp; $3,8$ &amp; 482  &amp;  1.44609178016640 \\ 
 \hline
  $4,5$  &amp; 67 &amp; 1.42558715174949 &amp; $1,9$ &amp; 654  &amp; $\pm 1.44749911396199$  \\ 
 \hline
  $1,6$  &amp; 48 &amp; 1.41951932571718 &amp;  &amp;   &amp;   \\ 
 \hline
\end{tabular}
\caption{Properties of the recurrence relation $N_{a,b}(n)$.}
\label{properties}
\end{table}


In the proof of Theorem~\ref{LRthm} we formed a system of linear recurrences, each of them the sum of one or two terms. Hence every row in the transition matrix representing the system of recurrences contains one or two `1's and all its other entries are 0. Equation~\eqref{14matrix} gives an example of this behavior for the case $\{a,b\} = \{1,4\}$. An $m \times m$ matrix $M$ whose rows consist of 0's except for at most two `1's cannot have an eigenvalue $\lambda$ of absolute value exceeding 2; else, the matrix $M - \lambda I_m$ is diagonally dominant and hence invertible. It follows that for every pair $\{a,b\}$, all the zeros of $h_{a,b}(x)$ are bounded above in absolute value by 2. Table~\ref{properties} shows that the largest zero of $h_{a,b}(x)$ is approximately $1.4$, but seems to exhibit a modest increase as $a$ and $b$ increase. 





\section{Concluding remarks} \label{S:conclude}


Several natural and interesting problems on difference necklaces remain open. As described in Proposition~\ref{exist}, we have established the existence of $\{a,b\}$-necklaces for all sufficiently large lengths $n$ when $\gcd(a,b) = 1$, $2a \leq b$, and $abn$ is even. Although our constructive existence proof~\cite{WGS} requires the restriction $2a \leq b$, it seems highly likely that this condition can be removed. It may be possible to prove the general existence result using properties of the transition matrix created in the proof of Theorem~\ref{LRthm}. For example, demonstrating that the transition matrix has a unique largest eigenvalue when $abn$ is even would be sufficient for this purpose.


Table~\ref{properties} suggests that the order of the recurrence relation satisfied by~$N_{a,b}(n)$ is a function that is monotonically increasing in both $a$ and $b$. The order of the recurrence is bounded by the number of rows in the transition matrix in the proof of Theorem~\ref{LRthm}, which is in turn bounded by the number of labelled acyclic graphs on $b$ vertices with maximum degree 2. However, the number of such graphs seems to grow much faster than the order of the recurrence of $N_{a,b}(n)$, so perhaps a better asymptotic estimate on the order is possible. This is another possible subject for future work.

Lastly, we conjecture that the characteristic polynomial $h_{a,b}(x)$ of $N_{a,b}(n)$ has a unique largest zero whenever $a,b$ are of different parity. If $a,b$ are both odd, then $h_{a,b}(x)$ should have two largest zeros in absolute value of the form $\pm \lambda$. These zeros are bounded by 2 in absolute value, but the values of $|\lambda|$ shown in Table~\ref{properties} seem to be significantly smaller than~2. It would be interesting to obtain an improved estimate on the largest zero or at least an asymptotic estimate as $a,b$ grow. 


\section{Acknowledgments}

The first and third author wish to pay tribute to their late co-author Richard Guy who passed away on March 9, 2020, at the impressive age of 103. Richard was a mathematical giant, a passionate educator, a generous philanthropist and an avid mountaineer. To us, he was also a valued colleague, mentor and friend.

We thank an anonymous referee for carefully reading our manuscript and providing helpful constructive feedback for improvement.




\begin{thebibliography}{99}

\bibitem{BG} E. R. Berlekamp and R. K. Guy, Fibonacci plays billards. 
\emph{Crux Math.} \textbf{46} (2020), 334--347.

\bibitem{GLW} D. Gray, C. Lanning, and H. Wang, Pattern containment in circular permutations, \emph{Integers}, \textbf{18B} (2018), Paper No.~A4.

\bibitem{KL}
M. Korenblit and V. E. Levit, A solution to simultaneous recurrences, preprint,
2013.  Available at \url{https://arxiv.org/abs/1306.1860}.

\bibitem{JR} J. Ram\'irez Alfons\'in, \emph{The Diophantine Frobenius Problem}. Oxford University Press, 2005.

\bibitem{sage} SageMath, the Sage Mathematics Software System (Version 9.3), The Sage Developers, 2021.   Available at \url{https://www.sagemath.org}.

\bibitem{RSSF} R. Simion and F. W. Schmidt, Restricted permutations, \emph{European J. Combin.} \textbf{6} (1985), 383--406.

\bibitem{NS} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at \url{https://oeis.org/}, 2022.

\bibitem{RS} R. P. Stanley, \emph{Enumerative Combinatorics}, 2nd ed., Cambridge University Press, 2012.  

\bibitem{SS} R. Stoyan and V. Strehl, Enumeration of Hamiltonian circuits
in rectangular grids. \emph{J. Combin. Math. Combin. Comput.} \textbf{21}
(1996), 109--127.

\bibitem{WGS} E. P. White, R. K. Guy, and R. Scheidler,
Difference necklaces, preprint, 2020.  Available at
\url{https://arxiv.org/abs/2006.15250}.

\end{thebibliography}



\bigskip
\hrule
\bigskip


\noindent 2020 {\it Mathematics Subject Classification}:~Primary 11B37; Secondary 05C30, 05A15, 05-04.
\medskip

\noindent \emph{Keywords:} $S$-necklace, Hamiltonian cycle, recurrence relation, generating function. 

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A003520},
\seqnum{A017899}, and
\seqnum{A079977}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 22 2022;
revised version received June 12 2022.
Published in {\it Journal of Integer Sequences}, June 13 2022.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}
</pre></body></html>