Generating trees for partitions and permutations with
no *k*-nestings†

Sophie Burrill<fnref n="1" /> Sergi Elizalde<fnref n="2" /> Marni Mishna<fnref n="1" /> Lily Yen<fnref n="1" />,<fnref n="3" />

**Abstract.** We describe a generating tree approach to the enumeration and exhaustive generation of *k*-nonnesting set partitions and permutations. Unlike previous work in the literature using the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with *k* as a parameter.

**Résumé.** Nous décrivons une approche, basée sur l'utilisation d'arbres de génération, pour l'énumération et la génération exhaustive de partitions et permutations sans *k*-emboîtement. Contrairement aux travaux antérieurs qui reposent sur un lien entre ces objets, tableaux de Young et familles de chemins dans des treillis, notre approche traite directement partitions et diagrammes de permutations. Nous fournissons des équations fonctionnelles explicites pour les séries génératrices, avec *k* en tant que paramètre.

**Keywords:** nonnesting, partition, permutation, generating tree

# 1 Introduction

Arc annotated sequences, also called arc diagrams, are structures that have proved particularly useful for encoding a variety of combinatorial classes. An arc annotated sequence is a row of increasingly labelled vertices, from 1 to *n*, with some collection of arcs between them, restricted according to the object. Many combinatorial objects, including matchings, set partitions, labelled graphs, RNA substructures and permutations, have straightforward descriptions using arc annotated sequences [CDD$^+$07, CHR09, Cor07, dM06, Eli11]. Two important patterns that occur in arc annotated sequences, and thus can be defined for each of the combinatorial objects that these sequences represent, are nestings and crossings. A set of *k* arcs forms a *k*-nesting (respectively *k*-crossing) if each of the $\binom{k}{2}$ pairs of arcs nest (resp. cross). Figure 1 illustrates a 3-nesting and a 3-crossing. Precise definitions of *k*-nestings in set partitions and permutations are given in Sections 2.2 and 5, respectively.

A diagram is *k*-nonnesting if it contains no *k*-nesting, and it is *k*-noncrossing if it contains no *k*-crossing. Krattenthaler [Kra06] and Chen, Deng, Du, Stanley and Yan [CDD$^+$07] proved that *k*-nonnesting

<footnote n="1">¹Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada</footnote>

<footnote n="2">²Department of Mathematics, Dartmouth College, Hanover, NH, USA</footnote>

<footnote n="3">³Department of Mathematics and Statistics, Capilano University, North Vancouver, BC, Canada</footnote>

<footnote>†The authors are grateful to the NSERC Discovery Grant Program and the Pacific Institute of Mathematical Sciences (Canada) for facilitating this collaboration. The second author was also partially supported by NSF grant DMS-1001046.</footnote>
<figure><img src="image_1.png" /><figcaption>Fig. 1: A 3-nesting and a 3-crossing.</figcaption></figure>

partitions are equinumerous to *k*-noncrossing partitions bijectively using growth diagrams or Young tableaux as an intermediate object. In fact, they proved stronger distribution results, both for partitions and for matchings. This work was extended by de Mier [dM07] to show that for embedded labelled graphs with certain restrictions, the number of *k*-noncrossing ones is the same as the number of *k*-nonnesting ones. Most recently, Burrill, Mishna and Post [BMP10] proved analogous results for permutations.

For most classes described by an arc annotated sequence, the following general enumerative question is open: *How many elements of class C of size n do not contain any k-nesting?* The reader can replace class C by matchings, set partitions, labelled graphs, or permutations. For all of the above classes, this question is equivalent to counting the number of *k*-noncrossing objects. The matching case was resolved by Chen et al. [CDD+07], giving rise to lovely formulas. The set partition case was addressed by Bousquet-Mélou and Xin [BMX07], who found explicit results in the case of *k* = 3. Their method passes through Young tableaux and restricted lattice paths to deliver functional equations, which are then analyzed using the kernel method. They showed that the generating function of 3-noncrossing set partitions is D-finite —i.e., it satisfies a linear differential equation with polynomial coefficients—, and hypothesized that this is not the case for larger *k*:

**Conjecture 1.1 (BMX07)** *For every k > 3, the generating function of k-noncrossing set partitions is not D-finite.*

Mishna and Yen [MY] determined functional equations for *k*-nonnesting set partitions, and described a process for isolating coefficients, giving additional evidence for Conjecture 1.1. To date in the literature, there is only very limited enumerative information on *k*-nonnesting permutations for *k* ≥ 3. The case *k* = 2 is easy, since 2-nonnesting permutations are those that avoid the pattern 321, that is, those without decreasing subsequences of length 3, and thus they are counted by the Catalan numbers. Note that, in general, *k*-nonnesting permutations are not closed under pattern containment: the permutation 564312 is 3-nonnesting, but it contains the pattern 54312, which is not a 3-nonnesting permutation.

## 1.1 Main results

Our main contribution is a generating tree approach which passes through neither Young tableaux nor lattice paths, and can be used to describe both *k*-nonnesting set partitions and *k*-nonnesting permutations, for arbitrary *k*. The generating tree construction leads to a functional equation for the generating function which provides us with information about the corresponding series. We describe generic functional equations in a number of variables which grows with *k*.

The key innovation in this study is a new class of structures that are essentially arc diagrams “under construction”, which we call *open arc diagrams*. These are arc diagrams in which we allow semi-arcs with a single end-point. Usual arc annotated sequences form the subclass of diagrams with no semi-arcs. Aside from nestings, it is relevant to consider *future nestings* in open arc diagrams. We describe how to identify both patterns in a generating tree construction.

This extended abstract is organized as follows. We describe open arc diagrams and their generating trees in Section 2. In Section 3 we give the first application of this construction to determine a set of functional equations to enumerate 3-nonnesting set partitions. In Section 4 we give the construction for
$k$-nonnesting partitions for general $k$, and we also consider partitions that avoid a related pattern called an enhanced $k$-nesting. In Section 5, using similar ideas and combining the descriptions for usual and enhanced nestings in set partitions, we construct a generating tree for $k$-nonnesting permutations and obtain analogous functional equations.

## 2 Open arc diagrams: a generalization of set partitions

An arc diagram of size $n$ is an embedded graph with vertices 1 to $n$ drawn in an increasing row. We take the convention of labelling our diagrams from left to right, so we can refer to left and right end-points of an arc. We first focus on the case of arc diagrams representing set partitions, which we call *partition diagrams* for short. In this case, the arcs are always drawn above the vertices, and the partition block $\{a_1, a_2, \dots, a_j\}$, where $a_1 < a_2 < \dots < a_j$, is represented by the arcs $(a_1, a_2), (a_2, a_3), \dots, (a_{j-1}, a_j)$. Figure 2(a) shows the diagram of a partition of $\{1, \dots, 9\}$.

<figure><img src="image_2.png" /><figcaption>Fig. 2: (a) The arc diagram representation of the partition $\{1, 3, 5\}\{2\}\{4, 6\}\{7, 8, 9\}$. (b) An open partition diagram.</figcaption></figure>

The vertices of a partition diagram can be of four types: *fixed points*, *openers*, *closers* and *transitories*. A fixed point has no incident edges, an opener has degree one and is the left end-point of an arc, a closer has degree one and is the right end-point of an arc, and a transitory vertex has degree two and is the right end-point of one arc and the left end-point of another. In Figure 2(a), the vertex labelled 2 is a fixed point; the vertices labelled 1, 4, and 7 are openers; vertices 5, 6, and 9 are closers; and 3 and 8 are transitory.

We generalize partition diagrams by allowing two additional vertex types: *semi-openers* and *semi-transitories*. These vertices are incident to *semi-arcs* with no right end-point, which we also call *open arcs*. We call these generalized diagrams *open partition diagrams*. To ensure a standard representation, we shall continue the semi-arcs to a vertical line to the right of vertex $n$, and retain their order, not allowing the semi-arcs to intersect. We denote the semi-arc with left end-point $i$ by $(i, *)$. Figure 2(b) displays an example. We view open partition diagrams as ancestors to proper set partitions, in a process which incrementally adds vertices in numerical order, possibly closing semi-arcs and/or opening new ones.

An open partition diagram could also be viewed as a set partition in which each block is coloured one of two colours: one for proper blocks, and another for blocks ending with a semi-arc. For example, the diagram in Figure 2(b) represents the bi-coloured partition $\{\mathbf{1}, \mathbf{3}\}, \{\mathbf{5}\}, \{\mathbf{7}\}, \{\mathbf{2}\}, \{\mathbf{4}, \mathbf{6}\}, \{\mathbf{8}, \mathbf{9}\}$. As such, it is easy to determine that the exponential generating function for open partition diagrams is $e^{2e^{-z^2}}$.

### 2.1 *Generating tree for open partition diagrams*

The method of generating trees was first introduced by West for the study of Catalan and Schröder numbers [Wes95] and pattern-avoiding permutations [Wes96]. The method was later expanded [BBMD+02] to provide a description of the tree, called a *rewriting rule*, to facilitate the translation to a functional equation. Most recently, Bousquet-Mélou [BM11] applied generating trees to enumerate permutations with no long monotone subsequences.
To construct a generating tree for our purpose, we describe how to create open partition diagrams of size $n$ from one of size $n-1$. First, begin with the root node representing the empty set. There are four different possibilities for the type of vertex $n$ when it is added to an open partition diagram of size $n-1$: (1) fixed point, (2) semi-opener, (3) semi-transitory (provided there is an available semi-arc), (4) closer (provided there is an available semi-arc). For example, the diagram in Figure 2(b) generates the 8 diagrams in Figure 3, which we call its children.

We remark that, by reducing the possible types of vertices, it is easy to adapt this construction to generate involutions (by disallowing semi-transitory vertices) and perfect matchings (by further disallowing fixed points). The ideas in Sections 3 and 4 can then be adapted to *k*-nonnesting involutions and matchings.

<figure><img src="image_3.png" /><figcaption>Fig. 3: The open partition diagram for $\pi$ and its children.</figcaption></figure>

The number of children that can be generated by adding a vertex to the diagram depends only upon the number of semi-arcs. Suppose a diagram has *m* semi-arcs (coming from either semi-opener or semi-transitory vertices). Here are the possible ways to generate its children, depending on the type of the vertex that is added: (1) fixed point: one child with *m* semi-arcs; (2) semi-opener: one child with *m* + 1 semi-arcs; (3) semi-transitory: *m* children, each with *m* semi-arcs; (4) closer: *m* children, each with *m* - 1 semi-arcs. This sums to a total of 2*m* + 2 children for any diagram with *m* semi-arcs.

In Sections 3 and 4 we will modify this generating tree in order to incorporate the *k*-nonnesting constraint. We will use the notion of future nestings, which we define next.

## 2.2 Nestings and future nestings

Recall that a *k*-nesting in a partition diagram is a set of *k* mutually nesting arcs, i.e., arcs $(i_1, j_1), \dots, (i_k, j_k)$ such that $i_1 < i_2 < \dots < i_k < j_k < j_{k-1} < \dots < j_1$. To incorporate the nesting constraint to the generating tree, we generalize the notion of *k*-nestings to open partition diagrams. We define a (regular) *k*-nesting in an open partition diagram to be a set of *k* mutually nesting (closed) arcs. To handle semi-arcs, we introduce the concept of a *future k-nesting*, which is a set of *k* − 1 arcs that form a regular *k* − 1-nesting together with a single semi-arc whose left end-point is to the left of first end-point of the *k* − 1-nesting (see Figure 4(a)). As its name suggests, any proper set partition that is a descendant of a diagram with a future *k*-nesting necessarily contains a *k*-nesting, because the semi-arc in the future *k*-nesting eventually has to close. Conversely, every partition diagram with a *k*-nesting has an ancestor with a future *k*-nesting, namely one where all but the outermost arc in the *k*-nesting have been closed. Note that having multiple semi-arcs above a *k* − 1-nesting does not guarantee *l*-nestings in its descendants for *l* > *k*.

We say that an open partition diagram is *k*-nonnesting if it contains neither regular nor future *k*-nestings. To enumerate *k*-nonnesting partitions, our strategy is to generate *k*-nonnesting open partition diagrams.
<figure><img src="image_4.png" /><figcaption>Fig. 4: (a) A future 4-nesting. (b) An open partition diagram with label [4, 2].</figcaption></figure>

Of these diagrams, *k*-nonnesting set partitions correspond to the ones that have no semi-arcs. As such, we are generating more objects than we require, but we can specialize the generating function for the more general class of objects to obtain the generating function for the subset of *k*-nonnesting partitions. Mishna and Yen [MY] constructed a different tree that generates *k*-nonnesting set partitions directly without producing superfluous objects. However, the present construction has two important advantages over theirs: it can handle the enhanced case (see Section 4.1), and it can be extended to *k*-nonnesting permutations (see Section 5), matchings and involutions.

## 3 3-nonnesting set partitions

The case of 3-nonnesting set partitions forms the template for the general case for both partitions and permutations; therefore, we first construct a generating tree for 3-nonnesting open partition diagrams, then we derive a functional equation for the corresponding generating function.

To each 3-nonnesting open partition diagram, we associate a label [*i*, *j*], where *i* is the number of semi-arcs in the diagram, and *j* is the number of semi-arcs which belong to a future 2-nesting (equivalently, the number of semi-arcs above at least one closed arc). For example, in Figure 4(b), the arrows indicate the semi-arcs which are in future 2-nestings. Note that semi-arcs contributing to future 2-nestings are always above the other semi-arcs which do not contribute to future 2-nestings. Since among the four semi-arcs there are two with this property, we associate to this diagram the label [4, 2]. Now consider a child of this diagram where the added vertex 12 is a closer or semi-transitory. If the added vertex closed the semi-arc originating from vertex 7, then (7, 12), (8, 9) and (3, *) would form a future 3-nesting. This is precisely what we are trying to avoid. On the other hand, vertex 12 can close any of the other semi-arcs without creating a future 3-nesting. Additionally, no such nesting is created if the added vertex 12 is a fixed point or a semi-opener.

Suppose now that $\pi$ is an arbitrary 3-nonnesting open partition diagram. To avoid creating a future 3-nesting when we add a new vertex to $\pi$, the only restriction is that if the added vertex is a closer or semi-transitory, it must not close a semi-arc of a future 2-nesting of $\pi$, except if it is the very top semi-arc. Note also that since $\pi$ does not contain future 3-nestings, the addition of a vertex cannot create a regular 3-nesting.

Next we show how to do the bookkeeping on the labels to incorporate this restriction. A fixed point or a semi-opener added to a diagram $\pi$ has no effect on whether or not a semi-arc is in a future 2-nesting. Suppose now that a closer vertex is added to $\pi$. If this vertex closes a semi-arc not belonging to a future 2-nesting of $\pi$, all the semi-arcs above it are now in a future 2-nesting, even if they were not in one of $\pi$, and the semi-arcs below it are unaffected. If the new vertex closes a semi-arc belonging to a future 2-nesting of $\pi$, then it must be the top semi-arc, and in this case, the number of semi-arcs is reduced by one, as is the number of semi-arcs in a 2-nesting. A semi-transitory vertex added to $\pi$ behaves exactly like a closer, except that a new semi-arc, not belonging to any future 2-nesting, is created.
The number of children and their labels depend only upon the label of the parent. Indeed, suppose the parent is a diagram with label $[i, j]$. Adding a fixed point produces a child with label $[i, j]$, while adding a semi-opener we get a child labelled $[i+1, j]$. Assuming that $i \ge 1$, adding a closer yields $i-j$ children with labels ranging from $[i-1, j]$ to $[i-1, i-1]$, corresponding to closing the semi-arcs not belonging to future 2-nestings, and, if $j > 0$, an additional child with label $[i-1, j-1]$, corresponding to closing the top semi-arc in a future 2-nesting. Adding a semi-transitory vertex has a similar effect to adding a closer, but the first part of the label in the children is $i$ instead of $i-1$. This description leads to the following theorem about the generating tree scheme.

**Theorem 3.1** Let $\Pi^{(2)}$ be the set of 3-nonnesting open partition diagrams. To each diagram, associate the label $\ell(\pi) = [i, j]$ as defined above. Then the number of diagrams in $\Pi^{(2)}$ of size $n$ is the number of nodes at level $n$ in the generating tree with root label $[0, 0]$, and succession rule given by

$$ \begin{array}{l@{\qquad}l} [i, j], & \text{(fixed point)} \\ [i+1, j], & \text{(semi-opener)} \\ [i, j] \to [i, j], [i, j+1], \dots, [i, i-1], & \text{(semi-transitory)} \\ [i-1, j], [i-1, j+1], \dots, [i-1, i-1], & \text{(closer)} \\ [i, j-1], [i-1, j-1]. & \text{(semi-transitory and closer when } j > 0) \end{array} $$

The number of 3-nonnesting set partitions of $\{1, \dots, n\}$ is equal to the number of nodes with label $[0, 0]$ at level $n$.

It is not hard (see [BEMY] for details) to translate the generating tree from Theorem 3.1 into a functional equation for the generating function $A(u, v; z) = \sum A_{i,j}(n)u^i v^j z^n$, where $A_{i,j}(n)$ is the number of 3-nonnesting open partition diagrams at level $n$ of the tree with label $[i, j]$.

**Corollary 3.2** The generating function $A(u, v) = A(u, v; z)$ for 3-nonnesting open partition diagrams, with variables $u$ and $v$ marking values $i$ and $j$ in the label, respectively, and $z$ marking number of vertices, satisfies the functional equation

$$ A(u, v) = 1 + z \left( (1+u)A(u, v) + \left(1 + \frac{1}{u}\right) \left( \frac{A(u, v) - A(uv, 1)}{1-v} + \frac{A(u, v) - A(u, 0)}{v} \right) \right). $$

By extracting the coefficient of $z^n$ from both sides of Corollary 3.2, we obtain $A_{i,j}(n)$ in terms of the other $A_{i,j}(n-1)$, and thus gives a cubic time and quadratic space algorithm for getting $A_{0,0}(n)$.

# 4 k-nonnesting set partitions

Here we generalize the construction from Section 3 to arbitrary $k$. It will be convenient to shift the index and consider $k+1$-nonnesting partitions. Suppose that $\pi$ is an $k+1$-nonnesting open partition diagram. To avoid creating a future $k+1$-nesting when adding a new vertex to $\pi$, the only restriction is that, if the added vertex is a closer or semi-transitory, it is not allowed to close a semi-arc belonging a future $k$-nesting of $\pi$, unless it is the very top semi-arc. Note also that since $\pi$ does not contain future $k+1$-nestings, the addition of a vertex cannot create a regular $k+1$-nesting.
In order to keep track of future *k*-nestings, we also need to keep track of future *j*-nestings for *j* < *k*. We define the *nesting index* of a semi-arc to be the maximum *j* such that there is a *j*-nesting beneath it. Equivalently, the nesting index of a semi-arc is the largest *j* such that the semi-arc is in a future *j* + 1-nesting. We will keep track of the distribution of nesting indices on the semi-arcs, updating this distribution every time we add a vertex, and avoiding the appearance of future *k* + 1-nestings.

To each $k+1$-nonnesting open partition diagram $\pi$ we associate a label with $k$ components $\ell(\pi) = [s_0, \dots, s_{k-1}]$, where $s_i$ is defined to be the number of semi-arcs of nesting index greater than or equal to $i$. Figure 5 contains an example. Remark that $s_0$ is the total number of semi-arcs, and $s_{k-1}$ is the number of semi-arcs in future $k$-nestings. For $k=2$, this labelling is consistent with Section 3. Furthermore, note that, by definition, $s_0 \ge s_1 \ge \dots \ge s_{k-1} \ge 0$. The label of the empty partition is $[0, \dots, 0]$, since it contains no semi-arcs.

<figure><img src="image_5.png" /><figcaption>Fig. 5: An open partition diagram with label [5, 4, 2, 1]. The nesting index of each semi-arc is labelled in italics.</figcaption></figure>

As before, the labels of the children of a given node depend only on its label. When a semi-arc is closed, the effect on the labels is determined by the fact that the nesting index of those semi-arcs above it which had the same nesting index increases by one. This allows us to describe a succession rule for the generating tree, summarized in the following theorem, which generalizes Theorem 3.1.

**Theorem 4.1** Let $\Pi^{(k)}$ be the set of $k+1$-nonnesting open partition diagrams. To each diagram, associate the label $\ell(\pi) = [s_0, \dots, s_{k-1}]$ as described above. Then, the number of diagrams in $\Pi^{(k)}$ of size $n$ is the number of nodes at level $n$ in the generating tree with root label $[0, \dots, 0]$, and succession rule given by

$$ [s_0, s_1, \dots, s_{k-1}] \rightarrow [s_0, s_1, \dots, s_{k-1}], \qquad (1) $$

$$ [s_0 + 1, s_1, \dots, s_{k-1}], \qquad (2) $$

$$ [s_0, s_1 - 1, \dots, s_{j-1} - 1, i, s_{j+1}, \dots, s_{k-1}], \quad \text{for } 1 \le j \le k-1, \text{ and } s_j \le i \le s_{j-1} - 1 \qquad (3) $$

$$ [s_0 - 1, s_1 - 1, \dots, s_{j-1} - 1, i, s_{j+1}, \dots, s_{k-1}], \quad \text{for } 1 \le j \le k-1, \text{ and } s_j \le i \le s_{j-1} - 1 \qquad (4) $$

$$ [s_0, s_1 - 1, \dots, s_{k-1} - 1], [s_0 - 1, s_1 - 1, \dots, s_{k-1} - 1], \quad \text{if } s_{k-1} > 0. \qquad (5) $$

**Proof:** The labels arise from adding the following kinds of vertices: (1) a fixed point, (2) a semi-opener, (3) a semi-transitory, (4) a closer, (5) a semi-transitory or a closer that closes the top semi-arc, if the diagram had a future *k*-nesting. $\square$

**Corollary 4.2** The generating function for $k+1$-nonnesting open partition diagrams, with variable $v_i$ marking value $s_i$ in the label, and $z$ marking number of vertices, denoted $Q = Q(v_0, v_1, \dots, v_{k-1}) =$
$Q(v_0, v_1, \dots, v_{k-1}; z)$, satisfies the functional equation

$$Q = 1 + z(1 + v_0) \left( Q + \frac{1}{v_0 v_1 \dots v_{k-1}} (Q - Q(v_0, v_1, \dots, v_{k-2}, 0)) \right. \\ \left. + \sum_{j=1}^{k-1} \frac{1}{v_0 v_1 \dots v_{j-1} (1 - v_j)} (Q - Q(v_0, \dots, v_{j-2}, v_{j-1} v_j, 1, v_{j+1}, \dots, v_{k-2}, v_{k-1})) \right).$$

Setting $v_0 = 0$, we obtain the generating function for $k+1$-nonnesting partitions. The functional equation in Corollary 4.2, which specializes to Corollary 3.2 for $k = 2$, is amenable to series generation, and it remains to be seen what can be extracted using a kernel method analysis.

## 4.1 Enhanced nestings

Another relevant pattern in partition diagrams is the enhanced $k$-nesting. An enhanced $k$-nesting is either a $k$-nesting, or a set of $k-1$ arcs $(i_1, j_1), \dots, (i_{k-1}, j_{k-1})$ and a fixed point vertex $i_k$ (a singleton block in the corresponding partition) such that $i_1 < i_2 < \dots < i_{k-1} < i_k < j_{k-1} < \dots < j_1$, that is, a $k-1$-nesting with a fixed point inside the innermost arc. With a comparable definition for enhanced $k$-crossings, the symmetry between nesting and crossing patterns for different structures has been shown to hold in the enhanced version of the patterns as well. Set partitions are one such structure. Bousquet-Mélou and Xin [BMX07] considered both enhanced and usual crossings in set partitions. Our construction that generates $k$-nonnesting partitions can be easily modified to generate partitions with no enhanced $k$-nesting. For this purpose, we define a future enhanced $k$-nesting as an enhanced $k-1$-nesting together with a semi-arc beginning to its left, and we let the enhanced nesting index of a semi-arc be the largest $j$ such that it is in a future enhanced $j+1$-nesting. The label of a diagram is now $[s_0, \dots, s_{k-1}]$, where $s_i$ is the number of semi-arcs with enhanced nesting index $\ge i$. The only difference in the construction of the tree is that the addition of a fixed point to an open partition diagram $\pi$ can create future enhanced 2-nestings. Indeed, the semi-arcs that had enhanced nesting index 0 in $\pi$ have enhanced nesting index 1 after the fixed point is added. This results in a variation of Theorem 4.1, which again can be translated to a functional equation for the corresponding generating function. We refer the reader to [BEMY] for details.

Corollary 4.2 and its counterpart for enhanced nestings allow us to generate data for the number of set partitions of size $n$ avoiding $k+1$-nestings and avoiding enhanced $k+1$-nestings for small $k$ and $n$. Tables with this data can be found in [BEMY].

## 5 $k$-nonnesting permutations

There are some similarities between $k$-nonnesting permutations and $k$-nonnesting set partitions, yet none of the techniques that have been applied in the literature to the enumeration of $k$-nonnesting set partitions [BMX07, MY] works for permutations. Our method, however, can be modified to take advantage of these similarities and deal with $k$-nonnesting permutations as well. This gives rise to the first substantial set of enumerative data on $k$-nonnesting permutations. Previously, only data up to $n = 12$ was known, and its obtaining required extensive computation.

First, we recall how to represent a permutation as an arc diagram. This representation was first used by Corteel [Cor07], and in a modified form by Elizalde [Eli11]. It is essentially a drawing of the cycle
structure of the permutation. Given $\sigma \in S_n$, the diagram of $\sigma$ has an arc between $i$ and $\sigma(i)$ for each $i$ from 1 to $n$, and the arc is drawn above the vertices (and is called an *upper arc*) if $i \le \sigma(i)$, and below the vertices (and is called a *lower arc*) if $i > \sigma(i)$. We call such a representation a *permutation diagram* of size $n$. In this notation, a subset of $k$ arcs is a *k-nesting* if either all $k$ arcs are upper arcs and form an *enhanced k-nesting* with the definition from Section 4.1 (considering fixed points $(i, i)$), or all $k$ arcs are lower arcs and form a *k-nesting* with the definition from Section 1.

We call the two above possibilities *upper enhanced k-nestings* and *lower k-nestings*, respectively. The reason behind the slight dissymmetry in the definition comes from the original paper of Corteel [Cor07], where this was necessary for bijections between certain classes of permutations. Burrill *et al.* [BMP10] maintained this dissymmetry. In any case, the construction we provide can be easily adapted to make a uniform treatment of upper and lower arcs. For simplicity, we do not draw an arc from $i$ to itself when $\sigma(i) = i$, although such a fixed point contributes to enhanced *k*-nestings of upper arcs. Figure 6 shows an example of a permutation diagram.

<figure><img src="image_6.png" /><figcaption>**Fig. 6:** The permutation $\sigma = (1 \ 1 \ 3)(2 \ 6 \ 4 \ 5)(7 \ 9)(8)(10)$ and its arc diagram representation. This diagram has two 3-nestings: $\{(1, 11), (2, 6), (4, 5)\}$ and $\{(1, 11), (7, 9), (8, 8)\}$.</figcaption></figure>

As in the case of set partitions, there is a related definition of *k*-crossings in permutations. Burrill *et al.* proved that *k*-noncrossing and *k*-nonnesting permutations are equinumerous. However, they present very limited enumerative results, which we significantly improve upon here.

We remark that the subset of upper arcs forms a set partition, and so does the subset of lower arcs. However, these two partitions are not independent. Their relationship is explicitly described in [BMP10]. This interpretation as a pair of partitions allows us to extend the construction from Section 4 quite naturally.

The vertices of a permutation diagram can be of five types: *fixed points*, *openers*, *closers*, *upper transistories*, and *lower transistories*. A fixed point has no incident edges, an opener (resp. closer) is the left (resp. right) end-point of an upper and a lower arc, and an upper (resp. lower) transitory vertex is the right end-point of an upper (resp. lower) arc and the left end-point of another.

## 5.1 Generating tree for open permutation diagrams

Similarly to what we did for partitions, we consider a more general class of objects that we call *open permutation diagrams*, by allowing three additional vertex types: *semi-openers*, *upper semi-transitories*, and *lower semi-transitories*. A semi-opener is the left end-point of an upper and a lower semi-arc, and an upper (resp. lower) transitory vertex is the right end-point of an upper (resp. lower) arc and the right end-point of an upper (resp. lower) semi-arc. Note that in an open permutation diagram, the number of upper semi-arcs equals the number of lower semi-arcs.

To create an open permutation diagram of size $n$ from one of size $n-1$, we add a vertex labelled $n$ which can be of any of the five following types: (1) fixed point, (2) semi-opener, (3) upper semi-transitory (provided there is an available upper semi-arc), (4) lower semi-transitory (provided there is an available lower semi-arc), (5) closer (provided there are available upper and lower semi-arcs).
To incorporate the nesting constraint to the tree, we define a notion of future nestings in open permutation diagrams. A *future enhanced upper k-nesting* is an upper enhanced *k* − 1-nesting together with an upper semi-arc beginning to its left, and a *future lower k-nesting* is a lower *k* − 1-nesting together with a lower semi-arc beginning to its left. An example of each is in Figure 7. The enhanced nesting index of an upper semi-arc is the largest *j* such that the semi-arc is in a future enhanced upper *j* + 1-nesting. The nesting index of a lower semi-arc is the largest *j* such that the semi-arc is in a future lower *j* + 1-nesting. An open permutation diagram is called *k*-nonnesting if it has no regular or future enhanced upper *k*-nesting, and no regular or future lower *k*-nesting.

<figure><img src="image_7.png" /><figcaption>**Fig. 7:** An open permutation diagram. The upper arcs (7, 12), (8, 9) and the upper semi-arc (3, *) form a future enhanced upper 3-nesting. The lower arc (7, 10) and the lower semi-arc (3, *) form a future lower 2-nesting. The nesting index of each semi-arc is labelled in italics.</figcaption></figure>

Again, it will be convenient to shift the index and consider *k* + 1-nonnesting permutations. To each *k* + 1-nonnesting open permutation diagram, we associate a label consisting of a 3-tuple, [*h*; *r*; *s*]. Here, *h* is the number of upper semi-arcs (and hence also the number of lower semi-arcs), *r* = [*r*₁, ..., *r*-*k*−₁] is a vector such that *r*ᵢ is the number of upper semi-arcs of enhanced nesting index greater than or equal to *i*, and *s* = [*s*₁, ..., *s*-*k*−₁] is a vector such that *s*ᵢ is the number of lower semi-arcs of nesting index greater than or equal to *i*. The label of the 4-nonnesting diagram in Figure 7 is [3; 1, 1; 1, 0].

We note that in an open permutation diagram $\sigma$, if we consider loops as fixed points, the upper (resp. lower) arcs and semi-arcs form an open partition diagram $\sigma^+$ (resp. $\sigma^-$) on the vertices $\{1, \dots, n\}$. If the label of $\sigma$ is $[h; r; s]$, then the label of $\sigma^+$ as described in Theorem 4.1 is $[h, r]$, and the label of $\sigma^+$ in the tree in Section 4.1 is $[h, s]$. In particular, $h \ge r_1 \ge \dots \ge r_{k-1} \ge 0$ and $h \ge s_1 \ge \dots \ge s_{k-1} \ge 0$.

## 5.2 3-nonnesting permutations

Again, the case of 3-nonnesting permutations is sufficiently insightful for the general method without being overly complicated. In this section we describe the generating tree for 3-nonnesting open permutation diagrams, and we determine a functional equation for the generating function.

The label of a 3-nonnesting open permutation diagram is [*h*, *r*₁, *s*₁] (we use commas instead of semicolons in this section). Here, 2*h* is the total number of semi-arcs, *r*₁ is the number of upper semi-arcs that belong to a future enhanced upper 2-nesting, and *s*₁ is the number of lower semi-arcs that belong to a future lower 2-nesting.

To predict the labels of the children of a 3-nonnesting open permutation diagram, we consider the different types of vertices that can be added. To avoid future 3-nestings, we are not allowed to add a closer or semi-transitory vertex that closes a semi-arc belonging to a future enhanced upper 2-nesting or a future lower 2-nesting, unless it is an outermost semi-arc, i.e., the top upper semi-arc or the bottom lower semi-arc. The succession rule for the generating tree is described in Theorem 5.1 (proved in [BEMY]). An example is drawn in Figure 8.
<figure><img src="image_8.png" /><figcaption>Fig. 8: A 3-nonnesting open permutation diagram and its children.</figcaption></figure>

**Theorem 5.1** Let $\Sigma^{(2)}$ be the set of 3-nonnesting open permutation diagrams. To each diagram $\sigma$ associate the label $l(\sigma) = [h, r, s]$, where $2h$ is the total number of semi-arcs, $r$ is the number of semi-arcs in a future enhanced upper 2-nesting and $s$ is the number of semi-arcs in a future lower 2-nesting. Then, the number of diagrams in $\Sigma^{(2)}$ of size $n$ is the number of nodes at level $n$ in the generating tree with root label $[0, 0, 0]$, and succession rule given by

$$ [h, h, s] \qquad (1) $$

$$ [h + 1, r, s] \qquad (2) $$

$$ [h, r, s] \rightarrow [h, i, s] \quad \text{for } \max\{0, r-1\} \le i \le h-1 \qquad (3) $$

$$ [h, r, j] \quad \text{for } \max\{0, s-1\} \le j \le h-1 \qquad (4) $$

$$ [h-1, i, j] \quad \text{for } \max\{0, r-1\} \le i \le h-1 \text{ and } \max\{0, s-1\} \le j \le h-1. \qquad (5) $$

The number of 3-nonnesting permutations of size $n$ is equal to the number of nodes with label $[0, 0, 0]$ at the $n$-th level of this generating tree.

As in the case of partitions, we have translated the generating tree from Theorem 5.1 into a functional equation for the multivariate generating function $F(u, v, w; z) = \sum F_{h,r,s}(n)u^h v^r w^s z^n$ where $F_{h,r,s}(n)$ is the number of open permutation arc diagrams at level $n$ with label $[h, r, s]$. The coefficient $F_{0,0,0}(n)$ is the number of 3-nonnesting permutations of $\{1, 2, \dots, n\}$. See [BEMY] for the functional equation and its derivation. We have found the equation useful to generate terms in the sequence, but we have been unable to solve it.

## 5.3 The general case: $k + 1$-nonnesting permutations

The construction in Section 5.2 can easily be generalized to this case. Recall that to each $k+1$-nonnesting open permutation diagram, we assign a label $[h; \mathbf{r}; \mathbf{s}] = [h; r_1, r_2, \dots, r_{k-1}; s_1, s_2, \dots, s_{k-1}]$. To describe the succession rule of the corresponding generating tree, we think of $[h, \mathbf{r}]$ as the label of the upper set partition, where we consider enhanced nestings, and of $[h, \mathbf{s}]$ as the label of the lower set partition, where we consider usual nestings. Due to space constraints, we refer the reader to [BEMY] for the precise succession rule and the resulting functional equation for the corresponding generating function, which has $2k$ variables.

Implementing in Maple the functional equation from Corollary 4.2 and its counterpart for permutations, we have computed over 70 terms of the generating function for $k$-nonnesting set partitions for $k = 3$, over
40 terms for $k = 4$, and about 25 for each $5 \le k \le 8$. For $k$-nonnesting permutations, we have computed 45 terms for $k = 3$, and at least 15 terms for each $4 \le k \le 7$. Our data suggests the following.

**Conjecture 5.2** *The generating function for $k$-nonnesting permutations is not $D$-finite for any $k > 2$.*

## References

[BBMD$^{+02}$] 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):29-55, 2002.

[BEMY] S. Burrill, S. Elizalde, M. Mishna, and L. Yen. A generating tree approach to $k$-nonnesting partitions and permutations. Preprint, arXiv:1108.5615.

[BM11] M. Bousquet-Mélou. Counting permutations with no long monotone subsequence via generating trees and the kernel method. *J. Alg. Combin.*, 33(4):571-608, 2011.

[BMP10] S. Burrill, M. Mishna, and J. Post. On $k$-crossings and $k$-nestings of permutations. pages 593-600, 2010.

[BMX07] M. Bousquet-Mélou and G. Xin. On partitions avoiding 3-crossings. *Sém. Lothar. Combin.*, 54:Art. B54e, 21 pp., 2005/07.

[CDD$^{+07}$] W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan. Crossings and nestings of matchings and partitions. *Trans. Amer. Math. Soc.*, 359(4):1555-1575, 2007.

[CHR09] W. Chen, H. Han, and C. Reidys. Random $k$-noncrossing RNA structures. *Proc. Natl. Acad. Sci. USA*, 106(52):22061-22066, 2009.

[Cor07] S. Corteel. Crossings and alignments of permutations. *Adv. in Appl. Math.*, 38(2):149-163, 2007.

[dM06] A. de Mier. On the symmetry of the distribution of $k$-crossings and $k$-nestings in graphs. *Electron. J. Combin.*, 13(1):Note 21, 6 pp., 2006.

[dM07] A. de Mier. $k$-noncrossing and $k$-nonnesting graphs and fillings of Ferrers diagrams. *Combinatorica*, 27(6):699-720, 2007.

[Eli11] S. Elizalde. The X-class and almost-increasing permutations. *Annals of Combinatorics*, 15:51-68, 2011.

[Kra06] C. Krattenthaler. Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. *Adv. in Appl. Math.*, 37(3):404-431, 2006.

[MY] M. Mishna and L. Yen. Set partitions with no $m$-nesting. Preprint, arXiv:1106.5036.

[Wes95] J. West. Generating trees and the Catalan and Schröder numbers. *Discrete Mathematics*, 146(1-3):247-262, 1995.

[Wes96] J. West. Generating trees and forbidden subsequences. *Discrete Mathematics*, 157(1-3):363-374, 1996.