# On naturally labelled posets
and permutations avoiding 12–34

David Bevan†, Gi-Sang Cheon‡ and Sergey Kitaev†

###### Abstract

A partial order $\prec$ on $[n]$ is naturally labelled (NL) if $x\prec y$
implies $x<y$. We establish a bijection between $\\{$3, 2+2$\\}$-free NL
posets and 12–34-avoiding permutations, determine functional equations
satisfied by their generating function, and use series analysis to investigate
their asymptotic growth. We also exhibit bijections between 3-free NL posets
and various other objects, and determine their generating function. The
connection between our results and a hierarchy of combinatorial objects
related to interval orders is described.

Keywords: naturally labelled poset, pattern avoidance, bijective
combinatorics, generating function, asymptotic series analysis

††footnotetext: †Department of Mathematics and Statistics, University of
Strathclyde, Glasgow, Scotland.††footnotetext: ‡Department of Mathematics,
Sungkyunkwan University, Suwon, South Korea.
Partially supported by National Research Foundation of Korea (NRF) grants
funded by the Korean government (MSIP) 2016R1A5A1008055 and 2019R1A2C1007518.

††footnotetext: 2020 Mathematics Subject Classification: 06A07, 05A05, 05A15,
05A16.

##  1 Introduction

A partial order $\prec$ on $[n]$ is said to be _natural_ [1] or _naturally
labelled_ [8] if $\prec$ is suborder of the normal linear order on the
integers. That is, $\prec$ is naturally labelled if $x\prec y$ implies $x<y$.
For brevity, we often use NL as an abbreviation for “naturally labelled”. The
counting sequence for NL posets on $[n]$ is A006455 in the OEIS [22].

Our focus in this work is NL posets that are 3-free (having no 3-element
chain), such as that at the left of Figure 1. In Section 2 we present
bijections between 3-free NL posets and a number of other equinumerous
combinatorial objects before deducing their generating function. Section 3 is
the heart of the paper and concerns 3-free NL posets which are also (2+2)-free
(having no induced subposet consisting of two disjoint 2-element chains). Our
main result is a bijection between $\\{$3, 2+2$\\}$-free NL posets and
permutations avoiding the vincular pattern 12–34. We also exhibit bijections
with other equinumerous objects. Definitions are given in the relevant
sections. The enumeration of these objects is also investigated, yielding
functional equations satisfied by their generating function, a lower bound on
their factorial growth rate, and (using series analysis) a conjecture that
their number behaves asymptotically like

$A\cdot(\log 4)^{-n}\cdot\mu^{n^{1/3}}\cdot n^{\beta}\cdot n!,$

where estimates are given for the constants $A$, $\mu$ and $\beta$. Finally,
Section 4 places our new results in the context of a hierarchy of
combinatorial objects related to interval orders. Avenues for future research
are suggested.

Given a partial order $\prec$ on $[n]$, its _incidence matrix_ or _poset
matrix_ is the $n\times n$ binary matrix $M_{\prec}$ in which
$M_{\prec}(i,j)=1$ if and only if $i\preccurlyeq j$. There is a natural
bijection between posets of $[n]$ and their poset matrices. The following
proposition characterises the incidence matrices of NL posets. See [6] for a
characterisation of which NL poset matrices can be represented as binary
_Riordan_ matrices.

######  Proposition 1.

Naturally labelled posets on $[n]$ are in bijection with upper-triangular
$n\times n$ binary matrices with ones on the main diagonal that contain no
$\big{(}\begin{smallmatrix}1&0\\\ {\bf 1}&1\end{smallmatrix}\big{)}$ whose
lower left entry (shown in bold) is on the main diagonal.

###### Proof.

Reflexivity implies that every poset matrix has ones on the main diagonal. A
partial order $\prec$ is NL if and only if its poset matrix is upper-
triangular since $i>j$ implies $M_{\prec}(i,j)=0$. Being upper-triangular
automatically satisfies antisymmetry: if $i\neq j$ then $M_{\prec}(i,j)=1$
implies $M_{\prec}(j,i)=0$. Finally, $M_{\prec}$ contains
$\big{(}\begin{smallmatrix}1&0\\\ {\bf 1}&1\end{smallmatrix}\big{)}$ as a
submatrix with its lower left entry on the main diagonal if and only if there
exist $i<j<k$ such that $M_{\prec}(i,j)=1$ and $M_{\prec}(j,k)=1$ but
$M_{\prec}(i,k)=0$, or equivalently, if $i\prec j$ and $j\prec k$, but
$i\nprec k$, contradicting transitivity. ∎

361589472

123456789

Figure 1: The Hasse diagram of a 3-free NL poset, and the corresponding
Stanley graph

##  2 3-free naturally labelled posets

A poset is _3 -free_ if it has no 3-element chains. That is, $\prec$ is 3-free
if there are no three elements $x\prec y\prec z$. Every element of a 3-free
poset is thus either minimal or maximal (with isolated elements being both
minimal and maximal). See Figure 1 for an example.

In this section, we consider 3-free NL posets. We exhibit bijections between
these posets and certain matrices and certain graphs, before determining the
generating function for these objects. We conclude by establishing the
generating function for those 3-free NL posets which have no isolated
elements.

The following proposition characterises the incidence matrices of 3-free NL
posets.

######  Proposition 2.

The 3-free naturally labelled posets on $[n]$ are in bijection with upper-
triangular $n\times n$ binary matrices with ones on the main diagonal that
contain no $\big{(}\begin{smallmatrix}1&\\\ {\bf 1}&1\end{smallmatrix}\big{)}$
whose lower left entry is on the main diagonal.

###### Proof.

By Proposition 1, the poset matrix of a NL partial order $\prec$ is upper-
triangular with ones on the main diagonal. The matrix $M_{\prec}$ contains
$\big{(}\begin{smallmatrix}1&\\\ {\bf 1}&1\end{smallmatrix}\big{)}$ with its
lower left entry on the main diagonal if and only if there exist $i<j<k$ such
that $M_{\prec}(i,j)=1$ and $M_{\prec}(j,k)=1$, or equivalently, if $i\prec
j\prec k$. Thus the poset matrix of a NL partial order is
$\big{(}\begin{smallmatrix}1&\\\ {\bf 1}&1\end{smallmatrix}\big{)}$-free if
and only if the poset is 3-free. ∎

A labelled graph with vertex set $[n]$ is a _Stanley graph_ if and only if no
vertex $v$ has both left neighbours ($u<v$) and right neighbours ($u>v$). Thus
every Stanley graph is bipartite: every edge connects a vertex with (only)
right neighbours to a vertex with (only) left neighbours. There is a natural
bijection between 3-free NL posets and Stanley graphs since Stanley graphs are
exactly the Hasse diagrams of 3-free NL posets. See Figure 1 for an example.

######  Proposition 3.

The 3-free naturally labelled posets on $[n]$ are in bijection with $n$-vertex
Stanley graphs.

The following proposition presents enumerative results concerning 3-free NL
posets, including a recurrence relation showing a relationship with a
$q$-analogue of the Stirling numbers of the second kind, and both a functional
equation and an explicit expression for the generating function. The counting
sequence for 3-free NL posets on $[n]$ is A135922 in [22].

######  Proposition 4.

Let $p(n,k)$ be the number of 3-free naturally labelled posets on $[n]$ with
$k$ minimal elements. Then

$p(n,k)\;=\;p(n-1,k-1)\>+\>(2^{k}-1)p(n-1,k)$ (1)

where $p(0,0)=1$, $p(n,0)=0$ if $n\geqslant 1$, and $p(n,k)=0$ if $n<k$. Thus,
$p(n,k)=S_{2}[n,k]$, where the $S_{q}[n,k]$ are the $q$-Stirling numbers of
the second kind.

Suppose

$F(z,y)\;=\;\sum_{n\geqslant k\geqslant 0}p(n,k)z^{n}y^{k}$ (2)

is the corresponding bivariate generating function. Then $F$ satisfies the
functional equation

$F(z,y)\;=\;1\>+\>z\big{(}F(z,2y)-(1-y)F(z,y)\big{)},$ (3)

and can be expressed explicitly by

$F(z,y)\;=\;\sum_{k\geqslant
0}\frac{z^{k}y^{k}}{\prod_{i=1}^{k}\big{(}1-(2^{i}-1)z\big{)}}.$ (4)

###### Proof.

The unique empty poset gives $p(0,0)=1$. Every nonempty poset has at least one
minimum, so $p(n,0)=0$ if $n\geqslant 1$, and no poset has more minima than
elements, so $p(n,k)=0$ if $n<k$.

The nonempty 3-free NL posets on $[n]$ with $k$ minima are of two types: (i)
those in which $n$ is minimal, and (ii) those in which $n$ is not minimal. In
type (i), $n$ is isolated. Thus, if we remove $n$ we obtain a 3-free NL poset
on $[n-1]$ with $k-1$ minima. So there are $p(n-1,k-1)$ posets of type (i).

Now consider a poset of type (ii). Since $n$ is not minimal, if we remove $n$
we obtain a 3-free NL poset on $[n-1]$ with $k$ minima. For every such poset,
a non-minimal $n$ can be added to cover any nonempty subset of the $k$ minima,
of which there are $2^{k}-1$. So there are $(2^{k}-1)p(n-1,k)$ posets of type
(ii). Hence $p(n,k)$ satisfies recurrence (1). This is identical to the
recurrence of Carlitz for $q$-Stirling numbers of the second kind with $q=2$
(see [4]):

$S_{q}[n,k]\;=\;S_{q}[n-1,k-1]\>+\>[k]_{q}\cdot S_{q}[n-1,k],$

where $[k]_{q}=1+q+\ldots+q^{k-1}$. Thus $p(n,k)=S_{2}[n,k]$ (see A139382 in
[22]).

If we reverse our decomposition, and consider the process of adding a new
maximal element to a 3-free NL poset with $k$ minima, then the new element may
cover any subset of the $k$ minimal elements, so there are $2^{k}$ ways of
adding a new element. Exactly one of these (covering no minima) increases the
number of minima to $k+1$; all the others leave $k$ minimal elements.

Now, in $F(z,y)$, each monomial $z^{n}y^{k}$ represents a 3-free NL poset on
$[n]$ with $k$ minima. So the process of adding a new maximal element is
represented by the following operation on monomials:

$z^{n}y^{k}\;\mapsto\;z^{n+1}\big{(}y^{k+1}+(2^{k}-1)y^{k}\big{)}\;=\;z^{n+1}\big{(}(2y)^{k}-(1-y)y^{k}\big{)}.$

Thus, by extending to a linear operator on the generating function and
including the empty poset as the base case, we see that $F(z,y)$ satisfies the
functional equation (3).

If we let $P_{k}(z)=\sum_{n\geqslant 0}p(n,k)z^{n}$, then, for each
$k\geqslant 1$, the recurrence relation (1) gives

$P_{k}(z)\;=\;z\big{(}P_{k-1}(z)+(2^{k}-1)P_{k}(z)\big{)}.$

Thus,

$P_{k}(z)\;=\;\frac{zP_{k-1}(z)}{1-(2^{k}-1)z}.$

Iterating, with $P_{0}(z)=1$, gives, for each $k\geqslant 0$,

$P_{k}(z)\;=\;\frac{z^{k}}{(1-z)(1-3z)\ldots(1-(2^{k}-1)z)}\;=\;\frac{z^{k}}{\prod_{i=1}^{k}\big{(}1-(2^{i}-1)z\big{)}}.$

The identity $F(z,y)=\sum_{k\geqslant 0}P_{k}(z)y^{k}$ then yields the
explicit expression (4) for $F(z,y)$. ∎

We conclude this section by presenting a new explicit formula for the
enumeration of those 3-free NL posets which have no isolated elements (see
A323842 in [22]).

######  Proposition 5.

Suppose $G(z,y)$ is the bivariate generating function in which the coefficient
of $z^{n}y^{k}$ is the number of 3-free naturally labelled posets on $[n]$
with no isolated elements and $k$ minima. Then $G$ satisfies the functional
equation

$G(z,y)\;=\;\frac{1}{1-z^{2}y^{2}}\left(1-zy+z\left(G\\!\left(\\!\frac{z}{1-zy},\,2y\\!\right)-(1-y)(1-zy)G(z,y)\right)\right)$
(5)

and can be expressed explicitly by

$G(z,y)\;=\;\frac{1}{1+zy}\,\sum_{k\geqslant
0}\frac{\big{(}z/(1+zy)\big{)}^{k}y^{k}}{\prod_{i=1}^{k}\big{(}1-(2^{i}-1)z/(1+zy)\big{)}}.$
(6)

251348967

012534

Figure 2: A 3-free NL poset with four isolated vertices, and the corresponding
decorated 3-free NL poset with no isolated vertices

###### Proof.

Let us say that a _decorated poset_ is a 3-free NL poset with no isolated
elements in which each element, including an additional invisible element 0,
is decorated with a sequence of zero or more rings. It is easy to see that
3-free NL posets on $[n]$ with $\ell$ isolated elements are in bijection with
decorated posets on $[n-\ell]$ with $\ell$ rings. Given a 3-free NL poset
$\mathcal{P}$, to construct the corresponding decorated poset $\mathcal{Q}$
simply process its elements in order. If an element is isolated in
$\mathcal{P}$, add a ring to the previous element in $\mathcal{Q}$; otherwise
add the element to $\mathcal{Q}$ with the covering relations corresponding to
those in $\mathcal{P}$. See Figure 2 for an example.

In terms of generating functions, this means we have the following
relationship between $G$ and $F$, the bivariate generating function (2) for
all 3-free naturally labelled posets:

$F(z,y)\;=\;\frac{1}{1-zy}\,G\\!\left(\\!\frac{z}{1-zy},\,y\\!\right).$

Here, ${z}/(1-zy)$ enumerates decorated elements, and $1/(1-zy)$ enumerates
the sequence of rings on invisible element 0. A simple change of variables
then gives us $G$ in terms of $F$:

$G(z,y)\;=\;\frac{1}{1+zy}\,F\\!\left(\\!\frac{z}{1+zy},\,y\\!\right).$

Substitution into the functional equation (3) for $F$ and some algebraic
rearrangement yields the functional equation for $G$ (5), and substitution
into (4) gives the explicit formula (6). ∎

##  3 $\\{$3, 2+2$\\}$-free naturally labelled posets

A poset is said to be (2+2)-free if it does not contain an _induced_ subposet
that is isomorphic to 2+2, the union of two disjoint 2-element chains. For
example, in Figure 3, the poset at the left is (2+2)-free, but the poset at
the right is not. See Section 4 below for further discussion of (2+2)-free
posets.

Figure 3: A (2+2)-free poset and a poset with an induced 2+2 subposet

In this section we consider $\\{$3, 2+2$\\}$-free NL posets. First, we exhibit
bijections between these posets and certain matrices, certain labelled binary
words, and certain bicoloured permutations. Then we establish a bijection with
permutations avoiding the vincular pattern 12–34. We then consider the
enumeration of these objects, firstly determining functional equations
satisfied by their generating function, and then investigating their
asymptotic growth.

The following proposition characterises the incidence matrices of $\\{$3,
2+2$\\}$-free NL posets.

######  Proposition 6.

The $\\{$3, 2+2$\\}$-free naturally labelled posets on $[n]$ are in bijection
with upper-triangular $n\times n$ binary matrices with ones on the main
diagonal that contain none of the four matrices

$M_{0}=\big{(}\begin{smallmatrix}1&\\\ {\bf
1}&1\end{smallmatrix}\big{)},\qquad M_{1}=\Big{(}\begin{smallmatrix}1&0&0\\\
{\bf 1}&0&0\\\ &{\bf 1}&1\end{smallmatrix}\Big{)},\qquad
M_{2}=\Big{(}\begin{smallmatrix}0&1&0\\\ {\bf 1}&0&1\\\ &{\bf
1}&0\end{smallmatrix}\Big{)},\qquad M_{3}=\Big{(}\begin{smallmatrix}0&0&1\\\
{\bf 1}&1&0\\\ &{\bf 1}&0\end{smallmatrix}\Big{)},$

with a lower left (bold) entry on the main diagonal.

###### Proof.

By Proposition 2, the incidence matrix of a 3-free NL poset is upper-
triangular with ones on the main diagonal and has no $M_{0}$ submatrix.
Suppose a NL partial order $\prec$ has an induced 2+2 subposet $i\prec j$,
$k\prec\ell$ (where $i$ and $j$ are both incomparable with both $k$ and $\ell$
under $\prec$). Without loss of generality, we may assume that $i<k$. Then
three cases are possible:

$i<j<k<\ell,\qquad\qquad i<k<j<\ell,\qquad\qquad i<k<\ell<j.$
$\begin{smallmatrix}i&{\bf\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>j&&{\bf 1}&0&0\\\ k&&&{\bf 1}&1\\\
\ell&&&&{\bf\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>&i&j&k&\ell\end{smallmatrix}\qquad\qquad\qquad\quad\begin{smallmatrix}i&{\bf\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>k&&{\bf 1}&0&1\\\ j&&&{\bf 1}&0\\\
\ell&&&&{\bf\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>&i&k&j&\ell\end{smallmatrix}\qquad\qquad\qquad\quad\begin{smallmatrix}i&{\bf\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>k&&{\bf 1}&1&0\\\ \ell&&&{\bf 1}&0\\\
j&&&&{\bf\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>&i&k&\ell&j\end{smallmatrix}$

These clearly correspond to an occurrence in $M_{\prec}$ of the submatrices
$M_{1}$, $M_{2}$, or $M_{3}$, respectively, as illustrated. ∎

It is well-known (see [3]) that a poset is (2+2)-free if and only if the set
of its strict downsets can be linearly ordered by inclusion. That is, given a
poset $(P,\prec)$, if for each $x\in P$, we let $D(x)=\\{t\in P:t\prec x\\}$
denote the strict downset of $x$, then for any pair of elements $x,y\in P$,
either $D(x)\subseteq D(y)$ or $D(y)\subseteq D(x)$. We use this
characterisation to exhibit natural bijections between $\\{$3, 2+2$\\}$-free
NL posets, and certain sets of labelled binary words and bicoloured
permutations.

######  Proposition 7.

The $\\{$3, 2+2$\\}$-free naturally labelled posets on $[n]$ are in bijection
with words over $\\{\mathsf{0},\mathsf{1}\\}$ of length $n$, with the letters
labelled $\mathsf{1},\ldots,\mathsf{n}$ and satisfying the following four
conditions:

  1. 1.

the first letter is $\mathsf{0}$,

  2. 2.

the labels on adjacent $\mathsf{0}$s are in decreasing order,

  3. 3.

the labels on adjacent $\mathsf{1}$s are in increasing order, and

  4. 4.

the label on any $\mathsf{1}$ is greater than the labels on all the
$\mathsf{0}$s earlier in the word.

###### Proof.

Given a $\\{$3, 2+2$\\}$-free NL poset $\mathcal{P}$, let $D_{1}\subsetneq
D_{2}\subsetneq\ldots\subsetneq D_{k}$ be the distinct strict downsets of its
non-isolated maxima. Each $D_{i}$ is a nonempty subset of the minima of
$\mathcal{P}$. Let $E_{1}=D_{1}$, and for $i=2,\ldots,k$, let
$E_{i}=D_{i}\setminus D_{i-1}$. Finally, let $E_{k+1}$ be the set of isolated
elements of $\mathcal{P}$. Then the $E_{i}$’s form a partition of the minima
of $\mathcal{P}$, with each part nonempty, except possibly $E_{k+1}$.

For each $i\in[k]$, let $M_{i}=\\{x\in\mathcal{P}:D(x)=D_{i}\\}$ be the set of
maxima of $\mathcal{P}$ whose strict downset is equal to $D_{i}$. The
$M_{i}$’s partition the non-isolated maxima of $\mathcal{P}$, and each $M_{i}$
is nonempty.

Clearly $\mathcal{P}$ is defined by the sequence
$(E_{1},M_{1},E_{2},M_{2},\ldots,E_{k},M_{k},E_{k+1})$. We encode this as a
labelled binary word
$\varepsilon_{1}\mu_{1}\ldots\varepsilon_{k}\mu_{k}\varepsilon_{k+1}$, in
which each $\varepsilon_{i}$ consists of $|E_{i}|$ $\mathsf{0}$s, labelled
with the elements of $E_{i}$ in decreasing order, and each $\mu_{i}$ consists
of $|M_{i}|$ $\mathsf{1}$s, labelled with the elements of $M_{i}$ in
increasing order111The choice of decreasing labels for minima and increasing
labels for maxima is motivated by the requirements of our bijection between
$\\{$3, 2+2$\\}$-free NL posets and permutations avoiding 43–12 in Proposition
10., so that each subset of elements is uniquely represented and the sets
comprising the sequence can be distinguished.

215634897 $\mathsf{0_{2}1_{4}0_{5}0_{1}1_{8}0_{6}1_{7}1_{9}0_{3}}$ 487925163

Figure 4: The Hasse diagram of a $\\{$3, 2+2$\\}$-free NL poset, and the
corresponding labelled binary word and bicoloured permutation

For example, for the poset at the left of Figure 4, we have

$E_{1}=\\{2\\}$, |  $\varepsilon_{1}=\mathsf{0_{2}}$, |  $M_{1}=\\{4\\}$, |  $\mu_{1}=\mathsf{1_{4}}$,
---|---|---|---
$E_{2}=\\{1,5\\}$, |  $\varepsilon_{2}=\mathsf{0_{5}0_{1}}$, |  $M_{2}=\\{8\\}$, |  $\mu_{2}=\mathsf{1_{8}}$,
$E_{3}=\\{6\\}$, |  $\varepsilon_{3}=\mathsf{0_{6}}$, |  $M_{3}=\\{7,9\\}$, |  $\mu_{3}=\mathsf{1_{7}1_{9}}$,
$E_{4}=\\{3\\}$, |  $\varepsilon_{4}=\mathsf{0_{3}}$, |  |

yielding the word in the centre of the figure.

Any word created in this way satisfies the four conditions in the statement of
the proposition: Condition 1 holds because $E_{1}$ is nonempty, conditions 2
and 3 hold as a result of our choices for the ordering of labels, and
condition 4 holds because $\mathcal{P}$ is naturally labelled.

Moreover, a unique poset can be built from any word satisfying the four
conditions. Reading from left to right, $\textsf{0}_{p}$ adds a new (initially
isolated) minimal element $p$, whereas $\textsf{1}_{q}$ adds a new maximal
element $q$ covering all existing minima. ∎

A reinterpretation of these words yields a bijection with certain bicoloured
permutations. An _inversion_ consists of two values (not necessarily
consecutive), the larger of which occurs first. A _descent_ is an inversion
consisting of two consecutive values.

######  Proposition 8.

The $\\{$3, 2+2$\\}$-free naturally labelled posets on $[n]$ are in bijection
with permutations of length $n$, each entry of which is coloured blue or red,
whose first entry is blue, and which avoid blue-blue ascents, red-red
descents, and blue–red inversions.

###### Proof.

These bicoloured permutations are simply an alternative representation of the
labelled binary words of Proposition 7, formed by switching the role of
letters and labels and using the colours blue and red for $\mathsf{0}$ and
$\mathsf{1}$, respectively. See Figure 4 for an example. The four conditions
on the colouring of entries precisely correspond to the four conditions in
Proposition 7 on the labelled binary words. ∎

###  3.1 Bijection with permutations avoiding 12–34

947863152 Figure 5: The single occurrence of the pattern 43–12 in the
permutation 947863152

A _vincular_ pattern is a permutation with adjacency conditions. We use the
traditional notation in which a vincular pattern is written as a permutation
with dashes inserted between terms that need not be adjacent but no dashes
between terms that must be adjacent. For example, the permutation $\sigma$
contains the vincular pattern 43–12 if there exist indices $i<j$ such that
$\sigma(j)<\sigma(j+1)<\sigma(i+1)<\sigma(i)$. The permutation in Figure 5
contains a single occurrence of 43–12. Vincular patterns were introduced in
[2] (under another name) and first called vincular patterns in [3].

We also require the ability to specify a pattern in which the first term must
occur at the start of the host permutation. We denote this with an initial
bracket. For example, the permutation $\sigma$ contains the pattern [3–12 if
there exists an index $i$ such that $\sigma(i)<\sigma(i+1)<\sigma(1)$. The
permutation in Figure 5 contains two occurrences of [3–12, formed by 947 and
915.

In this section we prove that $\\{$3, 2+2$\\}$-free NL posets have the same
counting sequence as permutations avoiding the vincular pattern 12–34. The
permutations avoiding 12–34 were first studied by Elizalde [15, Section 5],
who, among other things, established that 12–34-avoiders are equinumerous with
both 12–43-avoiders and 21–43-avoiders (and their symmetries).222That is,
12–34, 12–43 and 21–43 are _Wilf equivalent_.

######  Proposition 9 (see Elizalde [15, Propositions 5.2 and 5.3]).

The class $\operatorname{\mathsf{Av}}(\text{12--34})$ of permutations avoiding
the vincular pattern 12–34 is equinumerous with both
$\operatorname{\mathsf{Av}}(\text{12--43})$ and
$\operatorname{\mathsf{Av}}(\text{21--43})$, and also with the five other
symmetries of these three classes.

In light of this, the heart of our proof consists of the establishment of a
bijection between the bicoloured permutations of $[n]$ defined in Proposition
8 and permutations of $[n]$ avoiding 43–12.

######  Proposition 10.

The $\\{$3, 2+2$\\}$-free naturally labelled posets on $[n]$ are in bijection
with permutations of length $n$ avoiding the vincular pattern 12–34.

###### Proof.

By Propositions 8 and 9, it is sufficient to exhibit a bijection between
bicoloured permutations and permutations avoiding 43–12. Let $\mathcal{B}$
denote the set of bicoloured permutations defined in Proposition 8. Observe
that the runs (maximal sequences of ascending or descending points) of any
$\beta\in\mathcal{B}$ are coloured as follows:

  * •

The first point in an _ascending_ run of $\beta$ is blue (since the first
point of $\beta$ is blue, and red-red descents and blue–red inversions are
forbidden). Subsequent points may have either colour, but a pair of
consecutive points cannot both be blue (since blue-blue ascents are
forbidden). In particular, the second point of an ascending run is red.

  * •

The first point in a _descending_ run of $\beta$ may have either colour, but
subsequent points are all blue (avoiding red-red descents and blue–red
inversions).

We define $\Lambda$ to be the following length-preserving map from
$\mathcal{B}$ to uncoloured permutations:

  * •

If $\beta$ is a bicoloured permutation that doesn’t contain a red-blue ascent,
then $\Lambda(\beta)$ is simply the permutation that results from removing the
colours from $\beta$.

  * •

If $\beta$ contains one or more red-blue ascents, then for each such ascent
$PQ$, we _mark_ the point $Q$ and any points in a descending run beginning
with $Q$ that lie above the red point $P$. All these points are blue. In this
case, $\Lambda(\beta)$ is the uncoloured permutation that results from moving
all the marked points to the start of the permutation, placing them in
increasing order.

$\Lambda$ $\longmapsto$ $\Psi$ $\longmapsfrom$

Figure 6: A bicoloured permutation in $\mathcal{B}$, and the 43–12 avoider
that corresponds to it under the bijection $\Lambda$

See Figure 6 for an example; on the left, red-blue ascents are indicated with
a grey line, and the marked points are circled.

We claim that the map $\Lambda$ is a bijection from $\mathcal{B}$ to
$\operatorname{\mathsf{Av}}(\text{{43--12}})$. Suppose $\beta\in\mathcal{B}$.
Then $\beta$ avoids 43–12, because the lower point in each descent of $\beta$
is coloured blue and at least one of the points in each ascent of $\beta$ is
red, so any 43–12 would contain a forbidden blue–red inversion. Moreover,
$\beta$ avoids the pattern [3–12, since the first point of $\beta$ is blue.

Suppose $\sigma\in\operatorname{\mathsf{Av}}\big{(}\text{43--12},\text{{[}3--
12{}}\big{)}$. Then the points of $\sigma$ can be coloured to produce an
element of $\mathcal{B}$ that doesn’t contain a red-blue ascent, by colouring
the first point and the non-initial points of descending runs blue, and all
the other points (the non-initial points of ascending runs) red. This clearly
avoids blue-blue ascents, red-blue ascents and red-red descents. And if the
result contained a blue–red inversion $P$–$Q$, then $P$ would be either the
first point of $\sigma$ or the second point of a descent and $Q$ would be the
second point in an ascent, so $\sigma$ would contain either a [3–12 or a
43–12. Note that this is the only way of colouring $\sigma$ to create an
element of $\mathcal{B}$ avoiding red-blue ascents. Thus the restriction of
$\Lambda$ to elements of $\mathcal{B}$ avoiding red-blue ascents is a
bijection with $\operatorname{\mathsf{Av}}\big{(}\text{43--12},\text{{[}3--
12{}}\big{)}$.

Suppose now that $\beta$ contains a red-blue ascent. Then:

  * •

The points in all the red-blue ascents of $\beta$ form an increasing
subsequence; otherwise $\beta$ would contain a blue–red inversion.

  * •

Each red-blue ascent of $\beta$ consists of the upper two points of a blue-
red-blue or red-red-blue double ascent, since a point coloured red can’t be
the first point in an ascending run.

  * •

Thus, $\Lambda(\beta)$ contains a [3–12, formed from the lowest marked point
and the lower two points of the leftmost blue-red-blue or red-red-blue double
ascent.

  * •

The marked points of $\Lambda(\beta)$ form its initial increasing run (which
may be a single point), since the first point of $\beta$ is below the
lowermost marked point — which becomes the first point of $\Lambda(\beta)$;
otherwise there would be a blue–red inversion in $\beta$, formed of its first
point and the lower point of the leftmost red-blue ascent.

  * •

Thus, $\Lambda(\beta)$ avoids 43–12:

    * (a)

If the descent created in $\Lambda(\beta)$ by the uppermost marked point and
the first point of $\beta$ were to form the 43 of a 43–12, then $\beta$ would
have contained a [3–12.

    * (b)

If the deletion of a descending run of marked points were to create a descent
that formed the 43 of a 43–12 in $\Lambda(\beta)$, then the lowest of these
marked points would have been the first point of a 43–12 in $\beta$.

    * (c)

If the deletion of a descending run of marked points were to create an ascent
that formed the 12 of a 43–12 in $\Lambda(\beta)$, then the lowest of these
marked points would have been the third point of a 43–12 in $\beta$.

Let $\mathcal{A}$ = $\operatorname{\mathsf{Av}}(\text{43--
12})\setminus\operatorname{\mathsf{Av}}\big{(}\text{43--12},\text{{[}3--
12{}}\big{)}$ be comprised of those 43–12 avoiders that contain an occurrence
of [3–12.

We define $\Psi$ to be the following length-preserving map from $\mathcal{A}$
to $\mathcal{B}$: Suppose $\sigma\in\mathcal{A}$. If $P$ is a point in the
initial increasing run of $\sigma$, let $\alpha(P)$ be the ascent in the
rightmost occurrence of a 3–12 pattern in $\sigma$ whose first point is $P$.
Then $\Psi(\sigma)$ is the bicoloured permutation that results from moving
each point $P$ from the initial increasing run of $\sigma$ so that, for every
relevant ascent $QR$, the points in the preimage $\alpha^{-1}(QR)$ are placed
in decreasing order immediately after $R$. All the moved points are coloured
blue, as is the first point of $\Psi(\sigma)$ and non-initial points of
descending runs; the unmoved non-initial points of ascending runs are coloured
red. See Figure 6 for an example; at the right, the points in the initial run
are circled and the $\alpha(P)$ ascents are indicated with a grey line.

This colouring clearly avoids blue-blue ascents and red-red descents. If
$\Psi(\sigma)$ were to contain a blue–red inversion $P$–$R$, then $R$ would be
the second point in an ascent $QR$, and $P$ would be an unmoved point, because
a moved point would form a 3–12 with $QR$ in $\sigma$ and so be moved after
$R$ by $\Psi$. Thus, either

  * •

$P$ would be the first point of $\Psi(\sigma)$, in which case $\sigma$ would
contain a 21–34 pattern $SP$–$QR$, where $S$ could be any point in the initial
ascending run of $\sigma$, or else

  * •

$P$ would be the second (unmoved) point of a descent $SP$, in which case
$SP$–$QR$ would form a 21–34 in $\sigma$.

Hence, $\Psi(\sigma)$ avoids blue–red inversions, and
$\Psi(\sigma)\in\mathcal{B}$ as claimed.

Clearly $\Psi(\sigma)$ contains one red-blue ascent for each $\alpha(P)$
ascent in $\sigma$. So $\Lambda(\Psi(\sigma))=\sigma$. We claim that $\Psi$ is
in fact the inverse of the restriction of $\Lambda$ to bicoloured permutations
in $\mathcal{B}$ containing a red-blue ascent. Suppose $RP$ is a red-blue
ascent in $\beta$. Then $R$ is the upper point of an ascent $QR$ in
$\Lambda(\beta)$ because the first point in the ascending run containing $R$
is not moved by $\Lambda$. Moreover there is no ascent below and to the right
of $P$ in $\beta$, otherwise $\beta$ would contain a blue–red inversion $PS$,
since the second point in any ascending run is red. Thus $QR$ is the rightmost
ascent that forms a 3–12 pattern in $\Lambda(\beta)$ with the moved point $P$,
and also with any other moved points from the descending run beginning with
$P$ that lie above $R$. So $\Psi(\Lambda(\beta))=\beta$. Hence, $\Psi$ is the
partial inverse of $\Lambda$, and $\Lambda$ is a bijection between
$\mathcal{B}$ and $\operatorname{\mathsf{Av}}(\text{{43--12}})$. ∎

###  3.2 Enumerating 12–34-avoiding permutations

In this section, we consider the enumeration of 12–34-avoiders, and hence also
of $\\{$3, 2+2$\\}$-free NL posets. First we present functional equations
satisfied by their generating function. Then we give a lower bound on the
factorial growth rate of $\operatorname{\mathsf{Av}}(\text{12--34})$, and use
methods of series analysis to investigate its asymptotic growth, resulting in
a conjectured form for the asymptotics.

######  Proposition 11.

Suppose $H(z,x,y)$ is the trivariate generating function in which the
coefficient of $z^{n}x^{k}y^{\ell}$ is the number of permutations of length
$n$ avoiding 12–34 with lowest ascent top $k$ (with $k=n+1$ for the decreasing
permutation) and last entry $\ell$. Then $H(z,x,y)=H_{1}(z,x,y)+H_{2}(z,x,y)$,
where

$\displaystyle H_{1}(z,x,y)$
$\displaystyle\;=\;zxy\Big{(}x+\frac{1}{1-y}\big{(}H_{1}(z,x,1)-H_{1}(z,x,y)+H_{2}(z,x,1)-H_{1}(z,xy,1)\big{)}$
$\displaystyle\qquad\qquad\qquad+\frac{1}{1-xy}\big{(}H_{1}(z,1,xy)-H_{1}(z,xy,1)\big{)}\Big{)},$
$\displaystyle H_{2}(z,x,y)$
$\displaystyle\;=\;\frac{zy}{1-y}\big{(}H_{1}(z,xy,1)-yH_{1}(zy,x,1)+H_{2}(z,xy,1)-H_{2}(z,x,y)\big{)}.$

###### Proof.

We model the process of extending a 12–34-avoider by inserting a new point at
the right. There are two cases, depending on the relative positions of the
lowest ascent top and the last entry. If the last entry is not above the
lowest ascent top, then there is no restriction on the value of the inserted
point. (This first case is enumerated by $H_{1}$.) On the other hand, if the
last entry is above the lowest ascent top, then a new point cannot be inserted
above the last entry, or a 12–34 would be created. (This second case is
enumerated by $H_{2}$.) This process thus gives rise to the following
transition rules, as illustrated in Figure 7:

$(a)$$(b)$$(c)$

$(d)$$(e)$

Figure 7: The possibilities for inserting a new point at the right of two
12–34-avoiders

$(k,\ell)\;\longmapsto\;\begin{cases}(k+1,j),&\text{\phantom{$bcde$}$(a)$
~{}if $\ell\leqslant k$, for~{}}j=1,\,\ldots,\,\ell,\\\
(j,j),&\text{\phantom{$bcde$}$(b)$ ~{}if $\ell\leqslant k$,
for~{}}j=\ell+1,\,\ldots,\,k,\\\ (k,j),&\text{\phantom{$abde$}$(c)$ ~{}if
$\ell\leqslant k$, for~{}}j=k+1,\,\ldots,\,n+1,\\\\[3.0pt]
(k+1,j),&\text{\phantom{$abce$}$(d)$ ~{}if $\ell>k$,
for~{}}j=1,\,\ldots,\,k,\\\ (k,j),&\text{\phantom{$abcd$}$(e)$ ~{}if $\ell>k$,
for~{}}j=k+1,\,\ldots,\,\ell.\end{cases}$

These are readily checked, as is the correctness of setting the lowest ascent
top to $n+1$ for the decreasing $n$-permutation (which has no ascent).

The process for translating an insertion encoding like this into functional
equations is entirely standard. For example, the application of rule $(a)$ to
a permutation represented by the monomial $z^{n}x^{k}y^{\ell}$ yields
permutations represented by

$z^{n+1}\sum_{j=1}^{\ell}x^{k+1}y^{j}\;=\;\frac{zxy}{1-y}z^{n}x^{k}(1-y^{\ell}).$

Extending this to a linear operator on the appropriate generating function
gives

$\frac{zxy}{1-y}\big{(}H_{1}(z,x,1)-H_{1}(z,x,y)\big{)},$

to be included on the right of the equation for $H_{1}$. Together with similar
contributions from the other five rules, and a $zx^{2}y$ term for the initial
1-point permutation, this yields the desired functional equations. ∎

Ferraz de Andrade, Lundberg and Nagle [16, Corollary 1.4] prove that the
_factorial growth rate_ of a particular _subclass_ of the 43–12-avoiders is

$\lim\limits_{n\rightarrow\infty}\sqrt[n]{\big{|}\operatorname{\mathsf{Av}}_{n}(\text{21
--34},\text{43--12})\big{|}/n!}\;=\;1/\log 4.$

Together with Proposition 9, this yields the following lower bound on the
growth of 12–34-avoiders, which improves on the bound of 0.5 given in [10].

######  Proposition 12.

$\lim\limits_{n\rightarrow\infty}\sqrt[n]{\big{|}\operatorname{\mathsf{Av}}_{n}(\text{{12
--34}})\big{|}/n!}\;\geqslant\;(\log 4)^{-1}\;\approx\;0.72134752$.

The counting sequence for 12–34-avoiders — and hence also for $\\{$3,
2+2$\\}$-free NL posets — is A113226 in [22]. By iterating the recurrence in
the proof of Proposition 11, we were able to generate the first 557 terms in
this sequence. We now use the methods of series analysis, as presented by
Guttmann in [18], to estimate the asymptotics of
$\big{|}\operatorname{\mathsf{Av}}_{n}(\text{{12--34}})\big{|}$. This approach
was exploited in [9] to investigate the number of permutations avoiding the
classical pattern 1324; our analysis here is similar.

For each $n$, let $a_{n}=\big{|}\operatorname{\mathsf{Av}}_{n}(\text{{12--
34}})\big{|}/n!$, so $E(z):=\sum_{n\geqslant 0}a_{n}z^{n}$ is the exponential
generating function for the number of 12–34-avoiders. We consider the
behaviour of the ratios $r_{n}=a_{n+1}/a_{n}$ of consecutive terms in this
sequence.

If $E(z)$ were to exhibit a simple power-law singularity, with the asymptotics
of the coefficients given by $a_{n}\sim A\cdot\gamma^{n}\cdot n^{\beta}$, for
some constants $A$, $\gamma$ and $\beta$, then the ratios would satisfy

$r_{n}\;=\;\gamma\left(1\>+\>\beta/n\>+\>O(n^{-2})\right),$ (7)

in which case $r_{n}$ would be asymptotically linear with respect to $n^{-1}$.
On the other hand, if the coefficients were to behave like $a_{n}\sim
A\cdot\gamma^{n}\cdot\mu^{n^{\alpha}}\cdot n^{\beta}$, with a _stretched
exponential_ factor $\mu^{n^{\alpha}}$ for some constants $\mu>0$ and
$\alpha<1$, yielding a non-algebraic singularity, then

$r_{n}\;=\;\gamma\left(1\>+\>\frac{\alpha\log\mu}{n^{1-\alpha}}\>+\>\frac{\beta}{n}\>+\>O\big{(}n^{-(2-2\alpha)}\big{)}\right).$

In particular (anticipating our findings below), when $\alpha=1/3$, this
specializes to

$r_{n}\;=\;\gamma\left(1\>+\>\frac{\log\mu}{3n^{2/3}}\>+\>\frac{\beta}{n}\>+\>O(n^{-4/3})\right),$
(8)

in which $r_{n}$ is asymptotically linear with respect to $n^{-2/3}$.

Figure 8: Plots of the ratios against $n^{-1}$, and against $n^{-2/3}$

In Figure 8, the ratios are plotted against $n^{-1}$, and against $n^{-2/3}$.
The nonlinearity of the plot against $n^{-1}$ is not consistent with the
existence of an algebraic singularity, as can be seen from (7). On the other
hand, the plot against $n^{-2/3}$ appears close to being linear, which by (8)
would be consistent with the existence of a stretched exponential term with
$\alpha\approx 1/3$.

Figure 9: Plot of $n^{2/3}(r_{n}/\gamma-1)$ against $n^{-1/3}$, with
$\gamma=(\log 4)^{-1}$

Extrapolation of either of these plots is consistent with a limiting ratio of
$(\log 4)^{-1}$, as marked on the vertical axes, matching the lower bound for
$\gamma$ given in Proposition 12. Further evidence that $\gamma=(\log
4)^{-1}$, and also that $\alpha=1/3$, is provided by the visual linearity of
the plot in Figure 9, since equation (8) implies that

$n^{2/3}(r_{n}/\gamma-1)\;=\;\tfrac{1}{3}\log\mu\>+\>\beta
n^{-1/3}\>+\>O(n^{-2/3}).$ (9)

Choosing a slightly different value for either $\gamma$ or $\alpha$ results in
a plot with clear curvature. Thus we believe that the factorial growth rate is
actually equal to its lower bound.

######  Conjecture 13.

$\lim\limits_{n\rightarrow\infty}\sqrt[n]{|\operatorname{\mathsf{Av}}_{n}(\text{{12
--34}})|/n!}\;=\;(\log 4)^{-1}$.

Figure 10: Plots of direct fitting estimates for $A$, $\mu$, and $\beta$

By (9), extrapolating from the plot in Figure 9 also gives us an estimate for
$\log\mu$ near to 3.6. To gain a better approximation for $\mu$ and to
approximate the values of $A$ and $\beta$, we use a direct fitting approach.
Given our assumed asymptotic form for $a_{n}$, we have

$\log a_{n}\;\sim\;\log A\>+\>n\log\gamma\>+\>n^{1/3}\log\mu\>+\>\beta\log n.$
(10)

So, for each $n$, we solve the system of three linear equations

$\big{\\{}\log A_{n}\>+\>k^{1/3}\log\mu_{n}\>+\>\beta_{n}\log k\;=\;\log
a_{k}\>-\>k\log\gamma\>:\>k=n,n+1,n+2\big{\\}},$

to give estimates $A_{n}$, $\mu_{n}$ and $\beta_{n}$ for $A$, $\mu$ and
$\beta$, respectively. Assuming our conjectured asymptotic form is correct,
these estimates should converge to the actual values as $n$ increases. Plots
of the results are shown in Figure 10, which can be extrapolated to yield
approximations for the constants.

In addition, we used the _Mathematica_ FindFit function to find the values for
the constants that make the expression on the right side of (10) give the best
fit to different ranges of the data, as recorded in Table 1.

Data | $A$ | $\mu$ | $\beta$
---|---|---|---
500 terms: $\phantom{{}_{0}}a_{58},\ldots,a_{557}$ | $0.03351$ | $38.050$ | $-0.83314$
400 terms: $a_{158},\ldots,a_{557}$ | $0.03312$ | $37.976$ | $-0.82876$
300 terms: $a_{258},\ldots,a_{557}$ | $0.03298$ | $37.950$ | $-0.82710$
200 terms: $a_{358},\ldots,a_{557}$ | $0.03286$ | $37.936$ | $-0.82618$
100 terms: $a_{458},\ldots,a_{557}$ | $0.03280$ | $37.928$ | $-0.82557$
Table 1: Estimates for $A$, $\mu$ and $\beta$ from FindFit

These results show evidence of convergence and are consistent with the
extrapolated intercepts from the plots in Figures 9 and 10 ($\log 37.9\approx
3.63$). Hence, we believe that the asymptotics have the following form.

######  Conjecture 14.

The asymptotic number of 12–34-avoiders is given by

$|\operatorname{\mathsf{Av}}_{n}(\text{{12--34}})|\;\sim\;A\cdot(\log
4)^{-n}\cdot\mu^{n^{1/3}}\cdot n^{\beta}\cdot n!,$

with constants $A\approx 0.032$, $\mu\approx 37.9$ and $\beta\approx-0.82$.

##  4 Discussion

Suppose $\mathcal{P}$ is a poset with strict order relation $\prec$. Then
$\mathcal{P}$ is an _interval order_ if it has an _interval representation_ ,
that is, if we can assign a real closed interval $[\ell_{x},r_{x}]$ to each
element $x\in\mathcal{P}$ in such a way that $x\prec y$ if and only if
$r_{x}<\ell_{y}$ (so the interval corresponding to $x$ is strictly to the left
of that corresponding to $y$). The notion of an interval order was introduced
by Fishburn [17] in 1970, who proved that $\mathcal{P}$ is an interval order
if and only if $\mathcal{P}$ is (2+2)-free.

Interval orders have attracted much attention in the literature, and they have
been shown to be equinumerous with several combinatorial structures, namely
with _Fishburn matrices_ , ascent sequences, _Stoimenow matchings_ , and
_Fishburn permutations_.

  * •

A Fishburn matrix of size $n$ is an upper-triangular $n\times n$ matrix with
non-negative integer entries with the property that every row and every column
contains a nonzero element and the total sum of the entries is $n$.

  * •

A sequence $x_{1}x_{2}\ldots x_{n}$ of nonnegative integers is an ascent
sequence if $x_{1}=0$ and, for each $i>1$, we have $x_{i}\leqslant
1+\operatorname{\mathsf{asc}}(x_{1}\ldots x_{i-1})$, where

$\operatorname{\mathsf{asc}}(x_{1}\ldots x_{k})\;=\;\big{|}\\{j:1\leqslant
j<k\text{~{}and~{}}x_{j}<x_{j+1}\\}\big{|}$

is the number of _ascents_ in $x_{1}\ldots x_{k}$.

  * •

A Stoimenow matching of size $n$ is a matching on the set
$\\{1,2,\ldots,2n\\}$ with no _left-nestings_ or _right-nestings_ ; that is,
with no two nested edges that have adjacent endpoints.

Figure 11: Permutations avoiding this pattern are equinumerous with interval
orders

  * •

A Fishburn permutation is one that avoids the _bivincular_ pattern shown (as a
_mesh_ pattern) in Figure 11. An occurrence in a permutation $\sigma$ of this
pattern is an occurrence of 231 with no points in the shaded regions. That is,
the permutation $\sigma$ contains this pattern if there exist indices $i<j$
such that $\sigma(j)+1=\sigma(i)<\sigma(i+1)$.

The enumeration of interval orders was possible only after discovering their
decomposition and linking it to ascent sequences, which were then enumerated
[3]. The generating function for interval orders turns out to be the
non-$D$-finite power series

$\sum_{n\geqslant 0}\,\prod_{i=1}^{n}\,(1-(1-z)^{i}).$

Ascent sequences play a crucial role in papers [12, 19, 20, 21, 23] where
interval orders are enumerated explicitly with respect to extra _statistics_ ,
a statistic being a function from a set of objects to the natural numbers. In
particular, among other results, Kitaev and Remmel [20] obtained the bivariate
generating function for interval orders counting the number of minimal
elements. As another example, a result in [12] not only settled a conjecture
of Jovovic on the number of _primitive_ (that is, binary) Fishburn matrices,
but also allowed the generating function to be refined to count Fishburn
matrices whose entries do not exceed a fixed value $k$, enabling the counting
of interval orders with at most $k$ indistinguishable elements. Fishburn
matrices themselves (rather than ascent sequences) have also been used [19] to
obtain further enumeration results related to interval orders.

These equinumerous objects, collectively known as _Fishburn structures_
counted by the _Fishburn numbers_ , are useful, not only for enumerative
purposes, but also for gaining a deeper understanding of the underlying
structure of interval orders, and for solving problems concerning them.
Through bijections we can translate properties to an equinumerous structure
that is more amenable to analysis. Recently, Cerbai and Claesson [5]
introduced _Fishburn trees_ to this family, obtaining simplified versions of
(and enhancing our understanding of) some of the known bijections.

Interval orders and other Fishburn structures form the base level of a
hierarchy we are about to sketch. Restricting interval orders in two different
ways and considering corresponding restrictions on the other objects from the
base level, gives two lower levels in the hierarchy, whose existence is of
interest from the perspective of bijective combinatorics. Analysis of these
lower levels also led to the resolution of a conjecture of Pudwell [3] in the
theory of permutation patterns and of a conjecture of Jovovic [12] in the
theory of matrices.

In the other direction, Claesson and Linusson [8] considered supersets of the
objects from the base level that are equinumerous to each other. Specifically,
they investigated matchings without left nestings, a superset of Stoimenow
diagrams (which are matchings with neither left or right nestings). It turns
out that there are $n!$ such matchings. This led to the definition of a
certain subset of (2+2)-free NL posets counted by $n!$, which they called
_factorial posets_ , an extension of interval orders. Other factorial objects
include permutations, _inversion sequences_ (a superset of ascent sequences),
and _partition matrices_ (a superset of Fishburn matrices introduced by
Claesson, Dukes and Kubitske [7]).

(2+2)-free labelled posets composition matrices ascent seqs $\times$ set
partitions $\sum\limits_{n\geqslant
0}\prod\limits_{i=1}^{n}\big{(}1\\!-\\!e^{-zi}\big{)}$ factorial posets
partition matrices inversion sequences all permutations left-nesting- free
matchings $n!$ interval orders: (2+2)-free posets Fishburn matrices ascent
sequences Fishburn permutations Stoimenow matchings $\sum\limits_{n\geqslant
0}\prod\limits_{i=1}^{n}\big{(}1\\!-\\!(1\\!-\\!z)^{i}\big{)}$ $\\{$2+2,
N$\\}$-free posets self-modified ascent sequences
$\operatorname{\mathsf{Av}}\\!\big{(}3\overline{1}52\overline{4}\big{)}$
$\sum\limits_{k=1}^{n}\binom{n+\binom{k}{2}-1}{n-k}$ $\\{$2+2, 3+1$\\}$-free
posets path-like Fishburn matrices restricted ascent sequences
$\operatorname{\mathsf{Av}}(231)$ $\frac{1}{n+1}\binom{2n}{n}$
???????????????????? Figure 12: Relationships between interval orders and
associated combinatorial objects

One can extend this approach by considering (natural) subsets and supersets of
combinatorial objects already in the hierarchy, linking bijectively structures
that have the same cardinalities. The hierarchy obtained so far in this way
has twenty combinatorial objects on five levels, as shown in Figure 12. At the
right of each row is the enumeration of the objects in the row. Solid lines
indicate known bijections, and solid arrows indicate known embeddings. For
example, the class of permutations avoiding the pattern 231, being in one-to-
one correspondence with ascent sequences restricted in a certain way, is a
subset of permutations avoiding the pattern $3\overline{1}52\overline{4}$,
which in turn is in bijection with self-modified ascent sequences, a superset
of the restricted ascent sequences. Figure 12 is based on work in [3, 7, 8,
11, 13, 14]. We do not provide definitions of all the objects involved.

(2+2)-free labelled posets composition matrices ascent seqs $\times$ set
partitions $\sum\limits_{n\geqslant
0}\prod\limits_{i=1}^{n}\big{(}1\\!-\\!e^{-zi}\big{)}$
$\phantom{\ldots,}1,3,19,207,3451,\ldots$ NL posets poset matrices
$\,1,2,7,40,357\,$$\phantom{\ldots,}1,2,7,40,357,\ldots$ (2+2)-free NL posets
$\\{M_{1},M_{2},M_{3}\\}$-free poset matrices
$\,1,2,7,37,272\,$$\phantom{\ldots,}1,2,7,37,272,\ldots$ 3-free NL posets
$M_{0}$-free poset matrices $\sum\limits_{k\geqslant
0}\frac{z^{k}}{\prod_{i=1}^{k}\big{(}1-(2^{i}-1)z\big{)}}$
$\phantom{\ldots,}1,2,6,26,158,\ldots$ factorial posets partition matrices
inversion sequences all permutations left-nesting- free matchings $n!$
$\phantom{\ldots,}1,2,6,24,120,\ldots$ $\\{$3, 2+2$\\}$-free NL posets
$\\{M_{0},\ldots,M_{3}\\}$-free poset matrices labelled binary words
$\operatorname{\mathsf{Av}}(\text{43--12})$
$\,1,2,6,23,107\,$$\phantom{\ldots,}1,2,6,23,107,\ldots$ interval orders:
(2+2)-free posets Fishburn matrices ascent sequences Fishburn permutations
Stoimenow matchings $\sum\limits_{n\geqslant
0}\prod\limits_{i=1}^{n}\big{(}1\\!-\\!(1\\!-\\!z)^{i}\big{)}$
$\phantom{\ldots,}1,2,5,15,53,\ldots$????????????????????????????????????????????????
Figure 13: The place of naturally labelled posets in the hierarchy related to
interval orders

In Figure 13, we introduce to this hierarchy the objects related to NL posets
that we investigated in the previous sections of this paper. These new objects
are shown in blue. As before, solid lines indicate known bijections and solid
arrows indicate known embeddings.

Our bijections in Propositions 1, 2 and 6 are represented by the relationships
between families of NL posets and families of poset matrices in the first two
columns. Similarly, the other relationships between equinumerous families of
objects in the second row from the bottom represent our bijections between
$\\{$3, 2+2$\\}$-free NL posets and labelled binary words in Proposition 7 and
with permutations avoiding 43–12 in Proposition 10. Note that these labelled
binary words are labelled binary ascent sequences since every binary word
whose first letter is $\mathsf{0}$ forms an ascent sequence. The embeddings in
columns 1, 2 and 4 are all self-explanatory.

Figure 13 contains thirteen explicit open embedding questions. Out of those,
we would like to highlight the following that we consider to be of particular
interest:

  * •

Rows 1 and 2: Find an embedding of Fishburn permutations (avoiding the
bivincular pattern in Figure 11) into $\operatorname{\mathsf{Av}}(\text{43--
12})$ or one of its symmetries. Does this translate to nice embeddings of
other row 1 objects into objects in row 2?

  * •

Rows 2 and 3: Does the trivial embedding of permutations avoiding 43–12 into
the set of all permutations induce natural embeddings of the other row 2
objects into objects in row 3? In particular, it would be good to find an
embedding of $\\{$3, 2+2$\\}$-free NL posets into factorial posets of the same
size. A naturally labelled partial order $\prec$ on $[n]$ is _factorial_ if
for $i,j,k\in[n]$, $i<j\prec k$ implies $i\prec k$. Factorial posets are
(2+2)-free [8].

  * •

Rows 1–3: Discover a natural set of matchings equinumerous to $\\{$3,
2+2$\\}$-free NL posets that contain Stoimenow matchings and are left-nesting-
free.

  * •

Rows 3 and 4: Find an embedding of factorial posets into 3-free naturally
labelled posets. Find an embedding of partition matrices into $M_{0}$-avoiding
lower triangular binary matrices. See [7] for the definition of a partition
matrix.

## References

  * [1] S. P. Avann.  The lattice of natural partial orders.  Aequationes Math., 8:95–102, 1972.
  * [2] Eric Babson and Einar Steingrímsson.  Generalized permutation patterns and a classification of the Mahonian statistics.  Sém. Lothar. Combin., 44: Article B44b, 2000.
  * [3] Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev.  $(2+2)$-free posets, ascent sequences and pattern avoiding permutations.  J. Combin. Theory Ser. A, 117(7):884–909, 2010.
  * [4] Yue Cai, Richard Ehrenborg, and Margaret Readdy.  $q$-Stirling identities revisited.  Electron. J. Combin., 25(1): Paper 1.37, 2018.
  * [5] Guilio Cerbai and Anders Claesson.  Fishburn trees.  Adv. in Appl. Math., 151:102592, 2023.
  * [6] Gi-Sang Cheon, Bryan Curtis, Gukwon Kwon, and Arnauld Mesinga Mwafise.  Riordan posets and associated incidence matrices.  Linear Algebra Appl., 632:308–331, 2022.
  * [7] Anders Claesson, Mark Dukes, and Martina Kubitzke.  Partition and composition matrices.  J. Combin. Theory Ser. A, 118(5):1624–1637, 2011.
  * [8] Anders Claesson and Svante Linusson.  $n!$ matchings, $n!$ posets.  Proc. Amer. Math. Soc., 139(2):435–449, 2011.
  * [9] Andrew R. Conway, Anthony J. Guttmann, and Paul Zinn-Justin.  1324-avoiding permutations revisited.  Adv. in Appl. Math., 96:312–333, 2018.
  * [10] Joshua Cooper, Erik Lundberg, and Brendan Nagle.  Generalized pattern frequency in large permutations.  Electron. J. Combin., 20(1): Paper 28, 2013.
  * [11] Mark Dukes, Vít Jelínek, and Martina Kubitzke.  Composition matrices, $({\bf 2}+{\bf 2})$-free posets and their specializations.  Electron. J. Combin., 18(1): Paper 44, 2011.
  * [12] Mark Dukes, Sergey Kitaev, Jeffrey Remmel, and Einar Steingrímsson.  Enumerating $(2+2)$-free posets by indistinguishable elements.  J. Comb., 2(1):139–163, 2011.
  * [13] Mark Dukes and Peter R. W. McNamara.  Refining the bijections among ascent sequences, $(2+2)$-free posets, integer matrices and pattern-avoiding permutations.  J. Combin. Theory Ser. A, 167:403–430, 2019.
  * [14] Mark Dukes and Robert Parviainen.  Ascent sequences and upper triangular matrices containing non-negative integers.  Electron. J. Combin., 17(1): Paper 53, 2010.
  * [15] Sergi Elizalde.  Asymptotic enumeration of permutations avoiding generalized patterns.  Adv. in Appl. Math., 36(2):138–155, 2006.
  * [16] Rodrigo Ferraz de Andrade, Erik Lundberg, and Brendan Nagle.  Asymptotics of the extremal excedance set statistic.  European J. Combin., 46:75–88, 2015.
  * [17] Peter C. Fishburn.  Intransitive indifference with unequal indifference intervals.  J. Mathematical Psychology, 7:144–149, 1970.
  * [18] Anthony J. Guttmann.  Analysis of series expansions for non-algebraic singularities.  J. Phys. A, 48(4):045209, 33, 2015.
  * [19] Vít Jelínek.  Counting general and self-dual interval orders.  J. Combin. Theory Ser. A, 119(3):599–614, 2012.
  * [20] Sergey Kitaev and Jeffrey Remmel.  Enumerating $({\bf 2}+{\bf 2})$-free posets by the number of minimal elements and other statistics.  Discrete Appl. Math., 159(17):2098–2108, 2011.
  * [21] Paul Levande.  Fishburn diagrams, Fishburn numbers and their refined generating functions.  J. Combin. Theory Ser. A, 120(1):194–217, 2013.
  * [22] The OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences.  Published electronically at https://oeis.org.
  * [23] Sherry H. F. Yan.  On a conjecture about enumerating $(2+2)$-free posets.  European J. Combin., 32(2):282–287, 2011.