Algebraic Generating Functions for Languages Avoiding Riordan Patterns

Donatella Merlini and Massimo Nocentini Dipartimento di Statistica, Informatica, Applicazioni Università di Firenze viale Morgagni 65 50134 Firenze Italia

                         donatella.merlini@unifi.it
                         massimo.nocentini@unifi.it

Abstract We study the languages 𝔏^{[𝔭]} ⊂ {0, 1}^{∗} of binary words w avoiding a given pattern 𝔭 such that |w|_{0} ≤ |w|_{1} for every w ∈ 𝔏^{[𝔭]}, where |w|_{0} and |w|_{1} correspond to the number of 0-bits and 1-bits in the word w, respectively. In particular, we concentrate on patterns 𝔭 related to the concept of Riordan arrays. These languages are not regular, but can be enumerated by algebraic generating functions corresponding to many integer sequences that were previously unlisted in the On-Line Encyclopedia of Integer Sequences. We give explicit formulas for these generating functions, expressed in terms of the autocorrelation polynomial of 𝔭, and also give explicit formulas for the coefficients of some particular patterns, algebraically and combinatorially.

1 Introduction

In this paper we study the languages 𝔏^{[𝔭]} ⊂ {0, 1}^{∗} of binary words avoiding a given binary pattern 𝔭, having the property that |w|_{0} ≤ |w|_{1} for every word w ∈ 𝔏^{[𝔭]}, where |w|_{0} and |w|_{1} correspond to the number of 0-bits and 1-bits in the word w, respectively. The notion of a pattern can be formalized in several ways. In this paper we consider factor patterns, that is, patterns whose letters must appear in exact order and contiguously in the sequence under observation. The set of binary words avoiding a pattern, without the restriction |w|_{0} ≤ |w|_{1}, is defined by a regular language, and can be enumerated in terms of the number of 1-bits and 0-bits by using classical results (see, e.g., Guibas and Odlyzko [4, 5] and Sedgewick and Flajolet [11]). However, when we consider the additional restriction that the words have no more 0-bits than 1-bits, the language is no longer regular and enumerating it is a harder problem.

In this paper we are interested in Riordan patterns, a concept defined by Sprugnoli and the first author [9] in terms of the autocorrelation polynomial C^{[𝔭]}(x, y) of pattern 𝔭 = p_{0} ⋯ p_{h−1}. The coefficients of this polynomial are given by the autocorrelation vector associated to 𝔭, that is, the vector c = (c_{0}, …, c_{h−1}) of bits defined in terms of Iverson’s bracket notation (for a predicate P, the expression [[P]] has value 1 if P is true and 0 otherwise) as follows:

c_{i} = [[p_{0}p_{1} ⋯ p_{h−1−i} = p_{i}p_{i+1} ⋯ p_{h−1}]];

or in words, the bit c_{i} is determined by shifting 𝔭 to the right by i positions, setting c_{i} = 1 if and only if the remaining letters match the original. For example, when 𝔭 = 10101 the autocorrelation vector is c = (1, 0, 1, 0, 1), as illustrated in Table 1, and C^{[𝔭]}(x, y) = 1 + xy + x^{2}y^{2}, namely we add a term x^{j}y^{i} for each tail of the pattern with j 1-bits and i 0-bits, where c_{j+i} = 1.

1 0 1 0 1 Tails  c_{i}
1 0 1 0 1  1
1 0 1 0 1  0
1 0 1 0 1  1
1 0 1 0 1  0
1 0 1 0 1  1

Table 1: The autocorrelation vector for 𝔭 = 10101.

For each pattern 𝔭, we can compute the complement pattern 𝔭̄ by changing every 1 to 0 and every 0 to 1; for example, if 𝔭 = 10101 then 𝔭̄ = 01010, therefore C^{[𝔭]}(x, y) = C^{[𝔭̄]}(y, x).

Addition of constraints to the nature of a pattern 𝔭 yields the following definition:

Definition 1 (Riordan pattern). We say that 𝔭 = p_{0} ⋯ p_{h−1} is a Riordan pattern if and only if

C^{[𝔭]}(x, y) = C^{[𝔭̄]}(y, x) = ∑_{i=0}^{⌊(h−1)/2⌋} c_{2i}x^{i}y^{i}, with |n_{1}^{[𝔭]} − n_{0}^{[𝔭]}| ∈ {0, 1}

where n_{1}^{[𝔭]} and n_{0}^{[𝔭]} correspond to the number of 1-bits and 0-bits in the pattern, respectively.

For example, Table 1 corresponds to a Riordan pattern and 𝔭 = 1100110110011000 is another Riordan pattern having n_{1}^{[𝔭]} = n_{0}^{[𝔭]} = 8 and C^{[𝔭]}(x, y) = 1. Moreover, in Table 2 we give all the Riordan patterns of length 7 with first bit equal to 1 and their correlation polynomials, the corresponding complement patterns can be easily determined.

𝔭  C^{[𝔭]}(x, y)

{1010100, 1011000 \atop 1011100, 1100010}

{1100100, 1101000 \atop 1101010, 1101100}  1

{1110000, 1110010 \atop 1110100, 1111000}

1001100, 1100110  1 + x^{2}y^{2}
{1000111, 1001011 \atop 1001101, 1010011}  1 + x^{3}y^{3}

{1011001, 1100101 \atop 1101001, 1110001}

1010101  1 + xy + x^{2}y^{2} + x^{3}y^{3}

Table 2: The Riordan patterns of length 7 with first bit equal to 1 and their correlation polynomials

The name Riordan in the above definition is due to the connection with the well-known concept of Riordan arrays. We briefly recall that a Riordan array is an infinite lower triangular array (d_{n,k})_{n,k∈ℕ}, defined by a pair of formal power series (d(t), h(t)), such that d(0) ≠ 0, h(0) = 0, h′(0) ≠ 0 and the generic element d_{n,k} is the coefficient of monomial t^{n} in the series expansion of d(t)h(t)^{k}. Formally,

d_{n,k} = [t^{n}]d(t)h(t)^{k}, n, k ≥ 0

where d_{n,k} = 0 for k > n. These arrays were introduced in 1991 by Shapiro, Getu, Woan and Woodson [12], with the aim of defining a class of infinite lower triangular arrays with properties analogous to those of the Pascal triangle. Since then they have attracted, and continue to attract, much attention in the literature. Some of their structural properties were studied by Rogers, Sprugnoli, Verri and the first author [8], and additional properties were recently analyzed by Luzón, Morón, Sprugnoli and the first author [7]. In particular, we recall that the bivariate generating function enumerating the sequence (d_{n,k})_{n,k∈ℕ} is

R(t, w) = ∑_{n,k∈ℕ} d_{n,k}t^{n}w^{k} = \frac{d(t)}{1 − wh(t)}  (1)

An important property of Riordan array concerns the computation of combinatorial sums. A first paper in this direction is due to Sprugnoli [13], while the case dealing with implicit Riordan arrays is treated by Sprugnoli, Verri and the first author [10]. In particular we have the following result:

∑_{k=0}^{n} d_{n,k}f_{k} = [t^{n}]d(t)f(h(t)) or (d(t), h(t)) ∗ f(t) = d(t)f(h(t)),  (2)

that is, every combinatorial sum involving a Riordan array can be computed by extracting the coefficient of t^{n} from the series expansion of d(t)f(h(t)), where f(t) = G(f_{k}) = ∑_{k≥0} f_{k}t^{k} is the generating function of the sequence (f_{k})_{k∈ℕ} and the symbol G denotes the generating function operator. Due to its importance, relation (2) is often called the fundamental rule of Riordan arrays. In this paper, the notation (f_{k})_{k} will be used as an abbreviation of (f_{k})_{k∈ℕ}.

Coming back to the languages 𝔏^{[𝔭]} ⊂ {0, 1}^{∗} of binary words avoiding a pattern 𝔭, let R_{n,k}^{[𝔭]} be the number of words avoiding 𝔭 and having n 1-bits and n − k 0-bits; additionally,

let R^{[𝔭]} = (R_{n,k}^{[𝔭]})_{n,k∈ℕ} the enclosing matrix. The following theorem, which was proved by

Sprugnoli and the first author [9], shows the importance of Riordan patterns:

Theorem 2. Matrices R^{[𝔭]} and R^{[𝔭̄]} are Riordan arrays if and only if 𝔭 is a Riordan pattern.

By the previous theorem, matrices R^{[𝔭]} and R^{[𝔭̄]} can be defined as

R^{[𝔭]} = (d^{[𝔭]}(t), h^{[𝔭]}(t)) and R^{[𝔭̄]} = (d^{[𝔭̄]}(t), h^{[𝔭̄]}(t))

for the appropriate d^{[𝔭]}, h^{[𝔭]}, d^{[𝔭̄]}, h^{[𝔭̄]}, given a Riordan pattern 𝔭; moreover, they represent the lower and upper part of the array F^{[𝔭]} = (F_{n,k}^{[𝔭]})_{n,k∈ℕ}, where F_{n,k}^{[𝔭]} denotes the number of words avoiding pattern 𝔭 and having n 1-bits and k 0-bits . For the sake of clarity, Tables 3, 4 and 5 illustrate some rows for the matrices F^{[𝔭]}, R^{[𝔭]} and R^{[𝔭̄]}, where 𝔭 = 10101.

Remark 3. Riordan patterns are not the only patterns related to Riordan arrays; for example, given the pattern 𝔭 = 0100100 corresponding to C^{[𝔭]}(x, y) = 1 + xy^{2} + x^{2}y^{4}, matrix R^{[𝔭]} is still a Riordan array but R^{[𝔭̄]} is not, as illustrated by Baccherini, Sprugnoli and the first author [2, Example 5.4]. However, in these situations it is not easy to find functions d^{[𝔭]}(t) and h^{[𝔭]}(t), while for Riordan patterns it is always possible, as shown in Theorems 2 and 4.

\begin{matrix}n/k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 \\ 3 & 1 & 4 & 9 & 18 & 32 & 52 & 79 & 114 \\ 4 & 1 & 5 & 13 & 30 & 60 & 109 & 184 & 293 \\ 5 & 1 & 6 & 18 & 46 & 102 & 204 & 377 & 654 \\ 6 & 1 & 7 & 24 & 67 & 163 & 354 & 708 & 1324 \\ 7 & 1 & 8 & 31 & 94 & 248 & 580 & 1245 & 2490 \end{matrix}

Table 3: The matrix F^{[𝔭]} for 𝔭 = 10101

n/k 0  1  2 3 4 5 6 7
0  1
1  2  1
2  6  3  1
3 18  9  4 1
4 60 30 13 5 1
5 204 102 46 18 6 1
6 708 354 163 67 24 7 1
7 2490 1245 580 248 94 31 8 1

Table 4: R^{[𝔭]} for 𝔭 = 10101

n/k 0  1  2 3 4 5 6 7
0  1
1  2  1
2  6  3  1
3 18 10 4 1
4 60 32 15 5 1
5 204 109 52 21 6 1
6 708 377 184 79 28 7 1
7 2490 1324 654 293 114 36 8 1

Table 5: R^{[𝔭̄]} for 𝔭 = 10101

As already observed, the enumeration of the set of binary words avoiding a pattern, without the restriction about the number of 1-bits and 0-bits can be done by using classical results and gives the following rational bivariate generating function for the sequence (F_{n,k}^{[𝔭]})_{n,k∈ℕ} :

F^{[𝔭]}(x, y) = \frac{C^{[𝔭]}(x, y)}{(1 − x − y)C^{[𝔭]}(x, y) + x^{n_{1}^{[𝔭]}}y^{n_{0}^{[𝔭]}}} ,

where n_{1}^{[𝔭]} and n_{0}^{[𝔭]} correspond to the number of 1-bits and 0-bits, respectively, and C^{[𝔭]}(x, y) is the autocorrelation polynomial, all relative to pattern 𝔭. Consequently, F^{[𝔭]}(t, 1) and F^{[𝔭]}(t, t) count the words avoiding 𝔭 according to the number of 1-bits and to length of each word, respectively.

Using the theory of Riordan arrays and the results by Sprugnoli and the first author [9], we give explicit algebraic generating functions enumerating the set of binary words avoiding a Riordan pattern with the restriction |w|_{0} ≤ |w|_{1} according to various parameters, in particular to the number of 1-bits and to the words length. Most of the corresponding sequences are new to the On-Line Encyclopedia of Integer Sequences (OEIS)^{1} [6]; moreover, we also give explicit formulas for the coefficients of some particular patterns by providing algebraic and combinatorial proofs.

Finally, our results can be interpreted in the theory of paths and codes in light of the bijection among binary words and paths, which maps a 0-bit to a south-east step ⧹ and a 1-bit to a north-east step ⧸. From this point of view, a coefficient R_{n,k}^{[𝔭]} ∈ R^{[𝔭]} counts the number of paths containing n steps of ⧸ and n − k steps of ⧹, avoiding the subpath corresponding to pattern 𝔭, allowed to cross the x-axis but required to end at coordinate (2n − k, k) such that 0 ≤ k ≤ n. In particular, d^{[𝔭]}(t) is the generating function of paths that avoid 𝔭 and end on the x-axis.

1We attach a label Axxxxxx to a sequence if it appears in the OEIS with that identifier.

2 Riordan arrays for Riordan patterns

We start with a theorem that is a direct consequence of the results by Sprugnoli and the first author [9, Theorems 2.3 and 3.3].

Theorem 4. Let R_{n,k}^{[𝔭]} be the number of binary words with n 1-bits and n−k 0-bits, avoiding a Riordan pattern 𝔭. Then the triangle R^{[𝔭]} = (R_{n,k}^{[𝔭]}) is a Riordan array R^{[𝔭]} = (d^{[𝔭]}(t), h^{[𝔭]}(t)). In particular, if n_{1}^{[𝔭]} and n_{0}^{[𝔭]} correspond to the number of 1-bits and 0-bits in the pattern, C^{[𝔭]}(x, y) is the autocorrelation polynomial of 𝔭 and C^{[𝔭]}(t) = C^{[𝔭]}(\sqrt{t}, \sqrt{t}), then

• if n_{1}^{[𝔭]} − n_{0}^{[𝔭]} = 1 we have

d^{[𝔭]}(t) = \frac{C^{[𝔭]}(t)}{\sqrt{C^{[𝔭]}(t)^{2} − 4tC^{[𝔭]}(t)(C^{[𝔭]}(t) − t^{n_{0}^{[𝔭]}})}},

h^{[𝔭]}(t) = \frac{C^{[𝔭]}(t) − \sqrt{C^{[𝔭]}(t)^{2} − 4tC^{[𝔭]}(t)(C^{[𝔭]}(t) − t^{n_{0}^{[𝔭]}})}}{2C^{[𝔭]}(t)};

• if n_{1}^{[𝔭]} − n_{0}^{[𝔭]} = 0 we have

d^{[𝔭]}(t) = \frac{C^{[𝔭]}(t)}{\sqrt{(C^{[𝔭]}(t) + t^{n_{0}^{[𝔭]}})^{2} − 4tC^{[𝔭]}(t)^{2}}} ,

h^{[𝔭]}(t) = \frac{C^{[𝔭]}(t) + t^{n_{0}^{[𝔭]}} − \sqrt{(C^{[𝔭]}(t) + t^{n_{0}^{[𝔭]}})^{2} − 4tC^{[𝔭]}(t)^{2}}}{2C^{[𝔭]}(t)} ;

• if n_{0}^{[𝔭]} − n_{1}^{[𝔭]} = 1 we have

d^{[𝔭]}(t) = \frac{C^{[𝔭]}(t)}{\sqrt{C^{[𝔭]}(t)^{2} − 4tC^{[𝔭]}(t)(C^{[𝔭]}(t) − t^{n_{1}^{[𝔭]}})}},

h^{[𝔭]}(t) = \frac{C^{[𝔭]}(t) − \sqrt{C^{[𝔭]}(t)^{2} − 4tC^{[𝔭]}(t)(C^{[𝔭]}(t) − t^{n_{1}^{[𝔭]}})}}{2(C^{[𝔭]}(t) − t^{n_{1}^{[𝔭]}})}.

If R^{[𝔭]}(t, w) denotes the bivariate generating function of the Riordan array R^{[𝔭]}, as already mentioned in the Introduction, we have

R^{[𝔭]}(t, w) = ∑_{n,k∈ℕ} R_{n,k}^{[𝔭]}t^{n}w^{k} = \frac{d^{[𝔭]}(t)}{1 − wh^{[𝔭]}(t)},

and Theorem 4 allow us to state the following results.

Theorem 5. Let 𝔭 be a Riordan pattern and S^{[𝔭]}(t) = ∑_{n≥0} S_{n}^{[𝔭]}t^{n} the generating function enumerating the set of binary words {w ∈ {0, 1}^{∗} : |w|_{0} ≤ |w|_{1}} avoiding a Riordan pattern 𝔭 according to the number of 1-bits. Then we have

• if n_{1}^{[𝔭]} = n_{0}^{[𝔭]} + 1

S^{[𝔭]}(t) = \frac{2C^{[𝔭]}(t)}{\sqrt{Q(t)} (\sqrt{C^{[𝔭]}(t)} + \sqrt{Q(t)})},

where Q(t) = (1 − 4t)C^{[𝔭]}(t)^{2} + 4t^{n_{1}^{[𝔭]}};

• if n_{0}^{[𝔭]} = n_{1}^{[𝔭]} + 1

S^{[𝔭]}(t) = \frac{2C^{[𝔭]}(t)(C^{[𝔭]}(t) − t^{n_{1}^{[𝔭]}})}{\sqrt{Q(t)} (C^{[𝔭]}(t) − 2t^{n_{1}^{[𝔭]}} + \sqrt{Q(t)})},

where Q(t) = (1 − 4t)C^{[𝔭]}(t)^{2} + 4t^{n_{0}^{[𝔭]}}C^{[𝔭]}(t);

• if n_{1}^{[𝔭]} = n_{0}^{[𝔭]}

S^{[𝔭]}(t) = \frac{2C^{[𝔭]}(t)^{2}}{\sqrt{Q(t)} (C^{[𝔭]}(t) − t^{n_{0}^{[𝔭]}} + \sqrt{Q(t)})},

where Q(t) = (1 − 4t)C^{[𝔭]}(t)^{2} + 2t^{n_{0}^{[𝔭]}}C^{[𝔭]}(t) + t^{2n_{0}^{[𝔭]}}.

Proof. For the proof we can observe that S^{[𝔭]}(t) = ∑_{n≥0} S_{n}^{[𝔭]}t^{n} = R^{[𝔭]}(t, 1), or, equivalently, that S_{n}^{[𝔭]} = ∑_{k=0}^{n} R_{n,k}^{[𝔭]} and apply the fundamental rule (2) with f_{k} = 1. The statement of the theorem can be found after some algebraic simplification.

Theorem 6. Let 𝔭 be a Riordan pattern and L^{[𝔭]}(t) = ∑_{n≥0} L_{n}^{[𝔭]}t^{n} the generating function enumerating the set of binary words {w ∈ {0, 1}^{∗} : |w|_{0} ≤ |w|_{1}} avoiding a Riordan pattern 𝔭 according to the length. Then we have

• if n_{1}^{[𝔭]} = n_{0}^{[𝔭]} + 1

L^{[𝔭]}(t) = \frac{2tC^{[𝔭]}(t^{2})^{2}}{\sqrt{Q(t)} ((2t − 1)C(t^{2}) + \sqrt{Q(t)})},

where Q(t) = C^{[𝔭]}(t^{2}) ((1 − 4t^{2})C^{[𝔭]}(t^{2}) + 4t^{2n_{1}^{[𝔭]}});

• if n_{0}^{[𝔭]} = n_{1}^{[𝔭]} + 1

L^{[𝔭]}(t) = \frac{2t\sqrt{C^{[𝔭]}(t^{2})}(t^{2n_{1}^{[𝔭]}} − C^{[𝔭]}(t^{2}))}{\sqrt{Q(t)} ((1 − 2t)C^{[𝔭]}(t^{2}) + 2t^{n_{0}^{[𝔭]}+n_{1}^{[𝔭]}} − \sqrt{C^{[𝔭]}(t^{2})Q(t)})},

where Q(t) = (1 − 4t^{2})C^{[𝔭]}(t^{2}) + 4t^{2n_{0}^{[𝔭]}};

• if n_{1}^{[𝔭]} = n_{0}^{[𝔭]}

L^{[𝔭]}(t) = \frac{2tC^{[𝔭]}(t^{2})^{2}}{\sqrt{Q(t)} ((2t − 1)C(t^{2}) − t^{2n_{0}^{[𝔭]}} + \sqrt{Q(t)})},

where Q(t) = (1 − 4t^{2})C^{[𝔭]}(t^{2})^{2} + 2t^{2n_{0}^{[𝔭]}}C^{[𝔭]}(t^{2}) + t^{4n_{0}^{[𝔭]}}.

Proof. For the proof we can observe that the application of generating function R^{[𝔭]}(t, w) as

R^{[𝔭]} (tw, \frac{1}{w}) = ∑_{n,k∈ℕ} R_{n,k}^{[𝔭]}t^{n}w^{n−k}

entails that [t^{r}w^{s}]R^{[𝔭]} (tw, \frac{1}{w}) = R_{r,r−s}^{[𝔭]}, which is the number of binary words with r 1bits and s 0-bits. To enumerate according to the length let t = w, therefore L^{[𝔭]}(t) = ∑_{n≥0} L_{n}^{[𝔭]}t^{n} = R^{[𝔭]}(t^{2}, 1/t). The statement of the theorem can be found after some algebraic simplification.

Theorems 5 and 6 allow us to find the generating functions S^{[𝔭]}(t) and L^{[𝔭]}(t) in terms of the autocorrelation polynomial for every Riordan pattern 𝔭. In what follows, we study some special classes of patterns characterized by an autocorrelation polynomial that can be easily computed, as in the case C^{[𝔭]}(x, y) = 1. For such particular patterns, Theorem 4 can be simplified as follows:

Corollary 7. Let R^{[𝔭]} = (R_{n,k}^{[𝔭]})_{n,k∈ℕ} = (d^{[𝔭]}(t), h^{[𝔭]}(t)) be the Riordan array corresponding to the number of binary words with n 1-bits and n − k 0-bits that avoid the Riordan pattern 𝔭. Then we have the following particular cases:

• for 𝔭 = 1^{j+1}0^{j} we have the Riordan array

d^{[𝔭]}(t) = \frac{1}{\sqrt{1 − 4t + 4t^{j+1}}} , h^{[𝔭]}(t) = \frac{1 − \sqrt{1 − 4t + 4t^{j+1}}}{2} ;

• 𝔭 = 0^{j+1}1^{j} we have the Riordan array

d^{[𝔭]}(t) = \frac{1}{\sqrt{1 − 4t + 4t^{j+1}}} , h^{[𝔭]}(t) = \frac{1 − \sqrt{1 − 4t + 4t^{j+1}}}{2(1 − t^{j})} ;

• 𝔭 = 1^{j}0^{j} and 𝔭 = 0^{j}1^{j} we have the Riordan array

d^{[𝔭]}(t) = \frac{1}{\sqrt{1 − 4t + 2t^{j} + t^{2j}}} , h^{[𝔭]}(t) = \frac{1 + t^{j} − \sqrt{1 − 4t + 2t^{j} + t^{2j}}}{2} ;

• 𝔭 = (10)^{j}1 we have the Riordan array

\begin{aligned}d^{[𝔭]}(t) & = \frac{∑_{i=0}^{j} t^{i}}{\sqrt{1 − 2 ∑_{i=1}^{j} t^{i} − 3 (∑_{i=1}^{j} t^{i})^{2}}} , \\ h^{[𝔭]}(t) & = \frac{∑_{i=0}^{j} t^{i} − \sqrt{1 − 2 ∑_{i=1}^{j} t^{i} − 3 (∑_{i=1}^{j} t^{i})^{2}}}{2 ∑_{i=0}^{j} t^{i}}; \end{aligned}

• 𝔭 = (01)^{j}0 we have the Riordan array

\begin{aligned}d^{[𝔭]}(t) & = \frac{∑_{i=0}^{j} t^{i}}{\sqrt{1 − 2 ∑_{i=1}^{j} t^{i} − 3 (∑_{i=1}^{j} t^{i})^{2}}} , \\ h^{[𝔭]}(t) & = \frac{∑_{i=0}^{j} t^{i} − \sqrt{1 − 2 ∑_{i=1}^{j} t^{i} − 3 (∑_{i=1}^{j} t^{i})^{2}}}{2 ∑_{i=0}^{j−1} t^{i}} . \end{aligned}

As a peculiar instance, observe that when we instantiate a pattern from family 𝔭 = 1^{j}0^{j} with j = 1 we get a Riordan array R^{[10]} = (d^{[10]}(t), h^{[10]}(t)) such that

d^{[10]}(t) = \frac{1}{1 − t} and h^{[10]}(t) = t,

so the number R_{n,0}^{[10]} of words containing n 1-bits and n 0-bits, avoiding pattern 𝔭 = 10, is [t^{n}]d^{[10]}(t) = 1 for n ∈ ℕ. If we consider the combinatorial interpretation of R_{n,0}^{[𝔭]} as lattice paths as illustrated in the last paragraph of the Introduction, this corresponds to the fact that there is exactly one valley-shaped path having n steps of both kinds ⧸ and ⧹, avoiding 𝔭 = 10 and terminating at coordinate (2n, 0) for each n ∈ ℕ, formally the path 0^{n}1^{n}.

By applying Theorem 5 to the same patterns as before, we get the following corollary.

Corollary 8. Let S^{[𝔭]}(t) = ∑_{n≥0} S_{n}^{[𝔭]}t^{n} the generating function enumerating the set of binary words {w ∈ {0, 1}^{∗} : |w|_{0} ≤ |w|_{1}} avoiding a Riordan pattern 𝔭 according to the number of 1-bits. We have the following particular cases:

• for 𝔭 = 1^{j+1}0^{j} we have

S^{[𝔭]}(t) = \frac{2}{\sqrt{1 − 4t + 4t^{j+1}} (1 + \sqrt{1 − 4t + 4t^{j+1}})};

• for 𝔭 = 0^{j+1}1^{j} we have

S^{[𝔭]}(t) = \frac{2(1 − t^{j})}{\sqrt{1 − 4t + 4t^{j+1}} (1 − 2t^{j} + \sqrt{1 − 4t + 4t^{j+1}})};

• for 𝔭 = 1^{j}0^{j} and 𝔭 = 0^{j}1^{j} we have

S^{[𝔭]}(t) = \frac{2}{\sqrt{1 − 4t + 2t^{j} + t^{2j}} (1 − t^{j} + \sqrt{1 − 4t + 2t^{j} + t^{2j}})};

• for 𝔭 = (10)^{j}1 we have

S^{[𝔭]}(t) = \frac{2(1 − t^{j+1})}{1 − 4t + 3t^{j+1} + \sqrt{1 − 4t + 2t^{j+1} + 4t^{j+2} − 3t^{2j+2}}} ;

• for 𝔭 = (01)^{j}0 we have

S^{[𝔭]}(t) = \frac{2(1 − t^{j} − t^{j+1} + t^{2j+1})}{\sqrt{Q(t)} (1 − 2t^{j} + t^{j+1} + \sqrt{Q(t)})},

where Q(t) = 1 − 4t + 2t^{j+1} + 4t^{j+2} − 3t^{2j+2}.

We observe that the case 𝔭 = (10)^{j}1 in Corollary 8 corresponds to the sequence studied by Bilotta, Grazzini and Pergola [3]; moreover, in Table 6, Table 7, Table 8, Table 9 and Table 10 we report some expansions and some set of words related to the S^{[𝔭]}(t) functions just defined, respectively.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 3 & 7 & 15 & 31 & 63 & 127 & 255 & 511 & 1023 & 2047 & 4095 \\ 2 & 1 & 3 & 10 & 32 & 106 & 357 & 1222 & 4230 & 14770 & 51918 & 183472 & 651191 \\ 3 & 1 & 3 & 10 & 35 & 123 & 442 & 1611 & 5931 & 22010 & 82187 & 308427 & 1162218 \\ 4 & 1 & 3 & 10 & 35 & 126 & 459 & 1696 & 6330 & 23806 & 90068 & 342430 & 1307138 \\ 5 & 1 & 3 & 10 & 35 & 126 & 462 & 1713 & 6415 & 24205 & 91874 & 350406 & 1341782 \\ 6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6432 & 24290 & 92273 & 352212 & 1349768 \\ 7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24307 & 92358 & 352611 & 1351574 \\ 8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92375 & 352696 & 1351973 \end{matrix}

\begin{matrix}[t^{3}]S^{[110]}(t) & = |\{111, 0111, 1011, 00111, 01011, 10011, 10101, 000111, \\ 001011, 010011, 010101, 100011, 100101, 101001, 101010\}| = 15 \end{matrix}

Table 6: Some expansions for S^{[1^{j+1}0^{j}]}(t) and the set of words with n = 3 1-bits, avoiding pattern 𝔭 = 110, so j = 1 in the family; moreover, for j = 1 the sequence corresponds to \underline{A000225}, for j = 2 the sequence corresponds to \underline{A261058}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 3 & 8 & 20 & 48 & 112 & 256 & 576 & 1280 & 2816 & 6144 & 13312 \\ 2 & 1 & 3 & 10 & 33 & 111 & 378 & 1302 & 4525 & 15841 & 55783 & 197389 & 701286 \\ 3 & 1 & 3 & 10 & 35 & 124 & 447 & 1632 & 6015 & 22336 & 83439 & 313216 & 1180511 \\ 4 & 1 & 3 & 10 & 35 & 126 & 460 & 1701 & 6351 & 23890 & 90398 & 343713 & 1312108 \\ 5 & 1 & 3 & 10 & 35 & 126 & 462 & 1714 & 6420 & 24226 & 91958 & 350736 & 1343069 \\ 6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6433 & 24295 & 92294 & 352296 & 1350098 \\ 7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24308 & 92363 & 352632 & 1351658 \\ 8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92376 & 352701 & 1351994 \end{matrix}

\begin{matrix}[t^{3}]S^{[001]}(t) & = |\{111, 0111, 1011, 1101, 1110, 01011, 01101, 01110, 10101, 10110, 11010, 11100, \\ 010101, 010110, 011010, 011100, 101010, 101100, 110100, 111000\}| = 20 \end{matrix}

Table 7: Some expansions for S^{[0^{j+1}1^{j}]}(t) and the set of words with n = 3 1-bits, avoiding pattern 𝔭 = 001, so j = 1 in the family; moreover, for j = 1 the sequence corresponds to \underline{A001792}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 0 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92378 & 352716 & 1352078 \\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 2 & 1 & 3 & 9 & 27 & 82 & 253 & 791 & 2499 & 7960 & 25520 & 82248 & 266221 \\ 3 & 1 & 3 & 10 & 34 & 118 & 417 & 1493 & 5400 & 19684 & 72196 & 266122 & 985003 \\ 4 & 1 & 3 & 10 & 35 & 125 & 454 & 1671 & 6211 & 23261 & 87641 & 331821 & 1261398 \\ 5 & 1 & 3 & 10 & 35 & 126 & 461 & 1708 & 6390 & 24086 & 91328 & 347965 & 1331072 \\ 6 & 1 & 3 & 10 & 35 & 126 & 462 & 1715 & 6427 & 24265 & 92154 & 351666 & 1347326 \\ 7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6434 & 24302 & 92333 & 352492 & 1351028 \\ 8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24309 & 92370 & 352671 & 1351854 \end{matrix}

\begin{matrix}[t^{8}]S^{[01]}(t) & = |\{11111111, 111111110, 1111111100, 11111111000, 111111110000, \\ 1111111100000, 11111111000000, 111111110000000, 1111111100000000\}| = 9 \end{matrix}

Table 8: Some expansions for S^{[0^{j}1^{j}]}(t) (or, equivalently, S^{[1^{j}0^{j}]}(t)) and the set of words with n = 8 1-bits, avoiding pattern 𝔭 = 01 (or, equivalently, 𝔭 = 10), so j = 1 in the family; moreover, for j = 0 the sequence corresponds to \underline{A001700}, for j = 1 the sequence corresponds to \underline{A001477}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 3 & 7 & 18 & 48 & 131 & 363 & 1017 & 2873 & 8169 & 23349 & 67024 \\ 2 & 1 & 3 & 10 & 32 & 109 & 377 & 1324 & 4697 & 16795 & 60425 & 218485 & 793259 \\ 3 & 1 & 3 & 10 & 35 & 123 & 445 & 1631 & 6036 & 22511 & 84460 & 318438 & 1205457 \\ 4 & 1 & 3 & 10 & 35 & 126 & 459 & 1699 & 6350 & 23911 & 90572 & 344737 & 1317397 \\ 5 & 1 & 3 & 10 & 35 & 126 & 462 & 1713 & 6418 & 24225 & 91979 & 350910 & 1344092 \\ 6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6432 & 24293 & 92293 & 352317 & 1350272 \\ 7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24307 & 92361 & 352631 & 1351679 \\ 8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92375 & 352699 & 1351993 \end{matrix}

\begin{matrix}[t^{3}]S^{[101]}(t) & = |\{111, 0111, 1110, 00111, 01110, 10011, 11001, 11100, 000111, 001110, \\ 010011, 011001, 011100, 100011, 100110, 110001, 110010, 111000\}| = 18 \end{matrix}

Table 9: Some expansions for S^{[(10)^{j}1]}(t) and the set of words with n = 3 1-bits, avoiding pattern 𝔭 = 101, so j = 1 in the family; moreover, for j = 1 the sequence corresponds to \underline{A225034}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 3 & 8 & 22 & 61 & 171 & 483 & 1373 & 3923 & 11257 & 32418 & 93644 \\ 2 & 1 & 3 & 10 & 33 & 113 & 393 & 1384 & 4920 & 17618 & 63456 & 229642 & 834342 \\ 3 & 1 & 3 & 10 & 35 & 124 & 449 & 1647 & 6099 & 22754 & 85394 & 322022 & 1219205 \\ 4 & 1 & 3 & 10 & 35 & 126 & 460 & 1703 & 6366 & 23974 & 90818 & 345691 & 1321092 \\ 5 & 1 & 3 & 10 & 35 & 126 & 462 & 1714 & 6422 & 24241 & 92042 & 351156 & 1345049 \\ 6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6433 & 24297 & 92309 & 352380 & 1350518 \\ 7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24308 & 92365 & 352647 & 1351742 \\ 8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92376 & 352703 & 1352009 \end{matrix}

[t^{3}]S^{[010]}(t) = |{111, 0111, 1011, 1101, 1110, 00111, 01101, 01110,
10011, 10110, 11001, 11100, 000111, 001101, 001110, 011001,
011100, 100011, 100110, 101100, 110001, 111000}| = 22

Table 10: Some expansions for S^{[(01)^{j}0]}(t) and the set of words with n = 3 1-bits, avoiding pattern 𝔭 = 010, so j = 1 in the family; moreover, for j = 1 the sequence corresponds to \underline{A025566}.

Finally, by applying Theorem 6 to the pattern families already examined, we find the following result. Corollary 9. Let L^{[𝔭]}(t) = ∑_{n≥0} L_{n}^{[𝔭]}t^{n} the generating function enumerating the set of binary words {w ∈ {0, 1}^{∗} : |w|_{0} ≤ |w|_{1}} avoiding a Riordan pattern 𝔭 according to the length. We have the following particular cases:

• for 𝔭 = 1^{j+1}0^{j} we have

L^{[𝔭]}(t) = \frac{2t}{\sqrt{1 − 4t^{2} + 4t^{2(j+1)}} (2t − 1 + \sqrt{1 − 4t^{2} + 4t^{2(j+1)}})};

• for 𝔭 = 0^{j+1}1^{j} we have

L^{[𝔭]}(t) = \frac{2t(t^{2j} − 1)}{\sqrt{1 − 4t^{2} + 4t^{2(j+1)}} (1 − 2t + 2t^{2j+1} − \sqrt{1 − 4t^{2} + 4t^{2(j+1)}})};

• for 𝔭 = 1^{j}0^{j} and 𝔭 = 0^{j}1^{j} we have:

L^{[𝔭]}(t) = \frac{2t}{\sqrt{1 − 4t^{2} + 2t^{2j} + t^{4j}} (−1 + 2t − t^{2j} + \sqrt{1 − 4t^{2} + 2t^{2j} + t^{4j}})};

• for 𝔭 = (10)^{j}1 we have

L^{[𝔭]}(t) = \frac{2t(t^{2j+2} − 1)}{1 − 4t^{2} + 3t^{2j+2} + (2t − 1)\sqrt{Q(t)}};

• for 𝔭 = (01)^{j}0 we have

L^{[𝔭]}(t) = \frac{2t(t^{2j+2} − 1)(t^{2j} − 1)}{\sqrt{Q(t)}(t^{2j+2} − 2t^{2j+1} + 2t − 1 + \sqrt{Q(t)})},

where Q(t) = 1 − 4t^{2} + 2t^{2j+2} + 4t^{2j+4} − 3t^{4j+4}.

In Table 11, Table 12, Table 13, Table 14 and Table 15 we report some expansions related to the L^{[𝔭]}(t) functions just defined, respectively.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 3 & 3 & 7 & 7 & 15 & 15 & 31 & 31 & 63 & 63 & 127 & 127 & 255 \\ 2 & 1 & 1 & 3 & 4 & 11 & 15 & 38 & 55 & 135 & 201 & 483 & 736 & 1742 & 2699 & 6313 \\ 3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 63 & 159 & 247 & 610 & 969 & 2354 & 3802 & 9117 \\ 4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 255 & 634 & 1015 & 2482 & 4041 & 9752 \\ 5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1023 & 2506 & 4087 & 9880 \\ 6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4095 & 9904 \\ 7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908 \end{matrix}

Table 11: Some expansions for L^{[1^{j+1}0^{j}]}(t); moreover, for j = 1 the sequence corresponds to \underline{A052551}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 3 & 4 & 9 & 13 & 26 & 39 & 73 & 112 & 201 & 313 & 546 & 859 & 1469 \\ 2 & 1 & 1 & 3 & 4 & 11 & 16 & 40 & 61 & 147 & 231 & 542 & 870 & 2004 & 3269 & 7423 \\ 3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 161 & 253 & 622 & 999 & 2414 & 3942 & 9396 \\ 4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 636 & 1021 & 2494 & 4071 & 9812 \\ 5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2508 & 4093 & 9892 \\ 6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9906 \\ 7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908 \end{matrix}

Table 12: Some expansions for L^{[0^{j+1}1^{j}]}(t); moreover, for j = 1 the sequence corresponds to \underline{A079284}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 0 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 & 7 & 8 \\ 2 & 1 & 1 & 3 & 4 & 10 & 14 & 33 & 48 & 109 & 163 & 362 & 552 & 1207 & 1868 & 4036 \\ 3 & 1 & 1 & 3 & 4 & 11 & 16 & 41 & 62 & 154 & 240 & 583 & 928 & 2217 & 3587 & 8459 \\ 4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 162 & 254 & 629 & 1008 & 2455 & 4000 & 9614 \\ 5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 637 & 1022 & 2501 & 4080 & 9853 \\ 6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2509 & 4094 & 9899 \\ 7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9907 \end{matrix}

Table 13: Some expansions for L^{[0^{j}1^{j}]}(t) (or, equivalently, L^{[1^{j}0^{j}]}(t)); moreover, for j = 0 the sequence corresponds to \underline{A027306}, for j = 1 the sequence corresponds to \underline{A008619}.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 3 & 3 & 7 & 8 & 19 & 23 & 53 & 66 & 150 & 191 & 429 & 555 & 1235 \\ 2 & 1 & 1 & 3 & 4 & 11 & 15 & 38 & 56 & 139 & 210 & 511 & 790 & 1892 & 2973 & 7034 \\ 3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 63 & 159 & 248 & 614 & 978 & 2382 & 3857 & 9273 \\ 4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 255 & 634 & 1016 & 2486 & 4050 & 9780 \\ 5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1023 & 2506 & 4088 & 9884 \\ 6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4095 & 9904 \\ 7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908 \end{matrix}

Table 14: Some expansions for L^{[(10)^{j}1]}(t); moreover, no sequence is known in the literature, except for j = 0.

\begin{matrix}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 3 & 4 & 9 & 13 & 28 & 42 & 87 & 134 & 271 & 425 & 844 & 1342 & 2628 \\ 2 & 1 & 1 & 3 & 4 & 11 & 16 & 40 & 61 & 149 & 234 & 558 & 895 & 2098 & 3420 & 7909 \\ 3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 161 & 253 & 624 & 1002 & 2430 & 3967 & 9492 \\ 4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 636 & 1021 & 2496 & 4074 & 9828 \\ 5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2508 & 4093 & 9894 \\ 6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9906 \\ 7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908 \end{matrix}

Table 15: Some expansions for L^{[(01)^{j}0]}(t); moreover, no sequence is known in literature, except for j = 0.

3 Some combinatorial interpretations

In the previous section we proved results about the enumeration of words avoiding patterns from an algebraic point of view. The aim of this section is to analyze in more details some particular cases of the various pattern families. We approach these problems either combinatorially by providing an interpretation, or algebraically by computing the coefficients of the involved generating functions explicitly.

3.1 Enumeration with respect to the number of 1-bits

Corollary 10. Consider pattern 𝔭 = 1^{j+1}0^{j}. There is only one word in 𝔏^{[𝔭]} for j = 0; on the other hand, there are S_{n}^{[𝔭]} = 2^{n+1} − 1 words for j = 1.

Proof. When j = 0 the pattern to avoid is 𝔭 = 1, therefore only words w in {ε} ∪ {0}^{+} are suitable choices; however, the constraint |w|_{0} ≤ |w|_{1} makes w = ε the only one.

When j = 1 the pattern to avoid is 𝔭 = 110 and we observe that the generic binomial \binom{r}{k} can be interpreted as the number of binary words with r 0-bits containing k occurrences of the substring 10, which we call an inversion with respect to pattern 𝔭 = 110. In order to build a word in the language we start from the substring 0^{r} for r ∈ {0, …, n} and select k ∈ {0, …, r} 0-bits, transforming each one using the mapping 0 ↦ 10, while preventing the transformation of the 0-bit in the 10 just introduced. This maneuver introduces k inversions and the selection can be done in \binom{r}{k} ways; finally, we pad on the right with a strip 1^{n−k}, because it is mandatory for a word to have n 1-bits. Hence there is one padding for each set of inversions and there is no other way to avoid 𝔭. Therefore

∑_{r=0}^{n} ∑_{k=0}^{r} \binom{r}{k} = 2^{n+1} − 1 = S_{n}^{[𝔭]},

as can be verified algebraically by extracting the coefficient of the generating function

S^{[𝔭]}(t) = \frac{1}{1 − 3t + 2t^{2}} = \frac{2}{1 − 2t} − \frac{1}{1 − t},

as required.

The same argument can be rewritten in term of sets, which allows us to give a constructive approach. Let S_{n,k,i} be the set of binary words containing n and k occurrences of 1-bits and 0-bits, respectively, with i inversions, namely an occurrence of the subsequence 10. By union with respect to i and k, we get the sets S_{n,k}^{[𝔭]} and S_{n}^{[𝔭]}, formally

S_{n}^{[𝔭]} = ⋃_{k∈{0,...,n}} S_{n,k}^{[𝔭]} = ⋃_{i∈{0,...,k}} S_{n,k,i}^{[𝔭]} = ( ⋃_{i∈{0,...,k}} S_{k,k,i}^{[𝔭]}) × {1^{n−k}}.

For the sake of clarity, we enumerate all binary words avoiding 𝔭 = 110 containing n = 3 1-bits, formally we partition S_{3}^{[𝔭]} as follows:

S_{3}^{[𝔭]} = S_{0,0,0}^{[𝔭]} × {111}
∪ (S_{1,1,0}^{[𝔭]} ∪ S_{1,1,1}^{[𝔭]}) × {11}
∪ (S_{2,2,0}^{[𝔭]} ∪ S_{2,2,1}^{[𝔭]} ∪ S_{2,2,2}^{[𝔭]}) × {1}
∪ (S_{3,3,0}^{[𝔭]} ∪ S_{3,3,1}^{[𝔭]} ∪ S_{3,3,2}^{[𝔭]} ∪ S_{3,3,3}^{[𝔭]}) × {ε}

where

S_{3,0}^{[𝔭]} = S_{0,0,0}^{[𝔭]} × {111} = {ε} × {111} = {111}
S_{3,1}^{[𝔭]} = (S_{1,1,0}^{[𝔭]} ∪ S_{1,1,1}^{[𝔭]}) × {11} = {0111} ∪ {1011}
S_{3,2}^{[𝔭]} = (S_{2,2,0}^{[𝔭]} ∪ S_{2,2,1}^{[𝔭]} ∪ S_{2,2,2}^{[𝔭]}) × {1} = {00111} ∪ {10011, 01011} ∪ {10101}
S_{3,3}^{[𝔭]} = (S_{3,3,0}^{[𝔭]} ∪ S_{3,3,1}^{[𝔭]} ∪ S_{3,3,2}^{[𝔭]} ∪ S_{3,3,3}^{[𝔭]}) × {ε} = {000111} ∪ {001011, 100011, 010011}
∪ {101001, 100101, 010101} ∪ {101010},

the same set of words shown in Table 6.

Corollary 11. Consider pattern 𝔭 = 0^{j+1}1^{j}. There is one word S_{n}^{[𝔭]} = 1 for each n ∈ ℕ in 𝔏^{[𝔭]} when j = 0; on the other hand, there are (n + 2)2^{n−1} words for j = 1.

Proof. When j = 0 the pattern to avoid is 𝔭 = 0, therefore only words w = 1^{n} are suitable. Hence there is one of them for each n ∈ ℕ.

When j = 1 the pattern to avoid is 𝔭 = 001, therefore we extract the n-th coefficient after instantiation of the corresponding generating function:

[t^{n}]S_{n}^{[𝔭]}(t) = [t^{n}]\frac{1 − t}{(1 − 2t)^{2}} = (n + 2)2^{n−1},

as required.

We also provide a combinatorial interpretation of the theorem; first of all, we observe that sequence S_{n}^{[𝔭]} is the binomial transform of the sequence of the positive integers (n + 1)_{n∈ℕ}, formally

S_{n}^{[𝔭]} = (n + 2)2^{n−1} = ∑_{k=0}^{n} \binom{n}{k}(k + 1),

where the generic summand \binom{n}{k}(k + 1) can be interpreted as the number of binary words with n 1-bits containing n − k occurrences of the substring 01, which we call an inversion respect to the pattern 𝔭 = 001. We construct the set of words avoiding 𝔭 to show the bijection with the previous assertion as follows: if in a word w there are n − k occurrences of the substring 01 then w contains 2n − 2k bits in total, n − k of both kinds. Since it is mandatory that the number of 1 is n, we add k 1-bits to it, resulting in a new word w′ of length 2n − k, which can be augmented with at most k additional 0-bits, according to the constraint |w′|_{0} ≤ |w′|_{1}. In order to build a word with the structure of w′, we start from the substring 1^{n} and select n − k 1-bits, transforming each one using the mapping 1 ↦ 01, simultaneously to prevent transforming 1-bit in 01 just introduced. This maneuver introduces n − k inversions and the selection can be done in \binom{n}{k} ways; moreover, we are free to pad on the right with 0^{i} strips, for i ∈ {0, …, k}, hence there are k + 1 paddings for each set of inversions. Therefore, since there can be up to n inversions,

∑_{k=0}^{n} \binom{n}{n − k}(k + 1) = (n + 2)2^{n−1}

concludes the proof by symmetry of binomial coefficients.

Corollary 12. Consider pattern 𝔭 = 0^{j}1^{j} (or, equivalently, 𝔭 = 1^{j}0^{j}). There are

S_{n}^{[𝔭]} = ∑_{k=0}^{n} \binom{n + k}{k} = \binom{2n + 1}{n}

words in 𝔏^{[𝔭]} for j = 0; on the other hand, there are S_{n}^{[𝔭]} = n + 1 words for j = 1.

Proof. When j = 0 there is no pattern to avoid and this situation corresponds to the enumeration of binary words {w ∈ {0, 1}^{∗} : |w|_{0} ≤ |w|_{1} = n}. After instantiating the generating function S^{[𝔭]}(t), we extract the n-th coefficient, as follows:

[t^{n}]S_{n}^{[𝔭]}(t) = [t^{n}]\frac{1 − \sqrt{1 − 4t}}{2t\sqrt{1 − 4t}} = \frac{1}{2}\binom{2(n + 1)}{n + 1} = \binom{2n + 1}{n + 1} = \binom{2n + 1}{n},

which can be simplified by using the identity

\binom{r + s + 1}{s} = ∑_{q=0}^{s} \binom{r + q}{q},

as desired. It is possible to state the following combinatorial interpretation: since the maximum number of 0-bits is n, we reserve n boxes for them. To the left of each box reserve one more box and, finally, another one to the right of the very last box. In this way we have reserved 2n + 1 boxes where we can put n 1-bits in \binom{2n+1}{n} ways, as required.

When j = 1 the pattern to avoid is 𝔭 = 01 (or, equivalently, 𝔭 = 10), therefore only words w ∈ {1^{n}} × ⋃_{s∈{0,...,n}}{0^{s}} are suitable, which are n + 1, one for each value that s can take.

Last two patterns 𝔭 = (10)^{j}1 and 𝔭 = (01)^{j}0 are harder to study: for j = 0 there are S_{n}^{[𝔭]} = [[n = 0]] and S_{n}^{[𝔭]} = 1 words, respectively. On the other hand, when j = 1 we report only the instantiated generating functions

\begin{aligned}S^{[101]}(t) & = \frac{(1 + t) (1 − 3t − \sqrt{1 − 2t − 3t^{2}})}{2t(3t − 1)}, \\ S^{[010]}(t) & = \frac{1 − 2t − 3t^{2} − (1 − t)\sqrt{1 − 2t − 3t^{2}}}{2t^{2}(3t − 1)} . \end{aligned}

As pointed out by an anonymous referee, the previous functions can be rewritten as

\begin{aligned}S^{[101]}(t) & = \frac{(1 + t)(1 − tM(t))}{1 − 3t}, \\ S^{[010]}(t) & = \frac{(1 + tM(t))(1 − tM(t))}{1 − 3t}, \end{aligned}

where M(t) = \frac{1−t−\sqrt{1−2t−3t^{2}}}{2t^{2}} is the Motzkin numbers’ generating function. Such rewriting shows a relation among Motzkin numbers and powers of 3, which is not easy to state bijectively, to the best of our knowledge. However, for their generating functions, we have the following identity

\frac{1}{1 − 3t} = \frac{M(t)}{(1 − tM(t))^{2}} ,  (3)

and thus, by using the fundamental rule of Riordan arrays (2), we can express the functions S^{[101]}(t) and S^{[010]}(t) in terms of the Motzkin triangle and the sequence (1, 2, 2, 2, …)

\begin{aligned}S^{[101]}(t) & = \frac{(1 + t)M(t)}{1 − tM(t)} = \frac{(1 + tM(t))^{2}}{1 − tM(t)} = (1 + tM(t), tM(t)) ∗ \frac{1 + t}{1 − t}, \\ S^{[010]}(t) & = \frac{(1 + tM(t))M(t)}{1 − tM(t)} = (M(t), tM(t)) ∗ \frac{1 + t}{1 − t}, \end{aligned}

as illustrated in Table 16.

n/k 0 1 2 3 4 5 6 7
0 1
1 1 1
2 2 2 1
3 4 5 3 1
4 9 12 9 4 1
5 21 30 25 14 5 1
6 51 76 69 44 20 6 1
7 127 196 189 133 70 27 7 1

Table 16: The Motzkin triangle corresponding to the Riordan array (M(t), tM(t)) and to sequence \underline{A064189}. Multiplying the matrix by the column vector (1, 2, 2, 2, 2, …) we get the sequence S_{n}^{[010]} = (1, 3, 8, 22, 61, ⋯). Similarly, with matrix (1 + tM(t), tM(t)) we get the sequence S_{n}^{[101]} = (1, 3, 7, 18, 48, ⋯).

Identity (3) has a combinatorial interpretation in terms of compact-rooted directed animals or domino towers (see Ardila [1, Example 21, pp. 21–22] and the references therein); Motzkin triangle corresponds to sequence \underline{A064189} and has several combinatorial interpretations.

3.2 Enumeration with respect to the length

Corollary 13. Consider pattern 𝔭 = 1^{j+1}0^{j}. There is one word in 𝔏^{[𝔭]} for j = 0; on the other hand, there are 2^{m+1} − 1 words, where n = 2m + [[n is odd]], for j = 1.

Proof. When j = 0 the pattern to avoid is 𝔭 = 1, therefore instantiating the generating function we have L^{[𝔭]}(t) = 1, as required.

When j = 1 the pattern to avoid is 𝔭 = 110, therefore we instantiate and extract the n-th coefficient

L_{n}^{[𝔭]} = [t^{n}]\frac{2}{1 − 2t^{2}} + [t^{n−1}]\frac{2}{1 − 2t^{2}} − [t^{n}]\frac{1}{1 − t}

and proceed by cases on the parity of n. If n = 2m then the second term in the rhs disappears, otherwise if n = 2m + 1 the first term disappears; in both cases it is required to perform [u^{m}]\frac{2}{1−2u} = 2^{m+1} where u = t^{2}, as required.

It is possible to state a combinatorial interpretation using an argument similar to the one given in the proof of Corollary 10. Let n = 2m, therefore a word w needs to have m + j 1-bits, where j ∈ {0, …, m}; conversely, w needs to have n − m − j = m − j 0-bits. Fixing j in the given range, from the substring 0^{m−j} we select i ∈ {0, …, m − j} 0-bits to introduce i inversions, namely i occurrences of 10, applying the mapping 0 ↦ 10 simultaneously. This maneuver keeps the original 0-bits and introduces at most m−j 1-bits, so we pad with 1-bits on the right in order to have the required m + j 1-bits in the entire word; finally, selections can be done in

∑_{j=0}^{m} ∑_{i=0}^{m−j} \binom{m − j}{i} = ∑_{j=0}^{m} 2^{m−j} = 2^{m+1} − 1

ways, because padding can be done in only one way, completing the case for n even.

Let n = 2m + 1, therefore a word w needs to have m + 1 + j 1-bits, where j ∈ {0, …, m}; conversely, w needs to have n − m − 1 − j = m − j 0-bits. Fixing j in the given range, from the substring 0^{m−j} we select i ∈ {0, …, m − j} 0-bits to introduce i inversions as done in the even case, introducing at most m − j 1-bits, and padding as necessary to have m + 1 + j 1-bits, the total number of selections equals the one given for the even case, completing the case for n odd.

Corollary 14. Consider pattern 𝔭 = 0^{j+1}1^{j}. There is one word L_{n}^{[𝔭]} = 1 for each n ∈ ℕ in 𝔏^{[𝔭]} when j = 0; on the other hand, there are L_{n}^{[𝔭]} = F_{n+3} − 2^{m} words if n = 2m else L_{n}^{[𝔭]} = F_{n+3} − 2^{m+1} words if n = 2m + 1, for j = 1, where F_{n} is the n-th Fibonacci number.

Proof. When j = 0 the pattern to avoid is 𝔭 = 0, therefore suitable words of length n are of the form w = 1^{n}. Hence L_{n}^{[𝔭]} = 1 for each n ∈ ℕ.

When j = 1 the pattern to avoid is 𝔭 = 001, therefore we instantiate and extract the n-th coefficient

L_{n}^{[𝔭]} = 2[t^{n+1}]\frac{t}{1 − t − t^{2}} + [t^{n}]\frac{t}{1 − t − t^{2}} − [t^{n}]\frac{1}{1 − 2t^{2}} − 2[t^{n−1}]\frac{1}{1 − 2t^{2}}

in order to have L_{n}^{[𝔭]} = 2F_{n+1} + F_{n} − a_{n} = F_{n+3} − a_{n}, where a_{2m} = 2^{m} and a_{2m+1} = 2^{m+1}.

It is possible to state a combinatorial interpretation using an argument similar to the one given in the proof of Corollary 11. Let n = 2m, therefore a word w needs to have m + j 1-bits, where j ∈ {0, …, m}; conversely, w needs to have n − m − j = m − j 0-bits. Fixing j in the given range, from the substring 1^{m+j} we select i ∈ {0, …, m − j} 1-bits to introduce i inversions, namely i occurrences of 01, applying the mapping 1 ↦ 01 simultaneously. This maneuver keeps the original 1-bits and introduces at most m−j 0-bits; finally, selections can be done in ∑_{j=0}^{m} ∑_{i=0}^{m−j} \binom{m+j}{i} ways. In order to find a closed form for the double summation, we inspect the region of the Pascal triangle taken into account; marking with ∘ the involved binomials

n/j 0 1 … m − 1 m m + 1 … 2m − 1 2m …

0

⋮

m − 1

m ∘ ∘ … ∘  ∘
m + 1 ∘ ∘ … ∘
⋮  ⋮ ⋮ ...
2m − 1 ∘ ∘
2m ∘

2m + 1

⋮

and using the identity \binom{r+1}{k+1}−\binom{s}{k+1} = ∑_{i=s}^{r} \binom{i}{k} for rearranging the summation and identities 2^{n} = ∑_{i=0}^{n} \binom{n}{i} and F_{n+1} = ∑_{i=0}^{n} \binom{n−i}{i} to collect terms, we obtain

∑_{j=0}^{m} ∑_{i=0}^{m−j} \binom{m + j}{i} = ∑_{k=0}^{m} \binom{2m + 1 − k}{k + 1} − \binom{m}{k + 1} = F_{2m+3} − 2^{m} = L_{2m}^{[𝔭]},

completing the case for n even.

Let n = 2m + 1, therefore a word w needs to have m + 1 + j 1-bits, where j ∈ {0, …, m}; conversely, w needs to have n − m − 1 − j = m − j 0-bits. Fixing j in the given range, from the substring 1^{m+1+j} select i ∈ {0, …, m − j} 1-bits to introduce i inversions as done for the even case; in parallel, selections can be done in ∑_{j=0}^{m} ∑_{i=0}^{m−j} \binom{m+1+j}{i} ways. The involved region in the Pascal triangle has the same shape as the one shown for the even case translated one row to the bottom, so binomials lying on row m are excluded and binomials \binom{2m+1−k}{k} are included, for k ∈ {0, …, m}. Therefore we rewrite

∑_{j=0}^{m} ∑_{i=0}^{m−j} \binom{m + 1 + j}{i} = ∑_{k=0}^{m} \binom{2m + 2 − k}{k + 1} − \binom{m + 1}{k + 1} = F_{2m+4} − 2^{m+1} = L_{2m+1}^{[𝔭]},

completing the case for n odd.

Corollary 15. Consider pattern 𝔭 = 0^{j}1^{j} (or, equivalently, 𝔭 = 1^{j}0^{j}). There are 2^{n−1} words in 𝔏^{[𝔭]} if n is odd else 2^{n−1} + \frac{1}{2} \binom{2m}{m} where n = 2m, for j = 0; on the other hand, there are L_{n}^{[𝔭]} = m + 1 words, where n = 2m + [[n is odd]], for j = 1.

Proof. When j = 0 the pattern to avoid is 𝔭 = ε, namely the empty word, therefore instantiating the generating function we have

L^{[𝔭]}(t) = \frac{1}{2(1 − 2t)} + \frac{1}{2\sqrt{1 − 4t^{2}}}

we extract the coefficient L_{n}^{[𝔭]} = 2^{n−1} + \frac{a_{n}}{2} , where a_{2m+1} = 0 and a_{2m} = \binom{2m}{m}, as required. We observe that these values correspond to the summation ∑_{i=0}^{m} \binom{n}{i} for n = 2m, 2m+1, …, where the binomial coefficient computes the number of ways to choose i 0-bits among n bits, and this gives the combinatorial interpretation.

When j = 1 the pattern to avoid is 𝔭 = 01 (or, equivalently, 𝔭 = 10), therefore after instantiation

L^{[𝔭]}(t) = \frac{1}{4(1 − t)} + \frac{1}{2(1 − t)^{2}} + \frac{1}{4(1 + t)}

we extract the n-th coefficient L_{n}^{[𝔭]} = \frac{1}{4} + \frac{(−1)^{n}}{4} + \frac{n+1}{2}, so either n = 2m or n = 2m + 1 entails L_{n}^{[𝔭]} = m + 1, as required.

A combinatorial interpretation can be given as follows: if n = 2m then suitable words have structure 1^{m}1^{j}0^{m−j} for j ∈ {0, …, m}, and there are m + 1 of them. On the contrary, if n = 2m + 1 holds then suitable words have structure 1^{m+1}1^{j}0^{m−j} for j ∈ {0, …, m}, they are m + 1 in number again, as required.

As before, last two patterns 𝔭 = (01)^{j}0 and 𝔭 = (10)^{j}1 are harder to study and we avoid to report formulas about L^{[𝔭]}(t) functions because we have not a meaningful combinatorial interpretation: we only point out that these functions can be expressed in terms of M(t^{2}), where M(t) is the generating function of Motzkin numbers, similarly to the corresponding S^{[𝔭]}(t) functions.

4 Conclusions

As a final remark, we observe a structural properties of matrices R^{[𝔭]} against the studied families of patterns. As it is well-known (see, e.g., Shapiro, Getu, Woan, and Woodson [12]), Riordan arrays constitute a group with respect to the usual row-by-column product between matrices, and the product of two Riordan arrays D_{1} and D_{2} is defined as follows:

D_{1} ∗ D_{2} = (d_{1}(t), h_{1}(t)) ∗ (d_{2}(t), h_{2}(t)) = (d_{1}(t)d_{2}(h_{1}(t)), h_{2}(h_{1}(t))).

Moreover, the Riordan array I = (1, t) acts as the identity and the inverse of D = (d(t), h(t)) is the Riordan array:

D^{−1} = (\frac{1}{d(\overline{h}(t))}, \overline{h}(t))

where \overline{h}(t) is the compositional inverse of h(t).

The Pascal triangle and its inverse correspond to the Riordan arrays

P = (\frac{1}{1 − t}, \frac{t}{1 − t}) P^{−1} = (\frac{1}{1 + t}, \frac{t}{1 + t})

respectively. Therefore, for every Riordan array R^{[𝔭]} we can compute B^{[𝔭]} = P^{−1} ∗ R^{[𝔭]},, which is equivalent to saying that R^{[𝔭]} is the binomial transform of B^{[𝔭]}, or R^{[𝔭]} = P ∗ B^{[𝔭]}.

For the sake of clarity, consider the pattern family 𝔭 = 1^{j+1}0^{j}, so for j = 1 we have the minor

R^{[110]} = [ \begin{matrix}1 \\ 2 & 1 \\ 4 & 2 & 1 \\ 8 & 4 & 2 & 1 \\ 16 & 8 & 4 & 2 & 1 \\ 32 & 16 & 8 & 4 & 2 & 1 \\ 64 & 32 & 16 & 8 & 4 & 2 & 1 \\ 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 \\ 256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 \\ 512 & 256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 \\ 1024 & 512 & 256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 \end{matrix} ] ,

which corresponds to

B^{[110]} = [ \begin{matrix}1 \\ 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & −1 & 1 \\ 1 & 0 & 2 & −2 & 1 \\ 1 & 1 & −2 & 4 & −3 & 1 \\ 1 & 0 & 3 & −6 & 7 & −4 & 1 \\ 1 & 1 & −3 & 9 & −13 & 11 & −5 & 1 \\ 1 & 0 & 4 & −12 & 22 & −24 & 16 & −6 & 1 \\ 1 & 1 & −4 & 16 & −34 & 46 & −40 & 22 & −7 & 1 \\ 1 & 0 & 5 & −20 & 50 & −80 & 86 & −62 & 29 & −8 & 1 \end{matrix} ]

defined by functions d^{[110]}(t) = \frac{1}{1−t} and h^{[110]}(t) = \frac{t}{1+t}, which expands to h^{[110]}(t) = t − t^{2} + t^{3} − t^{4} + t^{5} − t^{6} + t^{7} − t^{8} + t^{9} − t^{10} + O (t^{11}).

On the other hand, the Riordan array R^{[11100]}, that is j = 2 in the family, is the binomial transform of

B^{[11100]} = [ \begin{matrix}1 \\ 1 & 1 \\ 3 & 1 & 1 \\ 5 & 3 & 1 & 1 \\ 15 & 7 & 3 & 1 & 1 \\ 31 & 16 & 9 & 3 & 1 & 1 \\ 87 & 43 & 17 & 11 & 3 & 1 & 1 \\ 201 & 101 & 55 & 18 & 13 & 3 & 1 & 1 \\ 543 & 271 & 119 & 67 & 19 & 15 & 3 & 1 & 1 \\ 1331 & 666 & 341 & 141 & 79 & 20 & 17 & 3 & 1 & 1 \\ 3533 & 1766 & 826 & 411 & 167 & 91 & 21 & 19 & 3 & 1 & 1 \end{matrix} ]

defined by functions d^{[11100]}(t) = \sqrt{\frac{1+t}{1−t−5t^{2}+t^{3}}} and h^{[11100]}(t) = ^{\frac{1+2t+t^{2}−\sqrt{(1−t−5t^{2}+t^{3})(1+t)}}{2(1+t)^{2}}},

which expands to h^{[11100]}(t) = t + 2t^{4} − t^{5} + 7t^{6} + 24t^{8} + 17t^{9} + 98t^{10} + O (t^{11}).

Riordan arrays B^{[𝔭]} can be completely defined by using the results of Theorem 4 and the product rule of the Riordan group. Doing so, for each pattern family studied in this work with j > 1, the Riordan array R^{[𝔭]} appears to be the binomial transform of another Riordan array B^{[𝔭]} with non-negative integer coefficients, although it is not easy to spot this property looking at the corresponding h functions because their series expansions might contain negative coefficients, as shown for matrices B^{[110]} and B^{[11100]}. This fact could be further investigated from an algebraic and combinatorial point of view and possibly yield interesting combinatorial interpretations also in the case j > 1.

5 Acknowledgements

We wish to thank the editor-in-chief and the referee(s) for the thoughtful and helpful comments and suggestions.

References

[1] F. Ardila. Algebraic and geometric methods in enumerative combinatorics, in M. Bóna, eds., Handbook of Enumerative Combinatorics, Chapman and Hall/CRC, 2015, pp. 3– 172.

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

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

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

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

[6] OEIS Foundation Inc., The On-line Encyclopedia of Integer Sequences,

    https://oeis.org/.

[7] A. Luzón, D. Merlini, M. A. Morón, and R. Sprugnoli, Complementary Riordan arrays, Discrete Appl. Math. 172 (2014), 75–87.

[8] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49 (1997), 301–320.

[9] 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.

[10] D. Merlini, R. Sprugnoli, and M. C. Verri, Combinatorial sums and implicit Riordan arrays, Discrete Math. 309 (2009), 475–486.

[11] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

[12] L. W. Shapiro, S. Getu, W.-J. Woan, and L. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[13] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 05A19. Keywords: Riordan array, language avoiding pattern, generating function.

(Concerned with sequences \underline{A000225}, \underline{A001477}, \underline{A001700}, \underline{A001792}, \underline{A008619}, \underline{A025566}, \underline{A027306}, \underline{A052551}, \underline{A064189}, \underline{A079284}, \underline{A225034}, and \underline{A261058}.)

Received January 20 2017; revised versions received January 24 2017; September 22 2017; November 7 2017; December 22 2017. Published in Journal of Integer Sequences, January 21 2018.

Return to Journal of Integer Sequences home page.