Counting Binary Words Avoiding Alternating Patterns

Stefano Bilotta, Elisabetta Grazzini,^{1} and Elisa Pergola Dipartimento di Sistemi e Informatica Università di Firenze Viale G. B. Morgagni 65 50134 Firenze Italy

                      egrazzini@unifi.it

Abstract

Let F^{[𝔭]} denote the set of binary words, with no more 0’s than 1’s, that do not contain the pattern 𝔭 = (10)^{j}1 as a factor for any fixed j ≥ 1. We give the generating function for the integer sequence enumerating, according to the number of 1’s, the words in F^{[𝔭]}.

1 Introduction

In this paper we consider the set F ⊂ {0, 1}^{∗} of binary words ω such that |ω|_{0} ≤ |ω|_{1}, for any ω ∈ F, where |ω|_{0} and |ω|_{1} denote the number of 0’s and 1’s in the word ω, respectively. We study the enumeration of the subset F^{[𝔭]} ⊂ F of binary words excluding a given pattern 𝔭 = p_{0} ⋯ p_{ℓ−1} ∈ {0, 1}^{ℓ}, i.e., a word ω is contained in F^{[𝔭]} if and only if there is no sequence of consecutive indices i, i + 1, …, i + ℓ − 1 such that ω_{i}ω_{i+1} ⋯ ω_{i+ℓ−1} = p_{0}p_{1} ⋯ p_{ℓ−1}.

If we consider the set of binary words without any restriction, the defined language is regular, and it can be enumerated on the basis of the number of bits 1 and 0 by using classical results (see, e.g., [7, 8, 9]). With the additional restriction that the words have no more 0’s than 1’s, the language F^{[𝔭]} is no longer regular, and it becomes more difficult to deal with. For example, in order to generate the language F^{[𝔭]} for each forbidden pattern 𝔭 an “ad hoc” grammar (from which the generating function can be obtained) must be defined. Consequently, for each pattern 𝔭 a different generating function enumerating the words in F^{[𝔭]} must be computed. Our aim is to determine a constructive algorithm suggesting a more unified approach, which makes it possible to generate all binary words in the class F^{[𝔭]}. Furthermore, this approach allows us to obtain a generating function for the enumeration of the class, according to the number of 1’s, which applies to each forbidden pattern 𝔭.

1 Corresponding author.

In this paper we compute an explicit formula for the generating function which counts the words of F^{[𝔭]} according to the number of 1’s where 𝔭 = (10)^{j}1, for any fixed j ≥ 1.

In order to obtain the enumeration of the class F^{[𝔭]} according to the number of 1’s, we use a standard method, called the ECO-method, for the enumeration of combinatorial objects which admit recursive descriptions in terms of generating trees (see, e.g., [1]). So, we first construct all binary words belonging to F and avoiding the pattern 𝔭 = (10)^{j}1, for any fixed j ≥ 1. Then, we obtain the succession rule [2, 5, 6], describing the generating algorithm, from which we can compute the generating function enumerating the words in F^{[𝔭]}.

We [4] introduced an algorithm for the construction of all binary words in F having a fixed number of 1’s and excluding those containing the forbidden pattern 1^{j+1}0^{j}, for any fixed j ≥ 1. That algorithm first generates all the words in F, and then it eliminates those containing the forbidden pattern. Basically, the construction marks in an appropriate way the forbidden patterns in the words and generates 2^{C} copies of each word having C forbidden patterns such that the 2^{C−1} instances containing an odd number of marked forbidden pattern are annihilated by the other 2^{C−1} instances containing an even number of marked forbidden patterns. For example, the words 00110\overline{110} and 00\overline{110}110, containing two copies of the forbidden pattern 𝔭 = 110, (the marked forbidden patterns are over-lined) are eliminated by the words 00110110 and 00\overline{110}\overline{110}, respectively.

This is possible since no prefix of 𝔭 = 1^{j+1}0^{j} is also a suffix of 𝔭, that is the forbidden patterns do not overlap and so they are uniquely identified inside the words.

However, the algorithm in [4] cannot be used to generate the words in F^{[𝔭]} when 𝔭 = (10)^{j}1 since now the forbidden patterns may overlap inside the words. For example, in ω = 110101010 there are two overlapping copies of the forbidden pattern 𝔭 = (10)^{2}1. So, we propose a new algorithm that generates (all and) only the words in F avoiding the forbidden pattern 𝔭 = (10)^{j}1, for any fixed j ≥ 1.

The paper is organized as follows. In Section 2 we give some basic definitions and notation. In particular, we recall how every binary word can be represented as a path on the Cartesian plane.

In Section 3 we give a construction, according to the number of 1’s, for the set of binary words in F excluding the pattern 𝔭 = (10)^{j}1, for any fixed j ≥ 1. The generating function enumerating such words according to the number of 1’s is given in Section 4.

2 Basic definitions and notation

We begin with some definitions. Recall that F ⊂ {0, 1}^{∗} is the set of binary words ω such that |ω|_{0} ≤ |ω|_{1}, for any ω ∈ F, where |ω|_{0} and |ω|_{1} denote the number of 0’s and 1’s in the word ω, respectively.

Given |ω| = |ω|_{0} + |ω|_{1} the length of ω ∈ F, we let ω^{h}, (h > 0) denote the word with length h · |ω| obtained by linking ω to itself h times, that is, ω^{h} = \underbrace{ω ω ⋯ ω}_{h} and ω^{0} = ε, ε

being the empty word.

Each word ω ∈ F can be naturally represented as a path on the Cartesian plane by associating a rise (or up) step, defined by (1,1) and indicated by x, with each bit 1 in ω and a fall (or down) step, defined by (1,-1) and indicated by x̄, with each bit 0 in ω. For example, the word ω = 11011010010000101111 is represented by the path γ = xxx̄xxx̄xx̄x̄xx̄x̄x̄x̄xx̄xxxx (see Figure 1). An up-down step is the sequence xx̄.

Figure 1: The path representing ω = 11011010010000101111

Hereafter we refer interchangeably to words or their graphical representation on the Cartesian plane, i.e., paths. So we let F denote both the set of patterns 𝔭 avoiding binary words, and the set of corresponding paths. In the rest of this paper, a path is

- primitive, if it begins and ends at ordinate 0 and remains strictly above the x-axis;

- positive, if it begins at ordinate 0 and remains above or on the x-axis;

- negative, if it begins and ends at ordinate 0 and remains below or on the x-axis (remark that a negative path in F^{[𝔭]} necessarily ends at ordinate 0);

- strongly negative, if it begins and ends at ordinate -1 and remains below or on the line y = −1;

- underground, if it ends with a negative suffix.

The complement of a path φ is the path φ^{c} obtained from φ by switching rise and fall steps.

3 A construction for the set F^{[𝔭]}

In this section we show the constructive algorithm to generate the set F^{[𝔭]}, 𝔭 = (xx̄)^{j}x = (10)^{j}1 for any fixed j ≥ 1, according to the number of rise steps, or equivalently to the number of 1’s.

The proof that the construction given in this section allows to generate all the words in F^{[𝔭]} with n 1’s for any fixed forbidden pattern 𝔭 = (xx̄)^{j}x = (10)^{j}1, j ≥ 1, is given in [3].

Given a path ω ∈ F^{[𝔭]} with n rise steps, we generate a given number of paths in F^{[𝔭]} with n + h rise steps, 1 ≤ h ≤ j, by means of constructive rules. The number and the shape of the generated paths depend on the ordinate k of the endpoint of ω and on its suffix. With regard to k, we can point out three cases: k = 0, k = 1 and k ≥ 2, while as for the suffix we consider whether it is equal to (xx̄)^{j} or not. When k = 0, we must pay attention also to the case in which ω is an underground path ending with the pattern (xx̄)^{j−1}x.

As we will show further on, for each ω ∈ F^{[𝔭]} such that k = 0 or k ≥ 2, the generating algorithm produces two or more positive paths and one underground path with n + h rise steps, 1 ≤ h ≤ j, while, when k = 1, it produces only one positive path with n + h rise steps.

The generating algorithm of the class F^{[𝔭]} with 𝔭 = (xx̄)^{j}x = (10)^{j}1, for any fixed j ≥ 1, is described in the following sections. The constructive rules related to the special cases in which the suffix of ω is (xx̄)^{j} or (xx̄)^{j−1}x are described in Sections 3.2 and 3.3, respectively. In Section 3.1 we examine all the other simple cases. The starting point of the algorithm is the empty word ε. ω_{|k} denotes a path with endpoint at ordinate k.

3.1 Simple cases

In this section we describe the constructive rules to be applied when the suffix of ω is neither (xx̄)^{j} nor (xx̄)^{j−1}x. We point out three cases for the ordinate k of the endpoint of ω: k = 0, k = 1 and k ≥ 2.

k = 0. A path ω ∈ F^{[𝔭]}, with n rise steps and such that its endpoint has ordinate 0, generates, for any h, 1 ≤ h ≤ j, three paths with n + h rise steps: a path ending at ordinate 1 by adding to ω a rise step and a sequence of h − 1 up-down steps; a path ending at ordinate 0 by adding to ω a rise step, a sequence of h − 1 up-down steps and a fall step, and an underground path obtained by the one generated in the previous step and mirroring on x-axis its rightmost primitive suffix. Figure 2 shows the above described operations; the number above the right arrow corresponds to the value of h. Both in this and in the following figures we consider j = 4, that is, 𝔭 = (xx̄)^{4}x = (10)^{4}1. Therefore,

ω_{|0} ⇒ \begin{cases}ω_{|0}x (xx̄)^{h−1}; \\ ω_{|0}x(xx̄)^{h−1}x̄; \\ ω_{|0}x̄(x̄x)^{h−1}x. \end{cases}  (1)

k = 1. A path ω ∈ F^{[𝔭]}, with n rise steps and such that its endpoint has ordinate 1, generates, for any h, 1 ≤ h ≤ j, a path with n + h rise steps with endpoint at ordinate 2 obtained by adding to ω a rise step and a sequence of h − 1 up-down steps (see Figure 3). Therefore,

ω_{|1} ⇒ ω_{|1}x(xx̄)^{h−1}.  (2)

Figure 2: The paths generated by ω_{|0}

Figure 3: The paths generated by ω_{|1}

k ≥ 2. A path ω ∈ F^{[𝔭]}, with n rise steps and such that its endpoint has ordinate k, k ≥ 2, generates, for any h, 1 ≤ h ≤ j, k + 2 paths with n + h rise steps: a path ending at ordinate (k +1) by adding to ω a rise step and a sequence of h−1 up-down steps; k −1 paths ending at ordinate (k − 1), (k − 2), …, (1), respectively, by adding to ω a rise step, a sequence of m, 2 ≤ m ≤ k, fall steps and a sequence of h − 1 up-down steps; a path ending at ordinate 0 by adding to ω a rise step, a sequence of k fall steps, a sequence of h − 1 up-down steps and a fall step, and an underground path which will be described in Section 3.4. Figure 4 shows the above described operations.

Figure 4: The paths generated by ω_{|k}, k ≥ 2

Therefore,

ω_{|k} ⇒ \begin{cases}ω_{|k}x(xx̄)^{h−1}; \\ ω_{|k}x(x̄)^{m}(xx̄)^{h−1}, & 2 ≤ m ≤ k; \\ ω_{|k}x(x̄)^{k}(xx̄)^{h−1}x̄. \end{cases}  (3)

At this point it is clear that:

1. when the path ω ends with the suffix (xx̄)^{j} the paths obtained by means of the constructions (1), (2) and (3) contain the forbidden pattern 𝔭 = (xx̄)^{j}x. So, we will act as described in Section 3.2;

2. when ω is an underground path ending with the pattern (xx̄)^{j−1}x, some paths generated by means of the above constructions might contain the forbidden pattern 𝔭 = (xx̄)^{j}x. So, we will follow the procedure described in Section 3.3.

3.2 Paths ending with (xx̄)^{j}

Even when the path ω ends with the suffix (xx̄)^{j}, the number and the shape of the generated paths depend on the ordinate k of the endpoint of ω. Let ϱ = (xx̄)^{j} be the suffix of ω.

k = 0. A path ω ∈ F^{[𝔭]}, with n rise steps and such that its endpoint has ordinate 0, generates, for any h, 1 ≤ h ≤ j, three paths with n + h rise steps (see Figure 5): a path ending at ordinate 1, by inserting a sequence of h − 1 up-down steps and a rise step on the left of ϱ; a path ending at ordinate 0, by inserting a sequence of h−1 up-down steps and a rise step on the left of ϱ and adding a fall step at the end of ω, and an underground path, obtained by mirroring on x-axis the rightmost primitive suffix of the path generated in the previous step.

Therefore,

ω_{|0}ϱ ⇒ \begin{cases}ω_{|0}(xx̄)^{h−1}xϱ; \\ ω_{|0}(xx̄)^{h−1}xϱ x̄; \\ ω_{|0}(xx̄)^{h−1}x̄x̄(xx̄)^{j−1}xx. \end{cases}  (4)

Figure 5: The paths generated by ω_{|0}(xx̄)^{j}

k = 1. A path ω ∈ F^{[𝔭]}, with n rise steps and such that its endpoint has ordinate 1, generates, for any h, 1 ≤ h ≤ j, a path with n+h rise steps with endpoint at ordinate 2, obtained by inserting a sequence of h − 1 up-down steps and a rise step on the left of the suffix ϱ (see Figure 6). Therefore,

ω_{|1}ϱ ⇒ ω_{|1}(xx̄)^{h−1}x ϱ.  (5)

k ≥ 2. A path ω ∈ F^{[𝔭]}, with n rise steps and such that its endpoint has ordinate k, k ≥ 2, generates, for any h, 1 ≤ h ≤ j, k + 2 paths with n + h rise steps (see Figure 7): a path ending at ordinate (k + 1), by inserting a sequence of h − 1 up-down steps and a rise step on the left of the suffix ϱ; k − 1 paths ending at ordinate (k − 1), (k − 2), …, (1), respectively, by inserting a sequence of h − 1 up-down steps, a rise step and a sequence of m, 2 ≤ m ≤ k, fall steps on the left of ϱ; a path ending at ordinate 0, by first inserting a sequence of h − 1 up-down steps, a rise step and a sequence of k fall steps on the left of ϱ, and then adding a fall step at the end of ω, and an underground path which will be described in Section 3.4.

Figure 6: The paths generated by ω_{|1}(xx̄)^{j}

Therefore,

ω_{|k}ϱ ⇒ \begin{cases}ω_{|k}(xx̄)^{h−1}xϱ; \\ ω_{|k}(xx̄)^{h−1}x(x̄)^{m} ϱ, & 2 ≤ m ≤ k; \\ ω_{|k}(xx̄)^{h−1}x (x̄)^{k} ϱ x̄. \end{cases}  (6)

Figure 7: The paths generated by ω_{|k}(xx̄)^{j}, k ≥ 2

3.3 Paths ending with (xx̄)^{j−1}x

The paths ω ∈ F^{[𝔭]} ending on the x-axis with the sequence (xx̄)^{j−1}x have the following shape ω_{|0} = μ x̄ η x (x̄x)^{j−1} where μ is a path ending on the x-axis and η is either the empty path ε or a strongly negative path.

The constructions applied to paths ending at ordinate 0 described in (1) (see Figure 2) can be used even for the paths ending with the sequence (xx̄)^{j−1}x, when h ≥ 2, or to generate the paths ending at ordinate 1 or on the x-axis with a positive suffix, when h = 1. Nevertheless, when h = 1, by applying the construction, we obtain an underground path which contains the forbidden pattern 𝔭 = (xx̄)^{j}x.

Therefore if the path ends with the sequence (xx̄)^{j−1}x and h = 1, in order to generate the underground path we proceed as follows. Two cases must be taken into consideration.

1) μ does not end with a peak xx̄.

The underground path is obtained by adding the path x̄x to ω_{|0}, mirroring on x-axis the rightmost suffix (x̄x)^{j} of ω_{|0}x̄x and shifting the sequence (xx̄)^{j} between μ and the sub-path x̄ η x. Therefore, the path ω_{|0} = μ x̄ η x (x̄x)^{j−1} generates the underground path μ (xx̄)^{j} x̄ η x (see Figure 8). Note that this construction applies to ω even if μ = ε.

Figure 8: The underground path generated by ω_{|0} in the case 1)

2) μ ends with a peak xx̄.

When the path μ ends with a peak xx̄, that is, μ = μ′xx̄, the insertion of the sequence (xx̄)^{j} between μ and the sequence x̄ η x produces the forbidden pattern 𝔭 = (xx̄)^{j}x. Let us consider the following subcases: η ≠ ε and η = ε.

2.1) η ≠ ε.

The underground path is obtained by shifting the rightmost peak xx̄ of μ to the right of the sub-path x̄ η x, mirroring on x-axis the sequence (x̄x)^{j−1} and adding to such path the steps x̄ x. So, when h = 1, the underground path with negative suffix generated by ω_{|0} = μ′ x x̄ x̄ η x (x̄x)^{j−1} is μ′ x̄ η x (xx̄)^{j} x̄ x (see Figure 9).

Figure 9: The underground path generated by ω_{|0} in the case 2.1)

2.2) η = ε. In this case, the underground path obtained by means of the construction described in 2.1) is ω′ = μ′ x̄ x (xx̄)^{j} x̄ x and it contains the forbidden pattern 𝔭 = (xx̄)^{j}x if μ′ ends with the sequence (x̄x)^{j} or with the sequence x̄ η′ x (x̄x)^{j−1}, where η′ is a non-empty strongly negative path. Let us take the longest suffix of ω_{|0} = μ′ x x̄ (x̄x)^{j} into account so that ω_{|0} = φ ν_{1} ν_{2} … ν_{k}, where

\begin{cases}ν_{1} = x̄ λ x (x̄x)^{j−1} x x̄; \\ ν_{i} = (x̄x)^{j} x x̄, & 1 < i < k; \\ ν_{k} = (x̄x)^{j}, \end{cases}

and λ is the empty path or is a strongly negative path. Every sequence ν_{i}, 1 ≤ i ≤ k, will be changed into ν̄_{i} in the following way.

2.2.1) If φ is a path that does not end with a peak x x̄, then

\begin{cases}ν̄_{1} = (xx̄)^{j} x̄ λ x; \\ ν̄_{i} = (xx̄)^{j} x̄ x, & 1 < i < k; \\ ν̄_{k} = (xx̄)^{j} x̄ x. \end{cases}

The underground path generated by ω_{|0} is φ ν̄_{1} … ν̄_{k} (see Figure 10).

Figure 10: The underground paths generated by ω_{|0} in the case 2.2.1)

2.2.2) If φ ends with a peak xx̄, that is, φ = φ′ xx̄, then

\begin{cases}ν̄_{1} = x̄ λ x(xx̄)^{j} x̄ x; \\ ν̄_{i} = (xx̄)^{j} x̄ x, & 1 < i < k; \\ ν̄_{k} = (xx̄)^{j} x̄ x. \end{cases}

The underground path generated by ω_{|0} is φ′ ν̄_{1} … ν̄_{k} (see Figure 11).

Figure 11: The underground paths generated by ω_{|0} in the case 2.2.2)

3.4 The underground path generated by ω_{|k}

In this section, we describe how to obtain the underground path generated by ω_{|k}, k ≥ 2. For any h, 1 ≤ h ≤ j, let ω′ = νφ be the path obtained from ω_{|k} and ending on the x-axis with a positive suffix; φ is the rightmost suffix in ω′ which is primitive.

If the path φ^{c} does not contain the forbidden pattern 𝔭, the underground path generated by ω_{|k} is νφ^{c}.

If the path φ^{c} contains the forbidden pattern 𝔭, we must apply a swap operation Φ in order to obtain a path φ_{1} = Φ(φ^{c}) avoiding the forbidden pattern. The underground path generated by ω_{|k} is νφ_{1}.

Before describing the Φ operation on φ^{c}, let us consider the following proposition.

Proposition 1. Let μ ∈ F^{[𝔭]} be a primitive path; μ^{c} contains the forbidden pattern 𝔭 = (xx̄)^{j}x if and only if μ contains the pattern 𝔭′ = (x̄)^{2}(xx̄)^{j}x̄.

From Proposition 1 it follows that, if φ^{c} contains the forbidden pattern 𝔭, then it is preceded and followed by at least a rise step.

Operation Φ must generate a path φ_{1} avoiding the forbidden pattern 𝔭 = (xx̄)^{j}x and such that φ_{1}^{c} ∈ F \F^{[𝔭]}; in this way φ_{1} is not the complement of any path in F^{[𝔭]}. The path φ_{1} = Φ(φ^{c}) is obtained as follows:

i) consider the straight line r from the beginning of the pattern 𝔭 = (xx̄)^{j}x and let t_{1} be the rightmost point in which r intersects φ^{c} on the left of 𝔭 such that t_{1} is preceded by at least two fall steps. Let δ_{2} = (xx̄)^{m}, 0 ≤ m < j, be the subsequence on the right of t_{1} and followed by at least a fall step;

ii) swap the initial subsequence δ_{1} = (xx̄)^{j} of 𝔭 and δ_{2}. It is straightforward to see that δ_{2} can not be equal to (xx̄)^{j} since φ does not contain the forbidden pattern 𝔭 = (xx̄)^{j}x (see Figure 12.a)). When m = 0, that is, δ_{2} is the empty word, we simply insert δ_{1} into t_{1} (see Figure 12.b)).

Operation Φ is applied to each forbidden pattern in φ^{c}.

Figure 12: Some examples of the Φ operation, 𝔭 = (xx̄)^{3}x

Proposition 2. Let φ_{1} = Φ(φ^{c}), then φ_{1}^{c} ∈ F \F^{[𝔭]}.

Proof. The Φ operation transforms the subsequence ϱ_{1} = (x̄)^{m} δ_{2} x̄, (m ≥ 2), of φ^{c} into the subsequence ϱ_{2} = (x̄)^{m} δ_{1} x̄ = (x̄)^{m} (xx̄)^{j} x̄ of φ_{1}. The complement of ϱ_{2} is

ϱ_{2}^{c} = (x)^{m} (x̄x)^{j} x = (x)^{m−1} (xx̄)^{j} x x.

So, φ_{1}^{c} contains the forbidden pattern 𝔭 = (xx̄)^{j}x.

Proposition 3. Let μ ∈ F \F^{[𝔭]} be a primitive path such that μ^{c} ∈ F^{[𝔭]}. Then there exists a path η ∈ F^{[𝔭]} such that μ^{c} = Φ(η^{c}).

Proof. If μ ∈ F \F^{[𝔭]} and μ^{c} ∈ F^{[𝔭]} then μ^{c} contains the pattern x̄x̄(xx̄)^{j}x̄; we apply to μ^{c} the following operation Φ^{−1}.

i) Consider the straight line r from the end of the pattern (xx̄)^{j} and let t_{2} be the leftmost point where r intersects μ^{c} on the right of (xx̄)^{j} such that t_{2} is followed by at least two rise steps. Let δ_{2} = (xx̄)^{m}, 0 ≤ m < j, be the subsequence on the left of t_{2} and preceded by at least a rise step.

ii) Swap the subsequence (xx̄)^{j} and δ_{2}. When m = 0, that is, δ_{2} is the empty word, we simply insert (xx̄)^{j} into t_{2}.

Figure 13 shows the initial steps of the generating algorithm of the paths corresponding to words in F^{[𝔭]}, with 𝔭 = (xx̄)^{2}x = (10)^{2}1.

Recall that, following the above constructions, given a path ω, the number of generated paths depends only on the ordinate of endpoint of ω.

Therefore, the complete generating algorithm can be briefly described by the succession rule (7). For more details on succession rules, the reader is invited to see [2, 5, 6].

\begin{cases}(0) \\ (0) ⇝^{h} (0)(0)(1) & 1 ≤ h ≤ j \\ (1) ⇝^{h} (2) & 1 ≤ h ≤ j \\ (k) ⇝^{h} (0)(0)(1) ⋯ (k − 1)(k + 1) & 1 ≤ h ≤ j, k ≥ 2 \end{cases}  (7)

Figure 13: The initial steps of the generating algorithm of the paths corresponding to words in F^{[𝔭]}, 𝔭 = (xx̄)^{2}x = (10)^{2}1. Dotted lines are related to h = 2

In the succession rule (7) each number corresponds to the ordinate of the endpoint of a path. The zero in the first line in (7) is associated with the empty path. Given the pattern 𝔭 = (xx̄)^{j}x = (10)^{j}1, the second line in (7) says that a path with n rise steps and ending at ordinate 0 generates two paths with n + h rise steps, 1 ≤ h ≤ j, and ending at ordinate 0, and one path with n+h rise steps and ending at ordinate 1, i.e., the second line is associated with operations (1) and (4). Similarly, the third line is associated with operations (2) and (5). The last line describes the construction when the endpoint of the path has ordinate k ≥ 2, underground path included.

4 Enumeration of F^{[𝔭]}

With reference to the succession rule (7), let A_{0} be the set of paths whose endpoints have ordinate 0, let A_{1} be the set of paths whose endpoints have ordinate 1 and let A_{k} be the set of paths whose endpoints have ordinate k, k ≥ 2. Then F^{[𝔭]} = A_{0} ∪ A_{1} ∪ A_{k}.

The paths in A_{0} with n rise steps are obtained from the paths in A_{0} with n−h, 1 ≤ h ≤ j, rise steps by means of the first production of (7) and from those in A_{k} with n − h rise steps by means of the last production of (7).

The paths in A_{1} with n rise steps are obtained from the paths in A_{0} with n−h, 1 ≤ h ≤ j, rise steps by means of the first production of (7) and from those in A_{k} with n − h rise steps by means of the last production of (7).

The paths in A_{k} with n rise steps are obtained from the paths in A_{1} with n−h, 1 ≤ h ≤ j, rise steps by means of the second production of (7) and from those in A_{k} with n − h rise steps by means of the last production of (7).

Let n(ω) be the number of rise steps of a path ω ∈ F^{[𝔭]} and let f(ω) be the ordinate of the last point of ω itself. From the succession rule (7) we obtain

A_{0}(x, 1) = 1 + 2 ∑_{h=1}^{j} ∑_{ω∈A_{0}} x^{n(ω)+h}y^{0} + 2 ∑_{h=1}^{j} ∑_{ω∈A_{k}} x^{n(ω)+h}y^{0},  (8)

A_{1}(x, y) = ∑_{h=1}^{j} ∑_{ω∈A_{0}} x^{n(ω)+h}y + ∑_{h=1}^{j} ∑_{ω∈A_{k}} x^{n(ω)+h}y,  (9)

A_{k}(x, y) = ∑_{h=1}^{j} ∑_{ω∈A_{1}} x^{n(ω)+h}y^{2} + ∑_{h=1}^{j} ∑_{ω∈A_{k}} ∑_{i=2}^{f(ω)−1} x^{n(ω)+h}y^{i} +

+ ∑_{h=1}^{j} ∑_{ω∈A_{k}} x^{n(ω)+h}y^{f(ω)+1}.  (10)

Since

∑_{h=1}^{j} ∑_{w∈A_{0}} x^{n(ω)+h}y^{0} = ∑_{h=1}^{j} x^{h} ∑_{w∈A_{0}} x^{n(ω)}y^{0} = ∑_{h=1}^{j} x^{h}A_{0}(x, 1) = \frac{(x − x^{j+1})}{1 − x}A_{0}(x, 1),

going on in the same way with the other terms, (8), (9) and (10) can rewritten

A_{0}(x, 1) = 1 + \frac{2(x − x^{j+1})}{1 − x}A_{0}(x, 1) + \frac{2(x − x^{j+1})}{1 − x}A_{k}(x, 1),  (11)
A_{1}(x, y) = \frac{y(x − x^{j+1})}{1 − x}A_{0}(x, 1) + \frac{y(x − x^{j+1})}{1 − x}A_{k}(x, 1),  (12)
A_{k}(x, y) = \frac{y^{2}(x − x^{j+1})}{1 − x}A_{1}(x, 1) + \frac{(x − x^{j+1})}{(1 − x)(y − 1)}A_{k}(x, y) −
−\frac{y^{2}(x − x^{j+1})}{(1 − x)(y − 1)}A_{k}(x, 1) + \frac{y(x − x^{j+1})}{1 − x}A_{k}(x, y).  (13)

From (13) we obtain

(y^{2}(x − x^{j+1}) − y(1 − x^{j+1}) + 1 − x^{j+1})A_{k}(x, y) =
= y^{2}(x − x^{j+1})A_{k}(x, 1) − y^{2}(y − 1)(x − x^{j+1})A_{1}(x, 1).

Let

y_{0} = \frac{1 − x^{j+1} − \sqrt{(1 − x^{j+1})^{2} − 4(x − x^{j+1})(1 − x^{j+1})}}{2(x − x^{j+1}}

be a solution of

y^{2}(x − x^{j+1}) − y(1 − x^{j+1}) + 1 − x^{j+1} = 0.

By using the kernel method [1] we have

A_{k}(x, 1) = (y_{0} − 1)A_{1}(x, 1).

By solving (11) and (12) we obtain

A_{0}(x, 1) = \frac{1 − x + 2(x − x^{j+1})(y_{0} − 1)A_{1}(x, 1)}{(1 − x) − 2(x − x^{j+1})},

A_{1}(x, 1) = \frac{x − x^{j+1}}{(1 − x) − (x − x^{j+1})(y_{0} + 1)}.

Hence, we can state the following result.

Proposition 4. The generating function F_{j}(x), j ≥ 1, for the words ω ∈ F^{[𝔭]} according to the number of 1’s is given by

F_{j}(x) = F_{j}(x, 1) = A_{0}(x, 1) + A_{1}(x, 1) + A_{k}(x, 1) =

= \frac{2(1 − x^{j+1})}{3x^{j+1} − 4x + 1 + \sqrt{(1 − x^{j+1})^{2} − 4(x − x^{j+1})(1 − x^{j+1})}}.

The first numbers of the sequences enumerating the binary words in F^{[𝔭]}, with 𝔭 = (10)^{j}1, according to the number n of 1’s, 1 ≤ n ≤ 10, and the value of j, 1 ≤ j ≤ 10, are shown in Table 1.

n
j 1 2 3 4 5 6 7 8 9 10
1 3 7 18 48 131 363 1017 2873 8169 23349
2 3 10 32 109 377 1324 4697 16795 60425 218485
3 3 10 35 123 445 1631 6036 22511 84460 318438
4 3 10 35 126 459 1699 6350 23911 90572 344737
5 3 10 35 126 462 1713 6418 24225 91979 350910
6 3 10 35 126 462 1716 6432 24293 92293 352317
7 3 10 35 126 462 1716 6435 24307 92361 352631
8 3 10 35 126 462 1716 6435 24310 92375 352699
9 3 10 35 126 462 1716 6435 24310 92378 352713
10 3 10 35 126 462 1716 6435 24310 92378 352716

Table 1: The sequences enumerating the binary words in F^{[𝔭]}, with 𝔭 = (10)^{j}1, according to the number n of 1’s

5 Conclusions and further developments

In this paper we give the generating function which counts particular binary words, according to the number of 1’s, excluding a fixed pattern 𝔭 = (10)^{j}1, j ≥ 1.

Successive studies should take into consideration binary words avoiding different forbidden patterns both from an enumerative and a constructive point of view.

Moreover, it would be interesting to study words avoiding patterns which have a different shape, that is, not just patterns consisting of a sequence of rise and fall steps.

Another interesting field of study consists of the determination of a sort of invariant class of avoiding patterns that is the paths 𝔭_{1}, 𝔭_{2}, …, 𝔭_{l} such that |F^{[𝔭_{1}]}| = |F^{[𝔭_{2}]}| = ⋯ = |F^{[𝔭_{l}]}| with consequent bijective problems.

One could also consider a forbidden pattern on an arbitrary alphabet and investigate words avoiding that pattern, or study words avoiding more than one pattern and the related combinatorial objects, considering various parameters.

References

[1] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Math. 246 (2002), 29–55.

[2] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, J. Difference Equ. Appl. 5 (1999), 435–490.

[3] S. Bilotta, E. Grazzini, E. Pergola and R. Pinzani, Generation of binary words avoiding alternating patterns, preprint, 2012. Available at http://arxiv.org/abs/1210.7620.

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

[5] S. Corteel, Séries génératrices exponentielles pour les eco-systèmes signés, Proc. of the 12th International Conference of Formal Power Series and Algebraic Combinatorics, Moscow, Springer, 2000, pp. 655–666.

[6] L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math. 271 (2003), 29–50.

[7] L. J. Guibas and M. Odlyzko, Long repetitive patterns in random sequences, Zeitschrift für Wahrscheinlichkeitstheorie 53 (1980), 241–262.

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

[9] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Chapman-Hall, 1995.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A05. Keywords: Binary words, generating functions, pattern avoidance.

(Concerned with sequence \underline{A225034}.)

Received November 27 2012; revised version received May 3 2013. Published in Journal of Integer Sequences, May 8 2013.

Return to Journal of Integer Sequences home page.