A New Combinatorial Interpretation of Partial Sums of m-Step Fibonacci Numbers

Erik Bates and Blan Morrison Department of Mathematics

North Carolina State University

Raleigh, NC 27695 USA

      ebates@ncsu.edu
     bhmorris@ncsu.edu

Arianna Serafini Bridgewater Associates Westport, CT 06880 USA

aserafini@alumni.stanford.edu

Mason Rogers Department of Earth, Atmospheric and Planetary Sciences Massachusetts Institute of Technology Cambridge, MA 02139 USA

                                             masonr@mit.edu

Anav Sood Department of Statistics Stanford University Stanford, CA 94305 USA

                                         anavsood@stanford.edu

Abstract

The sequence of partial sums of Fibonacci numbers, beginning with 2, 4, 7, 12, 20, 33, …, has several combinatorial interpretations (OEIS \underline{A000071}). For instance, the n-th term in this sequence is the number of length-n binary words that avoid 110. This paper proves a related but new interpretation. Given a length-3 binary word— called the keyword—we say two length-n binary words are equivalent if one can be obtained from the other by some sequence of substitutions: each substitution replaces an instance of the keyword with its negation, or vice versa. We prove that the number of induced equivalence classes is again the n-th term in the aforementioned sequence. When the keyword has length m + 1 (instead of 3), the same result holds with m-step Fibonacci numbers. What makes this result surprising—and distinct from the previous interpretation—is that it does not depend on the keyword, despite the fact that the sizes of the equivalence classes do. On this final point, we prove several results on the structure of equivalence classes, and also pose a variety of open problems.

1 Introduction

1.1 Main result

The primary goal of this paper is to give a new combinatorial interpretation of the partial sums of m-step Fibonacci numbers. For a positive integer m, the m-step Fibonacci numbers are the sequence (F_{n}^{(m)})_{n≥0} defined by the initial condition

F_{0}^{(m)} = 1, F_{n}^{(m)} = 2^{n−1} for n ∈ {1, …, m − 1},  (1)

together with the recurrence

F_{n}^{(m)} = F_{n−1}^{(m)} + ⋯ + F_{n−m}^{(m)} for n ≥ m.  (2)

The usual Fibonacci sequence (OEIS \underline{A000045} with index shifted by one) is the case m = 2. Typically the case m = 3 is called tribonacci (OEIS \underline{A000073} with index shifted by two), the case m = 4 is called tetranacci (OEIS \underline{A000078} with index shifted by three), and so on. The trivial scenario m = 1 has F_{n}^{(1)} = 1 for all n ≥ 0 (OEIS \underline{A000012}).

We realize the quantity F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)} combinatorially, from an equivalence relation ∼_{a} on \{0, 1\}^{n} defined as follows. For a binary word a ∈ \{0, 1\}^{m+1}, let \overline{a} denote its (bitwise) negation: every 0 becomes 1, and every 1 becomes 0. Upon fixing the word a and some positive integer n, we induce an equivalence relation on {0, 1}^{n} by declaring that an appearance of a as a subword can be replaced with \overline{a}, and vice versa. Extending this identification transitively (i.e., allowing multiple replacements done one at a time), we denote the resulting equivalence relation by ∼_{a}. We call a the keyword.

For example, if a = 101, then \overline{a} = 010, and the following three words of length n = 5 are equivalent:

10 \underline{010} ↑ replace \overline{a} ; with a∼_{a} \underline{101} ↑ replace a ; with \overline{a} 01 ∼_{a} 01001.  (3a)

In fact, there is a fourth equivalent word obtained by modifying the second replacement:

1 \underline{010} ↑ replace \overline{a} ; with a 1 ∼_{a} 11011.  (3b)

These four words constitute one equivalence class in {0, 1}^{5}/ ∼_{a}. Our main result determines the total number of equivalence classes, and surprisingly it depends only on the length of a:

Theorem 1. For all n, m ≥ 1 and every keyword a ∈ {0, 1}^{m+1}, the number of equivalence classes on {0, 1}^{n} induced by the equivalence relation ∼_{a} is equal to F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)}.

The proof of Theorem 1 is given in Section 2. The sizes and structure of equivalence classes are studied in Section 3, and open problems are provided in Section 4.

Remark 2 (Other relevant sequences for Theorem 1). For m = 2, we have F_{0}^{(2)} + F_{1}^{(2)} + ⋯ + F_{n}^{(2)} = F_{n+2}^{(2)} − 1 (OEIS \underline{A000071}). So in this case, Theorem 1 can be regarded as an interpretation of the Fibonacci sequence directly. But this simplification does not exist for m ≥ 3; for example, see OEIS \underline{A008937} for m = 3. For general m, the sequence (F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)})_{n≥0} is the m-th column of OEIS \underline{A172119}.

1.2 Discussion of main result

We first mention two easy cases of Theorem 1:

• If n < m+1, then the keyword a ∈ {0, 1}^{m+1} is too long to appear as a subword of any element of {0, 1}^{n}, so the equivalence relation ∼_{a} makes no nontrivial identifications. That is, every equivalence class has exactly one element. This is consistent with the fact that F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)} = 2^{n} whenever n ≤ m.

• If n = m + 1, then the only element of {0, 1}^{n} containing a as a subword is a itself, so the only nontrivial identification is a ∼_{a} \overline{a}. That is, there is one equivalence class with two elements, and all other equivalence classes are singletons. This is consistent with the fact that F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{m+1}^{(m)} = 2^{m+1} − 1.

As soon as n ≥ m + 2, the sizes of equivalence classes vary with a. For example, when n = 4 and m = 2, Theorem 1 says there are 1 + 1 + 2 + 3 + 5 = 12 equivalence classes, and Table 1 (top left) shows two different ways these equivalence classes can arrange themselves. This variability makes Theorem 1 all the more surprising, and invites questions on the sizes and structure of equivalence classes. We offer a few answers in Section 3, and list several open problems in Section 4.

When a = 110, the conclusion of Theorem 1 can be inferred from Zeckendorf’s theorem, which states that every nonnegative integer can be uniquely written as a sum of nonconsecutive Fibonacci numbers [21, 18, 6, 23]. To see the relevance of this fact, map the binary word u = (u_{1}, …, u_{n}) ∈ {0, 1}^{n} to the integer N_{u} = ∑_{i=1}^{n} u_{i}F_{i}^{(2)}. This mapping is not injective, thanks to the Fibonacci recursion F_{i}^{(2)} + F_{i+1}^{(2)} = F_{i+2}^{(2)} which is encoded by the relation 110 ∼_{a} 001. In this perspective, the equivalence class of u under ∼_{a} consists of different representations of N_{u} as a sum of distinct elements of {F_{1}^{(2)}, …, F_{n}^{(2)}}. Therefore, the number of equivalence classes is at least the number of integers between 0 = N_{(0,...,0)} and F_{1}^{(2)} + ⋯ + F_{n}^{(2)} = N_{(1,...,1)}. For the reverse inequality, one needs to check that no two equivalence classes correspond to the same integer. Indeed, every equivalence class has a representative avoiding the subword 110, and Zeckendorf’s theorem tells us—after a little extra work to account for Remark 3 stated below—that every integer has only one such representation.

\begin{matrix}n = 4 & a = 110 & a = 101 \\ s = 1 & 8 & 10 \\ s = 2 & 4 & 0 \\ s = 3 & 0 & 2 \\ total & 12 & 12 \end{matrix}

\begin{matrix}n = 5 & a = 110 & a = 101 \\ s = 1 & 10 & 16 \\ s = 2 & 8 & 0 \\ s = 3 & 2 & 0 \\ s = 4 & 0 & 4 \\ total & 20 & 20 \end{matrix}

\begin{matrix}n = 6 & a = 110 & a = 101 \\ s = 1 & 12 & 26 \\ s = 2 & 12 & 0 \\ s = 3 & 8 & 0 \\ s = 4 & 1 & 0 \\ s = 5 & 0 & 6 \\ s = 6 & 0 & 0 \\ s = 7 & 0 & 0 \\ s = 8 & 0 & 1 \\ total & 33 & 33 \end{matrix}

Table 1: Number of equivalence classes of size s induced on {0, 1}^{n} by two different choices of the keyword a.

Remark 3 (Technical point concerning the Fibonacci numeration system). Unless N is one less than a Fibonacci number, its Zeckendorf representation is one bit longer than its shortest representation. In other words, the “extra work” mentioned above is to compare words that avoid 110 but end in 11. Moreover, to ensure that the equivalence class in {0, 1}^{n} corresponding to N includes all representations of N, one should assume N can be written in n − 1 bits, i.e., N ≤ F_{1}^{(2)} + ⋯ + F_{n−1}^{(2)} = F_{n+1}^{(2)} − 2. The case N = F_{n+1}^{(2)} − 1 is also allowed (despite needing all n bits) because its representation is unique: see [14, Theorem 5(a)] or [7, Theorem 2].

Unfortunately, the argument discussed above for Theorem 1 does not extend to other keywords such as a = 101. After all, the relation 101 ∼_{a} 010 has no obvious connection to the Fibonacci recursion nor to a nice numeration system. Moreover, the structure of equivalence classes is different: in the previous discussion every equivalence class had a unique representative avoiding the keyword, but this no longer holds when the keyword is a = 101. For instance, the equivalence class from (3) has two representatives that avoid 101. This begins to explain the different equivalence class structures seen in Table 1, and also demonstrates the challenge of proving Theorem 1 for an arbitrary keyword.

Although our main objective is Theorem 1, the reader may wonder at this point when two keywords yield the same sizes of equivalence classes. For instance, it is immediate that ∼_{a} and ∼\overline{a} are the same equivalence relation, so a can be replaced with \overline{a} without any effect. In Proposition 15, we identify two other keyword modifications that preserve equivalence class structure: reversal and “seminegation” (see Definition 14). Together these operations can be used to transform any a ∈ {0, 1}^{3} to either 110 or 101, so these two keywords account for all possible equivalence class structures induced by length-3 keywords. Similarly, any length-4 keyword can be transformed to either 0000, 0001, or 0011, and these three keywords all have different equivalence class structures. But for longer keywords, the story is more complicated: see open problem 18.

1.3 Related literature

For the “Fibonacci keyword” a = 110, we have mentioned that each equivalence class corresponds to a nonnegative integer N, and the elements of the equivalence class are different representations of N as a sum of distinct Fibonacci numbers. A natural quantity to investigate is the number of such representations, denoted by R(N). By Remark 3, if N ≤ F_{n+1}^{(2)} −1, then R(N) is equal to the size of the equivalence class in {0, 1}^{n}/ ∼_{a} corresponding to N.

The study of the sequence (R(N))_{N≥0} (OEIS \underline{A000119}) dates back to at least Hoggatt and Basin [12]. The value of R(N) is known at various special values of N, based on a variety of recursions [14, 15, 7, 3]. For general N, Berstel [2] expressed R(N) as a product of 2 × 2 matrices determined by the Zeckendorf representation of N. This formula was generalized to m-step Fibonacci numbers by Kocábová, Masáková, and Pelantová [17]. An alternative formula was found by Edson and Zamboni [10] using binomial coefficients modulo 2.

To align with the Fibonacci numeration system, it is natural to partition the sequence (R(N))_{N≥1} into blocks of the form (R(N))_{F_{n}^{(2)}≤N<F_{n+1}^{(2)}}. Edson and Zamboni [9] showed how to recursively compute each block from the previous one, which enabled the observation that the set {N : R(N) = s and F_{n}^{(2)} ≤ N < F_{n+1}^{(2)}} has the same cardinality for all n ≥ 2s. For example, this fact manifests in Table 1 as follows: the number of equivalence classes of size s = 1 grows by 2 each time, and the number of equivalence classes of size s = 2 grows by 4 each time. When the keyword is 1^{m}0 with m ≥ 3, these increments are no longer constant and not fully understood. In the special case of s = 1, it is known that the increments are (m − 1)-step Fibonacci numbers [17, Proposition 3.1].

For other values of the keyword a, it seems that the induced equivalence classes have not been studied before. On the other hand, our pattern substitutions (a ↔ \overline{a}) can be thought of as a modification of pattern avoidance, which is a well-studied problem, e.g., [20, 1, 19, 5, 4, 8]; see also [22, Chapter 8]. In fact, Huang [13, Proposition 3.2] showed that F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)} is the number of length-n binary words avoiding 1^{j}0^{k}, for all positive integers j, k such that j+k = m+1. Meanwhile, the number of binary words avoiding 1^{j}0^{k}1^{ℓ} (where j+k+ℓ = m + 1) is a strictly larger number [13, Proposition 3.5], which reflects the earlier observation that 101 induces equivalence classes with potentially multiple representatives avoiding the keyword. For general alphabets, Guibas and Odlyzko [11] computed the generating function for the number of length-n words avoiding a given set of subwords. For instance, a word avoiding both a and \overline{a} is a size-1 equivalence class in our setting; see Proposition 10 for a precise consequence of this connection.

2 Proof of main result

2.1 Notation and definitions

An element u = (u_{1}, …, u_{n}) of {0, 1}^{n} is called a (binary) word of length n; the coordinate u_{i} is said to be i-th letter of u. The subword of u starting at letter i and ending at letter j is denoted by u_{i:j} = (u_{i}, …, u_{j}). An interval of integers is written as i, j = {i, i + 1, …, j}. The concatenation of u ∈ {0, 1}^{n} and w ∈ {0, 1}^{n′} is denoted by

u ⊕ w = (u_{1}, …, u_{n}, w_{1}, …, w_{n′}) ∈ {0, 1}^{n+n′}.

In what follows, a is a fixed element of {0, 1}^{m+1} referred to as the keyword.

Our goal in this subsection is to formalize the equivalence relation appearing in Theorem 1. The first step is to make the following definition.

Definition 4 (Substitutions involving the keyword). Given a word u ∈ {0, 1}^{n} and a keyword a ∈ {0, 1}^{m+1}, we say that a is applicable to u at letter i (and write a ⇝_{i} u) if either a or its negation appears as a subword of u starting at letter i:

u_{i:i+m} ∈ \{a, \overline{a}\}.

(Notice that this requires i + m ≤ n.) If a is not applicable to u at letter i, then we write a ⇝̸_{i} u. Let φ_{i}^{(a)} : \{0, 1\}^{n} → \{0, 1\}^{n} be the map that replaces a with \overline{a} or vice versa if one of them appears as a subword starting at letter i, and does nothing otherwise. More precisely:

If a ⇝_{i} u, then φ_{i}^{(a)}(u) = u′, where u′_{j} = \begin{cases}\overline{u}_{j}, & if j ∈ i, i + m ; \\ u_{j}, & otherwise. \end{cases}  (4a)
If a ⇝̸_{i} u, then φ_{i}^{(a)}(u) = u.  (4b)

We call φ_{i}^{(a)} a simple map of index i. We refer to the set of indices i, i + m as the line of action of φ_{i}^{(a)}.

Simple maps do not commute in general, since one substitution could prevent another. For example, if a = 101, then

(φ_{2}^{(a)} ∘ φ_{1}^{(a)})(\underline{010}10) = φ_{2}^{(a)}(10110) = 10110,
while (φ_{1}^{(a)} ∘ φ_{2}^{(a)})(0\underline{101}0) = φ_{1}^{(a)}(00100) = 00100.

Of course, it can also be the case that a certain substitution is only possible after a substitution of a different index takes place. For example (again with a = 101):

\begin{aligned}& (φ_{3}^{(a)} ∘ φ_{1}^{(a)})(\underline{101}10) = φ_{3}^{(a)}(01\underline{010}), = 01101 \\ while & (φ_{1}^{(a)} ∘ φ_{3}^{(a)})(10110) = φ_{1}^{(a)}(\underline{101}10) = 01010. \end{aligned}  (5)

What is clear, however, is that simple maps with disjoint lines of action do commute, since any substitution made by one does not interfere with a possible substitution by the other. We record this fact for later use:

i, i + m ∩ j, j + m = ∅ ⟹ φ_{i}^{(a)} ∘ φ_{j}^{(a)} = φ_{j}^{(a)} ∘ φ_{i}^{(a)}.  (6)

Proposition 12 gives necessary and sufficient conditions for commutativity, but for now it is enough to know (6).

Note that all simple maps are involutions; in particular, they are invertible. This explains why ∼_{a} defined below is an equivalence relation.

Definition 5 (Equivalence relation induced by the keyword). Given a keyword a ∈ {0, 1}^{m+1}, we write u ∼_{a} v if there exists a sequence of indices (i_{1}, …, i_{r}) such that (φ_{i_{r}}^{(a)}∘⋯∘φ_{i_{1}}^{(a)})(u) = v. We allow the empty composition (i.e., the identity map when r = 0) so that u ∼_{a} u.

Transitivity of ∼_{a} is seen by composing compositions, and symmetry follows from the fact that each simple map φ_{i}^{(a)} is its own inverse. Therefore, ∼_{a} is indeed an equivalence relation on {0, 1}^{n}. We denote the equivalence class of u ∈ {0, 1}^{n} by

[u]_{a} = {v ∈ {0, 1}^{n} : u ∼_{a} v}.

In Section 3 we consider the effect of changing the keyword. But for now we keep the value of a ∈ {0, 1}^{m+1} fixed, so for the remainder of Section 2 we dispense with notational decoration and just write φ_{i} for φ_{i}^{(a)}, ∼ for ∼_{a}, and [u] for [u]_{a}.

2.2 Preliminary observation

A key tool for proving Theorem 1 is the following lemma about concatenations.

Lemma 6. For every u, v ∈ {0, 1}^{n} and w ∈ {0, 1}^{n′}, the following equivalences hold:

u ∼ v ⟺ u ⊕ w ∼ v ⊕ w,  (7)
u ∼ v ⟺ w ⊕ u ∼ w ⊕ v.  (8)

The proof of Lemma 6 requires one additional definition and one additional lemma.

Definition 7 (Action by lists of simple maps). A list of simple maps Φ = (φ_{i_{r}}, …, φ_{i_{1}}) can be treated as a function {0, 1}^{n} → {0, 1}^{n} in the natural way: Φ(u) = (φ_{i_{r}} ∘ ⋯ ∘ φ_{i_{1}})(u). We say Φ acts completely on u if each simple map performs an actual substitution:

(φ_{i_{q}} ∘ ⋯ ∘ φ_{i_{1}})(u) ≠ (φ_{i_{q−1}} ∘ ⋯ ∘ φ_{i_{1}})(u) for each q ∈ {1, …, r}.  (9)

Lemma 8. Fix i ∈ 1, n . Consider a list of simple maps Υ = (φ_{j_{r}}, …, φ_{j_{1}}) that satisfies all three of the following conditions:

(i) j_{1}, …, j_{r} > i

(ii) φ_{i} ∘ Υ ≠ Υ ∘ φ_{i} as maps on {0, 1}^{n}.

(iii) There is some x ∈ {0, 1}^{n} such that (φ_{i}, Υ, φ_{i}) acts completely on x.

Then Υ contains an even number of instances of φ_{j}, where j = min(j_{1}, …, j_{r}).

Proof. We first claim that φ_{i} and φ_{j} have intersecting lines of action, i.e., i, i + m ∩ j, j + m ≠ ∅. Indeed, if this were not the case, then the line of action of φ_{i} would be disjoint from that of any simple map in Υ, by (i) and minimality of j. Hence φ_{i} would commute with Υ by (6), contradicting (ii). So we assume henceforth that φ_{i} and φ_{j} have intersecting lines of action.

Since φ_{i}(x) ≠ x by (iii), we have

x_{i:i+m} ∈ \{a, \overline{a}\}.  (10)

The application of Υ ∘ φ_{i} to x negates the i-th letter only once (namely, in the application of φ_{i}), since j_{1}, …, j_{r} > i. Since we have assumed φ_{i} and φ_{j} have intersecting lines of action, the j-th letter of x is also negated by φ_{i}. The j-th letter is further negated by φ_{j_{q}} in (φ_{i} ∘ φ_{j_{r}} ∘ ⋯ ∘ φ_{j_{1}} ∘ φ_{i})(x) whenever j_{q} = j, but not when j_{q} > j. So if the lemma were false (meaning there is an odd number of q’s such that j_{q} = j), then the j-th letter of x would be negated an even number of times by Υ ∘ φ_{i}, while the i-th letter is negated an odd number of times (in fact, only once) by Υ ∘ φ_{i}. This would imply the scenario of (10) is no longer true after the application of Υ ∘ φ_{i}:

((Υ ∘ φ_{i})(x))_{i:i+m} ∉ \{a, \overline{a}\}.

This in turn means φ_{i} has no effect on (Υ ∘ φ_{i})(x), which contradicts (iii).

Proof of Lemma 6. We just show (8), since it is notationally easier. To see that (7) follows, simply reverse the letters in all the words (including the keyword), apply (8), and then reverse back.

The ⟹ direction of (8) is trivial by just shifting indices and never modifying the prefix w of length n′:

if (φ_{i_{r}} ∘ ⋯ ∘ φ_{i_{1}})(u) = v, then (φ_{i_{r}+n′} ∘ ⋯ ∘ φ_{i_{1}+n′})(w ⊕ u) = w ⊕ v.

For the ⟸ direction, we suppose w ⊕ u ∼ w ⊕ v. That is, there exists a list of simple maps Φ = (φ_{i_{r}}, …, φ_{i_{1}}) such that

(φ_{i_{r}} ∘ ⋯ ∘ φ_{i_{1}})(w ⊕ u) = w ⊕ v.  (11)

We choose r minimally in the sense that no shorter list satisfies (11). In particular, Φ acts completely on w ⊕ u:

w ⊕ u ≠ φ_{i_{1}}(w ⊕ u) ≠ (φ_{i_{2}} ∘ φ_{i_{1}})(w ⊕ u) ≠ ⋯ ≠ (φ_{i_{r}} ∘ ⋯ ∘ φ_{i_{1}})(w ⊕ u).  (12)

If i_{q} > n′ for all q ∈ 1, r , then none of the letters in the prefix w ∈ {0, 1}^{n′} are modified in (11). In this case, a shift of indices results in

(φ_{i_{r}−n′} ∘ ⋯ ∘ φ_{i_{1}−n′})(u) = v,

so u ∼ v as desired. In fact, the remainder of the proof shows that this is the only way (11) can occur (when r is minimal). So suppose toward a contradiction that i_{q} ≤ n′ for some q.

Let i_{(1)} = min(i_{1}, …, i_{r}) ≤ n′. By minimality of i_{(1)}, the application of φ_{i_{q}} in (11) negates the i_{(1)}-th letter if and only if i_{q} = i_{(1)}. In total, the i_{(1)}-th letter is negated an even number of times since (w ⊕ u)_{i_{(1)}} = w_{i_{(1)}} = (w ⊕ v)_{i_{(1)}}. So there must be an even number of instances of φ_{i_{(1)}} in (11):

Φ = ( …, \underbrace{φ_{i_{(1)}}, …, φ_{i_{(1)}}, …, φ_{i_{(1)}}, … φ_{i_{(1)}}}_{even number of φ_{i_{(1)}}}, Ψ_{1}).

Here Ψ_{1} is a (possibly empty) list not containing any instance of φ_{i_{(1)}}. Consider the rightmost pair of φ_{i_{(1)}} and denote the sequence between them as Φ_{1} like so:

Φ = ( …, φ_{i_{(1)}}, Φ_{1}, φ_{i_{(1)}}, Ψ_{1}).

Now we check that the three hypotheses of Lemma 8 are satisfied with i = i_{(1)} and Υ = Φ_{1}. By construction, each simple map in Φ_{1} has index strictly greater than i_{(1)}, so assumption (i) is valid. Second, Φ_{1} does not commute with φ_{i_{(1)}} since φ_{i_{(1)}} ∘ φ_{i_{(1)}} = id and r is minimal for (11), so assumption (ii) is valid (in particular, Φ_{1} is not empty). Finally, assumption (iii) is valid with x = Ψ_{1}(w ⊕ u) because of (12). The conclusion of Lemma 8 is that there are at least two instances of φ_{i_{(2)}} in Φ_{1}, where i_{(2)} > i_{(1)} is the smallest index of the simple maps in Φ_{1}.

We now march inductively toward the desired contradiction. Isolate the rightmost pair of φ_{i_{(2)}} within Φ_{1}:

Φ_{1} = ( …, φ_{i_{(2)}}, Φ_{2}, φ_{i_{(2)}}, Ψ_{2}),

where Ψ_{2} and Φ_{2} contain no instances of φ_{i_{(2)}}. The argument of the previous paragraph goes through verbatim with (i_{(2)}, Φ_{2}) replacing (i_{(1)}, Φ_{1}), and x = (Ψ_{2} ∘ φ_{i_{(1)}} ∘ Ψ_{1})(w ⊕ u). Therefore, there are at least two instances of φ_{i_{(3)}} in Φ_{2}, where i_{(3)} > i_{(2)} is the smallest index of the simple maps in Φ_{2}, and so on. Repeating this procedure, we ultimately find a list Φ_{r} that is empty (since i_{(1)} < ⋯ < i_{(r)} have exhausted all available indices) but does not commute with φ_{i_{(r)}} (again by minimality of r). This is an obvious contradiction and completes the proof.

2.3 Counting equivalence classes

Here is an elementary lemma to set up our proof of the main result.

Lemma 9. Let (S_{n})_{n≥0} be a sequence of real numbers. The following two statements are equivalent:

(a) S_{n} = F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)} for every n ≥ 0.

(b) S_{n} = 2^{n} for all n ∈ 0, m , and S_{n} = 2S_{n−1} − S_{n−m−1} for all n ≥ m + 1.

Proof. (a) ⟹ (b): Assume S_{n} = F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)}. In particular, for n ∈ 0, m we have

S_{n} =^{(1)} 1 + 2^{0} + ⋯ + 2^{n−1} = 2^{n}.

For n ≥ m + 1, we recover the desired recursion as follows:

S_{n} = S_{n−1} + F_{n}^{(m)} =^{(2)} S_{n−1} + F_{n−1}^{(m)} + ⋯ + F_{n−m}^{(m)}
= S_{n−1} + S_{n−1} − S_{n−m−1}.

(b) ⟹ (a): We just showed that that the sequence (F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)})_{n≥0} satisfies statement (b). On the other hand, statement (b) uniquely determines the sequence (S_{n})_{n≥0}. Therefore, we must have S_{n} = F_{0}^{(m)} + F_{1}^{(m)} + ⋯ + F_{n}^{(m)}.

Proof of Theorem 1. Denote the set of equivalence classes in {0, 1}^{n} by C_{n}. We wish to show |C_{n}| = F_{0}^{(m)} + ⋯ + F_{n}^{(m)}. For n < m + 1, the keyword a ∈ {0, 1}^{m+1} is too long to appear in any word, so |C_{n}| = 2^{n}. By Lemma 9, it now suffices to show

|C_{n}| = 2|C_{n−1}| − |C_{n−m−1}| for all n ≥ m + 1,  (13)

where C_{0} has a single element: the equivalence class of the empty word. To this end, consider the equivalence classes in {0, 1}^{n−1}:

C_{n−1} = {[u^{(1)}], …, [u^{(|C_{n−1}|)}]}.  (14)

Here each u^{(k)} ∈ {0, 1}^{n−1} is a representative (chosen arbitrarily) of a different equivalence class. We claim that all the equivalence classes of length-n words can be found in the set

{[u^{(1)} ⊕ 0], [u^{(1)} ⊕ 1], …, [u^{(|C_{n−1}|)} ⊕ 0], [u^{(|C_{n−1}|)} ⊕ 1]}.  (15)

To see this, consider any v ∈ {0, 1}^{n}. We know from (14) that v_{1:n−1} ∼ u^{(k)} for some k ∈ 1, |C_{n−1}| . By the ⟹ direction of (7), if the last letter of v is v_{n} = 0, then v ∼ u^{(k)} ⊕0. If instead v_{n} = 1, then v ∼ u^{(k)} ⊕ 1. We have thus shown that (15) is equal to C_{n}.

We wish to determine the cardinality of C_{n}, but the list in (15) contains duplicates. To count the number of the duplicates, we make two observations:

• If two equivalence classes listed in (15) are equal, then they are of the form [u^{(k)} ⊕ 0], [u^{(ℓ)} ⊕ 1] for some k ≠ ℓ. This is because we have assumed u^{(k)} ≁ u^{(ℓ)} whenever k ≠ ℓ, so u^{(k)} ⊕ 0 ≁ u^{(ℓ)} ⊕ 0 and u^{(k)} ⊕ 1 ≁ u^{(ℓ)} ⊕ 1 by the ⟸ direction of (7).

• No three elements in the list are equal to each other. To see this, suppose [u^{(k)} ⊕ 0] = [u^{(ℓ)} ⊕ 1]. Then for all h ∈ 1, |C_{n−1}| \ {k, ℓ}, we know from the previous bullet that [u^{(h)} ⊕ 0] ≠ [u^{(k)} ⊕ 0] and [u^{(h)} ⊕ 1] ≠ [u^{(ℓ)} ⊕ 1].

Now define the set of ordered pairs yielding a repeat:

R = {(k, ℓ) : [u^{(k)} ⊕ 0] = [u^{(ℓ)} ⊕ 1]}.

It follows from the two observations above that |C_{n}| = 2|C_{n−1}| − |R|. To complete the proof of (13), we exhibit a bijection f: R → C_{n−m−1}.

To define the bijection, consider some (k, ℓ) ∈ R. Then u^{(k)} ⊕ 0 ∼ u^{(ℓ)} ⊕ 1, so there exists a list of simple maps Φ = (φ_{i_{r}}, …, φ_{i_{1}}) such that

(φ_{i_{r}} ∘ ⋯ ∘ φ_{i_{1}})(u^{(k)} ⊕ 0) = u^{(ℓ)} ⊕ 1.  (16)

In particular, since u^{(k)} ⊕ 0 ends in 0 while u^{(ℓ)} ⊕ 1 ends in 1, there must be some instance of φ_{n−m} in Φ in order to act on the n-th letter. By looking either immediately before or immediately after applying φ_{n−m} for the first time in (16), we find some word x ∈ {0, 1}^{n} that is equivalent to u^{(k)} ⊕ 0 ∼ u^{(ℓ)} ⊕ 1 and ends in the keyword a:

[x] = [u^{(k)} ⊕ 0] = [u^{(ℓ)} ⊕ 1],  (17a)
and x = (x_{1}, x_{2}, …, x_{n−m−1}, a_{1}, …, a_{m+1}).  (17b)

Define f: R → C_{n−m−1} by f(k, ℓ) = [x_{1:n−m−1}]. (By the ⟸ direction of (7), any x satisfying (17) yields the same value of [x_{1:n−m−1}], but we do not need this fact.)

To show injectivity, suppose f(k, ℓ) = f(k′, ℓ′), where f(k′, ℓ′) = [x′_{1:n−m−1}] for some x′ ∈ {0, 1}^{n} that ends in a and is equivalent to both u^{(k′)} ⊕ 0 and u^{(ℓ′)} ⊕ 1. We thus have

[u^{(k)} ⊕ 0] =^{(17a)} [x] =^{(17b)} [x_{1:n−m−1} ⊕ a]
= [x′_{1:n−m−1} ⊕ a] by the ⟹ direction of (7)
= [x′] = [u^{(k′)} ⊕ 0].

Now the ⟸ direction of (7) forces u^{(k)} ∼ u^{(k′)}. But each u^{(k)} is a representative of a distinct equivalence class in C_{n−1}, so we must have k = k′. An analogous argument shows ℓ = ℓ′, so f is injective.

To show surjectivity, consider an arbitrary equivalence class [y] in C_{n−m−1}. Without loss of generality, assume the last letter of a is a_{m+1} = 0. (The case a_{m+1} = 1 is handled analogously.) Since the concatenation y ⊕ a_{1:m} has length n − 1, we know y ⊕ a_{1:m} ∼ u^{(k)} for some k. This implies y ⊕ a ∼ u^{(k)} ⊕ 0 by the ⟹ direction of (7). By analogous reasoning, we also have y ⊕ \overline{a} ∼ u^{(ℓ)} ⊕ 1 for some ℓ. Since y ⊕ a ∼ y ⊕ \overline{a}, we conclude [u^{(k)} ⊕ 0] = [u^{(ℓ)} ⊕ 1]. This means (k, ℓ) ∈ R, so there exists x ∈ {0, 1}^{n} satisfying (17) such that f(k, ℓ) = [x_{1:n−m−1}]. Since [x_{1:n−m−1} ⊕a] = [x] = [u^{(k)} ⊕0] = [y ⊕a], the ⟸ direction of (7) gives [x_{1:n−m−1}] = [y]. Hence f(k, ℓ) = [y], thereby proving surjectivity.

3 Sizes and structures of equivalence classes

As discussed in Section 1.2, the sizes of equivalence classes depend on the keyword a ∈ {0, 1}^{m+1}, despite the total number of equivalence classes depending only on m. Here we study these equivalence classes more systematically. Section 3.1 examines size-1 equivalence classes, while Section 3.2 considers the graph-theoretic structure of larger equivalence classes.

3.1 Equivalence classes of size 1

The following result determines exactly when two keywords a and b yield the same number of size-1 equivalence classes. To help parse statement (b), we point out that the condition a_{1:i} ∈ \{a_{m+2−i:m+1}, \overline{a}_{m+2−i:m+1}\} simply means that the first i letters of a are the same as the last i letters, or the same as the negation of the last i letters.

Proposition 10. Let a, b ∈ {0, 1}^{m+1}. The following two statements are equivalent.

(a) For every n, the equivalence relations ∼_{a} and ∼_{b} on {0, 1}^{n} induce the same number of size-1 equivalence classes.

(b) For every i ∈ 1, m + 1 , the following equivalence is true:

a_{1:i} ∈ \{a_{m+2−i:m+1}, \overline{a}_{m+2−i:m+1}\} ⟺ b_{1:i} ∈ \{b_{m+2−i:m+1}, \overline{b}_{m+2−i:m+1}\}. (18)

Remark 11 (Other sizes of equivalence classes can still differ). An example of a, b satisfying statement (b) is a = 10001 and b = 01001. For both of these keywords, (18) is true if and only if i ∈ {1, 2, 5}. Hence Proposition 10 guarantees that ∼_{a} and ∼_{b} induce the same number of equivalence classes of size s = 1. Nevertheless, Table 2 shows that for some larger values of s, there are different numbers of size-s equivalence classes. These differences do not appear, however, until n = 12.

Proof of Proposition 10. For a given keyword a, denote the number of size-1 equivalence classes by

c_{n}^{(a)} = |\{u ∈ \{0, 1\}^{n} : u avoids both the subwords a and \overline{a}\}|,

with the convention c_{0}^{(a)} = 1. Denote the generating function of (c_{n}^{(a)})_{n≥0} by

G^{(a)}(z) = ∑_{n=0}^{∞} c_{n}^{(a)}z^{−n},  (19)

Following the strategy of Guibas and Odlyzko [11], we define the “correlation polynomials”

P_{1}^{(a)}(z) = ∑_{i=1}^{m} z^{m−i}𝟙{a_{1:i} = a_{m+2−i:m+1}},  (20a)

P_{2}^{(a)}(z) = ∑_{i=1}^{m} z^{m−i}𝟙\{a_{1:i} = \overline{a}_{m+2−i:m+1}\},  (20b)

\begin{matrix}n = 11 & a = 10001 & b = 01001 \\ s = 1 & 1262 & 1262 \\ s = 2 & 256 & 256 \\ s = 3 & 80 & 80 \\ s = 4 & 6 & 6 \\ s = 5 & 2 & 2 \\ total & 1606 & 1606 \end{matrix}  \begin{matrix}n = 12 & a = 10001 & b = 01001 \\ s = 1 & 2356 & 2356 \\ s = 2 & 528 & 528 \\ s = 3 & 176 & 176 \\ s = 4 & 26 & 24 \\ s = 5 & 8 & 12 \\ s = 6 & 2 & 0 \\ total & 3096 & 3096 \end{matrix}

Table 2: Number of equivalence classes of size s induced on {0, 1}^{n} by two different keywords (a and b). By Proposition 10, these two keywords induce the same number of equivalence classes of size s = 1 (bold blue), for every n. But for larger s, the number of equivalence classes of size s can still differ (italic red).

where 𝟙{S} is equal to 1 if statement S is true, or 0 if statement S is false. In the notation of [11], our P_{1}^{(a)}(z) and P_{2}^{(a)}(z) are their AA_{z} = BB_{z} and AB_{z} = BA_{z} respectively, where A = a and B = \overline{a}. Furthermore, our c_{n}^{(a)} and G^{(a)}(z) are their f(n) and F (z), respectively. Solving the linear system from [11, Theorem 1] (with q = 2) gives

G^{(a)}(z) = \frac{z(P_{1}^{(a)}(z) + P_{2}^{(a)}(z))}{(z − 2)(P_{1}^{(a)}(z) + P_{2}^{(a)}(z)) + 2}.  (21)

We thus have

c_{n}^{(a)} = c_{n}^{(b)} for all n ≥ 0 ⟺^{(19)} G^{(a)} = G^{(b)}

⟺^{(21)} P_{1}^{(a)} + P_{2}^{(a)} = P_{1}^{(b)} + P_{2}^{(b)}

⟺^{(20)} (18) holds for all i ∈ 1, m + 1 .

Interestingly, the prefix-suffix comparison appearing in (18) is also related to the commutativity of simple maps. The following result tells us precisely when two simple maps commute on all of {0, 1}^{n}.

Proposition 12. Given the keyword a ∈ {0, 1}^{m+1} and indices i < j ≤ n − m, let Δ = j − i. There is commutativity of simple maps

φ_{i}^{(a)} ∘ φ_{j}^{(a)} = φ_{j}^{(a)} ∘ φ_{i}^{(a)}  (22)

if and only if one of the following two conditions holds:

a_{1:m+1−Δ} ∉ \{a_{Δ+1:m+1}, \overline{a}_{Δ+1:m+1}\}  (23a)
or φ_{i}^{(a)} and φ_{j}^{(a)} have disjoint lines of action, i.e., Δ ≥ m + 1.  (23b)

In words, (23a) says the subword of length m + 1 − Δ at the start of a is not equal to the subword of the same length at the end of a, nor equal to the latter subword’s negation. This is impossible if Δ = m, as the subword in question is a single letter a_{1}, which must be equal to either a_{m+1} or \overline{a}_{m+1}. Therefore, φ_{i}^{(a)} and φ_{i+m}^{(a)} are never fully commutative; (5) is an example with m = 2.

Proof of Proposition 12. First we prove (23) ⟹ (22). The implication (23b) ⟹ (22) was already noted in (6). So let us assume (23a) and that the lines of action of φ_{i} and φ_{j} intersect, i.e., Δ ≤ m. We verify the equality

(φ_{i}^{(a)} ∘ φ_{j}^{(a)})(u) = (φ_{j}^{(a)} ∘ φ_{i}^{(a)})(u)  (24)

for all u ∈ {0, 1}^{n} by considering three cases. Case 1: a ⇝̸_{i} u and a ⇝̸_{j} u.

Both sides of (24) are equal to u in this case. Case 2: a ⇝̸_{i} u and a ⇝_{j} u.

Now the right-hand side of (24) is equal to φ_{j}^{(a)}(u). For the left-hand side to agree, we need to show a ⇝̸_{i} φ_{j}^{(a)}(u). Since a ⇝_{j} u, we have u_{j:j+m} ∈ \{a, \overline{a}\}. Omitting the last Δ letters from this subword, we have

u_{j:i+m} ∈ \{a_{1:m+1−Δ}, \overline{a}_{1:m+1−Δ}\},
and thus (φ_{j}^{(a)}(u))_{j:i+m} = \overline{u}_{j:i+m} ∈ \{\overline{a}_{1:m+1−Δ}, a_{1:m+1−Δ}\}.

Since we have assumed (23a), it follows that

(φ_{j}^{(a)}(u))_{j:i+m} ∉ \{\overline{a}_{Δ+1:m+1}, a_{Δ+1:m+1}\},
and thus (φ_{j}^{(a)}(u))_{i:i+m} ∉ \{\overline{a}, a\}.

So a ⇝̸_{i} φ_{j}^{(a)}(u), as desired. Case 3: a ⇝_{i} u.

In this case we have u_{i:i+m} ∈ \{a, \overline{a}\}. Omitting the first Δ letters from this subword, we have

u_{j:i+m} ∈ \{a_{Δ+1:m+1}, \overline{a}_{Δ+1:m+1}\}.

Since we have assumed (23a), it follows that

u_{j:i+m} ∉ \{\overline{a}_{1:m+1−Δ}, a_{1:m+1−Δ}\}
and thus u_{j:j+m} ∉ \{a, \overline{a}\}.  (25)

In addition, (φ_{i}^{(a)}(u))_{i:i+m} = \overline{u}_{i:i+m} ∈ \{\overline{a}, a\}, so the exact same logic shows

(φ_{i}^{(a)}(u))_{j:j+m} ∉ \{a, \overline{a}\}.  (26)

Now we compare the two sides of (24). On one hand, (25) says a ⇝̸_{j} u, so the left-hand side of (24) is equal to φ_{i}(u). On the other hand, (26) says a ⇝̸_{j} φ_{i}^{(a)}(u), so the right-hand side of (24) is also equal to φ_{i}^{(a)}(u). This completes the proof of (23) ⟹ (22).

Now we prove (22) ⟹ (23) by contrapositive. Suppose that φ_{i}^{(a)} and φ_{j}^{(a)} have intersecting lines of action (i.e., Δ ≤ m) and that

a_{1:m+1−Δ} ∈ \{a_{Δ+1:m+1}, \overline{a}_{Δ+1:m+1}\}.  (27)

We proceed to find a word u ∈ {0, 1}^{n} such that (φ_{i}^{(a)} ∘ φ_{j}^{(a)})(u) ≠ (φ_{j}^{(a)} ∘ φ_{i}^{(a)})(u). To this end, define the word b ∈ \{0, 1\}^{Δ} to be the last Δ letters of either a or \overline{a}, depending on the sign in (27):

b = \begin{cases}a_{m+1−Δ+1:m+1}, & if a_{1:m+1−Δ} = \overline{a}_{Δ+1:m+1}; \\ \overline{a}_{m+1−Δ+1:m+1}, & if a_{1:m+1−Δ} = a_{Δ+1:m+1}. \end{cases}

The definition of b is meant to swap the cases in (27) in the sense that

a_{Δ+1:m+1} ⊕ b ∉ \{a, \overline{a}\},  (28)
whereas (\overline{a}_{Δ+1:m+1}) ⊕ b ∈ \{a, \overline{a}\}.  (29)

Now let u ∈ {0, 1}^{n} be any word such that

u_{i:j+m} = a ⊕ b.

Then clearly a ⇝_{i} u, while a ⇝̸_{j} u since

u_{j:j+m} = a_{Δ+1:m+1} ⊕ b ∉^{(28)} \{a, \overline{a}\}.

Thus (φ_{i}^{(a)} ∘ φ_{j}^{(a)})(u) = φ_{i}^{(a)}(u). On the other hand, we know a ⇝_{j} φ_{i}^{(a)}(u) since

(φ_{i}^{(a)}(u))_{j:j+m} = \overline{a}_{Δ+1:m+1} ⊕ b ∈^{(29)} \{a, \overline{a}\}.

Thus (φ_{j}^{(a)} ∘ φ_{i}^{(a)})(u) ≠ φ_{i}^{(a)}(u) = (φ_{i}^{(a)} ∘ φ_{j}^{(a)})(u), so we do not have commutativity.

3.2 Graph structure within equivalence classes

Each keyword induces a graph as follows.

Definition 13. Given the keyword a ∈ {0, 1}^{m+1}, let G_{n}^{(a)} denote the graph whose vertex set is {0, 1}^{n}, and edge {u, v} is present if and only if v is obtained from u by a single substitution a ↦ \overline{a} or \overline{a} ↦ a, i.e., φ_{i}^{(a)}(u) = v for some i ∈ 1, n − m .

Figure 1: The unique size-8 component of G_{6}^{(101)} from Table 1 (right).

The connected components of G_{n}^{(a)} are the equivalence classes under ∼_{a}, and the graph distance is

d^{(a)}(u, v) := inf {r : ∃ i_{1}, …, i_{r} such that (φ_{i_{r}}^{(a)} ∘ ⋯ ∘ φ_{i_{1}}^{(a)})(u) = v}.

By convention we take d^{(a)}(u, u) = 0. Note that d^{(a)}(u, v) < ∞ if and only if u ∼_{a} v. See Figure 1 for an example.

A first natural question is whether two keywords yield isomorphic graphs. For instance, clearly G_{n}^{(a)} and G_{n}^{(\overline{a})} are the same graph, since a and \overline{a} are logically interchangeable in Definition 13. The next definition names two other transformations to consider alongside negation.

Definition 14. For u = (u_{1}, …, u_{n}) ∈ {0, 1}^{n}, the reversal of u is

ρ(u) := (u_{n}, …, u_{1}).  (30)

The seminegation of u is the negation of only the letters in even positions:

η(u) := (u_{1}, ¬u_{2}, u_{3}, ¬u_{4}, …, (¬)^{n−1}u_{n}),  (31)

where ¬ denotes negation of a single bit.

By composing the operations of negation, seminegation, and reversal, one can produce from a single keyword a family of either 4 or 8 keywords that—according to the following result—all yield isomorphic graphs.

Proposition 15. For every keyword a ∈ {0, 1}^{m+1} and any n ≥ 1,

G_{n}^{(a)} = G_{n}^{(\overline{a})} ≅ G_{n}^{(ρ(a))} ≅ G_{n}^{(η(a))}.

Our proof invokes the following sufficient condition for two keywords to induce isomorphic graphs.

Lemma 16. Fix keywords a, b ∈ {0, 1}^{m+1}. Suppose there exist bijections f: {0, 1}^{n} → {0, 1}^{n} and σ: 1, n → 1, n such that

(f ∘ φ_{i}^{(a)})(u) = (φ_{σ(i)}^{(b)} ∘ f)(u) for all u ∈ {0, 1}^{n} and i ∈ 1, n .  (32)

Then d^{(a)}(u, v) = d^{(b)}(f(u), f(v)) for all u, v ∈ {0, 1}^{n}.

Proof. Induction on (32) yields

f ∘ φ_{i_{r}}^{(a)} ∘ ⋯ ∘ φ_{i_{1}}^{(a)} = φ_{σ(i_{r})}^{(b)} ∘ ⋯ ∘ φ_{σ(i_{1})}^{(b)} ∘ f.  (33)

We thus have the following implications:

∃ i_{1}, …, i_{r} such that (φ_{i_{r}}^{(a)} ∘ ⋯ ∘ φ_{i_{1}}^{(a)})(u) = v
⟹ ∃ i_{1}, …, i_{r} such that (f ∘ φ_{i_{r}}^{(a)} ∘ ⋯ ∘ φ_{i_{1}}^{(a)})(u) = f(v)
⟹^{(33)} ∃ i_{1}, …, i_{r} such that (φ_{σ(i_{r})}^{(b)} ∘ ⋯ ∘ φ_{σ(i_{1})}^{(b)})(f(u)) = f(v).

Hence d^{(a)}(u, v) ≥ d^{(b)}(f(u), f(v)). Since f and σ are invertible, we can interchange the roles of a and b to obtain the reverse inequality.

Proof of Proposition 15. The equality G_{n}^{(a)} = G_{n}^{(\overline{a})} is immediate from the fact that φ_{i}^{(a)} = φ_{i}^{(\overline{a})} for all a ∈ {0, 1}^{m+1}.

The isomorphism G_{n}^{(a)} ≅ G_{n}^{(ρ(a))} is obtained by taking f(u) = ρ(u) and σ(i) = n−i−m+1 in Lemma 16. To verify (32), we set v = φ_{i}^{(a)}(u), w = φ_{σ(i)}^{(ρ(a))}(ρ(u)), and proceed to show ρ(v) = w. On one hand, the j-th letter of ρ(v) is

ρ(v)_{j} =^{(30)} v_{n−j+1} =^{(4)} \begin{cases}\overline{u}_{n−j+1}, & if a ⇝_{i} u and n − j + 1 ∈ i, i + m ; \\ u_{n−j+1}, & otherwise, \end{cases}

= \begin{cases}\overline{u}_{n−j+1}, & if a ⇝_{i} u and j ∈ σ(i), σ(i) + m ; \\ u_{n−j+1}, & otherwise. \end{cases}

On the other hand, the j-th letter of w is

w_{j} =^{(4)} \begin{cases}\overline{ρ(u)}_{j}, & if ρ(a) ⇝_{σ(i)} ρ(u) and j ∈ σ(i), σ(i) + m ; \\ ρ(u)_{j}, & otherwise, \end{cases}

=^{(30)} \begin{cases}\overline{u}_{n−j+1}, & if ρ(a) ⇝_{σ(i)} ρ(u) and j ∈ σ(i), σ(i) + m ; \\ u_{n−j+1}, & otherwise. \end{cases}

Comparing the two previous displays, we see that ρ(v) = w provided the following equivalence is true:

a ⇝_{i} u ⟺ ρ(a) ⇝_{σ(i)} ρ(u).  (34)

To prove (34), we observe that the (i + m)-th letter of u becomes the σ(i)-th letter of ρ(u). Hence

ρ(u_{i:i+m}) = ρ(u)_{σ(i):σ(i)+m},  (35)

so we have

a ⇝_{i} u ⟺ u_{i:i+m} ∈ \{a, \overline{a}\}

⟺ ρ(u_{i:i+m}) ∈ \{ρ(a), ρ(\overline{a})\} since reversal is a bijection on \{0, 1\}^{m+1}

⟺ ρ(u_{i:i+m}) ∈ \{ρ(a), \overline{ρ(a)}\} since reversal commutes with negation

⟺^{(35)} ρ(u)_{σ(i):σ(i)+m} ∈ \{ρ(a), \overline{ρ(a)}\} ⟺ ρ(a) ⇝_{σ(i)} ρ(u).

Finally, the isomorphism G_{n}^{(a)} ≅ G_{n}^{(η(a))} is obtained by taking f(u) = η(u) and σ(i) = i in Lemma 16. To verify (32), we set v = φ_{i}^{(a)}(u), w = φ_{i}^{(η(a))}(η(u)), and proceed to show η(v) = w. On one hand, the j-th letter of η(v) is

η(v)_{j} =^{(31)} (¬)^{j−1}v_{j} =^{(4)} \begin{cases}(¬)^{j}u_{j}, & if a ⇝_{i} u and j ∈ i, i + m ; \\ (¬)^{j−1}u_{j}, & otherwise. \end{cases}

On the other hand, the j-th letter of w is

w_{j} =^{(4)} \begin{cases}\overline{η(u)}_{j}, & if η(a) ⇝_{i} η(u) and j ∈ i, i + m ; \\ η(u)_{j}, & otherwise, \end{cases}

=^{(31)} \begin{cases}(¬)^{j}u_{j}, & if η(a) ⇝_{i} η(u) and j ∈ i, i + m ; \\ (¬)^{j−1}u_{j}, & otherwise. \end{cases}

Comparing the two previous displays, we see that η(v) = w provided the following equivalence is true:

a ⇝_{i} u ⟺ η(a) ⇝_{i} η(u).  (36)

To prove (36), we compare a subword of the seminegation to the seminegation of the subword:

η(u)_{i:i+m} = \begin{cases}η(u_{i:i+m}), & if i is odd; \\ \overline{η(u_{i:i+m})}, & if i is even. \end{cases}  (37)

We now obtain (36) as follows:

a ⇝_{i} u ⟺ u_{i:i+m} ∈ \{a, \overline{a}\}

⟺ η(u_{i:i+m}) ∈ \{η(a), η(\overline{a})\} since seminegation is a bijection on \{0, 1\}^{m+1}

⟺ η(u_{i:i+m}) ∈ \{η(a), \overline{η(a)}\} since seminegation commutes with negation

⟺^{(37)} η(u)_{i:i+m} ∈ \{η(a), \overline{η(a)}\} ⟺ η(a) ⇝_{i} η(u).

Our final result gives a restriction on the graphs obtainable from Definition 13.

Proposition 17. For every keyword a ∈ {0, 1}^{m+1} and n ≥ 1, G_{n}^{(a)} is bipartite.

Proof. We show G_{n}^{(a)} contains no odd cycles. Let u ∈ {0, 1}^{n} be a vertex in some cycle of length r. That is, there exists a list of simple maps Φ = (φ_{i_{r}}^{(a)}, …, φ_{i_{1}}^{(a)}) that acts completely on u (i.e., satisfies (9)) and such that Φ(u) = (φ_{i_{r}}^{(a)} ∘ ⋯ ∘ φ_{i_{1}}^{(a)})(u) = u, with each simple map corresponding to one edge in the cycle. We next argue that r must be even.

Take i_{(1)} = min(i_{1}, …, i_{r}). By minimality, the instances of φ_{i_{(1)}}^{(a)} are the only simple maps in Φ that act on the i_{(1)}-th letter. Additionally, since (Φ(u))_{i_{(1)}} = u_{i_{(1)}}, the application of Φ must negate the i_{(1)}-th letter an even number of times. Since Φ acts completely on u, it follows that there is an even number of instances of φ_{i_{(1)}}^{(a)} in Φ.

Let i_{(q)} be the q-th smallest distinct index, i.e.,

i_{(q)} = min ({i_{1}, …, i_{r}} \ {i_{(1)}, …, i_{(q−1)}}),

whenever the minimum is taken over a nonempty set. Assume inductively that for all p < q, there is an even number of instances of φ_{i_{(p)}}^{(a)} in Φ. Since (Φ(u))_{i_{(q)}} = u_{i_{(q)}}, the application of Φ must negate the i_{(q)}-th letter an even number of times. The simple maps in Φ that act on the i_{(q)}-th letter all have index at most i_{(q)}. Because there are an even number of simple maps in Φ with index strictly less than i_{(q)}, there must also be an even number of instances of φ_{i_{(q)}}^{(a)} (here we are again using the assumption that Φ acts completely on u).

We have thus shown that every distinct simple map in Φ = (φ_{i_{r}}, …, φ_{i_{1}}) must appear an even number of times. In particular, r is even.

4 Open problems

Open Problem 18. Does Proposition 15 exhaust all possible isomorphisms? That is, if G_{n}^{(a)} ≅ G_{n}^{(b)} for all n, is it necessarily the case that b can be obtained from a by some composition of negation, seminegation, and reversal?

The answer to Problem 18 is yes for m ∈ {1, 2, 3}, but there is evidence that the answer is no for larger m. Namely, when a = 10000 and b = 01000, we have verified by computer that G_{n}^{(a)} ≅ G_{n}^{(b)} for all n ≤ 17; see Table 3 for the sizes of the equivalence classes when n = 17. Yet these two keywords are not linked by any combination of negation, seminegation, and reversal.

Open Problem 19. If ∼_{a} and ∼_{b} induce the same number of size-s equivalence classes for every s, can one conclude that G_{n}^{(a)} ≅ G_{n}^{(b)}?

The converse of Problem 19 is trivially true. Note that the example from Table 2 shows that equality at s = 1 is not sufficient for equality at other values of s.

\begin{matrix}n = 17 & a = 10000 & b = 01000 \\ s = 1 & 46498 & 46498 \\ s = 2 & 28308 & 28308 \\ s = 3 & 3344 & 3344 \\ s = 4 & 3730 & 3730 \\ s = 5 & 154 & 154 \\ s = 6 & 312 & 312 \\ s = 7 & 4 & 4 \\ s = 8 & 42 & 42 \\ total & 82392 & 82392 \end{matrix}

Table 3: Number of equivalence classes of size s induced on {0, 1}^{17} by two different keywords (a and b). The evidence suggests these two keywords yield identical counts for every n (and even have isomorphic graphs), but this particular case falls outside the scope of Proposition 15.

The next open problem is inspired by a result of Klarner [14], who proved the solution set to R(N) = s is infinite for all s (and also identified these sets for s = 1, 2, 3). This implies that for every keyword a ∈ {110, 001, 100, 011}, there are equivalence classes of every size as n → ∞. The following question asks about other keywords.

Open Problem 20. For a given keyword not belonging to {110, 001, 100, 011}, which sizes of equivalence classes are possible?

One can also ask about extreme equivalence classes:

Open Problem 21. How does the maximal size of an equivalence class grow with n, and how does the growth rate vary with the keyword?

For the Fibonacci keyword a = 1^{m}0, Kocábová, Masáková, and Pelantová [16, 17] studied the following quantity related to Problem 21:

Max^{(m)}(n) := max{R^{(m)}(N) : F_{n}^{(m)} ≤ N < F_{n+1}^{(m)}},

where R^{(m)}(N) is the generalization of R(N) = R^{(2)}(N) to m-step Fibonacci numbers. For instance, one of their results [16, Theorem 4.7] says

Max^{(2)}(2n + 1) = F_{n+1}^{(2)} for n ≥ 0,
Max^{(2)}(2n + 2) = 2F_{n}^{(2)} for n ≥ 1.

Part of Problem 21 could be determining whether other keywords yield faster or slower growth.

5 Acknowledgments

E. Bates and B. Morrison were supported by National Science Foundation grant DMS-2412473. Part of this research began at the 2017 Stanford Undergraduate Research Institute in Mathematics (SURIM), which included invaluable discussions with Patrick Revilla. We thank George Schaeffer, the director of the 2017 SURIM, for feedback and encouragement. We thank Jia Huang for stimulating discussion and several useful references.

References

[1] D. Baccherini, D. Merlini, and R. Sprugnoli, Binary words excluding a pattern and proper Riordan arrays, Discrete Math. 307 (2007), 1021–1037.

[2] J. Berstel, An exercise on Fibonacci representations, Theor. Inform. Appl. 35 (2001), 491–498.

[3] M. Bicknell-Johnson and D. C. Fielder, The number of representations of N using distinct Fibonacci numbers, counted by recursive formulas, Fibonacci Quart. 37 (1999), 47–60.

[4] S. Bilotta, E. Grazzini, and E. Pergola, Counting binary words avoiding alternating patterns, J. Integer Seq. 16 (2013), Article 13.4.8.

[5] S. Bilotta, D. Merlini, E. Pergola, and R. Pinzani, Pattern 1^{j+1}0^{j} avoiding binary words, Fund. Inform. 117 (2012), 35–55.

[6] J. L. Brown, Jr., Zeckendorf’s theorem and some applications, Fibonacci Quart. 2 (1964), 163–168.

[7] L. Carlitz, Fibonacci Representations, Fibonacci Quart. 6 (1968), 193–220.

[8] J. Carrigan, I. Hollars, and E. Rowland, A natural bijection for contiguous pattern avoidance in words, Discrete Math. 347 (2024), Article 113793.

[9] M. Edson and L. Q. Zamboni, On representations of positive integers in the Fibonacci base, Theoret. Comput. Sci. 326 (2004), 241–260.

[10] M. Edson and L. Q. Zamboni, On the number of partitions of an integer in the m-bonacci base, Ann. Inst. Fourier (Grenoble) 56 (2006), 2271–2283.

[11] L. J. Guibas and A. M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981), 183–208.

[12] V. E. Hoggatt, Jr. and S. L. Basin, Representations by complete sequences. Part I (Fibonacci), Fibonacci Quart. 1 (1963), 1–14.

[13] J. Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv preprint 2501.07463 [math.CO], 2025. Available at https://arxiv.org/abs/2501.07463.

[14] D. A. Klarner, Representations of N as a sum of distinct elements from special sequences, Fibonacci Quart. 4 (1966), 289–306.

[15] D. A. Klarner, Partitions of N into distinct Fibonacci numbers, Fibonacci Quart. 6 (1968), 235–244.

[16] P. Kocábová, Z. Masáková, and E. Pelantová, Integers with a maximal number of Fibonacci representations, Theor. Inform. Appl. 39 (2005), 343–359.

[17] P. Kocábová, Z. Masáková, and E. Pelantová, Ambiguity in the m-bonacci numeration system, Discrete Math. Theor. Comput. Sci. 9 (2007), 109–123.

[18] C. G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190–195.

[19] D. Merlini and R. Sprugnoli, Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern, Theoret. Comput. Sci. 412 (2011), 2988–3001.

[20] J. Noonan and D. Zeilberger, The Goulden–Jackson cluster method: extensions, applications and implementations, J. Differ. Equations Appl. 5 (1999), 355–377.

[21] A. Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Sem. Univ. Hamburg 1 (1922), 77–98.

[22] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 2013.

[23] E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41 (1972), 179–182.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 05A15, 05A05. Keywords: m-step Fibonacci number, binary word, pattern avoidance.

(Concerned with sequences \underline{A000045}, \underline{A000071}, \underline{A000073}, \underline{A000078}, \underline{A000119}, \underline{A008937}, and \underline{A172119}.)

Received July 29 2025; revised versions received July 30 2025; September 29 2025. Published in Journal of Integer Sequences, November 24 2025.

Return to Journal of Integer Sequences home page.