Difference Necklaces

Ethan P. White^{1} Department of Mathematics Room 121, 1984 Mathematics Road Vancouver, BC V6T 1Z2 Canada

                  epwhite@math.ubc.ca

Richard K. Guy^{2}

Renate Scheidler^{3} Department of Mathematics and Statistics University of Calgary 2500 University Drive NW Calgary, AB T2N 1N4 Canada

                 rscheidl@ucalgary.ca

Abstract

An S-necklace of length n is a circular arrangement of the integers 0, 1, 2, …, 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.

1The first author is supported by funding from NSERC and the Killam Trusts.

2Deceased.

3The third author is supported by NSERC Discovery Grant RGPIN-2019-04844.

1 Introduction

Let n ≥ 3 be a positive integer and [n] denote the set {0, 1, …, 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 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 1.1.

0 4 8 1 5 9 2 6 10 3 7

Figure 1.1: A {4, 7}-necklace of length 11. Any two neighbors differ by ±4 or ±7.

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 [6] or the more recent article by Gray, Lanning, and Wang [2]. 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| ∈ S; we show an example in Figure 1.2. 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 ℤ/nℤ 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.

Theorem 1.1. Let S be a non-empty finite set of positive integers. Then the sequence (N_{S}(n))_{n∈ℕ} obeys a homogeneous linear recurrence relation with constant coefficients. That is, there exist a positive integer d and integers c_{1}, c_{2}, …, c_{d}, depending on S, such that

N_{S}(n) = ∑_{i=1}^{d} c_{i}N_{S}(n − i).

In previous work [10], we presented a highly technical construction for “growing” Snecklaces via walks in a digraph, which, in particular, implies this theorem. Here, we provide a substantially streamlined and much more useful proof of Theorem 1.1. The key feature of our proof herein is that it offers a general algorithm for finding the generating function of (N_{S}(n))_{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).

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Figure 1.2: The graph G_{1,5}(18). Any two adjacent vertices differ by ±1 or ±5.

Figure 1.2 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 1.1 and the resulting method for obtaining generating functions for (N_{S}(n))_{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 [9] who determined the generating functions for the number of Hamiltonian cycles in an m × k grid graph for m ≤ 8.

Berlekamp and the second author [1] 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 [10].

1.1 Existence of S-necklaces

Previously, we conducted an in-depth investigation of the existence of S-necklaces for the case |S| = 2 [10]. Put S = {a, b} with 0 < a < 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.

Proposition 1.2 ([10, Theorem 2.4]). Let a and b be positive coprime integers with 2a ≤ 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.

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 ≥ 2, the proof of Proposition 1.2 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 ≤ 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 ≥ 0. Noting that gcd(a + b, 3a + b) = 1 when gcd(a, b) = 1, we can invoke Frobenius’ Coin Problem [4, Theorem 2.1.1] to infer the existence of sufficiently long {a, b}-necklaces for all integers a, b subject to the conditions of Proposition 1.2. We also provided explicit lower bounds on n that guarantee their existence [10].

The existence of {a, b}-necklaces for 2a > 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 [10] of {a, b}-necklaces of length 3a + b fails when a and b are too close together.

1.2 Organization of the paper

In Section 2, we provide a constructive proof of Theorem 1.1 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 3. In Section 4, 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 5.

2 Linear recurrence for N_{a,b}(n)

This section contains a proof of our main result (Theorem 1.1), namely the fact that for every finite set S of absolute difference values, the sequence (N_{S}(n))_{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 3.5. As in Section 1.1, put S = {a, b} with 0 < a < b. The proof of Theorem 1.1 is based on two key ideas.

(A) 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′′.

(B) 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).

Definition 2.1. Let H be a graph with vertex set [b]. Define the graph G_{a,b}^{H}(n) to have vertex set [n] and edge set E(G_{a,b}(n)) ∪ E(H). Let C(G_{a,b}^{H}(n)) denote the collection of all Hamiltonian cycles of G_{a,b}^{H}(n) containing H.

0 1 2 0 1 2 3 4 0 1 2 3 4

Figure 2.1: A graph H on the left and two members of C(G_{1,3}^{H}(5)) on the right.

Note that for the independent graph I_{b}, C(G_{a,b}^{I_{b}}(n)) is precisely the set of {a, b}-necklaces of length n. If H has maximum degree exceeding 2, then C(G_{a,b}^{H}(n)) is empty. Figure 2.1 depicts a graph H with vertex set [3] and two members of C(G_{1,3}^{H}(5)).

To prove Theorem 1.1, we establish a recursive property held by |C(G_{a,b}^{H}(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{aligned}|C(G_{a,b}^{H}(n))| & = 0 or \\ |C(G_{a,b}^{H}(n))| & = |C(G_{a,b}^{H′}(n − 1))| or \\ |C(G_{a,b}^{H}(n))| & = |C(G_{a,b}^{H′}(n − 1))| + |C(G_{a,b}^{H′′}(n − 1))|. \end{aligned}  (2.1)

This implies that the collection of sequences (|C(G_{a,b}^{H}(n))|)_{n≥b} satisfies a system of coupled simultaneous linear recurrences. Applying standard techniques for decoupling linked difference equations (see [3], for example) produces a single linear recurrence relation for |C_{a,b}^{I_{b}}(n)| = N_{a,b}(n) as asserted in Theorem 1.1.

For brevity, let deg_{G}(v) denote the degree of a vertex v in a graph G and Δ(G) the maximum degree of G.

Proof of Theorem 1.1. Let H be a graph on [b]. If Δ(H) > 2, then C(G_{a,b}^{H}(n)) is empty, so assume that Δ(H) ≤ 2. We consider three cases, according to the degree of vertex 0 in H.

Case 1. Suppose deg_{H}(0) = 0. Then every C ∈ C(G_{a,b}^{H}(n)) contains the path a, 0, b and can hence contain at most one edge in H incident with a. Thus, |C(G_{a,b}^{H}(n))| = 0 when deg_{H}(a) = 2. So assume now that deg_{H}(a) ≤ 1. We form a graph H′ on the vertices in [b] with Δ(H′) ≤ 2 by performing the following operations on H:

(i) add the vertex b and the edge a, b;

(ii) delete the vertex 0; (iii) shift all vertex labels down by 1.

An example of this construction is depicted in Figure 2.2.

We establish a bijection between C(G_{a,b}^{H}(n)) and C(G_{a,b}^{H′}(n − 1)). Every C ∈ C(G_{a,b}^{H}(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 C(G_{a,b}^{H′}(n − 1)). Conversely, every C ∈ C(G_{a,b}^{H′}(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 C(G_{a,b}^{H}(n)).

H H′

⟶

All cycles contain path 1, 0, 4 Replace path with edge Shift labels down

⟶

0 1 2 3 0 1 2 3 4 0 1 2 3

Figure 2.2: Example for Case 1 with a = 1, b = 4.

Case 2. Suppose deg_{H}(0) = 1. Let u ∈ [b] be the neighbor of 0 in H. We consider two subcases.

Case 2.i. Suppose u = a. Then every C ∈ C(G_{a,b}^{H}(n)) contains the path a, 0, b and we can construct a graph H′ just as in Case 1.

Case 2.ii. Suppose u ≠ a. For x ∈ {a, b}, define the two graphs H_{a}, H_{b} on [b] by performing the following operations on H:

(i) add the edge {u, x};

(ii) delete the vertex 0;

(iii) shift all vertex indices down by 1;

(iv) add vertex b − 1.

We will show that

|C(G_{a,b}^{H}(n))| = |C(G_{a,b}^{H_{a}}(n − 1))| + |C(G_{a,b}^{H_{b}}(n − 1))|.  (2.2)

Partition C(G_{a,b}^{H}(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 ∈ S_{a} corresponds to a cycle in C(G_{a,b}^{H_{a}}(n − 1)) via the following operations:

(i) replace the path u, 0, a with the edge u, a;

(ii) delete the vertex 0; (iii) shift all vertex labels down by 1.

This process can be inverted, so there is a bijection between S_{a} and C(G_{a,b}^{H_{a}}(n − 1)). An analogous bijection exists between S_{b} and C(G_{a,b}^{H_{b}}(n − 1)), thus proving (2.2). Figure 2.3 shows an example of this construction.

H |C(G_{a,b}^{H}(n))| H_{a} |C(G_{a,b}^{H_{a}}(n − 1))| H_{b} |C(G_{a,b}^{H_{b}}(n − 1))|

⟶ −1

Edges replace paths Labels shifted down

= + +

0 1 2 3 0 1 2 3 0 1 2 3

Figure 2.3: Example for Case 2.ii with a = 1, b = 4.

Since Δ(H) ≤ 2 we have Δ(H_{b}) ≤ 2. Similarly, Δ(H_{a}) ≤ 2 if and only if deg_{H}(a) ≤ 1; if deg_{H}(a) = 2, then Δ(H_{a}) > 2 and hence C(G_{a,b}^{H_{a}}(n − 1)) is empty.

Case 3. Suppose deg_{H}(0) = 2. Let u, v ∈ [b] be the two neighbors of 0 in H. Build a graph H′ on [b] by performing the following operations on H:

(i) add the edge {u, v};

(ii) delete the vertex 0;

(iii) shift all vertex indices down by 1 by relabeling;

(iv) add vertex b − 1.

Similar reasoning as in the previous cases shows that there is a bijection between C(G_{a,b}^{H}(n)) and C(G_{a,b}^{H′}(n − 1)) because the path u, 0, v in every Hamiltonian cycle of C(G_{a,b}^{H}(n)) can be exchanged with the edge u − 1, v − 1 in every Hamiltonian cycle of C(G_{a,b}^{H_{1}}(n − 1)).

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

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 4.

3 Explicit S-necklace counts

In this section, we apply the technique from Section 2 to obtain explicit linear recurrence relations for N_{a,b}(n) when {a, b} ∈ {{1, 2}, {1, 3}, {2, 3}, {1, 4}} and for N_{S}(n) when S = {1, 2, 3}. To that end, we derive coupled recurrences as given in (2.1) and construct graphs as described in the proof of Theorem 1.1. We begin each construction with H_{0} = I_{b}, the independent graph with vertex set [b], and let H_{1}, H_{2}, … denote the graphs obtained through repeated application of the constructions in the proof of Theorem 1.1. We use the pictorial style of Figures 2.2 and 2.3 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 < 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.

3.1 Counting {1, 2}-necklaces

We begin with H_{0} = I_{1}. This is an instance of Case 1 in the proof of Theorem 1.1. Following the construction described there, we obtain the graph H_{1} on {0, 1} with one edge; see Figure 3.1.

⟶ −1 = |C(G_{1,2}^{H_{0}}(n))| |C(G_{1,2}^{H_{1}}(n − 1))| ; 0 1

Figure 3.1: Recurrence diagram for {1, 2}-necklaces: part 1.

Now we apply (2.1) with H = H_{1}. This is an instance of Case 2.i in the proof of Theorem 1.1. The construction in this case yields the graph H_{2} = H_{1}, as seen in Figure 3.2.

⟶ −1 = |C(G_{1,2}^{H_{1}}(n))| |C(G_{1,2}^{H_{2}}(n − 1))| ; 0 1

Figure 3.2: Recurrence diagram for {1, 2}-necklaces: part 2.

Since N_{1,2}(3) = 1, we conclude that

N_{1,2}(n) = 1 for all n ≥ 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.

3.2 Counting {1, 3}-necklaces

Starting with H_{0} = I_{2}, we display the sequence of identities derived from (2.1) and the graphs obtained via the proof technique for Theorem 1.1 in Figure 3.3.

⟶ −1 |C(G_{1,3}^{H_{0}}(n))| = |C(G_{1,3}^{H_{1}}(n − 1))| 0 1 2⟶ −1 + |C(G_{1,3}^{H_{1}}(n))| = |C(G_{1,3}^{H_{2}}(n − 1))| + |C(G_{1,3}^{H_{3}}(n − 1))| ⟶ −1 |C(G_{1,3}^{H_{2}}(n))| = |C(G_{1,3}^{H_{1}}(n − 1))| ⟶ −1 ⟶ −1 |C(G_{1,3}^{H_{3}}(n))| = |C(G_{1,3}^{H_{4}}(n − 1))| = |C(G_{1,3}^{H_{2}}(n − 2))|

Figure 3.3: Recurrence diagram for {1, 3}-necklaces.

To obtain a recurrence relation for N_{1,3}(n), note that 0 and 1 are adjacent in all {1, 3}- necklaces, so |C(G_{1,3}^{H_{0}}(n))| = |C(G_{1,3}^{H_{2}}(n))|. From the identities in Figure 3.3 we deduce that

|C(G_{1,3}^{H_{2}}(n))| = |C(G_{1,3}^{H_{2}}(n − 2))| + |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}, & if n ≥ 4 is even; \\ 0, & if n ≥ 5 is odd, \end{cases}

where F_{n} is the n^{th} Fibonacci number (with F_{0} = 0 and F_{1} = 1). The Fibonacci numbers interspersed with zeroes appear in the Online Encyclopedia of Integer Sequences (OEIS) [7] as \underline{A079977}, a note on \{1, 3\}-necklaces is included in this entry.

3.3 Counting {2, 3}-necklaces

As before, we begin with H_{0} = I_{3} and show the relevant equations of the form (2.1) and the corresponding graphs in Figure 3.4.

⟶ −1 |C(G_{2,3}^{H_{0}}(n))| = |C(G_{2,3}^{H_{1}}(n − 1))| 0 1 2⟶ −1 |C(G_{2,3}^{H_{1}}(n))| = |C(G_{2,3}^{H_{2}}(n − 1))| ⟶ −1 |C(G_{2,3}^{H_{2}}(n))| = |C(G_{2,3}^{H_{3}}(n − 1))| ⟶ −1 |C(G_{2,3}^{H_{3}}(n))| = |C(G_{2,3}^{H_{4}}(n − 1))| ⟶ −1 + |C(G_{2,3}^{H_{4}}(n))| = |C(G_{2,3}^{H_{4}}(n − 1))| + |C(G_{2,3}^{H_{5}}(n − 1))| ⟶ −1 |C(G_{2,3}^{H_{5}}(n)| = |C(G_{2,3}^{H_{1}}(n − 1))|

Figure 3.4: Recurrence diagram for {2, 3}-necklaces.

\begin{matrix}n & 5 & 6 & 7 \\ N_{2,3}(n) & 1 & 0 & 0 \end{matrix}

Table 3.1: Initial values of N_{2,3}(n).

In all {2, 3}-necklaces, vertices 0 and 2 are adjacent, so N_{2,3}(n) = |C(G_{2,3}^{H_{0}}(n))| = |C(G_{2,3}^{H_{5}}(n))|. Making the appropriate substitutions for the quantities derived in Figure 3.4, 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 3.1. We remark that the sequence given by N_{2,3}(n) is \underline{A017899} in OEIS; the entry points out the connection to \{2, 3\}-necklaces. In addition, \underline{A003520} is the same sequence modulo a shift. Note that the denominator of the generating function of N_{2,3}(n), given in Table 4.1, is irreducible. Hence N_{2,3}(n) does not satisfy a linear recurrence of order less than 5.

3.4 Counting {1, 4}-necklaces

Starting with H_{0} = I_{4}, Figure 3.5 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 3.5 to find a recurrence relation containing only terms in the sequence (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 3.5 yield the transition matrix equation (3.1); to reduce the notational burden, we

\begin{matrix}n & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ N_{1,4}(n) & 1 & 0 & 1 & 1 & 1 & 3 & 2 & 3 & 6 & 5 & 10 \end{matrix}

Table 3.2: Initial values of N_{1,4}(n).

put T_{i}(n) = C(G_{1,4}^{H_{i}}(n)) for 0 ≤ i ≤ 11.

(\begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}) (\begin{matrix}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{matrix}) = (\begin{matrix}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{matrix}) .  (3.1)

The characteristic polynomial of the matrix in (3.1) is the characteristic polynomial of the recurrence for N_{1,4}(n). The initial values N_{1,4}(n), 5 ≤ n ≤ 15, can be found by hand or by computer and are displayed in Table 3.2. The generating function corresponding to N_{1,4}(n), obtained via the technique [8, Theorem 4.1.1], for example, is

∑_{n=0}^{∞} N_{1,4}(n)x^{n} = \frac{x^{5} − x^{12}}{1 − x^{2} − x^{3} − x^{5} + x^{7} + x^{10}}

= \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}} ,

with associated linear recurrence

N_{1,4}(n) = −N_{1,4}(n − 1) + N_{1,4}(n − 3) + N_{1,4}(n − 4) + 2N_{1,4}(n − 5)
+ 2N_{1,4}(n − 6) + N_{1,4}(n − 7) + N_{1,4}(n − 8) + N_{1,4}(n − 9).

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).

3.5 Counting {1, 2, 3}-necklaces

The technique of finding a system of linear recurrences as in Theorem 1.1 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

⟶ −1 |C(G_{1,4}^{H_{0}}(n))| = |C(G_{1,4}^{H_{1}}(n − 1))| 0 1 2 3⟶ −1 + |C(G_{1,4}^{H_{1}}(n))| = |C(G_{1,4}^{H_{2}}(n − 1))| + |C(G_{1,4}^{H_{3}}(n − 1))| ⟶ −1 + |C(G_{1,4}^{H_{2}}(n))| = |C(G_{1,4}^{H_{4}}(n − 1))| + |C(G_{a,b}^{H_{5}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{3}}(n))| = |C(G_{1,4}^{H_{6}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{4}}(n))| = |C(G_{1,4}^{H_{1}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{5}}(n))| = |C(G_{1,4}^{H_{7}}(n − 1))| ⟶ −1 + |C(G_{1,4}^{H_{6}}(n))| = |C(G_{1,4}^{H_{8}}(n − 1))| + |C(G_{1,4}^{H_{9}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{7}}(n))| = |C(G_{1,4}^{H_{10}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{8}}(n))| = |C(G_{1,4}^{H_{4}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{9}}(n))| = |C(G_{1,4}^{H_{6}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{10}}(n))| = |C(G_{1,4}^{H_{11}}(n − 1))| ⟶ −1 |C(G_{1,4}^{H_{11}}(n))| = |C(G_{1,4}^{H_{2}}(n − 1))|

Figure 3.5: Recurrence diagram for {1, 4}-necklaces.

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 (2.1), the right-hand sides may have more than two terms. In Figure 3.6, 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.

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

⟶ + + −1 |C(G_{1,2,3}^{H_{0}}(n)| = |C(G_{1,2,3}^{H_{1}}(n − 1))| + |C(G_{1,2,3}^{H_{2}}(n − 1))| + |C(G_{1,2,3}^{H_{3}}(n − 1))| 0 1 2⟶ −1 + |C(G_{1,2,3}^{H_{1}}(n))| = |C(G_{a,b}^{H_{1}}(n − 1))| + |C(G_{1,2,3}^{H_{2}}(n − 1))| ⟶ −1 + |C(G_{1,2,3}^{H_{2}}(n))| = |C(G_{1,2,3}^{H_{1}}(n − 1))| + |C(G_{1,2,3}^{H_{3}}(n − 1))| ⟶ −1 |C(G_{1,2,3}^{H_{4}}(n)| = |C(G_{1,2,3}^{H_{1}}(n − 1))| ⟶ −1 + |C(G_{1,2,3}^{H_{3}}(n))| = |C(G_{1,2,3}^{H_{4}}(n − 1))| + |C(G_{1,2,3}^{H_{5}}(n − 1))| ⟶ −1 |C(G_{1,2,3}^{H_{5}}(n)| = |C(G_{1,2,3}^{H_{4}}(n − 1))|

Figure 3.6: Recurrence diagram for {1, 2, 3}-necklaces.

\begin{matrix}n & 3 & 4 & 5 & 6 & 7 & 8 \\ N_{1,2,3}(n) & 1 & 3 & 6 & 10 & 17 & 31 \end{matrix}

Table 3.3: Initial values of N_{1,2,3}(n).

displayed in Table 3.3. The generating function is

∑_{n=0}^{∞} 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).

4 Counting {a, b}-necklaces via computer

The process of obtaining a system of recurrences of the form (2.1), as described in the proof of Theorem 1.1 and carried out for special cases in Section 3, can be automated. In this section, we describe our algorithms for computing the numerator and denominator of the generating function

∑_{n=0}^{∞} N_{a,b}(n)x^{n} = \frac{f_{a,b}(x)}{g_{a,b}(x)}  (4.1)

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 3.4 illustrates. Furthermore, f_{a,b}(x) is always a multiple of x^{a+b} as N_{a,b}(n) = 0 for 0 ≤ n < a + b.

4.1 Algorithm for finding the generating function of N_{a,b}(n)

We partition the computation of the generating function of N_{a,b}(n) into four separate algorithms. Our first algorithm (Algorithm 4.1) is an auxiliary routine that constructs the collection of graphs H and associated recurrence relations for |C(G_{a,b}^{H}(n))| as described in (2.1).

Algorithm 4.1 (System of Recurrences).

Input: Relatively prime positive integers a, b with a < b.

Output: A list H list consisting of pairs (H, R_{H}) where H is a graph on [b] with Δ(H) ≤ 2 and R_{H} is the recurrence relation in (2.1) satisfied by |C(G_{a,b}^{H}(n))|.

Step 1: Initialize H list with the pair (I_{b}, R_{I_{b}}) where I_{b} is the independent graph on [b] and

       R_{I_{b}} = unassigned.

Step 2: While H list contains entries (H, R_{H}) with R_{H} = unassigned, do

Step 2.1: Choose the first pair (H, R_{H}) in H list with R_{H} = unassigned.

Step 2.2: Identify the correct recurrence relation for |C(G_{a,b}^{H}(n))| in (2.1), according to the cases in the proof of Theorem 1.1, and assign it to R_{H}.

Step 2.3: If the recurrence relation for |C(G_{a,b}^{H}(n))| involves a graph(s) Ĥ that do not yet appear in any pair in H list, append the pair(s) (Ĥ, RĤ) with RĤ = unassigned to H list.

Step 3: Return H list.

Algorithm 4.1 terminates because the number of pairs in H list is finite.

The next algorithm (Algorithm 4.2) uses the list of graph/recurrence relation pairs obtained by Algorithm 4.1 and computes the transition matrix for the system of recurrences as well as the denominator of (4.1). As in (3.1), for brevity, we put T_{i}(n) = |C(G_{a,b}^{H_{i}}(n))| for the i-th pair (H_{i}, R_{H_{i}}) in H list.

Algorithm 4.2 (Denominator).

Input: The list H list = ((H_{0}, R_{H_{0}}), …, (H_{r}, R_{H_{r}})) output by Algorithm 4.1.

Output: The transition matrix M for the system of recurrence relations R_{H_{i}}, 0 ≤ i ≤ r, and the denominator polynomial g_{a,b}(x) of the generating function (4.1).

Step 1: From the sequence R_{H_{i}}, 0 ≤ i ≤ r, construct the transition matrix M such that

(T_{0}(n) ; T_{1}(n) ; ⋮ ; T_{r}(n)) = M (T_{0}(n − 1) ; T_{1}(n − 1) ; ⋮ ; T_{r}(n − 1)) .

Step 2: Compute the characteristic polynomial P_{M}(x) of M.

Step 3: Put g_{a,b}(x) = x^{deg(P_{M})}P_{M}(1/x).

Step 4: Return M and g_{a,b}(x).

In Step 1, 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 (4.1) by g_{a,b}(x) and comparing coefficients of the appropriate powers of x, as was done in Sections 3.3 and 3.4. Specifically, if

g_{a,b}(x) = g_{0} + g_{1}x + ⋯ + g_{d}x^{d}, f_{a,b}(x) = x^{a+b}(f_{0} + f_{1}x + ⋯ + f_{d}x^{d}),

then the coefficients of f_{a,b}(x) are

f_{k} = ∑_{j=0}^{k} g_{j}N_{a,b}(a + b + k − j) (0 ≤ k ≤ d).  (4.2)

To compute these coefficients, we require the initial values N_{a,b}(a + b + j) for 0 ≤ j ≤ d. We compute these values as combinations of the quantities T_{i}(b) = |C(G_{a,b}^{H_{i}}(b))|, the number of Hamiltonian cycles in G_{a,b}^{H_{i}}(b) containing H_{i} for 0 ≤ i ≤ r, using the following framework.

Let W be a multiset consisting of graphs from the set {H_{0}, H_{1}, …, H_{r}} and define

T_{W} (n) = ∑_{H_{j}∈W} T_{j}(n).

Writing M = (M_{jk})_{0≤j,k≤r}, define a function on such multisets W as

S(W) = ⋃_{H_{j}∈W} {H_{k} ∈ {H_{0}, H_{1}, …, H_{r}} | M_{jk} = 1},

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

T_{W} (n + 1) = T_{S(W)}(n).  (4.3)

Example 4.3. Suppose H list = ((H_{0}, R_{H_{0}}), (H_{1}, R_{H_{1}}), (H_{2}, R_{H_{2}})) with the recurrence relations

R_{H_{0}} : T_{0}(n) = T_{1}(n − 1),
R_{H_{1}} : T_{1}(n) = T_{0}(n − 1) + T_{2}(n − 1),
R_{H_{2}} : T_{2}(n) = T_{0}(n − 1).

The associated transition matrix is

M = (\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) .

Now consider the multiset W = {H_{0}, H_{1}, H_{1}, H_{2}}. Then

S(W) = {H_{1}} ∪ {H_{0}, H_{2}} ∪ {H_{0}, H_{2}} ∪ {H_{0}} = {H_{0}, H_{0}, H_{0}, H_{1}, H_{2}, H_{2}},

and we have

T_{W} (n + 1) = T_{0}(n + 1) + 2T_{1}(n + 1) + T_{2}(n + 1)
= T_{1}(n) + 2(T_{0}(n) + T_{2}(n)) + T_{0}(n)
= 3T_{0}(n) + T_{1}(n) + 2T_{2}(n)
= T_{S(W)}(n),

as asserted in (4.3).

To compute the initial values N_{a,b}(a + b + j) for 0 ≤ j ≤ d, put W_{0} = {H_{0}} and recursively define W_{i+1} = S(W_{i}) for i ≥ 0. Then N_{a,b}(b) = T_{0}(b) = T_{W_{0}}(b) , and from (4.3) we inductively obtain

N_{a,b}(b + i) = T_{W_{i}}(b) (i ≥ 0).  (4.4)

It remains to determine the quantities T_{i}(b) for 0 ≤ i ≤ r. We prove that T_{i}(b) ∈ {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).

Lemma 4.4. Let H be a graph with vertex set [b] such that Δ(H) ≤ 2. Then G_{a,b}^{H}(b) has at most one Hamiltonian cycle containing H.

Proof. We show that there is at most one way to add successive edges to H to form a Hamiltonian cycle in G_{a,b}^{H}(b) containing H. Let C be a subgraph of G_{a,b}^{H}(b) containing H with Δ(C) ≤ 2, and let x ∈ [b] be the smallest vertex with deg_{C}(x) ≤ 1. If x < a, then the only vertex adjacent to x in G_{a,b}(b) is x + a. If a ≤ x ≤ 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_{a,b}^{H}(b) such that C ∪ {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_{a,b}^{H}(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_{a,b}^{H}(b) of maximum degree 2 containing H, which may or may not be a Hamiltonian cycle in G_{a,b}^{H}(b).

We present the process described in the proof of Lemma 4.4 in algorithmic form as Algorithm 4.5.

Algorithm 4.5 (Hamiltonian Cycle in G_{a,b}^{H}(b)).

Input: A graph H on [b] with Δ(H) ≤ 2.

Output: The number of Hamiltonian cycles (0 or 1) in G_{a,b}^{H}(b).

Step 1: Initialize C = H.

Step 2: For x = 0, 1, …, b − 1 do

Step 2.1: If deg_{C}(x) = 0, output 0 and quit;

Step 2.2: Else if deg_{C}(x) = 1 and any of the following hold: i) x+a ≥ b, ii) (x, x+a) is an edge in C, iii) deg_{C}(x + a) = 2, then output 0 and quit;

Step 2.3: Else if deg_{C}(x) = 1 and x + a < b, add the edge x, x + a to C.

Step 3: If C is a Hamiltonian cycle on [b], return 1, else return 0.

We now have all the ingredients for computing the numerator polynomial f_{a,b}(x) of (4.1), described in Algorithm 4.6.

Algorithm 4.6 (Numerator).

Input: Relatively prime positive integers a, b with a < b, the list H list = ((H_{i}, R_{H_{i}}) | 0 ≤ i ≤ r)) output by Algorithm 4.1, the transition matrix M = (M_{jk})_{0≤j,k≤r} and the denominator polynomial g_{a,b}(x) = g_{0}+g_{1}x+⋯+g_{d}x^{d} (g_{d} ≠ 0) output by Algorithm 4.2.

Output: The numerator polynomial f_{a,b}(x) of the generating function (4.1).

Step 1. For i = 0, 1, …, r, compute T_{i}(b), the number of Hamiltonian cycles in G_{a,b}^{H_{i}}(b), using Algorithm 4.5.

Step 2. Initialize W_{0} = {H_{0}}.

Step 3. For i = 1, 2, …, d + a do

Step 3.1: Compute W_{i} = S(W_{i−1}) = ⋃_{H_{j}∈W_{i−1}}{H_{k} | M_{jk} = 1}.
Step 3.2: Compute T_{W_{i}}(b) = ∑_{H_{j}∈W_{i}} T_{j}(b).

Step 4. For i = 0, 1, …, d do

Step 4.1: Compute f_{i} = g_{0}T_{W_{a+i}}(b) + g_{1}T_{W_{a+i−1}}(b) + ⋯ + g_{i}T_{W_{a}}(b).

Step 5. Return f(x) = f_{0}x^{a+b} + f_{1}x^{a+b+1} + ⋯ + f_{d}x^{a+b+d}.

The coefficients computed in Step 4 of Algorithm 4.6 are correct by (4.2) and (4.4).

4.2 Data on generating functions

We implemented the algorithms of Section 4.1 using SageMath [5]; our code is available from the first author upon request. In Table 4.1 we display the (relatively prime) numerator and denominator polynomials f_{a,b}(x) and g_{a,b}(x) as given in (4.1) 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.

Table 4.2 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 4.1 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 4.2, h_{a,b}(x) has two such zeros ±λ, both real. Hence N_{a,b}(2n) grows as |2λ|^{n} in this case. For all the pairs a, b of opposite parity appearing in Table 4.2, h_{a,b}(x) has a unique maximal positive real zero λ, so N_{a,b}(n) has growth rate λ^{n} here. These data supports our conjecture that {a, b}-necklaces of every sufficiently large length also exist when 2a > b.

In the proof of Theorem 1.1 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 (3.1) gives an example of this behavior for the case {a, b} = {1, 4}. An m×m matrix M whose rows consist of 0’s except for at most two ‘1’s cannot have an eigenvalue λ of absolute value exceeding 2; else, the matrix M − λ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 4.2 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.

f_{1,2}(x)  x^{3}
g_{1,2}(x)  1 − x
f_{1,3}(x)  x^{4} + x^{6}
g_{1,3}(x)  1 − x^{2} − x^{6}
f_{2,3}(x)  x^{5} − x^{6}
g_{2,3}(x)  1 − x − x^{5}
f_{1,4}(x)  x^{5} + x^{6} + x^{7} + x^{8} + x^{9} + x^{10} + x^{11}
g_{1,4}(x) 1 + x − x^{3} − x^{4} − 2x^{5} − 2x^{5} − x^{7} − x^{8} − x^{9}
f_{3,4}(x)  x^{7} − x^{9} − x^{12} − x^{13} − 2x^{14} − x^{15} + x^{16} + x^{17} + x^{19} + x^{20}
g_{3,4}(x) 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}
f_{1,5}(x)  x^{6} + x^{8} + x^{10} + x^{12} + 2x^{14} + 2x^{16} + x^{18} + x^{20} + x^{22}
g_{1,5}(x) 1 − x^{4} − 3x^{6} − 2x^{8} − 3x^{10} − 2x^{12} − 3x^{14} − 2x^{16} − x^{18} − x^{20}
f_{2,5}(x)  x^{7} − x^{8} + x^{11} − x^{12} − 2x^{14} + x^{15} − 2x^{18} + x^{19} + x^{21} + x^{25}
g_{2,5}(x)  1 − x − x^{6} − 4x^{7} + 4x^{8} − x^{9} − 3x^{10} + 2x^{11} + x^{12} − x^{13} + 5x^{14}

−2x^{15} + x^{16} + 2x^{17} − x^{19} + 2x^{20} − 3x^{21} + x^{24} − x^{25} + x^{28}

f_{3,5}(x)  x^{8} − x^{12} − x^{14} − 5x^{16} − 4x^{18} − x^{20} + 3x^{24} + 3x^{26} + x^{28} − x^{32}
g_{3,5}(x)  1 − x^{4} − x^{6} − 7x^{8} − 6x^{10} − x^{12} − x^{14} + 7x^{16} + 8x^{18}
+2x^{20} − 4x^{24} − 3x^{26} − x^{28} + 2x^{32}

Table 4.1: Generating functions for various counts N_{a,b}(n).

5 Concluding remarks

Several natural and interesting problems on difference necklaces remain open. As described in Proposition 1.2, we have established the existence of {a, b}-necklaces for all sufficiently large lengths n when gcd(a, b) = 1, 2a ≤ b, and abn is even. Although our constructive existence proof [10] requires the restriction 2a ≤ 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 1.1. For example, demonstrating that the transition matrix has a unique largest eigenvalue when abn is even would be sufficient for this purpose.

Table 4.2 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 1.1, 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.

a, b Order Largest zero(s) of h_{a,b} a, b Order Largest zero(s) of h_{a,b}(x)
1, 2  1  1 5, 6 232  1.44097085878288
1, 3  4  ±1.27201964951407 1, 7 112  ±1.43153399139975
2, 3  5  1.32471795724475 2, 7 153  1.43674405558324
1, 4  9  1.35393824208368 3, 7 154  ±1.43660604737112
3, 4 19  1.39439617374762 4, 7 293  1.44321501158368
1, 5 20  ±1.39434068621703 5, 7 346  ±1.44408397641332
2, 5 28  1.40714337368192 1, 8 304  1.44272948175431
3, 5 32  ±1.41001750346218 3, 8 482  1.44609178016640
4, 5 67  1.42558715174949 1, 9 654  ±1.44749911396199
1, 6 48  1.41951932571718

Table 4.2: Properties of the recurrence relation N_{a,b}(n).

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 ±λ. These zeros are bounded by 2 in absolute value, but the values of |λ| shown in Table 4.2 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.

6 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.

References

[1] E. R. Berlekamp and R. K. Guy, Fibonacci plays billards. Crux Math. 46 (2020), 334– 347.

[2] D. Gray, C. Lanning, and H. Wang, Pattern containment in circular permutations, Integers, 18B (2018), Paper No. A4.

[3] M. Korenblit and V. E. Levit, A solution to simultaneous recurrences, preprint, 2013.

Available at https://arxiv.org/abs/1306.1860.

[4] J. Ramírez Alfonsín, The Diophantine Frobenius Problem. Oxford University Press, 2005.

[5] SageMath, the Sage Mathematics Software System (Version 9.3), The Sage Developers,

    2021. Available at https://www.sagemath.org.

[6] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org/, 2022.

[8] R. P. Stanley, Enumerative Combinatorics, 2nd ed., Cambridge University Press, 2012.

[9] R. Stoyan and V. Strehl, Enumeration of Hamiltonian circuits in rectangular grids. J. Combin. Math. Combin. Comput. 21 (1996), 109–127.

[10] E. P. White, R. K. Guy, and R. Scheidler, Difference necklaces, preprint, 2020. Available

    at https://arxiv.org/abs/2006.15250.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 05C30, 05A15, 05-04.

Keywords: S-necklace, Hamiltonian cycle, recurrence relation, generating function.

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

Received February 22 2022; revised version received June 12 2022. Published in Journal of Integer Sequences, June 13 2022.

Return to Journal of Integer Sequences home page.