222021256002  222021256002

# Catalan words avoiding pairs of length three patterns

Jean-Luc Baril1  Carine Khalil 1  Vincent Vajnovszki1  LIB, Université de
Bourgogne Franche-Comté, Dijon, France

(2019-12-25; 2021-03-31; 2021-04-01)

###### Abstract

Catalan words are particular growth-restricted words counted by the eponymous
integer sequence. In this article we consider Catalan words avoiding a pair of
patterns of length $3$, pursuing the recent initiating work of the first and
last authors and of S. Kirgizov where (among other things) the enumeration of
Catalan words avoiding a patterns of length $3$ is completed. More precisely,
we explore systematically the structural properties of the sets of words under
consideration and give enumerating results by constructive bijections or
bivariate generating functions with respect to the length and descent number.
Some of the obtained enumerating sequences are known, and thus the
corresponding results establish new combinatorial interpretations for them.

###### keywords:

Catalan/pattern-avoiding words, enumeration, constructive bijections,
(bivariate) generating functions.

##  1 Introduction and notation

Catalan words are particular growth-restricted words and they represent still
another combinatorial class counted by the Catalan numbers, see for instance
[12, exercise 6.19.u, p. 222]. This paper contributes to a recent line of
research on classical pattern avoidance on words subject to some growth
restrictions (for instance, ascent sequences [2, 6], inversion sequences [5,
10, 14], restricted growth functions [4, 9]) by investigating connections
between sequences on the On-line Encyclopedia of Integer Sequences [11] and
Catalan words avoiding two patterns of length $3$.

Through this paper we consider words over the set of non-negative integers and
we denote such words by sequences (for instance $w_{1}w_{2}\dots w_{n}$) or by
italicized boldface letter (for instance $\boldsymbol{w}$ and
$\boldsymbol{u}$). The word $\boldsymbol{w}=w_{1}w_{2}\ldots w_{n}$ is called
a Catalan word if

$w_{1}=0\mbox{ and }0\leq w_{i}\leq w_{i-1}+1\mbox{ for }i=2,3,\ldots,n.$

Catalan words are in bijection with maybe the most celebrated combinatorial
class having the same enumerating sequence: Dyck paths111A Dyck path is a path
in the first quadrant of the plane which begins at the origin, ends at
$(2n,0)$, and consists of up steps $(1,1)$ and down steps $(1,-1)$.. Indeed,
in a length $2n$ Dyck path collecting for the up steps the ordinates of their
starting points we obtain a length $n$ Catalan word, and this construction is
a bijection. See Figure 1 where this bijection is depicted for an example. We
denote by $\mathcal{C}_{n}$ the set of length $n$ Catalan words and
$c_{n}=|\mathcal{C}_{n}|$ is the $n$th Catalan number $\frac{1}{n+1}{2n\choose
n}$.

A pattern is a word with the property that if $i$ occurs in it, then so does
$j$, for any $j$ with $0\leq j<i$. A pattern $\pi=\pi_{1}\pi_{2}\dots\pi_{k}$
is said to be contained in the word $\boldsymbol{w}=w_{1}w_{2}\ldots w_{n}$,
$k\leq n$, if there is a sub-word of $\boldsymbol{w}$,
$w_{i_{1}}w_{i_{2}}\dots w_{i_{k}}$, order-isomorphic with
$\pi_{1}\pi_{2}\dots\pi_{k}$. If $\boldsymbol{w}$ does not contain $\pi$, we
say that $\boldsymbol{w}$ avoids $\pi$, see for instance Kitaev’s seminal book
[7] on this topic.

For a pattern $\pi$, we denote by $\mathcal{C}_{n}(\pi)$ the set of length $n$
Catalan words avoiding $\pi$, and $c_{n}(\pi)=|\mathcal{C}_{n}(\pi)|$ is the
cardinality of $\mathcal{C}_{n}(\pi)$ and $\mathcal{C}(\pi)=\cup_{n\geq
0}\mathcal{C}_{n}(\pi)$. For example, $\mathcal{C}_{n}(101)$ is the set of
length $n$ Catalan words avoiding $101$, that is, the set of words
$\boldsymbol{w}$ in $\mathcal{C}_{n}$ such that there are no $i$, $j$ and $k$,
$1\leq i<j<k\leq n$, with $w_{i}=w_{k}>w_{j}$. So,
$\mathcal{C}_{4}(101)=\\{0000,0001,0010,0011,0012,0100,$
$0110,0111,0112,0120,0121,$ $0122,0123\\}$. Likewise, if $\pi$ is the set of
patterns $\\{\alpha,\beta,\dots\\}$, then $\mathcal{C}_{n}(\pi)$ and
$\mathcal{C}_{n}(\alpha,\beta,\dots)$ denote both the set of length $n$
Catalan words avoiding each pattern in $\pi$; and
$c_{n}(\pi)=c_{n}(\alpha,\beta,\dots)$ and
$\mathcal{C}(\pi)=\mathcal{C}(\alpha,\beta,\dots)$ have similar meaning as
above. A descent in a word $\boldsymbol{w}=w_{1}w_{2}\dots w_{n}$ is a
position $i$, $1\leq i\leq n-1$, with $w_{i}>w_{i+1}$. The (ordinary)
generating function of a set of pattern avoiding Catalan words
$\mathcal{C}(\pi)$ is the formal power series

$C_{\pi}(x)=\sum_{n\geq
0}c_{n}(\pi)x^{n}=\sum_{\boldsymbol{w}\in\mathcal{C}(\pi)}x^{|\boldsymbol{w}|},$

where $|\boldsymbol{w}|$ is the length of the word $\boldsymbol{w}$. In our
case of generating function approach for counting classes of pattern avoiding
Catalan words we consider the descent number as an additional statistic
obtaining ‘for free’ the bivariate generating function

$C_{\pi}(x,y)=\sum_{\boldsymbol{w}\in\mathcal{C}(\pi)}x^{|\boldsymbol{w}|}y^{\mathrm{des}(\boldsymbol{w})},$

where $\mathrm{des}(\boldsymbol{w})$ is the number of descents of
$\boldsymbol{w}$. With these notations, the coefficient of $x^{n}y^{k}$ in
$C_{\pi}(x,y)$ is the number of Catalan words of length $n$ avoiding $\pi$ and
having $k$ descents, and for a set $\mathcal{S}$ of Catalan words $S(x)$ and
$S(x,y)$ have similar meaning.

For a word $\boldsymbol{w}=w_{1}w_{2}\dots w_{n}$ and an integer $a$, we
denote by $(\boldsymbol{w}+a)$ the word obtained from $\boldsymbol{w}$ by
increasing by $a$ each of its entries, that is, the word
$(w_{1}+a)(w_{2}+a)\cdots(w_{n}+a)$. In our constructions we will often make
use of two particular families of Catalan words: those avoiding $10$ (i.e.,
with no descents) and we call these words weakly increasing (or w.i for short)
Catalan words; and those avoiding $00$ (and thus necessarily avoiding $10$)
and we call these words strictly increasing (or s.i for short) Catalan words.
It is easy to see that for each length $n\geq 1$ there are $2^{n-1}$ w.i.
Catalan words and one s.i. Catalan word.

The remaining of this paper is structured as follows. In the next section we
characterize pattern avoiding ascent sequences which are Catalan words,
establishing ties with some similar enumerative results for ascent sequences
in [2]. In Section 3 we consider classes of Catalan words avoiding both a
length two and a length three pattern. In the next sections we discuss Catalan
words avoiding two patterns of length three, in increasing order of their
complexity: obvious cases (Section 4), cases counted via recurrences (Section
5) and cases counted via generating functions (Section 6); these results are
summarized in Table 2. We conclude with some remarks and further research
directions.

$0$$0$$1$$2$$3$$3$$0$$1$$2$$1$$(a)$

$0$$0$$1$$2$$3$$3$$0$$1$$2$$1$$(b)$

Figure 1: (a) A Dyck path where each up step is labeled by the ordinate of its
starting point; and (b) its corresponding Catalan word $0012330121$.

##  2 Catalan words vs. ascent sequences

An ascent in a word $\boldsymbol{w}=w_{1}w_{2}\dots w_{n}$ is a position $i$,
$1\leq i\leq n-1$, with $w_{i}<w_{i+1}$, and $\mathrm{asc}(\boldsymbol{w})$
denotes the number of ascents in $\boldsymbol{w}$. Closely related to Catalan
words are ascent sequences introduced in [3] and defined as: the word
$\boldsymbol{w}=w_{1}w_{2}\ldots w_{n}$ is called an ascent sequence if

$w_{1}=0\mbox{ and }0\leq w_{i}\leq\mathrm{asc}(w_{1}w_{2}\dots
w_{i-1})+1\mbox{ for }i=2,3,\ldots,n,$

and $\mathcal{A}_{n}$ denotes the set of length $n$ ascent sequences, and
$\mathcal{A}=\cup_{n\geq 0}\mathcal{A}_{n}$. Similarly as for Catalan words,
if $\pi$ is a pattern, then $\mathcal{A}_{n}(\pi)$ is the set of length $n$
ascent sequences avoiding $\pi$, and $\mathcal{A}(\pi)=\cup_{n\geq
0}\mathcal{A}_{n}(\pi)$. Clearly, $\mathcal{C}_{n}=\mathcal{A}_{n}$ for $n\leq
3$, and $\mathcal{C}_{n}\subset\mathcal{A}_{n}$ for $n\geq 4$, and this
inclusion is strict, for instance
$0102\in\mathcal{A}_{4}\setminus\mathcal{C}_{4}$. It turns out that, for
particular patterns $\pi$, $\mathcal{A}_{n}(\pi)$ collapses to
$\mathcal{C}_{n}(\pi)$ for any $n$, and this behaviour where the pattern
$0102$ plays a critical role is discussed below.

######  Proposition 1.

If $\boldsymbol{w}\in\mathcal{A}\setminus\mathcal{C}$, then $\boldsymbol{w}$
contains the pattern $0102$.

###### Proof.

If $\boldsymbol{w}=w_{1}w_{2}\dots w_{n}$ is an ascent sequence which is not a
Catalan word, then there is an $i$ such that $w_{i}\geq w_{i-1}+2$, and let
$k$ be the smallest such $i$. It follows that $w_{i}\leq w_{i-1}+1$ for any
$i$, $2\leq i\leq k-1$, or equivalently $w_{1}w_{2}\dots w_{k-1}$ is a Catalan
word. Thus, if $w_{i}>0$, $2\leq i\leq k-1$, then each symbol less than
$w_{i}$ occurs in the prefix $w_{1}w_{2}\dots w_{i-1}$. We distinguish two
cases: (i) $w_{k-1}$ is not the maximal symbol of the prefix $w_{1}w_{2}\dots
w_{k-1}$, and (ii) otherwise.

(i) In this case there exist $i$ and $j$, $1\leq i<j<k-1$, such that
$w_{j}=w_{k-1}+1$ and $w_{i}=w_{k-1}$. It follows that
$w_{i}w_{j}w_{k-1}w_{k}$ is an occurrence of $0102$.

(ii) In this case the prefix $w_{1}w_{2}\dots w_{k-1}$ has a descent
(otherwise, since $\boldsymbol{w}$ is an ascent sequence, the maximal possible
value for $w_{k}$ is $w_{k-1}+1$), and let $j$ be such a descent, that is
$w_{j}>w_{j+1}$, $j+1<k-1$. As noticed above, the symbol $w_{j+1}$ already
occurs in $w_{1}w_{2}\dots w_{j-1}$, say in position $i$. Thus,
$w_{i}w_{j}w_{j+1}w_{k}$ is an occurrence of $0102$. ∎

######  Proposition 2.

For $n\geq 4$ and a pattern $\pi$ the followings are equivalent

  1. 1.

$\mathcal{A}_{n}(\pi)=\mathcal{C}_{n}(\pi)$,

  2. 2.

$0102$ contains the pattern $\pi$.

###### Proof.

‘2. $\Rightarrow$ 1.’ We proceed by contraposition and considering
$\mathcal{C}_{n}(\pi)\subseteq\mathcal{A}_{n}(\pi)$. If
$\boldsymbol{w}\in\mathcal{A}_{n}(\pi)\setminus\mathcal{C}_{n}(\pi)$, then, by
Proposition 1, $\boldsymbol{w}$ contains $0102$, and so $0102$ does not
contain $\pi$.

‘1. $\Rightarrow$ 2.’ Again by contraposition: if $0102$ does not contain
$\pi$, then at least one of the words $01023\cdots(n-2)$ or $01020^{n-4}$
belongs to $\mathcal{A}_{n}(\pi)$ and not to $\mathcal{C}_{n}(\pi)$, and so
$\mathcal{A}_{n}(\pi)\neq\mathcal{C}_{n}(\pi)$. ∎

Since the only patterns of length three of $0102$ are $001$, $010$, $012$ and
$102$, we have the following consequence of Proposition 2.

######  Corollary 1.

For $n\geq 4$ and a pattern $\pi$ of length three,
$\mathcal{A}_{n}(\pi)=\mathcal{C}_{n}(\pi)$ if and only if
$\pi\in\\{001,010,012,$ $102\\}$.

Pattern avoidance in ascent sequences was initiated in [6], and in [2] ascent
sequences avoiding a pair of patterns of length three are considered and exact
enumeration for several such pairs are given. In light of Corollary 1 it can
happen that if a pattern of the avoided pair is one of the four specified in
this corollary, then the resulting ascent sequences are Catalan words as well.
The pairs of avoided patterns for which ascent sequences and Catalan words
coincide, and for which the enumeration has already been considered in [2] are
highlighted in the summarizing Table 2. In order to keep the present article
self-contained we fully consider these cases, our proofs being alternative to
those in [2].

##  3 Avoiding a length two and a length three pattern

There are three patterns of length two, namely $00$, $01$ and $10$, and we
have:

######  Proposition 3.

The number of Catalan words avoiding a pattern of length two and a pattern
$\pi$ of length three is given by:

$c_{n}(00,\pi)=\left\\{\begin{array}[]{ll}0&{\rm if\ }\pi=012{\rm\ and\ }n\geq 3,\\\ 1&{\rm elsewhere;}\end{array}\right.$ | $c_{n}(01,\pi)=\left\\{\begin{array}[]{ll}0&{\rm if\ }\pi=000{\rm\ and\ }n\geq 3,\\\ 1&{\rm elsewhere;}\end{array}\right.$
---|---
$c_{n}(10,\pi)=\left\\{\begin{array}[]{ll}F_{n}&{\rm if\ }\pi=000,\\\ n&{\rm if\ }\pi\in\\{001,011,012\\},\\\ 2^{n-1}&{\rm elsewhere,}\end{array}\right.$ |

where $F_{n}$ is the $n$th Fibonacci number defined by $F_{0}=F_{1}=1$ and
$F_{n}=F_{n-1}+F_{n-2}$, $n\geq 2$.

###### Proof.

If $\boldsymbol{w}\in\mathcal{C}_{n}(00)$, then
$\boldsymbol{w}=012\cdots(n-1)$. Thus,
$\mathcal{C}_{n}(00,\pi)=\\{012\cdots(n-1)\\}$ except when $\pi=012$ and in
this case $\mathcal{C}_{n}(00,\pi)=\varnothing$ for $n\geq 3$, and the
counting relation for $\mathcal{C}_{n}(00,\pi)$ follows.
Similarly, if $\boldsymbol{w}\in\mathcal{C}_{n}(01)$, then
$\boldsymbol{w}=00\cdots 0$. Thus, $\mathcal{C}_{n}(01,\pi)=\\{000\cdots 0\\}$
except when $\pi=000$ and in this case $\mathcal{C}_{n}(01,\pi)=\varnothing$
for $n\geq 3$.

Finally, a Catalan word avoids $10$ if and only if it avoids $010$. It follows
that $c_{n}(10,\pi)=c_{n}(010,\pi)$, which falls in the case of avoidance of
two length 3 patterns and the corresponding proofs are given in the next
section, see also Table 2. ∎

##  4 Trivial cases

### Superfluous patterns

If the pattern $\tau$ contains the pattern $\sigma$, then clearly
$\mathcal{C}_{n}(\sigma,\tau)=\mathcal{C}_{n}(\sigma)$; but this phenomenon
can occur even when $\sigma$ and $\tau$ are not related by containment and in
this case, following [2], we say that $\tau$ is a superfluous pattern for
$\sigma$. For example, any word in $\mathcal{C}_{n}(012)$ is a binary word,
and thus any pattern with at least three different symbols is a superfluous
pattern for $012$. In Table 1 are listed all pairs of superfluous patterns of
length three. It is worth to mentioning that superfluousness is a transitive
relation, for instance $201$ is superfluous for $021$ which in turn is
superfluous for $011$. So, a pattern can be superfluous for several other
ones, for instance $\tau=201$ is superfluous for each of the patterns
$001,010,011,012,021,101,120$. Also it is easy to see that if $\tau$ is
superfluous for $\sigma$, then $\tau$ is larger lexicographically than
$\sigma$.

$\sigma$ | $000$ | $001$ | $010$ | $011$ | $012$ | $021$ | $101$ | $110$ | $120$
---|---|---|---|---|---|---|---|---|---
| $100$ | $101$ | $021$ | $021$ | $021$ | $201$ | $102$ | $210$ | $201$
|  | $102$ |  $10$0 | $101$ | $102$ | $210$ | $201$ |  | $210$
|  | $201$ | $101$ | $102$ | $120$ |  |  |  |
$\tau$ |  |  | $102$ | $110$ | $201$ |  |  |  |
|  |  | $110$ | $201$ | $210$ |  |  |  |
|  |  | $120$ | $210$ |  |  |  |  |
|  |  | $201$ |  |  |  |  |  |
|  |  | $210$ |  |  |  |  |  |
Table 1:  In each column, each pattern $\tau$ is superfluous for the pattern
$\sigma$.

### Ultimately constant sequences

It can happen that the number of Catalan words avoiding a pair of length $3$
patterns is constant for enough long words. The only two such cases are given
below.

######  Proposition 4.

$c_{n}(000,011)=\left\\{\begin{array}[]{ll}1&{\rm if\ }n=1,\\\ 2&{\rm if\
}n=2,\\\ 3&{\rm if\ }n\geq 3;\end{array}\right.$ and
$c_{n}(000,012)=\left\\{\begin{array}[]{ll}1&{\rm if\ }n=1,\\\ 2&{\rm if\
}n=2,\\\ 3&{\rm if\ }n=3{\rm\ or\ }n=4,\\\ 0&{\rm if\ }n\geq
5.\end{array}\right.$

###### Proof.

If $n\geq 3$, then
$\mathcal{C}_{n}(000,011)=\\{0\boldsymbol{x},\boldsymbol{x}0,\boldsymbol{x}(n-1)\\}$
where $\boldsymbol{x}$ is the word $01\cdots(n-2)$, and the first point
follows.
If a Catalan word avoids $012$, then it is a binary word. In addition if its
length is larger than $4$ it necessarily contains three identical entries, and
so $\mathcal{C}_{n}(000,012)=\varnothing$ for $n\geq 5$. Considering the
initial values of $c_{n}(000,012)$ the second point follows. ∎

### Counting sequence $n$

######  Proposition 5.

If $\pi$ is one of the pairs of patterns $\\{001,010\\}$, $\\{001,011\\}$,
$\\{001,012\\}$, $\\{010,011\\}$, $\\{010,012\\}$ or $\\{011,012\\}$, then
$c_{n}(\pi)=n$.

###### Proof.

The proof is based on the easy to understand description given below for the
corresponding sets of Catalan words:

$\begin{array}[]{c|c||c|c}\pi&\mathcal{C}_{n}(\pi)&\pi&\mathcal{C}_{n}(\pi)\\\
\hline\cr\\{001,010\\}&\\{012\cdots jj\cdots j\,:\,0\leq j\leq
n-1\\}&\\{010,011\\}&\\{0^{j}12\cdots(n-j)\,:\,1\leq j\leq n\\}\\\
\\{001,011\\}&\\{012\cdots j0\cdots 0\,:\,0\leq j\leq
n-1\\}&\\{010,012\\}&\\{0^{j+1}1^{n-j-1}\,:\,0\leq j\leq n-1\\}\\\
\\{001,012\\}&\\{01^{j}0^{n-j-1}\,:\,0\leq j\leq
n-1\\}&\\{011,012\\}&\\{0^{n}\\}\cup\\{0^{j}10^{n-j-1}\,:\,1\leq j\leq
n-1\\}\\\ \end{array}$ ∎

##  5 Counting via recurrence

### Counting sequence $2(n-1)$

######  Proposition 6.

If $\pi=\\{011,100\\}$ or $\pi=\\{011,120\\}$, then $c_{n}(\pi)=2(n-1)$ for
$n\geq 2$ (Sequence $\href https://oeis.org/A005843 $ in [11]).

###### Proof.

If $\pi=\\{011,100\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 2$,
then either

  1. $-$

$\boldsymbol{w}=0^{k}\boldsymbol{u}$, $0\leq k\leq n-1$, with $\boldsymbol{u}$
a s.i. Catalan word (of length at least one), or

  2. $-$

$\boldsymbol{w}=0^{k}\boldsymbol{u}0$, $0\leq k\leq n-3$, with
$\boldsymbol{u}$ a s.i. Catalan word (of length at least two).

In the first case there are $n$ possibilities for $\boldsymbol{w}$ and $n-2$
possibilities in the second case, and the result holds. If $\pi=\\{011,120\\}$
and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 2$, then either

  1. $-$

$\boldsymbol{w}=0^{k}\boldsymbol{u}$, $0\leq k\leq n-1$, with $\boldsymbol{u}$
a s.i. Catalan word, or

  2. $-$

$\boldsymbol{w}=0^{k}10^{n-k-1}$, $1\leq k\leq n-2$,

and as previously the result holds. ∎

### Sequences involving $2^{n}$

######  Proposition 7.

If $\pi=\\{000,101\\}$, then $c_{n}(\pi)=2^{n-1}$ for $n\geq 1$ ($\href
https://oeis.org/A000079 $ in [11]).

###### Proof.

If a Catalan word avoids $101$, then it is unimodal (that is, it can be
written not necessarily in a unique way as $\boldsymbol{uv}$ with
$\boldsymbol{u}$ a weakly decreasing and $\boldsymbol{v}$ weakly decreasing
word). In addition, if the word avoids $000$, then its maximal value occurs at
most twice, and when it occurs twice this happens in consecutive positions.
We denote by $\mathcal{D}_{n}$ the subset of words in $\mathcal{C}_{n}(\pi)$
where the maximal entry occurs once and by $\mathcal{E}_{n}$ that where it
occurs twice, $d_{n}=|\mathcal{D}_{n}|$, $e_{n}=|\mathcal{E}_{n}|$, and
$c_{n}(\pi)=d_{n}+e_{n}$. Any word $\boldsymbol{w}=w_{1}\cdots mm\cdots
w_{n-1}\in\mathcal{E}_{n-1}$ with its maximal value $m$ occurring twice can be
extended into a word in $\mathcal{D}_{n}$ by one of the transformations:

  * $\boldsymbol{w}\mapsto w_{1}\cdots m(m+1)m\cdots w_{n-1}$, and

  * $\boldsymbol{w}\mapsto w_{1}\cdots mm(m+1)\cdots w_{n-1}$,

and any word $\boldsymbol{w}=w_{1}\cdots m\cdots w_{n-1}\in\mathcal{D}_{n-1}$
with its maximal value $m$ occurring once can be extended into a word in
$\mathcal{D}_{n}$ by:

  * $\boldsymbol{w}\mapsto w_{1}\cdots m(m+1)\cdots w_{n-1}$.

Conversely, any word in $\mathcal{D}_{n}$, $n\geq 2$, can uniquely be obtained
from a word in $\mathcal{D}_{n-1}$ or in $\mathcal{E}_{n-1}$ by reversing one
of the transformations above, so

$d_{n}=2\cdot e_{n-1}+d_{n-1},$

for $n\geq 2$.
Reasoning in a similar way we have

$e_{n}=2\cdot e_{n-2}+d_{n-2},$

Thus, for $n\geq 3$, $e_{n}=d_{n-1}$, and finally

$c_{n}(\pi)=d_{n}+e_{n}=2\cdot(d_{n-1}+e_{n-1})=2\cdot c_{n-1}(\pi),$

and with the initial conditions $c_{1}(\pi)=1$ and $c_{2}(\pi)=2$, the result
follows. ∎

######  Proposition 8.

If $\pi=\\{101,210\\}$ or $\pi=\\{102,120\\}$, then $c_{n}(\pi)=(n-1)\cdot
2^{n-2}+1$ for $n\geq 2$ ($\href https://oeis.org/A005183 $ in [11]).

###### Proof.

If $\pi=\\{101,210\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$,
then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)0^{n-k-1}$ with $\boldsymbol{u}$ a w.i.
Catalan word of length $k$, $1\leq k\leq n-2$.

The number of words in each of the first two cases is $c_{n-1}(\pi)$. The
number of length $k$ w.i. Catalan words is $2^{k-1}$, so the number of words
in the last case is

$\sum^{n-2}_{k=1}2^{k-1}=\sum^{n-3}_{k=0}2^{k}=2^{n-2}-1.$

Thus, $c_{n}(\pi)=2c_{n-1}(\pi)+2^{n-2}-1$, and after calculation the result
holds.

If $\pi=\\{102,120\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$,
then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=01\boldsymbol{u}$ with $\boldsymbol{u}$ a length $(n-2)$
binary word other than $11\cdots 1$.

The number of words in each of the first two cases is $c_{n-1}(\pi)$, and the
number of words in the last case is $2^{n-2}-1$. So
$c_{n}(\pi)=2c_{n-1}(\pi)+2^{n-2}-1$, and again the result holds. ∎

######  Proposition 9.

If $\pi$ is one of the pairs of patterns $\\{021,100\\}$, $\\{021,101\\}$,
$\\{101,110\\}$ or $\\{101,120\\}$, then $c_{n}(\pi)=2^{n}-n$ for $n\geq 0$
($\href https://oeis.org/A000325$ in [11]).

###### Proof.

If $\pi=\\{021,100\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 4$,
then either

  1. $-$

$\boldsymbol{w}$ is a w.i. Catalan word, or

  2. $-$

$\boldsymbol{w}=\boldsymbol{u}0$ with $\boldsymbol{u}$ a w.i. Catalan word of
length $(n-1)$ other than $00\cdots 0$, or

  3. $-$

$\boldsymbol{w}=0\boldsymbol{v}0(\boldsymbol{u}+1)$ where $\boldsymbol{v}$ is
w.i. binary word ending by $1$ and $\boldsymbol{u}$ is a w.i. Catalan word of
length $k$, $1\leq k\leq n-3$.

In the first case the number of words $\boldsymbol{w}$ is $2^{n-1}$ and in the
second case the number of words $\boldsymbol{w}$ is $2^{n-2}-1$. In last case
the number of words $\boldsymbol{w}$ is

$\sum^{n-3}_{k=1}(n-k-2)\cdot 2^{k-1}=2^{n-2}-(n-1).$

Combining these cases and considering the initial values of $c_{n}(\pi)$ the
result holds.

If $\pi=\\{021,101\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 2$,
then either

  1. $-$

$\boldsymbol{w}=\boldsymbol{u}0$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0^{n-k}(\boldsymbol{u}+1)$ with $\boldsymbol{u}$ a w.i.
Catalan word of length $k$, $1\leq k\leq n-1$.

The number of words in the first case is $c_{n-1}(\pi)$ and the number of
words in the second case is $\sum_{k=1}^{n-1}2^{k-1}=2^{n-1}-1$. So
$c_{n}(\pi)=c_{n-1}(\pi)+2^{n-1}-1$ and after calculation the result follows.

If $\pi=\\{101,110\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$,
then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=\boldsymbol{u}0^{n-k}$ with $\boldsymbol{u}$ a s.i. Catalan
word of length $k$, $2\leq k\leq n-1$.

The number of words $\boldsymbol{w}$ in each of the first two cases is
$c_{n-1}(\pi)$. For the last case, for each $k$ there is exactly one word
$\boldsymbol{w}$, so their number is $(n-2)$ in this case. So
$c_{n}(\pi)=2c_{n-1}(\pi)+n-2$ and after calculation the result holds.

If $\pi=\\{101,120\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$,
then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=01^{k}0^{n-k-1}$, $1\leq k\leq n-2$.

So, again $c_{n}(\pi)=2c_{n-1}(\pi)+n-2$. ∎

######  Proposition 10.

If $\pi=\\{021,120\\}$, then $c_{n}(\pi)=(n+2)\cdot 2^{n-3}$ for $n\geq 3$
($\href https://oeis.org/A045623$ in [11]).

###### Proof.

If $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 4$, then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}0$ with $\boldsymbol{u}$ a length $(n-2)$
binary word, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with $\boldsymbol{u}$ a length $(n-1)$
w.i. Catalan word, or

  3. $-$

$\boldsymbol{w}=0\boldsymbol{u}0(\boldsymbol{v}+1)$ with $\boldsymbol{u}$ a
binary word and $\boldsymbol{v}$ w.i. Catalan word.

The number of words in each of the first two cases is $2^{n-2}$ and the number
of words in the last case is

$\sum_{k=1}^{n-2}2^{n-k-2}2^{k-1}=(n-2)2^{n-3},$

and so $c_{n}(\pi)=2^{n-1}+(n-2)2^{n-3}$, which gives the desired result. ∎

If a Catalan word avoids both $102$ and $110$, then it has at most one
descent. In the second part of the proof of the next proposition we need the
following technical lemma which gives the number of Catalan words in
$\mathcal{C}_{n}(102,110)$ with one descent and avoiding the pattern $00$
before the descent (note that in this case avoiding $00$ is equivalent to
avoiding equal consecutive entries). The set of these words is empty for
$n\leq 2$, it is the single word set $\\{010\\}$ for $n=3$, and
$\\{0100,0101,0120,0121\\}$ for $n=4$.

######  Lemma 1.

Let $\mathcal{D}_{n}$ be the set of words in $\mathcal{C}_{n}(102,110)$ having
one descent and avoiding $00$ before the descent. Then
$|\mathcal{D}_{n}|=\frac{n}{6}(n-1)(n-2)$.

###### Proof.

A word belongs to $\mathcal{D}_{n}$, $n\geq 3$, if and only if it can be
written as

$012\ldots(k-1)a(\boldsymbol{u}+a),$

with $2\leq k\leq n-1$ ($k$ is the position of the unique descent in the
word), $a\in\\{0,1,\ldots k-2\\}$, and $\boldsymbol{u}$ is a length $(n-k-1)$
w.i. Catalan word over $\\{0,1\\}$. For each choice of $k$, there are $k-1$
choices for $a$, and for each choice for $a$ there are $n-k$ choices for
$\boldsymbol{u}$. It follows that

$|\mathcal{D}_{n}|=\sum_{k=2}^{n-1}(k-1)\cdot(n-k),$

and after calculation the statement holds. ∎

######  Proposition 11.

If $\pi=\\{021,102\\}$ or $\pi=\\{102,110\\}$, then $c_{n}(\pi)=3\cdot
2^{n-1}-\frac{1}{2}(n+1)(n+2)+n$ for $n\geq 1$ ($\href
https://oeis.org/A116702$ in [11]).

###### Proof.

If $\pi=\\{021,102\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$,
then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with $\boldsymbol{u}$ a length $(n-1)$ binary
word, or

  2. $-$

$\boldsymbol{w}=0\cdots 0(\boldsymbol{u}+1)0\cdots 0$ with $\boldsymbol{u}$ a
length $k$, $2\leq k\leq n-1$, w.i. Catalan word other than $00\cdots 0$ and
$\boldsymbol{w}$ beginning by at least one $0$.

The number of words in the first case is $2^{n-1}$ and the number of those in
the second case is

$\sum_{k=2}^{n-1}(2^{k-1}-1)\cdot(n-k)=2\cdot
2^{n-1}-\frac{1}{2}(n+1)(n+2)+n,$

and combining the two cases the result holds.

If $\pi=\\{102,110\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either

  1. $-$

$\boldsymbol{w}$ is a w.i. Catalan word, the number of such words is
$2^{n-1}$, or

  2. $-$

$\boldsymbol{w}\in\mathcal{D}_{n}$, with $\mathcal{D}_{n}$ defined in Lemma 1,
or

  3. $-$

$\boldsymbol{w}=\boldsymbol{u}(\boldsymbol{v}+m)$, where $\boldsymbol{u}$ is a
w.i. Catalan word of length $k$, $1\leq k\leq n-3$, $m$ is the maximal
(rightmost) entry of $\boldsymbol{u}$, and $\boldsymbol{v}$ is a word
belonging to $\mathcal{D}_{n-k}$.

Indeed, the first case corresponds to words with no descents, the second one
to those with a descent and no occurrences of $00$ before the descent, and the
third one to those with both descent and occurrences of $00$ before the
descent (the rightmost such occurrence is in positions $k$ and $k+1$). By
Lemma 1, the number of words in the third case is

$\sum_{k=1}^{n-3}2^{k-1}\cdot(n-k)\cdot\left(\frac{1}{6}(n-k)^{2}-\frac{1}{2}(n-k)+\frac{1}{3}\right)=2^{n}-\frac{1}{6}(n+1)(n^{2}-n+6).$

Finally, combining the three previous cases the desired result holds. ∎

### Sequences involving binomial coefficients

In this part we use the notation

$ab\cdots c\underset{\underset{i}{\uparrow}}{d}e\cdots f$

to denote that the entry $d$ is in position $i$ in the word $ab\cdots
cde\cdots f$.

######  Proposition 12.

If $\pi=\\{001,210\\}$, then $c_{n}(\pi)={n\choose 3}+n$ for $n\geq 3$ ($\href
https://oeis.org/A000125$ in [11]).

###### Proof.

If $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then it has at most one descent.

If $\boldsymbol{w}$ has no descents, then it has the form
$\boldsymbol{w}=01\cdots(m-1)m\cdots m$ and there are $n$ such words.

If $\boldsymbol{w}$ has one descent, then it has the form
$\boldsymbol{w}=01\cdots(m-1)m\cdots mk\cdots k$ with $0\leq k<m<n-1$. It
follows that there is a bijection between the family of $3$-element subsets of
$\\{0,1,\dots,n-1\\}$ and the words in $\mathcal{C}_{n}(\pi)$ with one
descent:

$\\{k,m,\ell\\}\mapsto
0123\cdots(m-1)m\cdots\underset{\underset{\ell}{\uparrow}}{m}k\cdots k.$

Combining the two cases we have $c_{n}(\pi)={n\choose 3}+n$. ∎

######  Proposition 13.

If $\pi$ is one of the pairs of patterns $\\{001,021\\}$, $\\{001,110\\}$,
$\\{001,120\\}$, $\\{012,100\\}$, $\\{012,101\\}$ or $\\{012,110\\}$, then
$c_{n}(\pi)={n\choose 2}+1$ for $n\geq 2$ ($\href https://oeis.org/A000124$ in
[11]).

###### Proof.

In any of the six cases for $\pi$, the set $\mathcal{C}_{n}(\pi)$ is in
bijection with the family $S$ of subsets of $\\{2,\dots,n\\}$ with at most two
elements. We give below explicit definitions for such bijections, where the
empty set is mapped to $0\cdots 0\in\mathcal{C}_{n}(\pi)$ by each of them.

If $\pi=\\{001,021\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either $\boldsymbol{w}=00\cdots 0$ or for some $m\geq 1$,
$\boldsymbol{w}=0123\cdots(m-1)m^{s}$ with $s\geq 1$ or
$\boldsymbol{w}=0123\cdots(m-1)m^{s}0^{t}$ with $s\geq 1$, $t\geq 1$, and the
desired bijection $S\rightarrow\mathcal{C}_{n}(001,021)$ is

  * $\\{k\\}\mapsto 0123\cdots(m-1)\underset{\underset{k=m+1}{\uparrow}}{m}\cdots m$;

  * $\\{k,j\\}\mapsto 0123\cdots(m-1)\underset{\underset{k=m+1}{\uparrow}}{m}\cdots m\underset{\underset{j}{\uparrow}}{0}\cdots 0$.

If $\pi=\\{001,110\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either $\boldsymbol{w}=00\cdots 0$ or $\boldsymbol{w}=0123\cdots(m-1)m\cdots
m$ with $m$ the maximal entry of $\boldsymbol{w}$, or
$\boldsymbol{w}=0123\cdots(m-1)m\ell\cdots\ell$ with $\ell<m$, and the desired
bijection $S\rightarrow\mathcal{C}_{n}(001,110)$ is

  * $\\{k\\}\mapsto 0123\cdots(m-1)\underset{\underset{k=m+1}{\uparrow}}{m}\cdots m$;

  * $\\{k,j\\}\mapsto 0123\cdots(j-2)(k-2)\cdots(k-2)$.

If $\pi=\\{001,120\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either $\boldsymbol{w}=00\cdots 0$, or for some $m\geq 1$,
$\boldsymbol{w}=0123\cdots(m-1)m^{s}$ with $s\geq 1$ or
$\boldsymbol{w}=0123\cdots(m-1)m^{s}(m-1)^{t}$ with $s,t\geq 1$, and the
desired bijection $S\rightarrow\mathcal{C}_{n}(001,120)$ is

  * $\\{k\\}\mapsto 0123\cdots(m-1)\underset{\underset{k=m+1}{\uparrow}}{m}\cdots m$;

  * $\\{k,j\\}\mapsto 0123\cdots(m-1)\underset{\underset{k=m+1}{\uparrow}}{m}\cdots m\underset{\underset{j}{\uparrow}}{(m-1)}\cdots(m-1)$.

For the next three cases we need the following observation: a Catalan word
avoids $012$ if and only if it is a binary word (over $\\{0,1\\}$) beginning
by a $0$.

If $\pi=\\{012,100\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either $\boldsymbol{w}=0^{s}1^{t}$ with $s\geq 1$, $t\geq 0$ or
$\boldsymbol{w}=0^{s}1^{t}01^{r}$ with $s,t\geq 1$, $r\geq 0$, and the desired
bijection $S\rightarrow\mathcal{C}_{n}(012,100)$ is

  * $\\{k\\}\mapsto 0\cdots 0\underset{\underset{k}{\uparrow}}{1}\cdots 1$;

  * $\\{k,j\\}\mapsto 0\cdots 0\underset{\underset{k}{\uparrow}}{1}\cdots 1\underset{\underset{j}{\uparrow}}{0}1\cdots 1$.

If $\pi=\\{012,101\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either $\boldsymbol{w}=0^{s}1^{t}$ with $s\geq 1$, $t\geq 0$ or
$\boldsymbol{w}=0^{s}1^{t}0^{r}$ with $s,t\geq 1$, $r\geq 1$, and the desired
bijection $S\rightarrow\mathcal{C}_{n}(012,101)$ is

  * $\\{k\\}\mapsto 0\cdots 0\underset{\underset{k}{\uparrow}}{1}\cdots 1$;

  * $\\{k,j\\}\mapsto 0\cdots 0\underset{\underset{k}{\uparrow}}{1}\cdots 1\underset{\underset{j}{\uparrow}}{0}\cdots 0$.

If $\pi=\\{012,110\\}$ and $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, then
either $\boldsymbol{w}=0^{s}1^{t}$ with $s\geq 1$, $t\geq 0$ or
$\boldsymbol{w}=0^{s}10^{t}1^{r}$ with $s,t\geq 1$, $r\geq 0$, and the desired
bijection $S\rightarrow\mathcal{C}_{n}(012,110)$ is

  * $\\{k\\}\mapsto 0\cdots 0\underset{\underset{k}{\uparrow}}{1}\cdots 1$;

  * $\\{k,j\\}\mapsto 0\cdots 0\underset{\underset{k}{\uparrow}}{1}0\cdots\underset{\underset{j}{\uparrow}}{0}1\cdots 1$.

∎

### Sequences involving Fibonacci(-like) numbers

As in Proposition 3, we consider the sequence of Fibonacci numbers
$(F_{n})_{n\geq 0}$ defined as $F_{0}=1$, $F_{1}=1$ and
$F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 2$.

######  Proposition 14.

If $\pi=\\{000,001\\}$ or $\pi=\\{000,010\\}$, then $c_{n}(\pi)=F_{n}$ for
$n\geq 0$ ($\href https://oeis.org/A00045$ in [11]).

###### Proof.

For $\pi=\\{000,001\\}$ the proof is up to a certain point similar to that of
Proposition 7. A word belonging to $\mathcal{C}_{n}(\pi)$ is unimodal and its
maximal entry occurs once or twice in consecutive positions. Let
$\mathcal{D}_{n}$ denote the subset of words in $\mathcal{C}_{n}(\pi)$ where
the maximal entry occurs once and $\mathcal{E}_{n}$ denote that where it
occurs twice. If $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$ has its maximal entry
$m$, then the insertion of $(m+1)$ after the leftmost occurrence of $m$ in
$\boldsymbol{w}$ produces a word in $\mathcal{D}_{n+1}$, and the insertion of
$(m+1)(m+1)$ produces a word in $\mathcal{E}_{n+2}$. It is easy to see that
these transformations induce a bijection between $\mathcal{C}_{n}(\pi)$ and
$\mathcal{D}_{n+1}$, and between $\mathcal{C}_{n}(\pi)$ and
$\mathcal{E}_{n+2}$, and thus between
$\mathcal{C}_{n-2}(\pi)\cup\mathcal{C}_{n-1}(\pi)$ and $\mathcal{C}_{n}(\pi)$.
It follows that $c_{n}(\pi)$ satisfies a Fibonacci-like recurrence, and by
considering the initial values for $c_{n}(\pi)$ the result holds.

For $\pi=\\{000,010\\}$, a word $\boldsymbol{w}\in{C_{n}(\pi)}$ is
characterized by: $\boldsymbol{w}$ is w.i. and $\boldsymbol{w}$ does not have
three consecutive equal entries. So $\boldsymbol{w}$ can be represented by the
binary word $b_{1}b_{2}\dots b_{n-1}$ with no two consecutive $1$s where
$b_{i}=1$ iff $w_{i}=w_{i-1}$. This representation is a bijection between
$\mathcal{C}_{n}(\pi)$ and the set of binary words of length $(n-1)$ without
two consecutive $1$s, which cardinality is the Fibonacci number, see for
instance [13]. ∎

######  Proposition 15.

If $\pi=\\{001,100\\}$, then $c_{n}(\pi)=F_{n+1}-1$ for $n\geq 1$.

###### Proof.

If $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$, then either

  1. $-$

$\boldsymbol{w}=0\dotsb 0$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)0$ with
$\boldsymbol{u}\in\mathcal{C}_{n-2}(\pi)$.

So, $c_{n}(\pi)$ satisfies the recurrence
$c_{n}(\pi)=c_{n-1}(\pi)+c_{n-2}(\pi)+1$ for $n\geq 3$, and solving it we have
the desired result. ∎

In the next proposition we will make use of the following relation satisfied
by the even index Fibonacci numbers: $F_{2n}=F_{2n-2}+\sum_{i=0}^{n-1}F_{2i}$
for $n\geq 1$.

######  Proposition 16.

If $\pi=\\{100,201\\}$, then $c_{n}(\pi)=F_{2n-2}$ for $n\geq 1$ ($\href
https://oeis.org/A001519$ in [11]).

###### Proof.

If $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 3$, then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)0$ with
$\boldsymbol{u}\in\mathcal{C}_{n-2}(\pi)$, or

  4. $-$

$\boldsymbol{w}=01^{n-k-2}0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{k}(\pi)$ for some $k$, $1\leq k\leq n-3$.

In both of the first two cases the numbers of words $\boldsymbol{w}$ is
$c_{n-1}(\pi)$ and in the third case, this number is $c_{n-2}(\pi)$. In the
last case, the number of words $\boldsymbol{w}$ is
$\sum^{n-3}_{k=1}c_{k}(\pi).$ So,
$c_{n}(\pi)=2c_{n-1}(\pi)+c_{n-2}(\pi)+\sum_{k=1}^{n-3}c_{k}(\pi)=c_{n-1}(\pi)+\sum_{k=1}^{n-1}c_{k}(\pi)$,
and with the initial conditions we have $c_{n}(\pi)=F_{2n-2}$. ∎

The sequence of Pell numbers $(p_{n})_{n\geq 0}$ is defined as $p_{0}=0$,
$p_{1}=1$ and $p_{n}=2p_{n-1}+p_{n-2}$ for $n\geq 2$.

######  Proposition 17.

If $\pi=\\{100,101\\}$, then $c_{n}(\pi)$ is the $n$th Pell number for $n\geq
1$ ($\href https://oeis.org/A000129$ in [11]).

###### Proof.

If $\boldsymbol{w}\in\mathcal{C}_{n}(\pi)$, $n\geq 2$, then either

  1. $-$

$\boldsymbol{w}=0\boldsymbol{u}$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  2. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ with
$\boldsymbol{u}\in\mathcal{C}_{n-1}(\pi)$, or

  3. $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)0$ with
$\boldsymbol{u}\in\mathcal{C}_{n-2}(\pi)$.

In both of the first two cases the numbers of words $\boldsymbol{w}$ is
$c_{n-1}(\pi)$ and it is $c_{n-2}(\pi)$ in the last case. So, $c_{n}(\pi)$
satisfies Pell numbers recurrence and considering its initial values the
statement holds. ∎

##  6 Counting via generating function

Here we give bivariate generating functions $C_{\pi}(x,y)$ where the
coefficient of $x^{n}y^{k}$ is the number of Catalan words of length $n$
having $k$ descents and avoiding $\pi$, for each of the remaining pairs $\pi$
of patterns of length $3$. Plugging $y=1$ in $C_{\pi}(x,y)$ we obtain
$C_{\pi}(x)=C_{\pi}(x,1)$ where the coefficient of $x^{n}$ is the number of
Catalan words of length $n$ avoiding $\pi$. All the obtained enumerating
sequences are not yet recorded in [11], except that for: $\pi=\\{100,120\\}$
and for $\pi=\\{110,120\\}$ (see Corollary 3) and presumably for
$\pi=\\{100,210\\}$ (see Corollary 15). In almost all the proofs of the next
propositions the desired generating function is the solution of a functional
equation satisfied by it.

######  Proposition 18.

If $\pi=\\{000,021\\}$, then

$C_{\pi}(x,y)=-\frac{x^{4}y+x^{2}y+1}{x^{2}+x-1}.$

###### Proof.

Here we need the generating function for the Fibonacci numbers
$C_{000,010}(x)=\frac{1}{1-x-x^{2}}$ for the set in Proposition 14. Note that
words in $\mathcal{C}(000,010)$ have no descents.

Let $\boldsymbol{w}$ be a non-empty word in $\mathcal{C}(\pi)$. Then
$\boldsymbol{w}$ has one of the following forms:

  * $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1$) where
$\boldsymbol{u}\in\mathcal{C}(000,010)$; the generating function for these
words is $x\cdot\frac{1}{1-x-x^{2}}$,

  * $-$

$\boldsymbol{w}=00(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in C(000,010)$;
the generating function for these words is $x^{2}\cdot\frac{1}{1-x-x^{2}}$,

  * $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)0$ where
$\boldsymbol{u}\in\mathcal{C}(000,010)$; the generating function for these
words is $y\cdot x^{2}\cdot\frac{1}{1-x-x^{2}}$,

  * $-$

$\boldsymbol{w}=0101(\boldsymbol{u}+2)$ where
$\boldsymbol{u}\in\mathcal{C}(000,010)$; the generating function for these
words is $y\cdot x^{4}\cdot\frac{1}{1-x-x^{2}}$.

Combining these cases and adding 1 corresponding to the empty word we have

$C_{\pi}(x,y)=1+x(1+x)\cdot\frac{1}{1-x-x^{2}}+yx^{2}(1+x^{2})\left(\frac{1}{1-x-x^{2}}\right),$

which after calculation gives the desired result. ∎

######  Corollary 2.

If $\pi=\\{000,021\\}$, then

$C_{\pi}(x)=-\frac{x^{4}+x^{2}+1}{x^{2}+x-1}\\\
=1+x+3x^{2}+4x^{3}+8x^{4}+12x^{5}+20x^{6}+32x^{7}+O(x^{6}).$

######  Proposition 19.

If $\pi=\\{100,120\\}$, then

$C_{\pi}(x,y)=-\frac{(x-1)^{2}}{x^{3}y-2x^{2}+3x-1}.$

###### Proof.

A word $\boldsymbol{w}\in\mathcal{C}(\pi)$ is in one of the following cases:

  * $-$

$\boldsymbol{w}$ is a w.i. Catalan word,

  * $-$

$\boldsymbol{w}=\boldsymbol{u}(m-1)(\boldsymbol{v}+m)$ where $\boldsymbol{u}$
is a w.i. Catalan word other than $00\dotsb 0$, $m$ is the largest (last)
entry of $\boldsymbol{u}$ and $\boldsymbol{v}\in C(\pi)$.

The generating function for the words of the first form is $\frac{1-x}{1-2x}$
and the generating function for the words of the second form is

$\left(\frac{1-x}{1-2x}-\frac{1}{1-x}\right)\cdot x\cdot y\cdot C_{\pi}(x,y).$

Combining these cases we deduce the functional equation below which solution
gives the desired result:

$C_{\pi}(x,y)=\left(\frac{1-x}{1-2x}-\frac{1}{1-x}\right)\cdot x\cdot y\cdot
C_{\pi}(x,y)+\frac{1-x}{1-2x}.$

∎

######  Proposition 20.

If $\pi=\\{110,120\\}$, then

$C_{\pi}(x,y)=-\frac{(x-1)^{2}}{x^{3}y-2x^{2}+3x-1}.$

###### Proof.

A word $\boldsymbol{w}\in\mathcal{C}(\pi)$ is in one of the following cases:

  * $-$

$\boldsymbol{w}$ is a w.i. Catalan word,

  * $-$

$\boldsymbol{w}=\boldsymbol{u}(m+1)\boldsymbol{v}$ where $\boldsymbol{u}$ is a
non-empty w.i. Catalan word, $m$ is the largest (last) entry of
$\boldsymbol{u}$ and $\boldsymbol{v}$ is a word of the form $mm\cdots
m(\boldsymbol{x}+m+1)$ with at least one $m$ in its prefix and
$\boldsymbol{x}\in\mathcal{C}(\pi)$.

The generating function for the words of the first form is $\frac{1-x}{1-2x}$.
For the second form, the generating function for the words $\boldsymbol{u}$ is
$\frac{1-x}{1-2x}-1=\frac{x}{1-2x}$, and the generating function for the words
$mm\cdots m(\boldsymbol{x}+m+1)$ is $\frac{x}{1-x}\cdot C_{\pi}(x,y)$. Thus,
the generating function for the words of the second form is

$\frac{x}{1-2x}\cdot x\cdot y\cdot\frac{x}{1-x}\cdot\mathcal{C}_{\pi}(x,y).$

Combining these cases we deduce the functional equation

$C_{\pi}(x,y)=\frac{x}{1-2x}\cdot x\cdot y\cdot\frac{x}{1-x}\cdot
C_{\pi}(x,y)+\frac{1-x}{1-2x}.$

∎

The functional equations in the proofs of Propositions 19 and 20 are different
but the resulting bivariate generating functions are the same. Instantiating
$y$ by $1$ in $C_{\pi}(x,y)$ of these propositions we have the next corollary.

######  Corollary 3.

If $\pi=\\{100,120\\}$ or $\pi=\\{110,120\\}$, then

$C_{\pi}(x)=-\frac{(x-1)^{2}}{x^{3}-2x^{2}+3x-1}=1+x+2x^{2}+5x^{3}+12x^{4}+28x^{5}+65x^{6}+151x^{7}+O(x^{8}),$

and $c_{n}(\pi)$ is the sequence $\href https://oeis.org/A034943$ in [11].

######  Proposition 21.

If $\pi=\\{021,110\\}$, then

$C_{\pi}(x,y)=-\frac{x^{5}y+x^{4}y-x^{4}-x^{3}y+4x^{3}-6x^{2}+4x-1}{(2x-1)(x-1)^{3}}.$

###### Proof.

A non-empty word $\boldsymbol{w}\in\mathcal{C}(\pi)$ is in one of the
following cases:

  * $-$

$\boldsymbol{w}=0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$;
the generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a non-empty
w.i. Catalan word; the generating function for these words is
$x\cdot\frac{x}{1-2x}$,

  * $-$

$\boldsymbol{w}=01\boldsymbol{u}$ where $\boldsymbol{u}$ is a non-empty w.i.
Catalan word; the generating function for these words is $x^{2}\cdot
y\cdot\frac{x}{1-2x}$,

  * $-$

$\boldsymbol{w}=\boldsymbol{u}0\dotsb 0$ where $\boldsymbol{u}$ is a s.i.
Catalan word of length at least three and $\boldsymbol{w}$ ending by at least
one $0$; the generating function for these words is
$y\cdot\frac{x^{4}}{(1-x)^{2}}$.

Combining these cases and considering the empty word which contributes with
$1$ to $C_{\pi}(x,y)$, we deduce the functional equation

$C_{\pi}(x,y)=1+x\cdot C_{\pi}(x,y)+x\cdot\frac{x}{1-2x}+x^{2}\cdot
y\cdot\frac{x}{1-2x}+y\cdot\frac{x^{4}}{(1-x)^{2}}.$

∎

######  Corollary 4.

If $\pi=\\{021,110\\}$, then

$C_{\pi}(x)=-\frac{x^{5}+3x^{3}-6x^{2}+4x-1}{(2x-1)(x-1)^{3}}=1+x+2x^{2}+5x^{3}+12x^{4}+26x^{5}+53x^{6}+105x^{7}+O(x^{8}).$

######  Proposition 22.

If $\pi=\\{110,201\\}$, then

$C_{\pi}(x,y)=\frac{x^{4}y-x^{3}+3x^{2}-3x+1}{(x-1)(x^{3}y-2x^{2}+3x-1)}.$

###### Proof.

A non-empty word $\boldsymbol{w}\in\mathcal{C}(\pi)$ is in one of the
following cases:

  * $-$

$\boldsymbol{w}=0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$;
the generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a non-empty
word in $\mathcal{C}(\pi)$; the generating function for these words is
$x\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$\boldsymbol{w}=\boldsymbol{u}0\dotsb 0$ where $\boldsymbol{u}$ is a s.i.
Catalan word of length at least $2$ and $\boldsymbol{w}$ ending by at least
one $0$; the generating function for these words is
$y\cdot\frac{x^{3}}{(1-x)^{2}}$,

  * $-$

$\boldsymbol{w}=010\cdots 0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a
non-empty word in $\mathcal{C}(\pi)$ and $\boldsymbol{w}$ beginning by $010$;
the generating function for these words is $y\cdot
x^{3}\cdot\frac{1}{1-x}\cdot(C_{\pi}(x)-1)$.

Combining these cases and adding $1$ corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+x\cdot
C_{\pi}(x,y)+x\cdot(C_{\pi}(x,y)-1)+y\cdot\frac{x^{3}}{(1-x)^{2}}+y\cdot
x^{3}\cdot\frac{1}{1-x}\cdot(C_{\pi}(x,y)-1).$

∎

######  Corollary 5.

If $\pi=\\{110,201\\}$, then

$C_{\pi}(x)=\frac{x^{4}-x^{3}+3x^{2}-3x+1}{(x-1)(x^{3}-2x^{2}+3x-1)}=1+x+2x^{2}+5x^{3}+13x^{4}+32x^{5}+76x^{6}+178x^{7}+O(x^{8}).$

######  Proposition 23.

If $\pi=\\{102,201\\}$, then

$\mathcal{C}_{\pi}(x,y)=\frac{x^{5}y+x^{4}y^{2}-x^{5}-5x^{4}y+5x^{4}+6x^{3}y-10x^{3}-2x^{2}y+10x^{2}-5x+1}{(-x+1)(x^{2}y-x^{2}+2x-1)(x^{2}y-2x^{2}+3x-1)}.$

###### Proof.

A non-empty word $\boldsymbol{w}\in\mathcal{C}(\pi)$ is in one of the
following cases:

  * $-$

$\boldsymbol{w}=0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$;
the generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$\boldsymbol{w}=0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a non-empty
word in $\mathcal{C}(\pi)$; the generating function for these words is
$x\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$\boldsymbol{w}=0(\boldsymbol{v+1})0\dotsb 0$ where $\boldsymbol{u}$ is a non-
empty word in $\mathcal{C}(\pi)$ and $\boldsymbol{w}$ ending by at least one
$0$; the generating function for these words is $y\cdot
x^{2}\cdot\frac{1}{1-x}\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$\boldsymbol{w}=01\cdots 1\boldsymbol{u}$ where $\boldsymbol{u}$ is a binary
word beginning by a $0$ and different from $0\cdots 0$, or equivalently,
$\boldsymbol{u}$ a word in $\mathcal{C}(012)$ other than $0\cdots 0$; the
generating function for these words is $\frac{x^{2}}{1-x}\cdot
y\cdot\left(C_{012}(x,y)-\frac{1}{1-x}\right)=\frac{x^{2}\cdot
y}{1-x}\cdot\left(\frac{1-x+x^{2}-x^{2}y}{1-2x+x^{2}-x^{2}y}-\frac{1}{1-x}\right)$,
see Theorem 4 in [1].

Combining these cases and adding $1$ corresponding to the empty word we deduce
the functional equation

$\displaystyle C_{\pi}(x,y)=$ $\displaystyle 1+x\cdot
C_{\pi}(x,y)+x\cdot(C_{\pi}(x,y)-1)+\frac{x^{2}\cdot
y}{1-x}\cdot(C_{\pi}(x,y)-1)$ $\displaystyle+\frac{x^{2}\cdot
y}{1-x}\cdot\left(\frac{1-x+x^{2}-x^{2}y}{1-2x+x^{2}-x^{2}y}-\frac{1}{1-x}\right).$

∎

######  Corollary 6.

If $\pi=\\{102,201\\}$, then

${C_{\pi}(x)}=\frac{x^{4}-4x^{3}+8x^{2}-5x+1}{(x-1)(2x-1)(x^{2}-3x+1)}=1+x+2x^{2}+5x^{3}+14x^{4}+40x^{5}+113x^{6}+314x^{7}+O(x^{8}).$

######  Proposition 24.

If $\pi=\\{100,110\\}$, then

$C_{\pi}(x,y)=\frac{x^{4}y-x^{4}+2x^{3}-2x+1}{(x-1)(x^{3}y-2x^{3}+x^{2}+2x-1)}.$

###### Proof.

A non-empty word in $\mathcal{C}(\pi)$ has one of the following forms:

  * $-$

$0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the generating
function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(\pi)$; the generating function for these words is
$x\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$\boldsymbol{u}(m+1)(m+2)\boldsymbol{v}$ where $\boldsymbol{u}$ and
$\boldsymbol{v}$ are non-empty s.i. Catalan words, $m$ is the largest entry of
$\boldsymbol{u}$ and the length of $\boldsymbol{v}$ is less than or equal to
that of $\boldsymbol{u}$; the generating function for these words is $y\cdot
x^{4}\cdot(x+1)\cdot\frac{1}{(1-x^{2})^{2}}$,

  * $-$

$\boldsymbol{u}(m+1)\boldsymbol{u}(\boldsymbol{v}+m+1)$ where $\boldsymbol{u}$
is a non-empty s.i. Catalan word, $m$ is the largest entry of $\boldsymbol{u}$
and $\boldsymbol{v}\in\mathcal{C}(\pi)$; the generating function for these
words is $y\cdot x^{3}\cdot\frac{1}{1-x^{2}}\cdot C_{\pi}(x,y)$.

Combining these cases and adding $1$ corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+x\cdot C_{\pi}(x,y)+x\cdot(C_{\pi}(x,y)-1)+y\cdot
x^{4}\cdot\frac{(x+1)}{(1-x^{2})^{2}}+y\cdot x^{3}\cdot\frac{1}{1-x^{2}}\cdot
C_{\pi}(x,y).$

∎

######  Corollary 7.

If $\pi=\\{100,110\\}$, then

$C_{\pi}(x)=\frac{-2x^{3}+2x-1}{(x-1)(x^{3}-x^{2}-2x+1)}=1+x+2x^{2}+5x^{3}+12x^{4}+28x^{5}+64x^{6}+145x^{7}+O(x^{8}).$

######  Proposition 25.

If $\pi=\\{000,110\\}$, then

$C_{\pi}(x,y)=\frac{x^{3}y+x^{3}-x^{2}-x+1}{(-x+1)(x^{3}-x^{2}y-x^{2}-x+1)}.$

###### Proof.

A non-empty word in $\mathcal{C}(\pi)$ has one of the following forms:

  * $-$

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$\boldsymbol{u}\boldsymbol{u}(\boldsymbol{v}+m+1)$ where $\boldsymbol{u}$ is a
non-empty s.i. Catalan word, $m$ is the largest (last) entry of
$\boldsymbol{u}$ and $\boldsymbol{v}\in\mathcal{C}(\pi)$; the generating
function for these words is $y\cdot\frac{x^{2}}{1-x^{2}}\cdot C_{\pi}(x,y)$,

  * $-$

$\boldsymbol{u}(m+1)\boldsymbol{v}$ where $\boldsymbol{u}$ and $m$ are as
above, and $\boldsymbol{v}$ is a non-empty s.i. Catalan word of length less
than that of $\boldsymbol{u}$; the generating function for these words is
$y\cdot x^{3}\cdot(1+x)\cdot\frac{1}{(1-x^{2})^{2}}$.

Combining these cases and adding $1$ corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+x\cdot C_{\pi}(x,y)+y\cdot\frac{x^{2}}{1-x^{2}}\cdot
C_{\pi}(x,y)+y\cdot x^{3}\cdot(1+x)\cdot\frac{1}{(1-x^{2})^{2}}.$

∎

######  Corollary 8.

If $\pi=\\{000,110\\}$, then

$C_{\pi}(x)=\frac{2x^{3}-x^{2}-x+1}{(-x+1)(x^{3}-2x^{2}-x+1)}=1+x+2x^{2}+4x^{3}+8x^{4}+15x^{5}+28x^{6}+51x^{7}+O(x^{8}).$

######  Proposition 26.

If $\pi=\\{000,102\\}$ or $\pi=\\{000,201\\}$, then

$C_{\pi}(x,y)=\frac{yx^{2}-1}{yx^{4}+yx^{2}+x^{2}+x-1}.$

###### Proof.

If $\pi=\\{000,102\\}$, then a non-empty word in $\mathcal{C}(\pi)$ has one of
the following forms:

  * $-$

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$00(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $x^{2}\cdot C_{\pi}(x,y)$,

  * $-$

$0(\boldsymbol{u}+1)0$ where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(\pi)$; the generating function for these words is $y\cdot
x^{2}\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$01(\boldsymbol{u}+2)01$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $y\cdot x^{4}\cdot C_{\pi}(x,y)$.

Similarly, if $\pi=\\{000,201\\}$ and $\boldsymbol{w}$ is a non-empty word in
$\mathcal{C}(\pi)$, then $\boldsymbol{w}$ has either one of the first three
forms above, or

  * $-$

$\boldsymbol{w}=0101(\boldsymbol{u}+2)$ where
$\boldsymbol{u}\in\mathcal{C}(\pi)$; the generating function for these words
is $y\cdot x^{4}\cdot C_{\pi}(x,y)$.

In both cases we obtain the functional equation

$C_{\pi}(x,y)=1+x\cdot C_{\pi}(x,y)+x^{2}\cdot C_{\pi}(x,y)+y\cdot
x^{2}\cdot(C_{\pi}(x,y)-1)+y\cdot x^{4}\cdot C_{\pi}(x,y).$

∎

######  Corollary 9.

If $\pi=\\{000,102\\}$ or $\pi=\\{000,201\\}$, then

$C_{\pi}(x)=\frac{x^{2}-1}{x^{4}+2x^{2}+x-1}=1+x+2x^{2}+4x^{3}+9x^{4}+18x^{5}++38x^{6}+78x^{7}+O(x^{8}).$

######  Proposition 27.

If $\pi=\\{000,120\\}$, then

$C_{\pi}(x,y)=-\frac{x^{4}y+x^{3}y+1}{x^{4}y+x^{2}+x-1}.$

###### Proof.

A non-empty word in $\mathcal{C}(\pi)$ has one of the following forms:

  * $-$

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$00(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $x^{2}\cdot C_{\pi}(x,y)$,

  * $-$

$0101(\boldsymbol{u}+2)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $y\cdot x^{4}\cdot C_{\pi}(x,y)$.

Apart from these general cases, there are two other fixed length ones:

  * $-$

$010$; the corresponding generating function is $y\cdot x^{3}$,

  * $-$

$0110$; the corresponding generating function is $y\cdot x^{4}$.

Combining these cases and adding $1$ corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+x\cdot C_{\pi}(x,y)+x^{2}\cdot C_{\pi}(x,y)+y\cdot x^{4}\cdot
C_{\pi}(x,y)+y\cdot x^{3}+y\cdot x^{4}.$

∎

######  Corollary 10.

If $\pi=\\{000,120\\}$, then

$C_{\pi}(x)=-\frac{x^{4}+x^{3}+1}{x^{4}+x^{2}+x-1}=1+x+2x^{2}+4x^{3}+8x^{4}+13x^{5}+23x^{6}+40x^{7}+O(x^{8}).$

######  Proposition 28.

If $\pi=\\{201,210\\}$, then

$C_{\pi}(x,y)=\frac{x^{4}y-2x^{4}-3x^{3}y+7x^{3}+x^{2}y-9x^{2}+5x-1}{(2x-1)(x-1)(x^{2}y-2x^{2}+3x-1)}.$

###### Proof.

A non-empty word $\boldsymbol{w}$ in $\mathcal{C}(\pi)$ has one of the
following forms:

  * $-$

$0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the generating
function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$0(\boldsymbol{u}+1$) where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(\pi)$; the generating function for these words is
$x\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$01\cdots 1\boldsymbol{u}$ where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(\pi)$ and $01$ is a prefix of $\boldsymbol{w}$; the generating
function for these words is $y\cdot\frac{x^{2}}{1-x}\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$0(\boldsymbol{u}+1)0\dots 0$ where $\boldsymbol{u}$ is a w.i. Catalan word
other than $0\cdots 0$ and $\boldsymbol{w}$ ending by a $0$; the generating
function for these words is
$y\cdot\frac{x^{2}}{1-x}\cdot(\frac{1-x}{1-2x}-\frac{1}{1-x})$.

Combining these cases and adding 1 corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+x\cdot
C_{\pi}(x,y)+x\cdot(C_{\pi}(x,y)-1)+y\cdot\frac{x^{2}}{1-x}\cdot(C_{\pi}(x,y)-1)+y\cdot\frac{x^{2}}{1-x}\cdot\left(\frac{1-x}{1-2x}-\frac{1}{1-x}\right).$

∎

######  Corollary 11.

If $\pi=\\{201,210\\}$, then

$C_{\pi}(x)=\frac{x^{4}-4x^{3}+8x^{2}-5x+1}{(x-1)(2x-1)(x^{2}-3x+1)}=1+x+2x^{2}+5x^{3}+14x^{4}+40x^{5}+113x^{6}+314x^{7}+O(x^{8}).$

######  Proposition 29.

If $\pi=\\{102,210\\}$, then

$C_{\pi}(x,y)=$

$\frac{2x^{7}y-2x^{7}+13x^{6}-10x^{6}y-x^{6}y^{2}-36x^{5}+19x^{5}y+55x^{4}-17x^{4}y-50x^{3}+7x^{3}y+27x^{2}-yx^{2}-8x+1}{(x-1)^{3}(2x-1)^{2}(x^{2}y-x^{2}+2x-1)}.$

###### Proof.

A non-empty word $\boldsymbol{w}$ in $\mathcal{C}(\pi)$ has one of the
following forms:

  * $-$

$0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the generating
function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(\pi)$; the generating function for these words is
$x\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$01\cdots 1\boldsymbol{u}$ where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(012)$, and $\boldsymbol{w}$ begins by $01$; the generating
function for these words is
$y\cdot\frac{x^{2}}{1-x}\cdot(C_{012}(x,y)-1)=y\cdot\frac{x^{2}}{1-x}\cdot(\frac{1-x+x^{2}-x^{2}y}{1-2x+x^{2}-x^{2}y}-1)$
(see Theorem 4 in [1] for the generating function of $C_{012}(x,y)$),

  * $-$

$0(\boldsymbol{u}+1)\boldsymbol{v}$ where $\boldsymbol{u}$ is a w.i. Catalan
word of length at least $2$ different from $0\cdots 0$ and $\boldsymbol{v}$ is
a non-empty word in $\mathcal{C}(010,012)$ (see Proposition 5); the generating
function for these words is $x\cdot(\frac{1-x}{1-2x}-\frac{1}{1-x})\cdot
y\cdot C_{010,012}(x,y)=y\cdot
x\cdot\frac{x}{(1-x)^{2}}\cdot(\frac{1-x}{1-2x}-\frac{1}{1-x})$.

Combining these cases and adding 1 corresponding to the empty word we deduce
the functional equation

$\displaystyle C_{\pi}(x,y)=$ $\displaystyle 1+x\cdot
C_{\pi}(x,y)+x\cdot(C_{\pi}(x,y)-1)+y\cdot\frac{x^{2}}{1-x}\cdot\left(\frac{1-x+x^{2}-x^{2}y}{1-2x+x^{2}-x^{2}y}-1\right)+$
$\displaystyle
y\cdot\frac{x^{2}}{(1-x)^{2}}\cdot\left(\frac{1-x}{1-2x}-\frac{1}{1-x}\right).$

∎

######  Corollary 12.

If $\pi=\\{102,210\\}$, then

$\displaystyle C_{\pi}(x)$ $\displaystyle=$
$\displaystyle\frac{2x^{6}-17x^{5}+38x^{4}-43x^{3}+26x^{2}-8x+1}{(x-1)^{3}(2x-1)^{3}}$
$\displaystyle=$ $\displaystyle
1+x+2x^{2}+5x^{3}+14x^{4}+40x^{5}+111x^{6}+295x^{7}+O(x^{8}).$

######  Proposition 30.

If $\pi=\\{100,102\\}$, then

$C_{\pi}(x,y)=\frac{x^{5}y-x^{4}y-x^{3}+2x^{3}y+3x^{2}-x^{2}y-3x+1}{(x-1)(x^{4}y-x^{3}y-2x^{2}+x^{2}y+3x-1)}.$

###### Proof.

A non-empty word in $\mathcal{C}(\pi)$ has one of the following forms:

  * $-$

$0\boldsymbol{u}$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the generating
function for these words is $x\cdot C_{\pi}(x,y)$,

  * $-$

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}$ is a non-empty word in
$\mathcal{C}(\pi)$; the generating function for these words is
$x\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$0(\boldsymbol{u}+1)0$ where $\boldsymbol{u}$ is as above; the generating
function for these words is $y\cdot x^{2}\cdot(C_{\pi}(x,y)-1)$,

  * $-$

$011\cdots 1(\boldsymbol{u}+2)01$ where $\boldsymbol{u}$ is as above; the
generating function for these words is
$y\cdot\frac{x^{4}}{1-x}(C_{\pi}(x,y)-1)$,

  * $-$

$\boldsymbol{u}\boldsymbol{v}$ where $\boldsymbol{u}$ and $\boldsymbol{v}$ are
binary words of length at least $2$ of the form $011\cdots 1$; the generating
function for these words is $y\cdot\frac{x^{4}}{(1-x)^{2}}$.

Combining these cases and adding 1 corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+x\cdot C_{\pi}(x,y)+x\cdot(C_{\pi}(x,y)-1)+y\cdot
x^{2}\cdot(C_{\pi}(x,y)-1)+y\cdot\frac{x^{4}}{1-x}(C_{\pi}(x,y)-1)+y\cdot\frac{x^{4}}{(1-x)^{2}}.$

∎

######  Corollary 13.

If $\pi=\\{100,102\\}$, then

$C_{\pi}(x)=\frac{x^{5}-x^{4}+x^{3}+2x^{2}-3x+1}{(x-1)(x^{4}-x^{3}-x^{2}+3x-1)}=1+x+2x^{2}+5x^{3}+13x^{4}+34x^{5}+87x^{6}+220x^{7}+O(x^{8}).$

In the proof of the next proposition we need the following lemma where the
generating functions for some particular subsets of $\mathcal{C}(000,210)$ are
given.

######  Lemma 2.

The bivariate generating function corresponding to

  1. 1.

the set $\mathcal{A}$ of words $\boldsymbol{u}\boldsymbol{u}$ with
$\boldsymbol{u}$ a non-empty s.i. Catalan word is
$A(x,y)=x^{2}+yx^{2}\cdot\frac{x^{2}}{1-x^{2}}$ and
$A(x)=\frac{x^{2}}{1-x^{2}}$;

  2. 2.

the set $\mathcal{B}$ of words $\boldsymbol{u}\boldsymbol{v}$ with
$\boldsymbol{u}$ and $\boldsymbol{v}$ non-empty s.i. Catalan words and the
length of $\boldsymbol{v}$ is less than or equal to that of $\boldsymbol{u}$
is $B(x,y)=y\cdot\frac{x^{2}}{1-x^{2}}\cdot\frac{1}{1-x}$;

  3. 3.

the set $\mathcal{D}$ of words $\boldsymbol{u}\boldsymbol{v}$ with
$\boldsymbol{u}$ and $\boldsymbol{v}$ non-empty s.i. Catalan words and the
length of $\boldsymbol{v}$ is less than that of $\boldsymbol{u}$ is
$D(x,y)=y\cdot\frac{x^{2}}{1-x^{2}}\cdot\frac{x}{1-x}$.

###### Proof.

1\. For any even $n$ there is exactly one word of this form, so the
monovariate corresponding generating function is $\frac{x^{2}}{1-x^{2}}$; and
only words of length larger than two have one descent.

2\. The transformation
$(\boldsymbol{u}\boldsymbol{u},\boldsymbol{x})\mapsto\boldsymbol{u}\boldsymbol{x}\boldsymbol{u}$
where $\boldsymbol{u}\boldsymbol{u}\in\mathcal{A}$ and $\boldsymbol{x}$ is a
s.i. Catalan word defines a bijection between pairs of such words and
$\mathcal{B}$, and thus $B(x,y)=y\cdot A(x)\cdot\frac{1}{1-x}$.

3\. Similarly as point 2. ∎

######  Proposition 31.

If $\pi=\\{000,210\\}$, then

$\mathcal{C}_{\pi}(x,y)=-\frac{(x+1)(x^{3}+x^{3}y-2x+1)}{(x^{4}-x^{4}y+x^{3}-2x^{2}-x+1)(x^{2}+x-1)}.$

###### Proof.

A non-empty word in $\mathcal{C}(000,210)$ has one of the following forms:

  * -

$\boldsymbol{u}$ with $\boldsymbol{u}\in\mathcal{D}$ and $\mathcal{D}$ as in
Lemma 2; the generating function for these words is
$D(x,y)=y\cdot\frac{x^{2}}{1-x^{2}}\cdot\frac{x}{1-x}$,

  * -

$\boldsymbol{u}(m+1)(m+1)(\boldsymbol{x}+m+2)\boldsymbol{v}$ with
$\boldsymbol{u}$ and $\boldsymbol{v}$ non-empty s.i. Catalan words and the
length of $\boldsymbol{v}$ is less than or equal to that of $\boldsymbol{u}$,
$m$ is the largest entry of $\boldsymbol{u}$, and
$\boldsymbol{x}\in\mathcal{C}(000,010)$; the generating function for these
words is $B(x,y)\cdot
x^{2}\cdot\frac{1}{1-x-x^{2}}=y\cdot\frac{x^{2}}{1-x^{2}}\cdot\frac{1}{1-x}\cdot
x^{2}\cdot\frac{1}{1-x-x^{2}}$ (see Lemma 2 and Proposition 14),

  * -

$0(\boldsymbol{u}+1)$ where $\boldsymbol{u}\in\mathcal{C}(\pi)$; the
generating function for these words is $x\cdot C_{\pi}(x,y)$,

  * -

$\boldsymbol{u}\boldsymbol{u}(\boldsymbol{v}+m+1)$ where $\boldsymbol{u}$ is a
non-empty s.i. Catalan word, $m$ the largest entry of $\boldsymbol{u}$ and
$\boldsymbol{v}\in\mathcal{C}(\pi)$; the generating function for these words
is $A(x,y)\cdot C_{\pi}(x,y)$.

Combining these cases and adding $1$ corresponding to the empty word we deduce
the functional equation

$C_{\pi}(x,y)=1+y\cdot\frac{x^{2}}{1-x^{2}}\cdot\frac{x}{1-x}+y\cdot\frac{x^{4}}{1-x^{2}}\cdot\frac{1}{1-x}\cdot\frac{1}{1-x-x^{2}}+x\cdot
C(x,y)+\left(x^{2}+y\cdot\frac{x^{4}}{1-x^{2}}\right)\cdot C(x,y).$

∎

######  Corollary 14.

If $\pi=\\{000,210\\}$, then

$C_{\pi}(x)=-\frac{(x+1)(2x^{3}-2x+1)}{(x^{3}-2x^{2}-x+1)(x^{2}+x-1)}=1+x+2x^{2}+4x^{3}+9x^{4}+18x^{5}+37x^{6}+72x^{7}+O(x^{8}).$

In the proof of the next proposition we need the following lemma where the
generating functions for two subsets of $\mathcal{C}(100,210)$ are given.

######  Lemma 3.

  1. 1.

The generating function corresponding to the set $\mathcal{\mathcal{E}}$ of
words $\boldsymbol{u}\boldsymbol{v}$ with $\boldsymbol{u}$ a w.i. Catalan
word, $\boldsymbol{v}$ a non-empty s.i. Catalan word and the largest entry of
$\boldsymbol{v}$ is equal to that of $\boldsymbol{u}$ minus $1$ is
$\frac{x^{3}}{(x-1)(x^{2}+x-1)}$.

  2. 2.

The generating function corresponding to the set $\mathcal{F}$ of words
$\boldsymbol{u}\boldsymbol{v}$ with $\boldsymbol{u}$ a w.i. Catalan word,
$\boldsymbol{v}$ a non-empty s.i. Catalan word and the largest entry of
$\boldsymbol{v}$ is less than that of $\boldsymbol{u}$ minus $1$ is
$\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot\frac{x}{1-2x}$.

###### Proof.

1\. If $\mathcal{E}_{n}$ is the set of words of length $n$ in $\mathcal{E}$,
then $\mathcal{E}_{n}=\varnothing$ for $0\leq i\leq 2$,
$\mathcal{E}_{3}=\\{010\\}$ and $\mathcal{E}_{4}=\\{0010,0110\\}$. With
$\boldsymbol{u}$ and $\boldsymbol{v}$ as above, for any $n\geq 3$, the
transformation

  * $\boldsymbol{u}\boldsymbol{v}\mapsto\boldsymbol{u}a\boldsymbol{v}$, with $a$ the maximal entry of $\boldsymbol{u}$, transforms a word in $\mathcal{E}_{n}$ into one in $\mathcal{E}_{n+1}$ where the maximal entry occurs at least twice,

  * $\boldsymbol{u}\boldsymbol{v}\mapsto\boldsymbol{u}(a+1)\boldsymbol{v}(b+1)$, with $a$ and $b$ the maximal entries of $\boldsymbol{u}$ and of $\boldsymbol{v}$ respectively, transforms a word in $\mathcal{E}_{n}$ into one in $\mathcal{E}_{n+2}$ where the maximal entry occurs once.

Any word in $\mathcal{E}_{n}$, $n\geq 5$, except $0\cdots 010$, can be
obtained in a unique way from either a word in $\mathcal{E}_{n-1}$ or in
$\mathcal{E}_{n-2}$ by one of these transformations. This yields the
recurrence $|\mathcal{E}_{n}|=1+|\mathcal{E}_{n-1}|+|\mathcal{E}_{n-2}|$ for
$n\geq 5$, and the desired generating function is precisely that of the
sequence $\left(|\mathcal{E}_{n}|\right)_{n\geq 0}$.

2\. Any pair of words $(\boldsymbol{w},\boldsymbol{x})$ with
$\boldsymbol{w}=\boldsymbol{u}\boldsymbol{v}\in\mathcal{E}$ (with
$\boldsymbol{u}$ and $\boldsymbol{v}$ as above) and $\boldsymbol{x}$ a non-
empty w.i. Catalan word can be transformed into the word
$\boldsymbol{u}\boldsymbol{x}\boldsymbol{v}\in\mathcal{F}$, and
$(\boldsymbol{w},\boldsymbol{x})\mapsto\boldsymbol{u}\boldsymbol{x}\boldsymbol{v}$
is a bijection, so the generating function for $\mathcal{F}$ is that for
$\mathcal{E}$ multiplied by $\frac{x}{1-2x}$.

∎

######  Proposition 32.

If $\pi=\\{100,210\\}$, then

$C_{\pi}(x,y)=\frac{1-x}{1-2x}-\frac{x^{3}y}{(2x-1)(2x^{3}-x^{3}y+x^{2}-3x+1)}.$

###### Proof.

First we consider only words in $\mathcal{C}(\pi)$ having at least one
descent, and we denote by $G(x,y)$ the corresponding generating function, and
clearly $C_{\pi}(x,y)=\frac{1-x}{1-2x}+G(x,y)$.

A word in $\mathcal{C}(\pi)$ with at least one descent has one of the
following forms:

  * $-$

$\boldsymbol{u}(\boldsymbol{\alpha}+s+1)(\boldsymbol{v}+s+t+1)$ where
$\boldsymbol{u}$ and $\boldsymbol{v}$ are both w.i. Catalan words,
$\boldsymbol{\alpha}$ belongs to the set $\mathcal{E}$ defined in Lemma 3, and
$s$ is the largest symbol of $\boldsymbol{u}$ (and for convenience $-1$ if
$\boldsymbol{u}$ is empty) and $t$ that of $\boldsymbol{\alpha}$; the
generating function for these words is
$y\cdot\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot\left(\frac{1-x}{1-2x}\right)^{2}$,

  * $-$

$\boldsymbol{u}(\boldsymbol{\alpha}+s+1)$ where $\boldsymbol{u}$ and $s$ are
as above, and $\boldsymbol{\alpha}$ belongs to the set $\mathcal{F}$ defined
in Lemma 3; the generating function for these words is
$y\cdot\frac{1-x}{1-2x}\cdot\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot\frac{x}{1-2x}$,

  * $-$

$\boldsymbol{u}(\boldsymbol{\alpha}+s+1)(\boldsymbol{v}+s+t+1)$ where
$\boldsymbol{u}$ and $s$ are as above, $\boldsymbol{\alpha}$ belongs to
$\mathcal{E}$, $\boldsymbol{v}$ is a word in $\mathcal{C}(\pi)$ with at least
one descent, and $t$ is the largest symbol of $\boldsymbol{\alpha}$; the
generating function for these words is
$y\cdot\frac{1-x}{1-2x}\cdot\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot G(x,y)$.

It follows that $G(x,y)$ satisfies the functional equation

$\displaystyle G(x,y)$ $\displaystyle=$ $\displaystyle
y\cdot\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot\left(\frac{1-x}{1-2x}\right)^{2}+y\cdot\frac{1-x}{1-2x}\cdot\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot\frac{x}{1-2x}+$
$\displaystyle y\cdot\frac{1-x}{1-2x}\cdot\frac{x^{3}}{(x-1)(x^{2}+x-1)}\cdot
G(x,y).$

Finally, solving it and adding the generating function for the Catalan words
with no descents (that is, w.i. Catalan words) the statement holds. ∎

######  Corollary 15.

If $\pi=\\{100,210\\}$, then

$C_{\pi}(x)=\frac{x-1}{2x-1}-\frac{x^{3}}{(2x-1)(x-1)(x^{2}+2x-1)}=1+x+2x^{2}+5x^{3}+13x^{4}+34x^{5}+88x^{6}+225x^{7}+O(x^{8}).$

Numerical evidences let us believe that $c_{n}(100,210)$ is the sequence
A267905 in [11], however we failed to prove this formally.

##  7 Final remarks

Catalan words are in bijection with Dyck paths (see Figure 1) and thus pattern
avoiding Catalan words correspond to restricted Dyck paths. For instance, a
Catalan word avoiding $012$ corresponds to a Dyck path of height at most two.
In this context, it can be of interest to investigate how our results on
pattern avoiding Catalan words translate to corresponding restricted Dyck
paths.

Even if in this article we restrict ourselves to the avoidance of two patterns
of length 3, some classes considered here can be trivially extended to larger
length patterns, for instance $\mathcal{C}(102,201)=\mathcal{C}(01012,01201)$.
In this light, it can be of interest to explore Catalan words avoiding
patterns of length 4 or more, triples of patterns or generalized patterns.

$\sigma\backslash\tau$ | 000 | 001 | 010 | 011 | 012 | 021 | 100 | 101 | 102 | 110 | 120 | 201 | 210
---|---|---|---|---|---|---|---|---|---|---|---|---|---
000 | - | P. 14 |  P. 14 |  $u.c$. | $u.c.$ | C. 2 | $s$ |  P. 7 | C. 9 | C. 8 | C. 10 | C. 9 | C. 14
001 | - | - |  P. 5 |  P. 5 |  P. 5 |  P. 13 | P. 15 | $s$ | $s$ |  P. 13 |  P. 13 | $s$ |  P. 12
010 | - | - | - |  P. 5 |  P. 5 | $s$ | $s$ | $s$ | $s$ | $s$ | $s$ | $s$ | $s$
011 | - | - | - | - |  P. 5 | $s$ |  P. 6 | $s$ | $s$ | $s$ |  P. 6 | $s$ | $s$
012 | - | - | - | - | - | $s$ |  P. 13 |  P. 13 | $s$ |  P. 13 | $s$ | $s$ | $s$
021 | - | - | - | - | - | - |  P. 9 |  P. 9 | P. 11 | C. 4 |  P. 10 | $s$ | $s$
100 | - | - | - | - | - | - | - |  P. 17 | C. 13 | C. 7 |  C. 3 |  P. 16 |  C. 15
101 | - | - | - | - | - | - | - | - | $s$ |  P. 9 |  P. 9 | $s$ |  P. 8
102 | - | - | - | - | - | - | - | - | - |  P. 11 | P. 8 | C. 6 | C. 12
110 | - | - | - | - | - | - | - | - | - | - |  C. 3 | C. 5 | $s$
120 | - | - | - | - | - | - | - | - | - | - | - | $s$ | $s$
201 | - | - | - | - | - | - | - | - | - | - | - | - | C. 11
210 | - | - | - | - | - | - | - | - | - | - | - | - | -
Table 2:  Pairs $\\{\sigma,\tau\\}$ where $\tau$ is superfluous for $\sigma$
are marked by $s$ and those yielding ultimately constant enumerating sequences
(see Proposition 4) by $u.c.$. The references are to the propositions or the
corollaries where the enumerating sequences or generating functions are given.
Pairs referred by the same proposition or corollary form a Wilf-equivalence
class and enumerating results that are not yet recorded in [11] are
italicized. Highlighted pairs are already enumerated in [2] in the context of
ascent sequences, see Section 2.

###### Acknowledgements.

The authors are grateful to the anonymous referees for their careful reading
of the paper and their many insightful comments and suggestions.

## References

  * [1] J.-L. Baril, S. Kirgizov, and V. Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, Discrete Mathematics, 341(9), 2608-2615, 2018.
  * [2] A. Baxter and L. Pudwell, Ascent sequences avoiding pairs of patterns, Electronic Journal of Combinatorics, 22(1), P1.58, electronic, 2015.
  * [3] M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev, (2 + 2)-free posets, ascent sequences and pattern avoiding permutations, Journal of Combinatorial Theory, Series A, 117 (7), 884–909, 2010.
  * [4] L.R. Campbell, S. Dahlberg, R. Dorward, J. Gerhard, T. Grubb, C. Purcell, and B.E. Sagan, Restricted growth function patterns and statistics, Discrete Mathematics and Theoretical Computer Science, 18(2), electronic, 2016.
  * [5] S. Corteel, M.A. Martinez, C.D. Savage, and M. Weselcouch, Patterns in inversion sequences I, Discrete Mathematics and Theoretical Computer Science, 18(2), electronic, 2016.
  * [6] P. Duncan and E. Steingrímsson, Pattern avoidance in ascent sequences, The Electronic Journal of Combinatorics, 18(1), P226, electronic, 2011.
  * [7] S. Kitaev, Patterns in Permutations and Words, Springer, 2011.
  * [8] D.E. Knuth, The Art of Computer Programming, volume 1, Fundamental Algorithms. Addison-Wesley, 1968.
  * [9] Z. Lin and S. Fu, On 1212-avoiding restricted growth functions, The Electronic Journal of Combinatorics, 24(1), P53, electronic, 2017.
  * [10] T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, Pure Mathematics and Applications 25(2), 157-176, 2015.
  * [11] OEIS Foundation Inc. On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2011.
  * [12] R.P. Stanley, Enumerative Combinatorics, volume 2. Cambridge University Press, 1999.
  * [13] V. Vajnovszki, A loopless generation of bitstrings without $p$ consecutive ones, Discrete Mathematics and Theoretical Computer Science\--Springer, 227-240, 2001.
  * [14] C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, https://arxiv.org/pdf/1912.03674.pdf, electronic, 2019.