# Subregularity in infinitely labeled generating trees of restricted
permutations

Toufik Mansour  Department of Mathematics, University of Haifa, 3498838 Haifa,
Israel<EMAIL_ADDRESS>,  Reza Rastegar  Occidental Petroleum
Corporation, Houston, TX 77046 and Departments of Mathematics and Engineering,
University of Tulsa, OK 74104, USA<EMAIL_ADDRESS>and  Mark Shattuck
Department of Mathematics, University of Tennessee, Knoxville, TN 37996, USA
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we revisit the application of generating trees to the pattern
avoidance problem for permutations. In particular, we study this problem for
certain general sets of patterns and propose a new procedure leveraging the
FinLabel algorithm and exploiting the subregularities in the associated
generating trees. We consider some general kinds of generating trees for which
the FinLabel algorithm fails to determine in a finite number of iterations the
generating function that enumerates the underlying class of permutations. Our
procedure provides a unified approach in these cases leading to a system of
equations satisfied by a certain finite set of generating functions which can
be readily solved with the aid of programming.

###### Key words and phrases:

pattern avoidance, generating tree, directed graph, generating function

###### 2010 Mathematics Subject Classification:

05A15, 05A05

##  1\. Introduction

The study of pattern avoidance in permutations has been an object of ongoing
interest to combinatorists over the past few decades. See, for example, the
text [13] for a general review of main results, techniques and directions. We
seek a general procedure for enumerating broad classes of pattern restricted
permutations. Previously, an automatic approach to counting members of an
avoidance class via enumeration schemes was initiated by Zeilberger [24] and
later applied to a variety of problems (see [6, 7, 9, 17] and references
contained therein). In [8], further algorithms were found that derived
functional equations for the generating functions automatically which enabled
polynomial-time enumeration for a set of consecutive patterns. In [16], the
more general problem of counting permutations according to the number
occurrences of a pattern was undertaken using an automatic approach and the
problem for patterns of length three was considered in detail.

Here, we revisit the classical avoidance problem for various sets of patterns
and provide a somewhat general procedure through an in-depth analysis of
certain kinds of generating trees. Recall that each node of a generating tree
corresponds to a combinatorial object, and the branch leading to a node
encodes a particular choice made in the construction of the object. Certain
families of combinatorial objects admit a recursive description in terms of
generating trees [2, 3, 4, 11], which frequently leads to the enumeration of
the object in question, related explicit formulas and efficient random
generation algorithms [1].

Generating trees were first utilized in the enumeration of subclasses of
permutations by West [22, 23] in the context of pattern avoidance and have
been further exploited in closely related problems [5]. Later in [20, 21], the
generating tree idea was developed in the context of restricted permutations
and powerful algorithms were found that can automatically produce the related
generating functions, in particular, in the case when the associated
generating trees are of finite size. Herein, we demonstrate how to extend
these algorithms applicable only to finitely labeled generating trees to study
several families in which they are infinitely labeled. This is achieved
through a more in-depth understanding of a form of subregularity in the tree
structure.

We put forth in this section a preliminary discussion following [20] and
demonstrate how the enumeration of permutations avoiding a given set of
patterns can be described in terms of counting paths within the corresponding
generating tree. A few definitions are in order. Recall that a generating tree
is a rooted, labeled tree such that the label of a node determines the labels
of its children, if any. The nature of the labels of the nodes is immaterial
and, as can be seen in our context, we use permutations to label the nodes. To
specify a generating tree, it suffices to identify: (i) the label of the root,
and (ii) a set of succession rules of the form

$\displaystyle(l)\rightsquigarrow(l_{1}),(l_{2}),\ldots,(l_{s})$

describing how to label the nodes connected by the edges emanating from a node
with label $(l)$ using the labels $(l_{1}),(l_{2}),\ldots,(l_{s})$. One often
refers to the label on the left side of the rule as the _parent_ and the
labels on the right as the _children_ , with these terms applying to the nodes
themselves as well. For example, each node in an infinite complete binary tree
has two children, hence it is enough to use only one label, say $(2)$, leading
to the following description:

  * Root: $(2)$

  * Rule: $(2)\rightarrow(2)(2)$.

We use the standard notation ${\mathbb{N}}$ and ${\mathbb{C}}$ to refer to the
sets of natural and complex numbers, respectively. Let $[n]=\\{1,\ldots,n\\}$
for $n\in{\mathbb{N}}$, with $[0]=\varnothing$. Also, for any word $\sigma$ of
length $n\in{\mathbb{N}}$, let $\sigma(i)$ represent its $i$-th entry for
$i\in[n]$. Similarly, for any matrix $\mathcal{M}$, $\mathcal{M}(i,j)$ will
denote its $(i,j)$-th entry. A _permutation_ of the set $[n]$ is any
arrangement of the elements of $[n]$. We denote the set of all permutations of
$[n]$ by $S_{n}$ and let $S:=\cup_{j\geq 1}S_{j}$ be the set of all
permutations of finite length. Throughout this paper, for any $\pi\in S_{n}$,
$|\pi|:=n$ refers to the length of the permutation $\pi$. For
$\tau=\tau(1)\tau(2)\cdots\tau(k)\in S_{k}$ and
$\sigma=\sigma(1)\sigma(2)\cdots\sigma(n)\in S_{n}$, we say that the
permutation $\sigma$ _contains_ $\tau$ as a _pattern_ if there exist indices
$1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n$ such that $\sigma(i_{a})<\sigma(i_{b})$
if and only if $\tau(a)<\tau(b)$ for all $1\leq a,b\leq k$. Otherwise, it is
said that $\sigma$ _avoids_ $\tau$. We denote the set of all permutations in
$S_{n}$ that avoid the pattern $\tau$ by $S_{n}(\tau)$, and similarly, define
$S(\tau):=\cup_{j\geq 1}S_{j}(\tau)$ as the set of all permutations avoiding
$\tau$. More generally, for a set $1\notin B\subset S$ of patterns, we use the
notation $S_{n}(B):=\cap_{\tau\in B}S_{n}(\tau)$ and $S(B):=\cap_{\tau\in
B}S(\tau)$ to refer to the set of permutations of a given length or of any
length, respectively, avoiding all patterns in the set $B$. Our interest here
is to find the number of permutations in $S_{n}(B)$, i.e., $|S_{n}(B)|$, or
equivalently to study the corresponding generating function

$\displaystyle G_{B}(x):=\sum_{n\geq 1}|S_{n}(B)|x^{n},\qquad
x\in{\mathbb{C}}.$

To establish a useful connection between generating trees and the avoidance
problem in permutations, we define a pattern-avoidance tree $\mathcal{T}(B)$
for a given set of patterns $B$ as follows. The tree $\mathcal{T}(B)$ is
understood to be empty if there is no permutation of arbitrary length avoiding
the set $B$. Otherwise, $1\notin B$ and the root can always be taken as $1$,
i.e., $1\in\mathcal{T}(B)$. Starting with this root, the remainder of the tree
$\mathcal{T}(B)$ can then be constructed in a recursive manner. To this end,
we let the $n$-th level of the tree consist precisely of the elements of
$S_{n}(B)$ arranged in such a way that the parent of a permutation
$\pi:=\pi(1)\cdots\pi(n)\in S_{n}(B)$ for which $\pi(j)=n$ for some $1\leq
j\leq n$ is the unique permutation
$\pi^{\prime}:=\pi^{\prime}(1)\cdots\pi^{\prime}(n-1)\in S_{n-1}(B)$ where
$\pi^{\prime}(i)=\pi(i)$ for $i\in[j-1]$ and $\pi^{\prime}(i)=\pi(i+1)$ for
$i\in[j,n-1]$. See Figure 1 for the first few levels of
$\mathcal{T}(\\{123\\})$. A simple but important observation is that the size
of $S_{n}(B)$ is equal to the number of nodes in the $n$-th level of
$\mathcal{T}(B).$

for tree=fit=band, [1[21,[321,[4321] [3421] [3241] [3214]] [231,[4231] [2431]]
[213,[4213], [2413],[2143]]] [12,[312,[4312] [3412] [3142]] [132,[4132]
[1432]]]]

Figure 1. First four levels of $\mathcal{T}(\\{123\\})$

Hence, we focus on an understanding of the nature of this tree, more
specifically, subregular structures contained within it. More precisely, let
$\mathcal{T}(B;\pi)$ denote the subtree consisting of $\pi$ and its
descendants in $\mathcal{T}(B)$. For any $1\leq m<n\in{\mathbb{N}}$, we say
that the node (labeled by) $\pi\in S_{n}(B)$ is reducible to the node
$\pi^{\prime}\in S_{m}(B)$ if the subtrees starting from $\pi$ and
$\pi^{\prime}$ are isomorphic, i.e.,
$\mathcal{T}(B;\pi)\cong\mathcal{T}(B;\pi^{\prime})$. For instance, it is seen
that $\mathcal{T}(\\{123\\};12)\cong\mathcal{T}(\\{123\\};1)$ and
$\mathcal{T}(\\{123\\};312)\cong\mathcal{T}(\\{123\\};21)$. Suppose $t$ is the
length of the longest pattern in $B$. Then, from [21], we have
$\mathcal{T}(B;\pi)\cong\mathcal{T}(B;\pi^{\prime})$ for $\pi,\pi^{\prime}\in
S(B)$ if and only if, for each $1\leq j\leq t$, the number of nodes in the
$j$-th level of subtree $\mathcal{T}(B;\pi)$ is equal to the number of nodes
in the $j$-th level of subtree $\mathcal{T}(B;\pi^{\prime})$.

Now, based on this subregularity concept, we form the tree denoted by
$\mathcal{T}[B]$ which is an isomorphic copy of $\mathcal{T}(B)$ wherein the
nodes belonging to the same irreducible class are labeled the same. Clearly,
$\mathcal{T}[B]$ is a generating tree whose labels correspond exactly to the
isomorphism classes of $\mathcal{L}[B]:=\\{\mathcal{T}(B;\pi)|\pi\in S(B)\\}$.
We let $\mathcal{R}[B]$ denote the set of succession rules for this generating
tree. For instance, the first few levels of $\mathcal{T}[\\{123\\}]$ are given
in Figure 2.

for tree=fit=band, [1[21,[321,[4321] [1] [21] [321]] [1,[21] [1]] [21,[321] [1
21]]] [1,[21,[321] [1] [21]] [1,[21] [1]]]]

Figure 2. First four levels of $\mathcal{T}[\\{123\\}]$

For any generating tree $\mathcal{T}[B]$, we define the directed graph
$\mathcal{D}[B]$ whose vertices correspond to the set of all isomorphism
classes of labels in $\mathcal{T}(B)$. An edge from the label $\alpha$ to the
label $\beta$ exists if and only if the rule $\alpha\rightsquigarrow\beta$
belongs to the set of succession rules $\mathcal{R}[B]$. For instance, the
graph $\mathcal{D}[\\{123\\}]$ is depicted in Figure 3. Note that multiple
edges occurring between $\alpha$ and $\beta$ corresponds to the case when
$\beta$ arises more than once as a child of $\alpha$.

$1$$21$$321$$4321$$\ldots$ Figure 3. Directed graph $\mathcal{D}[\\{123\\}]$

We equip the set $\mathcal{L}[B]$ of all isomorphism classes of labels with
the lexicographical ordering wherein each permutation of length $k$ appears
before all permutations of length $k+1$ for all $k$. For example, the nodes of
$\mathcal{D}[\\{123\\}]$ are ordered as $1,21,321,\ldots$ . We then define
$\mathcal{M}[B]$ for the graph $\mathcal{D}[B]$ as the matrix whose entries
are given by $\mathcal{M}[B](v,w)=s$ for all $v,w\in\mathcal{D}[B]$, where $s$
is the number of edges from $v$ to $w$. $\mathcal{M}[B]$ is referred to as the
_transition matrix_ of the graph $\mathcal{D}[B]$ and clearly has non-negative
integral entries. For instance, $\mathcal{M}[\\{123\\}]$ is given by the
following infinite matrix

$\displaystyle\mathcal{M}[\\{123\\}]=\left(\begin{array}[]{llllll}1&1&0&0&0&\cdots\\\
1&1&1&0&0&\cdots\\\ 1&1&1&1&0&\cdots\\\ 1&1&1&1&1&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

It is seen that the number of permutations in $S_{n}(B)$ is equal to the
number of paths of length $n-1$ starting at the node $1$ in the graph
$\mathcal{D}[B]$. Hence, the transfer-matrix method [19, Theorem 4.7.2]
implies the generating function $G_{B}(x)$ is given by

(2) $\displaystyle G_{B}(x)=(1,0,0,\ldots)\sum_{n\geq
1}(\mathcal{M}[B])^{n-1}x^{n}(1,1,1,\ldots)^{t},$

where $v^{t}$ denotes the transpose of the vector $v$. If the set of all
isomorphism classes $\\{\mathcal{T}(B;\pi)|\pi\in S(B)\\}$ is finite (i.e., if
$\mathcal{M}[B]$ is finite), then (2) implies the generating function
$G_{B}(x)$ is rational and equal to

(3) $\displaystyle
G_{B}(x)=x(1,0,0,\ldots)(I-x\mathcal{M}[B])^{-1}(1,1,1,\ldots)^{t}.$

In [14] and [21], it was shown that the set of isomorphism classes is finite
if and only if $B$ contains both a child of an increasing permutation and a
child of a decreasing permutation. Furthermore, a Maple package has been
developed (described in [21] and available at
http://math.rutgers.edu/$\sim$vatter/) that finds the generating function in
this case. We will refer to this package (algorithm) as the FinLabel algorithm
throughout this paper.

We close this section with a simple finite case example.

######  Example 1.

Let $B=\\{123,43215\\}$. Then the rules of $\mathcal{T}[B]$ are given by

$\displaystyle\mathcal{R}[B]$ $\displaystyle=$
$\displaystyle\\{1\rightsquigarrow 1,21\\}$
$\displaystyle\cup\\{21\rightsquigarrow 1,21,321\\}$
$\displaystyle\cup\\{321\rightsquigarrow 1,21,321,321\\},$

with the root $1$. Thus $\mathcal{D}[B]$ is as presented in Figure 4.

$1$$21$$321$ Figure 4. Directed graph $\mathcal{D}[\\{123,43215\\}]$

The matrix $\mathcal{M}[B]$ is given by

$\displaystyle\mathcal{M}[B]=\left(\begin{array}[]{lll}1&1&0\\\ 1&1&1\\\
1&1&2\end{array}\right).$

Hence, by (3), the generating function $G_{B}(x)$ is equal to

$\displaystyle
x(1,0,0)(I-x\mathcal{M}[B])^{-1}(1,1,1)^{t}=\frac{x(1-2x)}{(1-x)(1-3x)},$

as expected (see Theorem 3.1 in [10]).

However, when the matrix $\mathcal{M}[B]$ is infinite, the evaluation of
$G_{B}(x)$ can be an intricate task which we will focus on in this paper. In
the next section, we develop an algorithm for computing $\mathcal{T}[B]$,
$\mathcal{D}[B]$ and $\mathcal{M}[B]$ after finitely many iterations which is
applicable to cases when $\mathcal{M}[B]$ is infinite. In the third section,
we apply this algorithm together with a simple general enumerative result to
deduce $G_{B}(x)$ for several classes of pattern sets $B$ for which
$\mathcal{D}[B]$ belongs to one of three general families of graphs.

##  2\. Infinite size $\mathcal{M}[B]$: subregularity structures

To study $\mathcal{M}[B]$ of infinite size, we define $P_{n}(B;\pi)$ to be the
number of nodes at the $n$-th level of $\mathcal{T}(B;\pi)$. Let $F_{\pi}(x)$
be given by

(5) $\displaystyle
F_{\pi}(x):=x^{|\pi|-1}\sum_{n=1}^{\infty}P_{n}(B;\pi)x^{n}.$

In words, $F_{\pi}(x)$ is the generating function that enumerates the paths
beginning with the root $\pi$ of $\mathcal{T}(B;\pi)$. Clearly,
$G_{B}(x)=F_{1}(x)$. Note that $F_{\pi}(x)$ is analytic for all $\pi$ in some
interval containing zero dependent upon $B$. For any rule $v\rightsquigarrow
w_{1}w_{2}\cdots w_{s}$, we have

(6) $\displaystyle P_{n}(B;v)=\begin{cases}1,&\quad\text{if}\quad n=1;\\\
\sum_{j=1}^{s}P_{n-1}(B;w_{j}),&\quad\text{if}\quad n\geq 2.\end{cases}$

Therefore, substituting (6) into (5) implies

(7) $\displaystyle F_{v}(x)$ $\displaystyle=$ $\displaystyle
x^{|v|}+x^{|v|-1}\sum_{n=2}^{\infty}\left(\sum_{j=1}^{s}P_{n-1}(B;w_{j})\right)x^{n}$
$\displaystyle=$ $\displaystyle
x^{|v|}+\sum_{j=1}^{s}x^{|v|+1-|w_{j}|}F_{w_{j}}(x),$

where we exchange sums and apply definition (5) to $w_{j}$ in obtaining the
second equality.

Our general approach will be to rewrite the set of succession rules as a set
of equations of the form (7) and then obtain information on $F_{1}(x)$. We
begin with a simple example to illustrate the general idea.

######  Example 2.

Let $B=\\{123,132\\}$. Here, the generating tree $\mathcal{T}[B]$ has the
rules

(10) $\displaystyle\mathcal{R}[B]$ $\displaystyle:=$
$\displaystyle\\{1\rightsquigarrow 21,12\\}$ $\displaystyle\cup\\{k(k-1)\cdots
21\rightsquigarrow(12)^{k},(k+1)k\cdots 21\mid k\geq 2\\}$
$\displaystyle\cup\\{k(k-1)\cdots 312\rightsquigarrow(12)^{k-2},(k+1)k\cdots
312\mid\ k\geq 2\\},$

with the ordered set

$\mathcal{L}[B]=\\{1,21,12,321,312,4321,4312,\ldots\\},$

and the infinite matrix $\mathcal{M}[B]$ given by

$\mathcal{M}[B]=\left(\begin{array}[]{llllllllll}0&1&1&0&0&0&0&0&0&\cdots\\\
0&0&2&1&0&0&0&0&0&\\\ 0&0&0&0&1&0&0&0&0&\\\ 0&0&3&0&0&1&0&0&0&\cdots\\\
0&0&1&0&0&0&1&0&0&\\\ 0&0&4&0&0&0&0&1&0&\cdots\\\ 0&0&2&0&0&0&0&0&1&\\\
\vdots&&&\vdots&&&&\vdots\end{array}\right).$

Since $\mathcal{M}[B]$ is not finite, the FinLabel algorithm fails to count
the members of $S_{n}(B)$. However, we can describe $\mathcal{M}[B]$ as an
infinite system of equations as follows. Observe that, by (7), the rule (10)
can be written as $F_{1}(x)=x+F_{21}(x)+F_{12}(x)$. Similarly, we can write
rules (10) and (10) as

(11) $\displaystyle F_{k(k-1)\cdots
1}(x)=x^{k}+kx^{k-1}F_{12}(x)+F_{(k+1)k\cdots 1}(x),\qquad k\geq 2,$

and

(12) $\displaystyle F_{k(k-1)\cdots
312}(x)=x^{k}+(k-2)x^{k-1}F_{12}(x)+F_{(k+1)k\cdots 312}(x),\qquad k\geq 2.$

Consider the set of equations (11) for all $k\geq 2$. By addition of the left
and right sides of all the equations, and cancellation of like terms on both
sides, we obtain

(13) $\displaystyle F_{21}(x)=\frac{x^{2}}{1-x}+F_{12}(x)\sum_{k\geq
2}kx^{k-1}.$

In a similar manner, (12) implies

(14) $\displaystyle F_{12}(x)=\frac{x^{2}}{1-x}+F_{12}(x)\sum_{k\geq
2}(k-2)x^{k-1}.$

Solving the system (13) and (14) for $F_{12}(x)$ and $F_{21}(x)$ yields

$\displaystyle F_{12}(x)=\frac{x^{2}(1-x)}{1-2x}\mbox{ and
}F_{21}(x)=\frac{x^{2}(1+x)}{1-2x}.$

Hence, we have

$\displaystyle G_{B}(x)=F_{1}(x)=x+F_{12}(x)+F_{21}(x)=\frac{x}{1-2x},$

which is in accordance with [18].

Since the determination of the rule set $\mathcal{R}[B]$ is the key to our
process, we will formulate a simple algorithm which draws upon and extends
FinLabel as follows. To this end, we say that a set $R$ of $m$ rules
constructs a general rule with index $k$ if the general rule with
$k=1,2,\ldots,m$ gives exactly all the rules in the set $R$. For example, the
set

$R=\\{1\rightsquigarrow 1,12;\,12\rightsquigarrow
1^{2},123;\,123\rightsquigarrow 1^{3},1234;\,\ldots;12\cdots
50\rightsquigarrow 1^{50},12\cdots 51\\}$

of $50$ rules constructs the general rule $12\cdots k\rightsquigarrow
1^{k},12\cdots(k+1)$. The question is how many rules should be included in $R$
so that the correct corresponding general rule can be extracted. The next
observation implies that we only need a finite number of rules to construct a
general rule.

######  Proposition 1.

Let $B\subset S$ be any finite set of patterns and let $t$ be the length of
its longest pattern. Suppose $R$ is a set of $m$ rules that is a subset of the
rules of the tree $\mathcal{T}[B]$ which constructs a general rule
parameterized by index $k$. If $m\geq t-1$, then the general rule holds in
$\mathcal{T}[B]$ for all $k$.

###### Proof.

This is equivalent to the statement that for any two given permutations
$\pi,\pi^{\prime}\in S(B)$, we have
$\mathcal{T}(B;\pi)\cong\mathcal{T}(B;\pi^{\prime})$ if and only if for each
$1\leq j\leq t$, the number of nodes at the $j$-th level of subtree
$\mathcal{T}(B;\pi)$ is equal to the number of nodes of the $j$-th level of
subtree $\mathcal{T}(B;\pi^{\prime})$. ∎

Using this proposition, we can guarantee that the following procedure
calculating $\mathcal{T}[B]$, $\mathcal{D}[B]$ and $\mathcal{M}[B]$ exits
after finitely many iterations. The procedure is comprised of two main parts.
For the first part, we find the set of rules of the generating tree
$\mathcal{T}[B]$. To that end, Step (II) proposes to use a small modification
of the algorithm FinLabel from [21], where the algorithm stops after $D$ units
of time and outputs the set $\mathcal{R}_{D}$. Next, step (III) searches for a
set of rules constructing a general one by looking at rules with an offspring
of form either $\alpha m(m+1)\cdots m^{\prime}\beta\in S_{m^{\prime}}$ or
$\alpha m^{\prime}(m^{\prime}-1)\cdots m\beta\in S_{m^{\prime}}$ for some
$m^{\prime}>m$. Then Step (IV) verifies whether or not we obtained exactly the
set $\mathcal{R}[B]$. If not, then the algorithm increases the value of $D$
and reruns Steps (II) and (III). If yes, then we have successfully found the
generating tree $\mathcal{T}[B]$. As seen below, $D$ depends upon the pattern
set $B$ and theoretically might need to be quite large, which would preclude
the possibility of simply guessing the set of rules. After calculating
$\mathcal{T}[B]$, the algorithm proceeds with the second part in which the
generating function $G_{B}(x)$ is computed.

Algorithm 1 Calculating $\mathcal{R}[B]$ and $\mathcal{D}[B]$

(I): Input Let $1\notin B\subset S$ be any set of patterns and $D\geq 2$.

(II): Let $P=\\{1\\}$ and $\mathcal{R}_{D}=\emptyset$ as specified by the
FinLabel algorithm given in [21]. Then run the FinLabel algorithm $D$
iterations to update $P$ and $\mathcal{R}_{D}$.

(III): Let $\mathcal{R}^{\prime}:=\mathcal{R}_{D}[B]$. Construct one or more
general rules from $R\subseteq\mathcal{R}^{\prime}$ through use of Proposition
1; then remove $R$ from $\mathcal{R}^{\prime}$ and replace with general
rule(s).

(IV): Using Proposition 1 and induction, we attempt to show
$\mathcal{R}^{\prime}=\mathcal{R}[B]$. If successful, proceed to (V).
Otherwise, increase $D$ by one and return to (II).

(V): Find $\mathcal{D}[B]$ and the associated matrix $\mathcal{M}[B]$ for
$\mathcal{T}[B]$.

We illustrate how the algorithm works with the following two examples.

######  Example 3.

Let $B=\\{123,132\\}$ and $D=200$. Note that step (II) gives the set of rules
$\mathcal{R}_{D}=\\{1\rightsquigarrow 21,12;\,12\rightsquigarrow
312;\,21\rightsquigarrow 12^{2},321;\,312\rightsquigarrow
12,4312;\,321\rightsquigarrow 12^{3},4321;\,4312\rightsquigarrow
12^{2},54312;\,4321\rightsquigarrow 12^{4},54321;\ldots\\}$. Then step (III)
outputs

$\displaystyle\mathcal{R}[B]$ $\displaystyle=\\{k(k-1)\cdots
312\rightsquigarrow 12^{k-2},(k+1)k\cdots 312\mid k\geq 2\\}$
$\displaystyle\cup\\{k(k-1)\cdots 21\rightsquigarrow 12^{k},(k+1)k\cdots
21\mid k\geq 1\\}.$

By an induction argument with respect to $k$, we have that the generating tree
$\mathcal{T}[B]$ is indeed given by the rules $\mathcal{R}[B]$. The associated
matrix $\mathcal{M}[B]$ is given in Example 2.

######  Example 4.

Let $B=\\{123,1432,2143\\}$. Using the algorithm above with $D=200$, we obtain

$\displaystyle\mathcal{R}[B]$ $\displaystyle=\\{k(k-1)\cdots
4132\rightsquigarrow 12^{k-3},(k+1)k\cdots 4132\mid k\geq 3\\}$
$\displaystyle\cup\\{k(k-1)\cdots 21\rightsquigarrow 12^{k},(k+1)k\cdots
21\mid k\geq 1\\}$ $\displaystyle\cup\\{12\rightsquigarrow 21,132\\}$
$\displaystyle\cup\\{1\rightsquigarrow 12,21\\}.$

We rewrite the rule $k(k-1)\cdots 4132\rightsquigarrow 12^{k-3},(k+1)k\cdots
4132$ as

$\displaystyle F_{k(k-1)\cdots
4132}(x)=x^{k}+(k-3)x^{k-1}F_{12}(x)+F_{(k+1)k\cdots 4132}(x),\,\qquad k\geq
3.$

Thus, proceeding similarly as in the derivation of (13), we obtain

(15) $\displaystyle F_{132}(x)=\frac{x^{3}}{1-x}+F_{12}(x)\sum_{k\geq
3}(k-3)x^{k-1}.$

Likewise, the rule $k(k-1)\cdots 21\rightsquigarrow 12^{k},(k+1)k\cdots 21$
yields

$\displaystyle F_{k(k-1)\cdots 1}(x)=x^{k}+kx^{k-1}F_{12}(x)+F_{(k+1)k\cdots
1}(x),\,\qquad k\geq 1,$

and hence

(16) $\displaystyle F_{1}(x)$
$\displaystyle=\frac{x}{1-x}+F_{12}(x)\sum_{k\geq 1}kx^{k-1}.$

By the last rule above and upon taking $k=1$ in the formula for
$F_{k(k-1)\cdots 1}(x)$, we have

(17) $\displaystyle F_{12}(x)=x^{2}+xF_{21}+F_{132}(x),$ (18) $\displaystyle
F_{1}(x)=x+F_{12}(x)+F_{21}(x).$

Thus, solving the system (15)-(18) for $F_{1}(x)$ gives

$\displaystyle G_{B}(x)=F_{1}(x)=\frac{x}{1-2x-x^{2}}.$

Let us say that $a(x)$ is a rational linear combination of
$b_{1}(x),\ldots,b_{s}(x)$ if there exist rational functions $c_{j}(x)$ such
that $a(x)=c_{0}(x)+\sum_{j=1}^{s}c_{j}(x)b_{j}(x)$. In order to
systematically leverage Algorithm 1, we will need the following simple yet
important result.

######  Theorem 5.

Let $1\notin B$ be any set of patterns and $m\geq 1$ be a natural number.
Suppose that for any node $\pi$ of $\mathcal{D}[B]$ with $|\pi|=:m$, the
generating function $F_{\pi}(x)$ can be expressed as a rational linear
combination of the $F_{\pi^{\prime}}(x)$ with $\pi^{\prime}\in\mathcal{D}[B]$
and $|\pi^{\prime}|\leq m$ such that $c_{j}(0)=0$ for all $j$ in the
corresponding coefficients $c_{j}(x)$. Then $G_{B}(x)$ is a rational
generating function.

###### Proof.

Since $1\notin B,$ there is a rule in $\mathcal{R}[B]$ with parent $1$.
Further, the result is apparent if $m=1$, so we may assume $m\geq 2$. Define
$R^{\prime}$ to be the set of all rules in $\mathcal{R}[B]$ whose parents are
of length at most $m-1$. For any rule $v\rightsquigarrow w_{1}w_{2}\cdots
w_{s}$ in $R^{\prime}$, we rewrite it in the form of (7):

(19) $\displaystyle
F_{v}(x)=x^{|v|}+\sum_{j=1}^{s}x^{|v|+1-|w_{j}|}F_{w_{j}}(x),$

where $|w_{j}|\leq m$ for any $1\leq j\leq s$. By hypothesis, for each
$\pi\in\mathcal{D}[B]$ with $|\pi|=m$, $F_{\pi}(x)$ is a rational linear
combination of $F_{v}(x)$ with $|v|\leq m$. Therefore, combining these
equations with those given in (19) for $|v|\leq m-1$, one obtains a linear
system of equations in the variables $F_{v}(x)$ where $|v|\leq m$. The
associated coefficient matrix of this system has rational function
coefficients and non-zero determinant since each main diagonal entry is of the
form $1-xf(x)$ for some rational $f(x)$, with each entry below the diagonal
seen to be a multiple of $x$ (possibly zero). Indeed, the determinant is equal
to $1$ at $x=0$, and hence by continuity, there exists some open interval
containing zero for which the determinant is non-zero. Thus, Cramer’s rule
implies that each component of the solution of the system (valid for all $x$
on the interval) is a rational function. In particular, $G_{B}(x)=F_{1}(x)$ is
rational, as desired. ∎

##  3\. Enumeration results for families of patterns

In this section, we use Algorithm 1 along with Theorem 5 to study several
families of sets of patterns whose corresponding graphs are infinite and hence
FinLabel is not applicable directly. In each of these cases, let $G=(V,E)$ be
a directed graph with set of nodes $V\subset S$ and edge set $E\subset V\times
V$.

###  3.1. Almost path-directed graphs

We say that $G$ is an almost path-directed graph if the set of nodes $V$ can
be partitioned as $V:=V^{\prime}\cup W$, where
$V^{\prime}:=\\{v_{0},v_{1},\ldots\\}$ and $|v_{i}|=i+m$ for all $i\geq 0$
with $m\geq 1$ fixed such that

  * •

The length of any node $w$ in $W=V\backslash V^{\prime}$ is at most $m$.

  * •

$(v_{j},v_{j+1})\in E$ for all $j\geq 0$ and is not repeated.

  * •

All other edges $(c,d)\in E$ may be repeated (with $c=d$ possible) and are
such that $c$ or $d$ belongs to $W$ (possibly both).

In this context, $V^{\prime}$ and $W$ will be referred to as the parameters of
the almost path-directed graph $G$. Note that $(e_{1},e_{2})\in E$ with
$e_{1}\in W$ implies $e_{2}\in W\cup\\{v_{0},v_{1}\\}$ since $|e_{1}|\leq m$.
In practice, we frequently have for each $m^{\prime}>m$ that the node
$v_{m^{\prime}-m}\in V^{\prime}$ is obtained from $v_{0}$ by replacing $m$
with either $m(m+1)\cdots m^{\prime}$ or $m^{\prime}(m^{\prime}-1)\cdots m$.
Furthermore, the result below is seen to apply more generally to any
generating function which enumerates paths starting from the root and having
$n-1$ steps for $n\geq 1$ in an almost path-directed graph $G$ independent of
whether or not $G$ arose in the context of pattern avoidance. A similar remark
applies to the graphs discussed in the subsequent two sections.

When $B$ is a set of patterns whose directed graph $\mathcal{D}[B]$ is almost
path-directed, we may apply Algorithm 1 together with the following result to
ascertain the generating function.

######  Theorem 6.

Let $1\notin B\subset S$ be any set of patterns. Supposed $\mathcal{D}[B]$ is
an almost path-directed graph with parameters $V^{\prime}$ and $W$. If for
each $w\in W$, the generating function $\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{j}$ is rational, then $G_{B}(x)$ is rational.

###### Proof.

We first show that $F_{v_{0}}(x)$ is a rational linear combination of the
$F_{w}(x)$ with $w\in W$ such that $c_{j}(0)=0$ for each corresponding
coefficient $c_{j}(x)$. To this goal, since $\mathcal{D}[B]$ is almost path-
directed, we have

$\displaystyle F_{v_{j}}(x)=x^{|v_{0}|+j}+\sum_{w\in
W}\mathcal{M}[B](v_{j},w)x^{|v_{0}|+j+1-|w|}F_{w}(x)+F_{v_{j+1}}(x),\qquad
j\geq 0.$

Hence, by summing over $j\geq 0$ and using the fact that
$F_{v_{j}}(x)\rightarrow 0$ as $j\rightarrow\infty$ for $x$ sufficiently close
to zero, we obtain

(20) $\displaystyle F_{v_{0}}(x)=\frac{x^{|v_{0}|}}{1-x}+\sum_{w\in
W}x^{|v_{0}|+1-w}\left(\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{j}\right)F_{w}(x).$

By assumption, each of the functions $\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{j}$ is rational, and hence by (20), $F_{v_{0}}(x)$
is a rational linear combination of the $F_{w}(x)$ with $w\in W$ of the
desired form and $W$ a finite set. By a similar argument (starting all sums
from $j=1$), the same holds for $F_{v_{1}}(x)$. Note that the set of all nodes
of length at most $m$ is given by $W^{\prime}=W\cup\\{v_{0}\\}$ since
$\mathcal{D}[B]$ is almost path-directed. Then $W^{\prime}$ is seen to meet
the conditions of Theorem 5 concerning nodes of length $m$, which implies the
stated result. ∎

######  Example 7.

Let $B=\\{123,312\\}$. Then Algorithm 1 outputs

$\displaystyle\mathcal{R}[B]$ $\displaystyle=$
$\displaystyle\\{12\rightsquigarrow 12\\}$ $\displaystyle\cup\\{k(k-1)\cdots
1\rightsquigarrow 12^{k},(k+1)k\cdots 1\mid k\geq 1\\}.$

See Figure 5 for the schematic of the corresponding directed graph which is
almost path-directed. One may verify that the parameters in this case are
$V^{\prime}=\\{v_{j}:=(j+2)(j+1)\cdots 1\mid j\geq 0\\}$ and $W=\\{1,12\\}$.
We also have that $\sum_{j\geq 0}\mathcal{M}[B]((j+2)(j+1)\cdots 1,12)x^{j}$
is the rational function $\sum_{j\geq 0}(j+2)x^{j}=\frac{2-x}{(1-x)^{2}}$
(with $\sum_{j\geq 0}\mathcal{M}[B]((j+2)(j+1)\cdots 1,1)x^{j}=0$). Therefore,
Theorem 6 implies that $G_{B}(x)$ is a rational generating function. Moreover,
it allows us to calculate $G_{B}(x)$ by solving the following system:

$\displaystyle F_{1}(x)=x+F_{12}(x)+F_{21}(x),$ $\displaystyle
F_{12}(x)=x^{2}+xF_{12}(x),$ $\displaystyle
F_{21}(x)=\frac{x^{2}}{1-x}+\frac{x(2-x)}{(1-x)^{2}}F_{12}(x).$

Hence,

$\displaystyle G_{B}(x)=F_{1}(x)=\frac{x}{1-x}+\frac{x^{2}}{(1-x)^{3}}.$

$1$$21$$12$$321$$4321$$\cdots$ Figure 5. Direct graph
$\mathcal{D}[\\{123,312\\}]$

######  Example 8.

Let $B=\\{123,2143\\}$. Applying Algorithm 1 yields

$\mathcal{R}[B]=\\{k(k-1)\cdots 1\rightsquigarrow 1^{k},(k+1)k\cdots 1\mid
k\geq 1\\}.$

Note that $\mathcal{D}[B]$ is an almost path-directed graph with parameters
$V^{\prime}=\\{v_{j}=(j+2)(j+1)\cdots 1\mid j\geq 0\\}$ and $W=\\{1\\}$. Thus,
Theorem 6 implies $G_{B}(x)$ is rational with associated linear system

$\displaystyle F_{1}(x)=x+xF_{1}(x)+F_{21}(x),$ $\displaystyle
F_{21}(x)=\frac{x^{2}}{1-x}+\frac{x^{2}(2-x)}{(1-x)^{2}}F_{1}(x).$

Hence,

$\displaystyle G_{B}(x)=F_{1}(x)=\frac{x-x^{2}}{1-3x+x^{2}}.$

######  Example 9.

Let $B=\\{123,312,21543\\}$. Then by Algorithm 1, we get

$\displaystyle\mathcal{R}[B]$ $\displaystyle=$
$\displaystyle\\{1\rightsquigarrow 12,21\\}$
$\displaystyle\cup\\{12\rightsquigarrow 12\\}$
$\displaystyle\cup\\{213\rightsquigarrow 2143\\}$
$\displaystyle\cup\\{j(j-1)\cdots 1\rightsquigarrow 12,213^{j-1},(j+1)j\cdots
1\mid j\geq 2\\}.$

Hence, $\mathcal{D}[B]$ is almost path-directed with parameters
$V^{\prime}=\\{v_{j}=(j+3)(j+2)\cdots 1\mid j\geq 0\\}$ and
$W=\\{1,12,21,213\\}$. We then have the following system of equations:

$\displaystyle F_{1}(x)=x+F_{12}(x)+F_{21}(x),$ $\displaystyle
F_{12}(x)=x^{2}+xF_{12}(x),$ $\displaystyle
F_{213}(x)=x^{3}+F_{2143}(x)=x^{3}+x^{4},$ $\displaystyle
F_{321}(x)=\frac{x^{3}}{1-x}+\frac{x^{2}}{1-x}F_{12}(x)+F_{213}(x)\sum_{j\geq
3}(j-1)x^{j-2}.$

Hence, solving this system for $F_{1}(x)$ gives

$\displaystyle G_{B}(x)=F_{1}(x)=\frac{x+x^{3}+x^{4}}{(1-x)^{2}}.$

In general, $\mathcal{D}[B]$ is almost path-directed for all pattern sets
$B=\\{123,312,21k(k-1)\cdots 3\\}$ where $k\geq 4$.

###  3.2. Backward path-directed graphs

We say $G$ is a backward path-direct graph if the set of nodes $V$ can be
partitioned as $V:=V^{\prime}\cup W$, where
$V^{\prime}:=\\{v_{0},v_{1},\ldots\\}$ and $|v_{i}|=i+m$ for all $i\geq 0$
with $m\geq 1$ fixed such that

  * •

The length of any node $w$ in $W=V\backslash V^{\prime}$ is at most $m$.

  * •

For each $j\geq 0$, $(v_{j},v_{i})\in E$ for all $i=0,1,\ldots,j-1,j+1$, with
all of these edges occurring once. Additionally, for some fixed integer $a\geq
0$, there are $a$ loops at the node $v_{i}$ for all $i\geq 0$.

  * •

All other edges $(c,d)\in E$ may be repeated (with $c=d$ possible) and are
such that $c$ or $d$ belongs to $W$ (possibly both).

In this context, $V^{\prime}$, $W$ and $a$ are called the parameters of the
backward path-directed graph $G$. In practice, we frequently have for each
$m^{\prime}>m$ that the node $v_{m^{\prime}-m}\in V^{\prime}$ is obtained from
$v_{0}$ by replacing $m$ with either $m(m+1)\cdots m^{\prime}$ or
$m^{\prime}(m^{\prime}-1)\cdots m$. A basic example of a backward path-
directed graph is $D[\\{123\\}]$, where the tree $\mathcal{T}[\\{123\\}]$ is
defined by the root $1$ and the set of succession rules $k(k-1)\cdots
1\rightsquigarrow 1,21,\ldots,(k+1)k\cdots 1$.

######  Example 10.

Let $B=\\{1243,1324,1342,1423,1432,2143,2413,2431,3142,4132\\}.$ Then the
Algorithm 1 describes the tree $\mathcal{T}[B]$ by the following succession
rules:

(21) $\displaystyle\mathcal{R}[B]=\\{1\rightsquigarrow 12,21\\}$
$\displaystyle\qquad\quad\cup\\{12\rightsquigarrow 21,123,132\\}$
$\displaystyle\qquad\quad\cup\\{21\rightsquigarrow 21,213,321\\}$
$\displaystyle\qquad\quad\cup\\{123\rightsquigarrow 21,123\\}$
$\displaystyle\qquad\quad\cup\\{213\rightsquigarrow 21,123\\}$
$\displaystyle\qquad\quad\cup\\{j(j-1)\cdots 1\rightsquigarrow
21,213,321,4321,\ldots,(j+1)j\cdots 1\mid j\geq 3\\}.$

One may verify that $\mathcal{D}[B]$ is backward path-directed with parameters
$V^{\prime}=\\{v_{j}=(j+3)(j+2)\cdots 1\mid j\geq 0\\}$,
$W=\\{1,12,21,123,132,213\\}$ and $a=1$.

$1$$21$$12$$321$$4321$$54321$$123$$132$$213$$\cdots$ Figure 6.
$D[\\{1243,1324,1342,1423,1432,2143,2413,2431,3142,4132\\}]$

To determine $G_{B}(x)$ when $\mathcal{D}[B]$ is backward path-directed, we
may apply Algorithm 1 to determine $\mathcal{T}[B]$ and then employ the
following result.

######  Theorem 11.

Let $1\notin B\subset S$ be any set of patterns. Suppose $\mathcal{D}[B]$ is a
backward path-directed graph with parameters $V^{\prime}$, $W$ and $a\geq 0$.
If $\sum_{j\geq 0}\mathcal{M}[B](v_{j},w)x^{j}$ is a rational generating
function for any $w\in W$, then $G_{B}(x)$ is a rational generating function
of $x$ and

$\displaystyle t_{0}:=\frac{1+x-ax-\sqrt{(1+x-ax)(1-3x-ax)}}{2x(1+x-ax)}.$

###### Proof.

We first determine an expression for the generating function $F_{v_{0}}(x)$.
Since $\mathcal{D}[B]$ is backward path-directed, formula (7) yields

$\displaystyle
F_{v_{j}}(x)=x^{|v_{0}|+j}+axF_{v_{j}}(x)+F_{v_{j+1}}(x)+x^{j+1}F_{v_{0}}(x)+\cdots+x^{2}F_{v_{j-1}}(x)$
(22) $\displaystyle\qquad\qquad+\sum_{w\in
W}\mathcal{M}[B](v_{j},w)x^{|v_{0}|+j+1-|w|}F_{w}(x),\qquad j\geq 0.$

Define $A(t):=\sum_{j\geq 0}F_{v_{j}}(x)t^{j}$. Multiplying both sides of
(3.2) by $t^{j}$, and summing over all $j\geq 0$, we obtain

$\displaystyle A(t)$ $\displaystyle=$
$\displaystyle\frac{x^{|v_{0}|}}{1-xt}+\sum_{w\in W}\left(\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{|v_{0}|+1-|w|}(xt)^{j}\right)F_{w}(x)$
$\displaystyle+\frac{x^{2}t}{1-xt}A(t)+axA(t)+\frac{A(t)-A(0)}{t},$

which is equivalent to

$\displaystyle\left(1-\frac{x^{2}t}{1-xt}-ax-\frac{1}{t}\right)A(t)$
$\displaystyle=$ $\displaystyle\frac{x^{|v_{0}|}}{1-xt}+\sum_{w\in
W}\left(\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{|v_{0}|+1-|w|}(xt)^{j}\right)F_{w}(x)$
$\displaystyle-\frac{1}{t}A(0).$

We apply the _kernel method_ (see, e.g., [12]) to the last equation and take
$t=t_{0}$, where $t_{0}$ satisfies
$1-\frac{x^{2}t_{0}}{1-xt_{0}}-ax-\frac{1}{t_{0}}=0$, to obtain

(23) $\displaystyle
F_{v_{0}}(x)=A(0)=\frac{x^{|v_{0}|}t_{0}}{1-xt_{0}}+t_{0}\sum_{w\in
W}\left(\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{|v_{0}|+1-|w|}(xt_{0})^{j}\right)F_{w}(x),$

with

$t_{0}=\frac{1+x-ax-\sqrt{(1+x-ax)(1-3x-ax)}}{2x(1+x-ax)}=1+ax+(a^{2}+1)x^{2}+\cdots.$

By (23) and the assumed rationality of $\sum_{j\geq
0}\mathcal{M}[B](v_{j},w)x^{j}$, we have that $F_{v_{0}}(x)$ is a linear
combination of $F_{v}(x)$ for $w\in W$ whose coefficients are rational in $x$
and $t_{0}$ with $W$ a finite set. Upon considering $B(t)=\sum_{j\geq
1}F_{v_{j}}(x)t^{j-1}$ and finding $B(0)=F_{v_{1}}(x)$, one can show that
$F_{v_{1}}(x)$ is a similar linear combination of $F_{v_{0}}(x)$ and the
$F_{w}(x)$ with $w\in W$. Upon substituting out this expression for
$F_{v_{1}}(x)$ as needed, it is seen that the nodes of length $m$ meet the
conditions of Theorem 5, but where the coefficients $c_{j}(x)$ are now
rational in $x$ and $t_{0}$. Thus, it follows that the generating function
$F_{1}(x)=G_{B}(x)$ is rational in $x$ and $t_{0}$. ∎

In the following example, we elaborate on how to apply Theorem 11 to Example
10.

######  Example 12.

It is easy to check that Theorem 11 applies to the case

$\displaystyle B=\\{1243,1324,1342,1423,1432,2143,2413,2431,3142,4132\\},$

and hence $G_{B}(x)$ is rational in $x$ and $t_{0}=C(x)$, where
$C(x)=\frac{1-\sqrt{1-4x}}{2x}=\sum_{n\geq 0}C_{n}x^{n}$ and
$C_{n}=\frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number. The set of
succession rules given by (21) can be written as the system of equations

$\displaystyle F_{1}(x)=x+F_{12}(x)+F_{21}(x),$ $\displaystyle
F_{12}(x)=x^{2}+xF_{21}(x)+F_{123}(x)+F_{132}(x),$ $\displaystyle
F_{21}(x)=x^{2}+xF_{21}(x)+F_{213}(x)+F_{321}(x),$ $\displaystyle
F_{132}(x)=x^{3},$ $\displaystyle
F_{123}(x)=x^{3}+x^{2}F_{21}(x)+xF_{123}(x),$ $\displaystyle
F_{213}(x)=x^{3}+x^{2}F_{21}(x)+xF_{123}(x),$ $\displaystyle F_{321}(x)=A(0).$

In addition, from $\mathcal{M}[B](v_{j},21)=\mathcal{M}[B](v_{j},213)=1$ for
all $j\geq 0$, have

$A(0)=\frac{x^{3}t_{0}}{1-xt_{0}}+\frac{x^{2}t_{0}}{1-xt_{0}}F_{21}(x)+\frac{xt_{0}}{1-xt_{0}}F_{213}(x).$

Hence, by solving the above system, we obtain
$G_{B}(x)=F_{1}(x)=x^{3}-1+C(x)$, as was shown in [15, Lemma 4.13].

Similarly, one may verify that Theorem 11 is applicable to the case

$\displaystyle B=\\{1234,1243,1324,1342,1423,2134,2314,2341,3124,4123\\}.$

In particular, it yields $G_{B}(x)=x^{3}-1+C(x)$, as was also shown in [15,
Lemma 4.13].

_Remark:_ Note that we may allow for nodes in $W$ in the definition above to
have length greater than $m$, provided it is required that $W$ be finite where
there are no edges $(a,b)$ such that $a\in W$ with $|a|>m$ and $b=v_{i}$ for
some $i\geq 2$. The same can be said in the case when $\mathcal{D}[B]$ is
almost path-directed.

###  3.3. Directed graph with $\alpha$-growing paths

For $\alpha\geq 1$, suppose that the set $V$ of nodes in $\mathcal{D}[B]$ for
some $B$ can be partitioned into sets $V^{(j)}$ for $1\leq j\leq\alpha$ and
$W$, where $V^{(j)}:=\\{v_{i}^{(j)}\ |\ i\geq 0\\}$ and $W$ is a finite set
with $W:=\\{w_{1},\ldots,w_{\ell}\\}$ for some $\ell\geq 1$. Then we will say
that $V$ has _$\alpha$ -growing paths_ if the following conditions are
satisfied:

  * •

$|v_{i}^{(1)}|=\cdots=|v_{i}^{(\alpha)}|=i+m$ for all $i\geq 0$ where $m\geq
1$ is fixed.

  * •

The length of any node in $W$ is at most $m$.

  * •

The edges that start with a member of $\cup_{j=1}^{\alpha}V^{(j)}$ are
dictated by the following succession rules:

$\displaystyle v_{k}^{(1)}\rightsquigarrow$ $\displaystyle
v_{0}^{(1)},v_{1}^{(1)},\ldots,v_{k-1}^{(1)},(v_{k}^{(1)})^{r_{1}},(w_{1})^{p_{1,1}^{(k)}},\ldots,(w_{\ell})^{p_{1,\ell}^{(k)}},$
$\displaystyle v_{k}^{(s)}\rightsquigarrow$ $\displaystyle
v_{0}^{(s^{\prime})},v_{1}^{(s^{\prime})},\ldots,v_{k-1}^{(s^{\prime})},(v_{k}^{(s^{\prime})})^{r_{s}},(v_{k+1}^{(s^{\prime})})^{r_{s,1}},(v_{k}^{(s)})^{r_{s,2}},$
$\displaystyle(w_{1})^{p_{s,1}^{(k)}},\ldots,(w_{\ell})^{p_{s,\ell}^{(k)}},\quad
1\leq s^{\prime}<s\leq\alpha-1,$ $\displaystyle
v_{k}^{(\alpha)}\rightsquigarrow$ $\displaystyle
v_{0}^{(\alpha^{\prime})},v_{1}^{(\alpha^{\prime})},\ldots,v_{k-1}^{(\alpha^{\prime})},(v_{k}^{(\alpha^{\prime})})^{r_{\alpha}},(v_{k}^{(\alpha)})^{r_{\alpha}^{\prime}},(v_{k+1}^{(1)})^{r_{\alpha,1}},\ldots,(v_{k+1}^{(\alpha)})^{r_{\alpha,\alpha}},$
$\displaystyle(w_{1})^{p_{\alpha,1}^{(k)}},\ldots,(w_{\ell})^{p_{\alpha,\ell}^{(k)}},\quad
1\leq\alpha^{\prime}<\alpha.$

  * •

All other edges start with a node in $W$.

Here, the non-negative exponents $r_{\alpha}^{\prime}$, $r_{i},r_{\alpha,i}$
for $i\in[\alpha]$, $r_{i,1},r_{i,2}$ for $i\in[2,\alpha-1]$ and
$p_{i,j}^{(k)}$ for $k\geq 0$, $1\leq i\leq\alpha$ and $1\leq j\leq\ell$ are
all assumed to be fixed. Further, the parameters $\alpha^{\prime}$ and
$s^{\prime}$ in the penultimate condition above are also fixed with
$s^{\prime}$ depending upon $s>1$. For each $1\leq j\leq\alpha$, it is often
the case that the node $v_{i}^{(j)}\in V^{(j)}$ for $i>0$ contains either the
subword $m(m+1)\cdots(m+i)$ or $(m+i)(m+i-1)\cdots m$.

We now consider two examples of sets of patterns whose corresponding directed
graphs have $\alpha$-growing paths.

12112$c_{3}$$b_{3}$$a_{3}$132312$c_{4}$$b_{4}$$a_{4}$$c_{5}$$b_{5}$$a_{5}$$\vdots$$\vdots$$\vdots$(2)
Figure 7. The label on the loop indicates that is repeated.

######  Example 13.

Let $B=\\{1324,1423,2143,2413,3124,3142,3412,4132,4213,4231,4312\\}.$ Then, by
Algorithm 1, $\mathcal{R}[B]$ is given by

$\displaystyle\mathcal{R}[B]$ $\displaystyle=$
$\displaystyle\\{1\rightsquigarrow 12,21\\}$
$\displaystyle\cup\\{12\rightsquigarrow 12,132,312\\}$
$\displaystyle\cup\\{21\rightsquigarrow 213,231,321\\}$
$\displaystyle\cup\\{132\rightsquigarrow 132^{2}\\}$
$\displaystyle\cup\\{a_{k}\rightsquigarrow a_{4},\ldots,a_{k},213,\quad k\geq
3\\}$ $\displaystyle\cup\\{b_{k}\rightsquigarrow
a_{4},\ldots,a_{k},b_{k},132,213,\quad k\geq 3\\}$
$\displaystyle\cup\\{c_{k}\rightsquigarrow
a_{4},\ldots,a_{k},a_{k+1},b_{k+1},c_{k+1},213,\quad k\geq 3\\},$

where

$\displaystyle a_{k}$ $\displaystyle=$
$\displaystyle(k-1)(k-2)k(k-3)(k-4)\cdots 1,$ $\displaystyle b_{k}$
$\displaystyle=$ $\displaystyle(k-1)k(k-2)(k-3)\cdots 1,$ $\displaystyle
c_{k}$ $\displaystyle=$ $\displaystyle k(k-1)\cdots 1.$

Here, $\mathcal{D}[B]$ (see Figure 7) has $3$-growing paths.

######  Example 14.

Let $B=\\{1243,1324,1342,1423,1432,2143,2413,2431,3142,3412,4132\\}$.
$\mathcal{R}[B]$ is given by

$\displaystyle\mathcal{R}[B]$ $\displaystyle=$
$\displaystyle\\{1\rightsquigarrow 12,21\\}$
$\displaystyle\cup\\{12\rightsquigarrow 123,132,312\\}$
$\displaystyle\cup\\{21\rightsquigarrow 213,231,321\\}$
$\displaystyle\cup\\{123\rightsquigarrow 123^{2}\\}$
$\displaystyle\cup\\{213\rightsquigarrow 123,213\\}$
$\displaystyle\cup\\{312\rightsquigarrow 123,312\\}$
$\displaystyle\cup\\{a_{k}\rightsquigarrow
a_{3},\ldots,a_{k-1},a_{k}^{2},213,\quad k\geq 3\\}$
$\displaystyle\cup\\{b_{k}\rightsquigarrow
a_{3},\ldots,a_{k},a_{k+1},b_{k+1},213,\quad k\geq 3\\},$

where

$\displaystyle a_{k}$ $\displaystyle=$ $\displaystyle(k-1)k(k-2)(k-3)\cdots
1,$ $\displaystyle b_{k}$ $\displaystyle=$ $\displaystyle k(k-1)\cdots 1.$

Here, $\mathcal{D}[B]$ (see Figure 8) has $2$-growing paths.

12112312123132$b_{3}$$a_{3}$213$b_{4}$$a_{4}$$b_{5}$$a_{5}$$\vdots$$\vdots$2222
Figure 8. The labels on four of the loops indicate their repetition as edges
in the graph.

If $B$ is a set of patterns whose directed graph $\mathcal{D}[B]$ has
$\alpha$-growing paths, we may apply Algorithm 1 and the following result to
deduce the rationality of $G_{B}(x)$.

######  Theorem 15.

Let $1\notin B\subset S$ be any set of patterns whose corresponding
$\mathcal{D}[B]$ has $\alpha$-growing paths with
$V^{(1)},\ldots,V^{(\alpha)},W$ as described above. If the generating function
given by $\sum_{j\geq 0}\mathcal{M}[B](v_{j}^{(i)},w)x^{j}$ is rational for
each $i\in[\alpha]$ and $w\in W$, then $G_{B}(x)$ is rational.

###### Proof.

We prove the statement in the case when $|\alpha|\geq 3$, as the adjustments
required for the $\alpha=1,2$ cases will be apparent. Note that
$\\{v_{1}^{(1)},v_{1}^{(2)},\ldots,v_{1}^{(\alpha)}\\}$ comprises the set of
all nodes in $V$ of length $m+1$. By Theorem 5, it suffices to show that
$F_{v_{1}^{(i)}}(x)$ for each $i\in[\alpha]$ is a rational linear combination
of the $F_{v}(x)$ for $v\in V$ with $|v|\leq m$ wherein the corresponding
coefficients all vanish at $x=0$. In order to aid in doing so, we define the
generating function $A_{i}(t)=\sum_{k\geq 0}F_{v_{k}^{(i)}}(x)t^{k}$ for
$1\leq i\leq\alpha$. From the succession rules, we have

(24)
$\left(1-r_{1}x-\frac{x^{2}t}{1-xt}\right)A_{1}(t)=\frac{x^{m}}{1-xt}+\sum_{w\in
W}x^{m+1-|w|}\left(\sum_{k\geq
0}\mathcal{M}[B](v_{k}^{(1)},w)(xt)^{k}\right)F_{w}(x),$
$\displaystyle\left(1-r_{s,2}x\right)A_{s}(t)$
$\displaystyle=\frac{x^{m}}{1-xt}+\left(\frac{x^{2}t}{1-xt}+\frac{r_{s,1}}{t}+r_{s}x\right)A_{s^{\prime}}(t)-r_{s,1}\frac{A_{s^{\prime}}(0)}{t}$
(25) $\displaystyle\quad+\sum_{w\in W}x^{m+1-|w|}\left(\sum_{k\geq
0}\mathcal{M}[B](v_{k}^{(s)},w)(xt)^{k}\right)F_{w}(x),\quad 2\leq
s\leq\alpha-1,$

and

$\displaystyle\left(1-r_{\alpha}^{\prime}x\right)A_{\alpha}(t)$
$\displaystyle=\frac{x^{m}}{1-xt}+\left(\frac{x^{2}t}{1-xt}+r_{\alpha}x\right)A_{\alpha^{\prime}}(t)+\sum_{i=1}^{\alpha}r_{\alpha,i}\left(\frac{A_{i}(t)-A_{i}(0)}{t}\right)$
(26) $\displaystyle\quad+\sum_{w\in W}x^{m+1-|w|}\left(\sum_{k\geq
0}\mathcal{M}[B](v_{k}^{(\alpha)},w)(xt)^{k}\right)F_{w}(x).$

By (24), we have that $A_{1}(t)$ is a linear combination of the $F_{w}(x)$ for
$w\in W$ whose coefficients $c_{j}(x,t)$ are rational in $x$ and $t$ and
satisfy $c_{j}(0,t)=0$ for all $j$ and each fixed $t$. Then by an induction
argument using (25), we have that $A_{s}(t)$ for $2\leq s\leq\alpha-1$ also
admits of such a form. Note that $r_{\alpha,i}\in\\{0,1\\}$ for $i\in[\alpha]$
since there is at most one way to produce a certain offspring of length $k+1$
from a parent of length $k$. If $r_{\alpha,\alpha}=0$, then (26) implies, like
in the prior cases, that $A_{\alpha}(t)$ admits of this form too. If
$r_{\alpha,\alpha}=1$, then taking $t=1$ in (26), and solving for
$A_{\alpha}(0)$, implies $A_{\alpha}(0)$ has the desired form and hence
$A_{\alpha}(t)$ does as well. Thus, for each $i\in[\alpha]$, we have in
particular that $F_{v_{1}^{(i)}}(x)=\frac{A_{i}(t)-A_{i}(0)}{t}\mid_{t=0}$ is
a rational linear combination of the $F_{v}(x)$ with $|v|\leq m$ of the form
stated above, which completes the proof. ∎

######  Example 16.

As shown in [15] using different techniques, there are exactly $10$ sets of
patterns of size 11 consisting of members of $S_{4}$ where the FinLabel
algorithm fails to terminate in a finite number of iterations, and they are
given by

$\displaystyle B_{1}=$
$\displaystyle\\{1324,1423,2143,2413,3124,3142,3412,4132,4213,4231,4312\\},$
$\displaystyle B_{2}=$
$\displaystyle\\{1324,1423,2143,2413,3124,3142,4123,4132,4213,4231,4312\\},$
$\displaystyle B_{3}=$
$\displaystyle\\{1324,1423,2143,2413,3124,3142,3412,4123,4132,4213,4231\\},$
$\displaystyle B_{4}=$
$\displaystyle\\{1324,1423,2143,3124,3142,3412,4123,4132,4213,4231,4312\\},$
$\displaystyle B_{5}=$
$\displaystyle\\{1324,1423,2143,2413,3124,3142,3412,4123,4132,4231,4312\\},$
$\displaystyle B_{6}=$
$\displaystyle\\{1243,1324,1342,1423,1432,2143,2413,3142,3412,4132,4231\\},$
$\displaystyle B_{7}=$
$\displaystyle\\{1324,1423,2143,2413,3124,3142,3412,4123,4132,4213,4312\\},$
$\displaystyle B_{8}=$
$\displaystyle\\{1324,1423,2413,3124,3142,3412,4123,4132,4213,4231,4312\\},$
$\displaystyle B_{9}=$
$\displaystyle\\{1243,1324,1342,1423,1432,2143,2413,2431,3142,3412,4132\\},$
$\displaystyle B_{10}=$
$\displaystyle\\{1234,1243,1324,1342,1423,2134,2314,2341,3124,3412,4123\\}.$

The set $B_{1}$ was discussed in Example 13, where $\mathcal{D}[B_{1}]$ was
seen to have $3$-growing paths with $V^{(1)}=\\{(k-1)(k-2)k(k-3)(k-4)\cdots
1\mid k\geq 4\\}$, $V^{(2)}=\\{(k-1)k(k-2)(k-3)\cdots 1\mid k\geq 4\\}$,
$V^{(3)}=\\{k(k-1)\cdots 1\mid k\geq 4\\}$ and
$W=\\{1,12,21,132,213,231,312,321\\}$. Note that $\sum_{v\in W}\sum_{j\geq
0}\mathcal{M}[B](v_{j}^{(s)},v)x^{j}$ equals $(1-x)^{-1}$ when $s=1,3$ and
$2(1-x)^{-1}$ when $s=2$. Hence, Theorem 15 implies $G_{B_{1}}(x)$ is a
rational generating function. As noted in the following table, all other cases
also have $\alpha$-growing paths. One can readily show that Theorem 15 is
applicable in each of these cases as well. Additionally, following the same
process as the one given in Example 9, one can calculate $G_{B_{s}}(x)$ in all
cases, which we omit here for the sake of brevity.

$B_{s}$ |  $\alpha$-growing paths
---|---
$B_{1}$,$B_{2}$, $B_{3}$, $B_{4}$, $B_{5}$, $B_{10}$ | 3
$B_{6}$, $B_{7}$ | 4
$B_{8}$, $B_{9}$ | 2

We conclude by mentioning some further applications of the preceding results.
Algorithm 1 together with Theorems 6 and 15 have been applied to many sets $B$
consisting of members of $S_{4}$ where $3\leq|B|\leq 12$. In our study, we
have shown that there are $48$ sets of patterns of size ten for which the
FinLabel algorithm fails to find $G_{B}(x)$ in a finite number of iterations.
From these cases, exactly $10$ (resp. $19$, $10$, $2$ and $3$) cases have
directed graphs with $2$-growing (resp. $3$-, $4$-, $5$\- and $6$-) paths. In
other words, with the exception of four cases, Theorem 15 (and its proof)
provides the solution to the problem of finding the generating function
$G_{B}(x)$ when $|B|=10$. Interestingly enough, Theorem 11 yields $G_{B}(x)$
for the four remaining cases, two of which were treated in Example 12.

## References

  * [1] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou Beauchamps, Generating functions for generating trees, _Discrete Math._ 246:1-3 (2002), 29–55.
  * [2] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, A methodology for plane tree enumeration, _Discrete Math._ 180:1-3 (1998), 45–64.
  * [3] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, _J. Difference Equ. Appl._ 5:4-5 (1999), 435–490.
  * [4] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, From Motzkin to Catalan permutations, _Discrete Math._ 217:1–3 (2000), 33–49.
  * [5] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, _Discrete Math. Theor. Comput. Sci._ 4:1 (2000), 31–44.
  * [6] A. M. Baxter, Algorithms for permutation statistics, Ph.D. thesis, Rutgers, 2011.
  * [7] A. M. Baxter, Refining enumeration schemes to count according to permutation statistics, _Electron. J. Combin._ 21:2 (2014), P2.50.
  * [8] A. Baxter, B. Nakamura and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes, _Advances in Combinatorics: Waterloo Workshop in Computer Algebra,_ W80, May 26–29, 2011.
  * [9] A. M. Baxter and L. K. Pudwell, Enumeration schemes for vincular patterns, _Discrete Math._ 312:10 (2012), 1699–1712.
  * [10] T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, _Discrete Math._ 204 (1999), 119–128.
  * [11] F. R. K. Chung, R. L. Graham, V .E. Hoggatt, Jr., and M. Kleiman, The number of Baxter permutations, _J. Combin. Theory Ser. A_ 24:3 (1978), 382–394.
  * [12] Q. Hou and T. Mansour, Kernel method and linear recurrence system, J. Comput. Appl. Math. 216(1) (2008), 227–242.
  * [13] S. Kitaev, _Patterns in Permutations and Words_ , Monographs in Theoretical Computer Science, Springer, 2011.
  * [14] D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, _Discrete Math._ 268:1-3 (2003), 171–183.
  * [15] T. Mansour and M. Schork, Wilf classification of subsets of four letter patterns, _J. Combin. Number Theory_ 8:1 (2016), 1–129.
  * [16] J. Noonan and D. Zeilberger, The enumeration of permutations with a prescribed number of forbidden patterns, _Adv. in Appl. Math._ 17 (1996), 381–407.
  * [17] L. Pudwell, Enumeration schemes for words avoiding permutations, in _Permutation Patterns: London Math. Soc. Lecture Notes Ser._ , Vol. 376, Cambridge University Press (2010), 193–211.
  * [18] R. Simion and F. W. Schmidt, Restricted permutations, _European J. Combin._ 6 (1985), 383–406.
  * [19] R. P. Stanley, _Enumerative Combinatorics,_ Vol. 1, Cambridge University Press, 1997.
  * [20] V. Vatter, Enumeration schemes for restricted permutations, _Combin., Probab. and Comput._ 17:1 (2005), 137–159.
  * [21] V. Vatter, Finitely labeled generating trees and restricted permutations, _J. Symbolic Comput._ 41 (2006), 559–572.
  * [22] J. West, Generating trees and the Catalan and Schröder numbers, _Discrete Math._ 146 (1996), 247–262.
  * [23] J. West, Generating trees and forbidden subsequences, _Discrete Math._ 157 (1996), 363–374.
  * [24] D. Zeilberger, Enumeration schemes, and more importantly, their automatic generation, _Ann. Comb._ 2 (1998), 185–195.