Abstract

A certain subset of the multiset permutations of length n satisfying two restrictions has been recently shown to be enumerated by the Catalan number C_n−1. These sequences have been termed Catalan words and are closely related to the 321-avoiding permutations. Here, we consider the problem of avoidance of patterns of type (1,2) wherein the second and third letters within an occurrence of a pattern are required to be adjacent. We derive in several cases functional equations satisfied by the generating functions enumerating members of the avoidance class which we solve by various methods. In one case, the generating function can be expressed in terms of a sum of reciprocals of Chebyshev polynomials, while in another, in terms of a previously studied q-Bell number. Among the sequences arising as enumerators of avoidance classes are the Motzkin and Fibonacci numbers. In several cases, it is more convenient to consider first the problem of avoidance on the subset of Catalan words whose members have no adjacent letters the same before moving to the larger problem on all Catalan words.

1. Introduction

By a Catalan word we will mean a word over the alphabet of non-negative integers satisfying

(i) for and

(ii) if with i minimal, then there exist such that

If then let denote the set of Catalan words of length n. For example, there are 5 members of namely,

Property (i) states that within members of W(n), there are no drops of size greater than one, while (ii) says that the left-most occurrence of each k>0 has k −1 somewhere to its left and somewhere to its right. It is well-known (see, e.g., ^{7, 12}) that W(n) is equinumerous with the set of Dyck paths of semilength n − 1.

Let Given define the reduction of denoted red(w), to be the word obtained by replacing all occurrences of the i-th smallest letter of w with i for each i. For example, red(7931379) = 3421234. The words v and w are said to be order-isomorphic if red(v) = red(w) and is denoted v ∼ w. By a pattern, we will mean a word that contains every letter in [j] for some j ≥ 1. A word π = π₁π₂ · · · π_n contains σ = σ₁σ₂ · · · σ_ℓ as a classical pattern if there exists a subsequence for 1 ≤ i₁ < i₂ < · · · <i_ℓ≤n such that and is said to avoid σ otherwise.

Similar terminology applies to vincular, or dashed, patterns, which resemble classical patterns except that some of the indices i_j must be consecutive (see, e.g., ²). If is a vector of positive integers, then a vincular pattern is said to be of type if the first t₁ letters within an occurrence are adjacent, the next t₂ letters are adjacent, and so on. A classical pattern is then one of type (1, 1, . . . , 1). Vincular patterns are often represented by inserting dashes between consecutive letters where there is no adjacency requirement. Here we will consider patterns x-yz of type (1,2), that is, subsequences of the form where i < j. For example, the word π = 135432414 contains two occurrences of the (1, 2) pattern 3-12 (as witnessed by the subsequences 524 and 514), but avoids the pattern 2-11 (note that the 4’s are not adjacent within the 544 subsequences).

In this paper, we consider the pattern avoidance problem on Catalan words and enumerate members of avoiding a single pattern of type (1,2). The analogous question has been considered earlier on permutations ^{2, 3}, compositions ⁴, and set partitions ⁶. Given and a pattern let denote the subset of whose members avoid and let To determine the we start by writing recurrences for refinements or slight variations of these numbers, which are obtained by considering suitable statistics on The recurrences may be expressed equivalently as functional equations satisfied by the corresponding generating functions, which we take steps to solve.

We now describe the general kinds of functional equations encountered in our study. Some had singularities at the particular value for which we sought a solution, while others did not. The first type of equation was of the form

and we are interested in finding , where is not defined at . In this case, we employ the kernel method ⁵ to ascertain , and hence the generating function for the numbers . For four of the patterns, the generating function satisfied functional equations that were special cases of the equation

where all functions are defined at In the case when (which occurred for two patterns), one is able to solve the general equation for F by iteration if x is sufficiently close to zero and y is restricted to a given bounded interval. For two other patterns, we encountered particular cases of the equation above when and To solve the equation in these cases, we iterate it for special values of y expressed in terms of quotients of linear combinations of Chebyshev polynomials, the properties of which bring about a significant simplification in the resulting series. This allows one to determine explicit expressions for and

The paper is divided as follows. In the next section, we introduce notation and provide some preliminary results relating the number of Catalan words in an avoidance class to the number of members in the class having no two adjacent letters the same. In the next three sections, we determine generating function formulas in several cases by solving various types of functional equations. Among our results, we find that is given by the (n−1)-st Motzkin number, which provides an apparently new combinatorial interpretation of this sequence. We also find that the generating function in the case 1-23 can be expressed in terms of q-Bell numbers, while in the cases 2-13 and 1-11, it can be expressed in terms of Chebyshev polynomials of the second kind. In the final section, we complete the enumeration of all (1,2) avoidance classes, up to one case. Our results are summarized in Table 1.

2. Preliminaries

In our study, it will be useful to consider the members of an avoidance class that contain a fixed number of zeros and/or that have no two adjacent letters the same. Here, we provide some algebraic results which will be needed in later sections. If and is a pattern, then let and denote, respectively, the subsets of and whose members contain exactly zeros. Let and

Members of an avoidance class having no adjacent letters the same will be termed as primitive. Let and denote the subsets of and consisting of the primitive members, with the obvious comparable meanings for and Let and

A run of a letter ℓ within a word w is a maximal subsequence of consecutive letters in w each of which is ℓ.

Definition 2.1. By the skeleton of a word w, denoted by skel(w), we will mean the word obtained from w by removing all but one of the letters from each of its runs.

Note that implies skel(w) is a (primitive) Catalan word. Furthermore, if with then for some and For example, if then Also, if τ is a pattern in which no two consecutive letters are equal, then w avoids τ if and only if skel(w) avoids τ.

Let and with similar meanings for and

The following formulas relate to (and to ).

Proposition 2.2. If then

(2.1)

and thus Comparable relations hold for and whenever no two consecutive letters are equal within the pattern

Proof. We count the members according to the number i of runs. Observe that deleting all letters within each run of π except for one leaves a member of for some Conversely, given any there are members of that have skeleton λ, upon adding n−i letters across the i runs of λ to generate members of Grouping together members of having the same skeleton of length i and summing over i gives (2.1). For the second statement, note that

The same relations are seen to hold if no two consecutive letters of τ are equal for then at most one letter out of each run within a Catalan word can appear as part of an occurrence of τ.

Let and where with similar meanings for and

Similar, though more complicated, relations can be given when the number of zeros in a Catalan word is prescribed.

Proposition 2.3. If n > i ≥ 2, then

(2.2)

with and for all In terms of generating functions, we have

(2.3)

Comparable relations hold for and whenever no two consecutive letters are equal within the pattern τ.

Proof. We first show the recurrence (2.2), its boundary values being clear. For each we claim that there are words such that To see this, note first that we must add zeros to u (in order to obtain a member of ), which can be achieved only by increasing the lengths of its zero runs since otherwise the skeleton would change. Thus, there are ways of adding zeros. We must also add non-zero letters to u by increasing the lengths of its non-zero runs, which can be done in ways. Putting together the prior two observations establishes the claim. Grouping together members of having skeletons of the same length and number of zeros then gives (2.2).

Multiplying (2.2) by and summing over all implies

(2.4)

Multiplying (2.4) by yⁱ and summing over i ≥ 2 yields

which gives (2.3).

3. The Case 1-22

Given and let denote the number of 1-22 avoiding Catalan words of length n having i ones in which the right-most 1 that is followed by at least one zero is the j-th 1 from the left. Let denote the subset of enumerated by Let and where and are as previously defined. Note that if and that if We have the following recurrence relation for the numbers

Lemma 3.1. The array may assume non-zero values only when n ≥ 3 and with and If then

(3.1)

with

(3.2)

Proof. The boundary conditions follow from the definitions; note that for otherwise there would be two adjacent ones, which is not allowed. To prove the recurrences, note first that there are members of in which the final run of zeros has length greater than one, for adding a zero directly after the j-th one from the left within a member of defines a bijection. On the other hand, there are members of where the final run of zeros consists of a single zero, with the letter (if it exists) following this zero greater than one, and where there are at least two zeros outside of the initial run of zeros. This follows from adding a single zero directly after the j-th one from the left within some member of which defines a bijection between this set and the subset of in question. In the case when it is also possible for the letter following the right-most zero to equal one. Then there are additional members of in this case, upon adding 01 directly after the j-th one from the left within some member of

Combining the cases in the previous paragraph accounts for all members of in which there are at least two zeros outside of zeros found within the initial run. To complete the proof, we then need to show that there are

members of containing only a single zero outside of the initial run of zeros when and such members of when In both cases, we may form possible words as follows. Suppose for some is written using positive instead of non-negative integers and is of the form where the 1 represents the j-th one from the left within w. Then is of the desired form. Allowing ℓ and w to vary gives all words in question in the case j = i and thus completes the proof of (3.2). If j < i, then it is also possible for a one to follow the right-most zero. Such words may be created by starting with for some expressed as as before, and letting This gives additional members of of the desired form when which completes the proof of (3.1).

Let

Given and let

Define the generating function by

Lemma 3.2. We have

(3.3)

Proof. Multiplying both sides of (3.1) by and summing over and adding times (3.2) gives

which for n ≥ 5 implies

(3.4)

Note that (3.4) is also seen to hold for n = 3 and n = 4 since and where we take if or and for all .

Multiplying (3.4) by and summing over gives

(3.5)

with Multiplying both sides of (3.5) by and summing over yields

Rearranging the last equation gives (3.3).

Let C_n and M_n denote the Catalan and Motzkin number sequences, respectively (see A000108 and A001006 in ¹¹). Recall that

and the relation Let By the definitions, we have

with since we must also include the Catalan word consisting of all zeros.

Theorem 3.3. We have

(3.6)

and hence a_n = M_n−1 for all n ≥ 1.

Proof. Taking v = 1/u in (3.3) implies

(3.7)

To solve (3.7), we use the kernel method ⁵ and let to cancel out the term.

This yields

where we have used (2.3).

Recall from [ ⁷, Theorem 2.8] that and, in particular, that Thus, we have

where It follows that

which completes the proof.

Remark: Theorem 3.3 provides an apparently new combinatorial interpretation for the Motzkin number sequence.

4. The Cases 2-12 and 3-12

We first recall some notation. If i is a positive integer and x is an indeterminate, then let with Define for n positive, with We will need the following preliminary result.

Theorem 4.1. Suppose F(x, y) satisfies the functional equation for −1 < x < 1 and y real:

(4.1)

where c(x, y) is continuous. Then we have

(4.2)

for all x sufficiently close to zero.

Proof. Note first that since c is continuous, we have for all positive integers j,

for some constant k < 1 whenever y lies on any given bounded interval and x is sufficiently close to zero. Thus, iteration of (4.1) leads to

(4.3)

for all such x and y. Note that both infinite series in (4.3) are seen to converge, upon comparison with a geometric series. Substituting y = 1 in (4.3), we have

and solving for F(x, 1) gives (4.2).

Note that substituting the expression for F(x, 1) from (4.2) back into (4.3) yields a formula for F(x, y).

If {2-12, 3-12}, then let for Note that may assume non-zero values only when and Define the generating functions for and

We now determine formulas for the generating functions in the cases 2-12 and 3-12.

4.1. The case 2-12. It will be more convenient to consider the primitive members of W_2-12(n). The numbers in this case are determined recursively as follows.

Lemma 4.2. We have

(4.4)

with for all n ≥ 1.

Proof. We show recurrence (4.4), the boundary conditions being clear. Let Note that members of containing k ones, where may be formed by adding single zeros at the beginning and following exactly m−1 of the ones within a member of , expressed using positive letters. Note that no occurrence of 2-12 is introduced by inserting zeros as described since a letter succeeding any added zero (except for the zero at the very beginning) is strictly larger than one. Conversely, removing the zeros from any member of containing exactly k ones, and decreasing each remaining letter by one, is seen to result in a member of . Thus, there are members of that contain k ones. Summing over k gives (4.4).

Multiplying (4.4) by summing over and noting we obtain

(4.5)

Letting a(x, y) = xy, b(x, y) = −xy, and c(x, y) = 1 in Theorem 4.1 gives

Furthermore, by the proof of Theorem 4.1, we have

which implies

where denotes the i-th elementary symmetric function. Comparing the coefficients of on both sides of the last equation leads to the following result.

Theorem 4.3. The generating function for the sequence is given by

(4.6)

Moreover, the generating function is given by

(4.7)

Replacing x by x/(1 − x) in (4.6) gives the generating function that counts all members of W_2-12(n) for n ≥ 1, by Proposition 2.2.

4.2. The case 3-12. Again, we consider the primitive members of the avoidance class in question. The numbers in this case are determined recursively as follows.

Lemma 4.4. If 2 ≤ m ≤ n − 1, then

(4.8)

with for all

Proof. To show (4.8), let where Then the first sum on the right side of (4.8) counts all members of starting 012 according to the number k of ones. To see this, note that the letter following any zero, other than the first, within such members of must be greater than one in order to avoid an occurrence of 3-12. Thus, these members of may be obtained by inserting single 0’s at the beginning and after any of the 1’s, except the first, within a member of expressed using positive letters, which can be done in ways.

To finish the proof, we must show that the double sum on the right-hand side of (4.8) counts all members of starting 010. To do so, it is enough to show for each 0 ≤ i ≤ m− 2, that there are

members of the form or where ρ starts with 2 if non-empty. Let us denote this subset by Suppose that is such that the word 1ρ contains exactly k ones. Note that By subtraction, has length or and contains zeros. Deleting the zeros from (and decreasing the remaining letters by one) results in a member Since these deleted zeros occurred singly within ρ, for each α produced, there are possible words that could have given rise to it (note that a zero cannot follow the initial 1 in ). Thus, there are members of such that contains k ones. Summing over all k gives the desired formula for and completes the proof.

Multiplying both sides of (4.8) by and summing over gives

(4.9)

with Multiplying (4.9) by and summing over yields

Let and in (4.1) above. Note that even though fails to be continuous for all and it is continuous for all on a given bounded interval if is sufficiently close to zero. Thus, the proof of Theorem 4.1 can be slightly modified to accommodate this case and gives the following result.

Theorem 4.5. The generating function for the sequence is given by

(4.10)

5. The Cases 1-23, 2-13, and 1-11

We will need the following additional definition for the combinatorial proofs in this section.

Definition 5.1. By an alternating binary string within we will mean a subsequence of the form for some and contained in no other subsequences of this form (i.e., it is maximal in this respect).

For example, if π = 01010210101032101 W(17), then the alternating binary strings are 1010, 101010 and 101. Note that zeros belonging to the initial run of zeros are not part of any binary string.

For τ {1-23, 2-13} and 1 ≤ m ≤ n, let and denote the number of members of either not ending in zero or ending in zero, respectively. For note that and may assume non-zero values only when or respectively. Let and denote the subsets of enumerated by and , respectively. Given let and for either pattern. Finally, let and

5.1. The case 1-23. We determine a formula for the generating function in the case 1-23. The numbers and may be determined recursively as follows in this case.

Lemma 5.2. If n ≥ 3 and 2 ≤ m ≤ n − 1, then

(5.1)

and

(5.2)

with and for all

Proof. The boundary conditions follow easily from the definitions. We first show recurrence (5.1). Suppose contains k (alternating) binary strings. First assume that Note that within a binary string of we must have (whence r is odd) in order to avoid an occurrence of 1-23. We remove the initial zero of α as well as all letters except for the first within each binary string. Then concatenate the remaining letters and decrease each letter by one to obtain Let s denote the number of ones that are removed from α in the process of obtaining Note that for each one that is removed from α, the zero directly following it is removed as well. Taking also into account the removal from α of the initial zero as well as the second letter (a zero) of each binary string, we have that . Thus, there are

letters removed in all. This implies For example, if

which contains 4 binary strings, then

Conversely, starting with first increase each letter by one and then insert single zeros following each 1 and at the beginning. Let denote the resulting word; note that and contains k binary strings. We then increase the lengths of the binary strings of by adding sequences of the form for some to them, with a total of strings of 10 to be added. Note that this may be achieved in ways and hence each gives rise to members of ending in a letter greater than one. Thus, the first sum on the right-hand side of (5.1) counts such members of according to the number k of binary strings; note that in this case, we have from the definitions.

Similar reasoning shows that there are members of containing binary strings and ending in a 1. In this case, one would first increase by one each letter of and then add single 0’s at the beginning and after each 1, except for the last, to obtain ending in 1. To one can then add a sequence of the form following any 0, except after the initial 0, as well as a sequence of the form following the terminal 1. As the total number of 10 or 01 strings to be added is m−k, this may be achieved in ways. Summing over all k gives the second sum on the right-hand side of (5.1) and completes the proof of it. Similar reasoning as in the first case above gives (5.2).

By the above recurrences, we obtain for m ≥ 2,

(5.3)

and

(5.4)

with and Thus,

(5.5)

Recall from [ ¹³, Eq. 24] the sequence defined by the recurrence

(5.6)

with Note that is a polynomial generalization of the Bell numbers that reduces to them when Comparison of (5.4) with (5.6) reveals

(5.7)

At the conclusion of this subsection, we provide a bijective proof of (5.7). We have the following explicit formula for the exponential generating function of the sequence

Lemma 5.3. We have

(5.8)

where Moreover,

(5.9)

Proof. The recurrence relation with can be written as

Let Then for Hence, for all n, which implies that Upon noting it follows that as required.

Remark: Formula (5.9) is seen to be a q-generalization of the Dobinski formula, reducing to it when q = 1.

Note that by the definitions, we have By Proposition 2.3, to determine the generating function for the sequence we only need to do so for

Theorem 5.4. If m ≥ 2, then

(5.10)

where

and

Proof. Let By (5.5) and (5.7), we have

with

Define Then the above recurrence can be written as

Assume that Then

which implies that or all Hence,

Since and we obtain

Hence, for all m ≥ 2,

which implies that

By (5.7) and (5.9), we have

Combinatorial proof of formula (5.7).

Let denote the set of all partitions of Let with its blocks satisfying Define the statistic w on by setting It is well known (see, e.g., ¹³) that

Thus, to show (5.7), we need to show for all and that the number of members of equals the number of partitions of having w statistic value r. To do so, suppose Since avoids 1-23, all (maximal) subsequences of consecutive non-zero letters of must be of the form for various i. Since ρ is primitive, contains exactly m zeros, and ends in a zero, it follows that there are exactly m−1 such subsequences. Furthermore, the first subsequence of the form must occur to the left of the first of the form if for otherwise the second defining property of a Catalan sequence would be violated.

Let be the subsequence of ρ of length m − 1 obtained by taking the first letter of each (maximal) string of non-zero letters. Let us represent sequentially as Then the word possesses the restricted growth property (see, e.g., ⁹) and thus represents a partition π of [m − 1]. Furthermore, equating expressions for the length of ρ implies and thus the second equality following from the definition of the w statistic. Hence, it is seen that the mapping defines a bijection from the set to the subset of whose members have w statistic value r, as desired.

5.2. The case 2-13. We determine a formula for the generating function. The numbers and are defined recursively in this case as follows.

Lemma 5.5. If n ≥ 3 and 2 ≤ m ≤ n − 1, then

(5.11)

and

(5.12)

with and for all

Proof. We apply similar reasoning as in the case of 1-23 above and show that the right-hand sides of (5.11) and (5.12) count the members of and , respectively, according to the number k of binary strings. Note that a binary string not ending a member of either or must have odd length (i.e., end in a 1) in order to avoid an occurrence of 2-13.

For (5.11), note first that members of having k binary strings may be obtained by adding a single zero to some expressed using positive letters, and then inserting m − 1 strings of 01 in positions directly following the ones of α, which can be achieved in ways. This implies that there are members of that have k binary strings and summing over k gives (5.11).

For (5.12), we show that there are members of having k binary strings. Such members may be obtained by adding a single zero to the beginning and end of some on positive letters and then adding sequences of the form for some j ≥ 0 directly following the ones and a sequence of the form following the terminal zero. Since the total number of 01 or 10 strings to be added is m − 2, this can be achieved in ways, as desired.

By (5.12) and (5.11), we have

and

with and

Then the above recurrence relations can be expressed as

(5.13)

(5.14)

Let denote the j-th Chebyshev polynomial of the second kind (see, e.g., ¹⁰) defined by the recurrence for with and Define by

It is possible to express the generating function in terms of Chebyshev polynomials as follows.

Lemma 5.6. We have

and, moreover,

Proof. By (5.13) and the recurrence for the Chebyshev polynomials, we have

Iterating this equation for i ≥ 0, we obtain

which implies

Letting y = 1 gives

which is equivalent to

By [ ⁷, Corollary 2.7], we have as required.

By (5.14) and the recurrence for the Chebyshev polynomials, we have

for all Iterating this equation for we obtain

which is equivalent to

Setting y = 1 and noting that and we find

which is equivalent to

Since and it follows that

Hence,

which is equivalent to

Since we have

In order to simplify the expression of we need the following lemma.

Lemma 5.7. We have

Proof. Let Define and Using the fact that we obtain that

By [ ⁷, Corollary 2.7], we have

which completes the proof.

Hence, by Lemma 5.7, one can write as

which is equivalent to

The last equality, combined with Lemma 5.6, gives the following result.

Theorem 5.8. We have

(5.15)

where is the m-th Chebyshev polynomial of the second kind.

We conclude this section with a couple of combinatorial results. We first provide a combinatorial proof of the relation from Lemma 5.6. Let

Proposition 5.9. If n ≥ 1, then

(5.16)

Proof. First note that a Catalan word avoids 2-13 if and only if it avoids 13 (i.e., ascents of size more than one). For if is a Catalan word and i is an index such that then there exists an index such that and thus would be an occurrence of 2-13. Let and Then for all by the previous observation, the first condition for Catalan words, and the primitiveness of Thus implies if n is even, upon observing If n is odd, then recording the sequence of differences for and replacing +1’s by up steps and −1’s by down steps defines a bijection between members of and Catalan paths of length n−1. This implies the odd case of (5.16) and completes the proof.

By a first quadrant path, we will mean one consisting of up (1,1) steps and down (1,-1) steps starting at the origin and never dipping below the x-axis. The height of a point will refer to the y-coordinate of the point. Points on the x-axis have height zero, including the initial point.

Definition 5.10. We will say that a first quadrant path P satisfies the height condition if for each i > 0 for which there is at least one point of P of height i, there is at least one point of height i – 1 to the right of the left-most point of height i.

By the i = 1 case, paths satisfying the height condition must have at least one return to the x-axis. Upon recording the sequence of differences, one sees that first quadrant paths of length n−1 satisfying the height condition are in bijection with members of with the number of returns to the x-axis corresponding to the number of zeros (excluding the initial zero).

First quadrant paths where horizontal (1,0) steps are also allowed are known as Motzkin left factors (see, e.g., [ ¹, p. 111]). The set of Motzkin left factors having n−1 steps is enumerated by the sequence L_n, which occurs as A005773 in ¹¹. Upon recording the sequence of differences, one obtains the following description of the members of W_2-13(n) in terms of lattice paths.

Proposition 5.11. Members of W_2-13(n) are in one-to-correspondence with Motzkin left factors of length n − 1 satisfying the height condition.

By Proposition 2.2, replacing x by in equation (5.15) gives the generating function for the sequence and hence for the sequence that counts Motzkin left factors of length n − 1 satisfying the height condition.

5.3. The case 1-11. For this pattern, we refine the enumerating sequence in a slightly different way. First observe that if a Catalan word avoids 1-11, then all runs of any letter have length one, except for possibly the first run, which can have length two. Let denote the number of members of in which all runs of the letter zero have length one. Note that since the initial run of zeros can have length one or two. The numbers are determined recursively as follows.

Lemma 5.12. If n ≥ 3 and 2 ≤ m ≤ n − 1, then

(5.17)

with for all

Proof. Let denote the subset of enumerated by where Let be the subset of all of whose runs of ones have length one as well and denote those members of having exactly k binary strings for We will show that

(5.18)

whence the first part of the sum on the right-hand side of (5.17) gives the cardinality of .

To do so, we show that there are members of that contain ones for whence (5.18) follows from summing over Observe first that members of containing ones may be formed from members of expressed using positive letters, by adding a zero at the beginning and then inserting in positions following the ones j strings of 01 together with m−j−1 single zeros. Note that a single zero can follow a (possibly empty) sequence of the form after a one, but that a binary string cannot contain more than one single zero. Given these restrictions, we see for each that there are members of containing ones which give rise to λ when the initial zero and all letters except the first within each binary string are removed, from which the claim follows.

Upon inserting an additional one within the initial run of ones, we see that equals and is thus given by the second part of the sum on the right-hand side of (5.17), which completes the proof.

Define Multiplying (5.17) by and summing over yields

with

Define Multiplying the last recurrence by and summing over yields

which is equivalent to

(5.19)

In order to solve this equation, we define

with

Lemma 5.13. For all m ≥ 0,

where

Proof. Let Then, by the definitions, we have and with and This implies or

with and By induction and the defining recurrence of the Chebyshev polynomials we obtain

Noting gives the desired result.

By (5.19) and the definition of , we have

Iteration of this last equation yields

which implies

Note that where which gives the following result.

Theorem 5.14. We have

(5.20)

where and is the m-th Chebyshev polynomial of the second kind.

Since for the generating function is given by . Hence, we can state the following result.

Theorem 5.15. We have

where and is the m-th Chebyshev polynomial of the second kind.

6. The Remaining Cases

We consider the remaining patterns of type (1,2). Our work is reduced by the following observations.

Observation 6.1. We have for all i.e., there is no restriction introduced by 2-31, by the first defining property of Catalan words. We have for all since only the word consisting of all zeros is possible, by the second property of Catalan words.

Let denote the Fibonacci sequence defined by if with

Observation 6.2. If {1-12, 1-32, 2-21, 3-21}, then it is seen that a Catalan word avoids if and only if it avoids the corresponding classical pattern of length three (obtained by removing the adjacency requirement concerning the second and third letters). Furthermore, in ⁸, it was shown that a_1-1-2(n) = F_n, a_1-3-2(n) = 2ⁿ⁻¹ −(n −1), a_2-2-1(n) = 2ⁿ⁻² if n ≥ 2 with a_2-2-1(1) = 1, and a_3-2-1(n) = F_2n−3.

Finally, the only pattern of type (1,2) that remains is 2-11. Note, in this case, that it is not useful to first consider the primitive members of the avoidance class due to the equal consecutive letters within the pattern. We have not been able to find a recurrence satisfied by the numbers nor have we determined a formula for the generating function Based on numerical evidence, the sequence does not seem to occur in OEIS ¹¹. We leave the question of determining a formula for as an open problem.

References