# Modified difference ascent sequences
and Fishburn structures

Giulio Cerbai G.C. is member of the Gruppo Nazionale Calcolo
Scientifico–Istituto Nazionale di Alta Matematica (GNCS-INdAM). Department of
Mathematics, University of Iceland, Reykjavik, Iceland<EMAIL_ADDRESS><EMAIL_ADDRESS> Anders Claesson  Department of Mathematics, University of
Iceland, Reykjavik, Iceland<EMAIL_ADDRESS><EMAIL_ADDRESS> Bruce E. Sagan
Department of Mathematics, Michigan State University, East Lansing, MI
48824-1027, USA<EMAIL_ADDRESS>
(August 28, 2024
Key Words: ascent sequence, Burge transpose, difference ascent sequence,
Fishburn permutations, modified ascent sequence, permutation patterns, weak
ascent sequence
AMS subject classification (2020): 05A19 (Primary) 05A05 (Secondary) )

###### Abstract

Ascent sequences and their modified version play a central role in the
bijective framework relating several combinatorial structures counted by the
Fishburn numbers. Ascent sequences are nonnegative integer sequences defined
by imposing a bound on the growth of their entries in terms of the number of
ascents contained in the corresponding prefix, while modified ascent sequences
are the image of ascent sequences under the so-called hat map. By relaxing the
notion of ascent, Dukes and Sagan have recently introduced difference ascent
sequences. Here we define modified difference ascent sequences and study their
combinatorial properties. Inversion sequences are a superset of the difference
ascent sequences and we extend the hat map to this domain. Our extension
depends on a parameter which we specialize to obtain a new set of permutations
counted by the Fishburn numbers and characterized by a subdiagonality
property.

##  1 Introduction

Fishburn structures is a collective term for combinatorial objects counted by
the Fishburn numbers. These numbers appear as sequence A22493 in the OEIS
[OEI] and the $n$th Fishburn number is defined as the coefficient of $x^{n}$
in the series

$\sum_{n\geq 0}\prod_{k=1}^{n}\bigl{(}1-(1-x)^{k}\bigr{)}.$

This generating function first appeared 2001 in a paper by Zagier [Zag01]
concerned with bounds on the dimension of the space of Vassiliev’s knot
invariants. Eight years later, Bousquet-Mélou, Claesson, Dukes and Kitaev
[BMCDK10] proved that this series also enumerates unlabeled interval orders,
thus resolving a long standing open problem. Peter C. Fishburn pioneered the
study of interval orders [Fis70a, Fis70b, Fis85] and it is in honor of him
Claesson and Linusson [CL11] named the coefficients of Zagier’s series.

Bousquet-Mélou et al. [BMCDK10] laid the foundation of a bijective framework
relating interval orders, Stoimenow matchings, and Fishburn permutations,
defined by avoidance of a single bivincular pattern of length three. To link
these objects, as well as to count them, they introduced an auxiliary set of
sequences that embody their recursive structure more transparently, the ascent
sequences. They defined them as certain nonnegative integer sequences whose
growth of their entries is bounded by the number of ascents contained in the
corresponding prefix. Research into Fishburn structures (sparked by the work
of Bousquet-Mélou et al.) has blossomed over the last 15 years. The structures
studied are mostly the ones previously mentioned but also include Fishburn
matrices [Fis70b, DP10], descent correcting sequences [CL11] and inversion
sequences avoiding the covincular pattern $\leavevmode\hbox to18.31pt{\vbox
to18.31pt{\pgfpicture\makeatletter\hbox{\hskip 0.19398pt\lower-0.19398pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{
}{0.0}{1.0}{0.0pt}{0.0pt}{ \lxSVG@closescope
}{0}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{11.95053pt}\pgfsys@moveto{0.0pt}{11.95053pt}\pgfsys@lineto{0.0pt}{5.97527pt}\pgfsys@lineto{17.9258pt}{5.97527pt}\pgfsys@lineto{17.9258pt}{11.95053pt}\pgfsys@closepath\pgfsys@moveto{17.9258pt}{5.97527pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}{}{ {}{}{}{}{ }{
}{ }{
}{}}{}\pgfsys@moveto{0.00601pt}{0.00601pt}\pgfsys@moveto{0.00601pt}{5.97527pt}\pgfsys@lineto{17.91978pt}{5.97527pt}\pgfsys@moveto{0.00601pt}{11.95053pt}\pgfsys@lineto{17.91978pt}{11.95053pt}\pgfsys@moveto{5.97527pt}{0.00601pt}\pgfsys@lineto{5.97527pt}{17.91978pt}\pgfsys@moveto{11.95053pt}{0.00601pt}\pgfsys@lineto{11.95053pt}{17.91978pt}\pgfsys@moveto{17.91978pt}{17.91978pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{5.97527pt}{11.95053pt}\pgfsys@moveto{7.0253pt}{11.95053pt}\pgfsys@curveto{7.0253pt}{12.53044pt}{6.55518pt}{13.00056pt}{5.97527pt}{13.00056pt}\pgfsys@curveto{5.39536pt}{13.00056pt}{4.92523pt}{12.53044pt}{4.92523pt}{11.95053pt}\pgfsys@curveto{4.92523pt}{11.37062pt}{5.39536pt}{10.9005pt}{5.97527pt}{10.9005pt}\pgfsys@curveto{6.55518pt}{10.9005pt}{7.0253pt}{11.37062pt}{7.0253pt}{11.95053pt}\pgfsys@closepath\pgfsys@moveto{5.97527pt}{11.95053pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{11.95053pt}{5.97527pt}\pgfsys@moveto{13.00056pt}{5.97527pt}\pgfsys@curveto{13.00056pt}{6.55518pt}{12.53044pt}{7.0253pt}{11.95053pt}{7.0253pt}\pgfsys@curveto{11.37062pt}{7.0253pt}{10.9005pt}{6.55518pt}{10.9005pt}{5.97527pt}\pgfsys@curveto{10.9005pt}{5.39536pt}{11.37062pt}{4.92523pt}{11.95053pt}{4.92523pt}\pgfsys@curveto{12.53044pt}{4.92523pt}{13.00056pt}{5.39536pt}{13.00056pt}{5.97527pt}\pgfsys@closepath\pgfsys@moveto{11.95053pt}{5.97527pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\,.$ Recently, Cerbai
and Claesson [CC23a] introduced Fishburn trees and Fishburn covers to obtain
simplified versions of the existing bijections.

The bijection relating ascent sequences with Fishburn permutations is easy to
describe. Ascent sequences encode the recursive construction of Fishburn
permutations by insertion of a new maximum element. On the other hand, their
relation with $(\mathbf{2+2})$-free posets is better expressed in terms of a
modified version, that is, their bijective image under the hat map. Roughly
speaking, the hat map goes through the ascent tops of a given ascent sequence;
at each step it increases by one all the entries in the corresponding prefix
that are currently greater than or equal to the current ascent top. Modified
ascent sequences interact better with Fishburn trees too, as they are simply
obtained by reading the labels of Fishburn trees with the in-order traversal.
Further, Fishburn trees arise from the max-decomposition of modified ascent
sequences. In fact, even though they only appeared marginally in the original
paper [BMCDK10], modified ascent sequences have recently assumed a key role in
the understanding of Fishburn structures [CC23b, CC23a, Cera, Cerb].

In 2023, Bényi, Claesson and Dukes [BCD23] generalized ascent sequences to
weak ascent sequences. They are defined analogously to the classical case, but
(strict) ascents are replaced with weak ascents. In the spirit of the original
framework, the authors provided bijections with several classes of matrices,
posets and permutations. Among them, weak ascent sequences encode the active
site construction of weak Fishburn permutations, a superset of Fishburn
permutations defined by avoidance of a single bivincular pattern of length
four.

By relaxing the bound on the growth of the rightmost entry further, that is,
by replacing ascents or weak ascents with difference $d$ ascents, Dukes and
Sagan [DS23] arrived at $d$-ascent sequences. This allowed them to generalize
the ascent and weak ascent constructions whose corresponding combinatorial
objects now depended on the paramenter $d$. They also provided natural
injections from $d$-ascent sequences to permutations avoiding a bivincular
pattern of length $d+3$, leaving the problem of improving these maps to
bijections open. This was done very recently by Zang and Zhou [ZZ], who
introduced $d$-Fishburn permutations and proved that their recursive structure
is embodied by $d$-ascent sequences in the same way as ascent sequences encode
Fishburn permutations.

In this paper, we generalize the hat map to $d$-ascent sequences, obtaining
modified $d$-ascent sequences in the process. We present a recursive
construction of modified $d$-ascent sequences and use it to study their
combinatorial properties. Our framework is in fact more flexible: it extends
to inversion sequences, a superset of $d$-ascent sequences. Further, our
definition of the hat map depends on a parameter whose specific choices lead
to interesting examples. Fishburn permutations are obtained [BMCDK10] by
applying the Burge transpose [CC23b] to modified ascent sequences, and we
prove that the same construction holds for modified $d$-ascent sequences and
$d$-Fishburn permutations. Finally, we initiate the study of pattern avoidance
on $d$-Fishburn permutations.

We start by giving the necessary tools and definitions in Section 2.

In Section 3, we introduce the $d$-hat map and use it to define the set of
modified $d$-ascent sequences. We then provide a recursive description of
modified $d$-ascent sequences and show in Proposition 3.3 that they are Cayley
permutations whose $d$-ascent set is equal to the set of leftmost copies of
the unmodified sequence.

Section 4 is devoted to the study of certain properties of the $d$-hat map.
Our main result, Corollary 4.7, shows that $d$-hat is injective on modified
$d$-ascent sequences. We then consider which statistics are preserved by
$d$-hat in Section 4.2.

In Section 5, we define modified inversion sequences and the
$\mathrm{hat}_{\max}$ map. We show that, under $\mathrm{hat}_{\max}$, a
permutation corresponds bijectively to the inversion sequence recording its
recursive construction by insertion of a new rightmost maximum value.

This approach is pushed further in Section 6. We restrict the
$\mathrm{hat}_{\max}$ map to ascent sequences and weak descent sequences,
characterizing the corresponding sets of permutations as those that are
subdiagonal in a certain sense.

In Section 7, we prove that $d$-Fishburn permutations can be obtained as the
bijective image of $d$-ascent sequences under the composition of the $d$-hat
map with the Burge transpose, lifting a classical result by Bousquet-Mélou et
al. [BMCDK10] to any $d\geq 0$.

In Section 8, we enumerate $d$-Fishburn permutations avoiding $231$ using a
bijection with certain Motzkin paths and the cluster method.

Section 9 contains some final remarks and suggestions for future work.

##  2 Preliminaries

For any nonnegative integer number $n$, let $\operatorname{End}_{n}$ be the
set of _endofunctions_ , $\alpha:[n]\to[n]$, where $[n]=\\{1,2,\ldots,n\\}$.
We sometimes identify an endofunction $\alpha$ with the word
$\alpha=a_{1}\ldots a_{n}$, where $a_{i}=\alpha(i)$ for each $i\in[n]$. We
will use the convention that Greek letters will usually be used for sequences
and the corresponding Roman letters will be used for their elements so, for
example, $a_{i}$ will be the $i$th element of $\alpha$ unless otherwise
indicated. Let $\operatorname{End}=\cup_{n\geq 0}\operatorname{End}_{n}$. In
general, given a definition of $E_{n}$ (of elements of size $n$) we let
$E=\cup_{n\geq 0}E_{n}$. Or, conversely, given a set $E$ whose elements are
equipped with a notion of size, we will denote by $E_{n}$ the set of elements
in $E$ that have size $n$.

A _Cayley permutation_ is an endofunction $\alpha$ where
$\operatorname{Im}\alpha=[k]$, for some $k\leq n$. In other words, $\alpha$ is
a Cayley permutation if it contains at least one copy of each integer between
$1$ and its maximum element. The set of Cayley permutations of length $n$ is
denoted by $\operatorname{Cay}_{n}$. For example,
$\operatorname{Cay}_{1}=\left\\{1\right\\}$,
$\operatorname{Cay}_{2}=\left\\{11,12,21\right\\}$ and

$\operatorname{Cay}_{3}=\left\\{111,112,121,122,123,132,211,212,213,221,231,312,321\right\\}.$

There is a well-known one-to-one correspondence between ballots (ordered set
partitions) and Cayley permutations: The Cayley permutation
$\alpha=a_{1}\ldots a_{n}$ encodes the ballot $B_{1}\ldots B_{k}$ where
$k=\max\alpha$ and $i\in B_{a_{i}}$ for every $i\in[n]$.

An endofunction $\alpha\in\operatorname{End}_{n}$ is an _inversion sequence_
if $a_{i}\leq i$ for each $i\in[n]$. We let $\operatorname{I}_{n}$ denote the
set of inversion sequences of length $n$. For example,

$\operatorname{I}_{1}=\\{1\\},\quad\operatorname{I}_{2}=\\{11,12\\},\quad\operatorname{I}_{3}=\left\\{111,112,113,121,122,123\right\\}.$

Let $\alpha:[n]\to[n]$ be an endofunction. We call $i\in[n]$ an _ascent_ of
$\alpha$ if $i=1$ or $i\geq 2$ and

$a_{i}>a_{i-1}.$

We define the ascent set of $\alpha$ to be

$\operatorname{Asc}\alpha=\\{i\in[n]\mid\text{$i$ is an ascent of
$\alpha$}\\}$

and

$\operatorname{asc}\alpha=\\#\operatorname{Asc}\alpha$

where, for any set $S$, $\\#S$ denotes the cardinality of $S$. Note that our
conventions differ from some others in the literature in that we are taking
the indices of ascent tops, rather than bottoms, and that $1$ is always an
ascent which is done for the purpose of simplifying the definition of an
ascent sequence. It will sometimes be convenient to order
$\operatorname{Asc}\alpha$ and other similar sets below increasingly to obtain
the ascent list

$\operatorname{Asc}\alpha=(i_{1},i_{2},\ldots,i_{k}),$

where $k=\operatorname{asc}\alpha$. Our notation will not distinguish between
the set and its sequence.

From now on, let $\alpha_{i}=a_{1}\ldots a_{i}$ denote the prefix of $\alpha$
of length $i$. Call $\alpha$ an _ascent sequence_ if for all $i\in[n]$ we have

$a_{i}\leq 1+\operatorname{asc}\alpha_{i-1}.$

Note that when $i=1$ we have $a_{1}\leq 1+\operatorname{asc}\epsilon=1$, where
$\epsilon$ denotes the empty sequence. Since the entries of $\alpha$ are
positive integers, this forces $a_{1}=1$. Let $\operatorname{A}_{0}$ be the
set of ascent sequences and let $\operatorname{A}_{0,n}$ denote the set of
ascent sequences of length $n$. For instance,

$\operatorname{A}_{0,3}=\\{111,112,121,122,123\\}.$

Clearly, every $\alpha\in\operatorname{A}_{0,n+1}$ is of the form
$\alpha=\beta a$, where $\beta\in\operatorname{A}_{0,n}$ and $1\leq a\leq
1+\operatorname{asc}(\beta)$. Note that
$\operatorname{A}_{0,n}\subseteq\operatorname{I}_{n}$. On the other hand, some
ascent sequences are not Cayley permutations, the smallest example of which is
$12124$. Note also that we depart slightly from the original definition of
ascent sequences [BMCDK10] and other papers on the topic in that our sequences
use the positive, rather than nonnegative, integers. The reason is that we
want to bring all the families of sequences considered in this paper under the
umbrella of endofunctions of $[n]$ so as to relate them with Cayley
permutations and inversion sequences.

The set $\operatorname{\hat{\operatorname{A}}}_{0}$ of _modified ascent
sequences_ [BMCDK10] is the bijective image of $\operatorname{A}_{0}$ under
the $\alpha\mapsto\hat{\alpha}$ mapping, defined as follows. Given an ascent
sequence $\alpha$, let

$M(\alpha,j)=\alpha^{+},\text{ where
}\alpha^{+}(i)=a_{i}+\begin{cases}1&\text{if $i<j$ and $a_{i}\geq a_{j}$,}\\\
0&\text{otherwise,}\end{cases}$

and extend the definition of $M$ to multiple indices $j_{1}$,$j_{2}$,…,$j_{k}$
by

$M(\alpha,j_{1},j_{2},\dots,j_{k})=M\bigl{(}M(\alpha,j_{1},\dots,j_{k-1}),j_{k}\bigr{)}.$

Then

$\hat{\alpha}=M(\alpha,\operatorname{Asc}\alpha),$

where in this context $\operatorname{Asc}\alpha$ is the ascent list of
$\alpha$. For example, if $\alpha=121242232$, then
$\operatorname{Asc}\alpha=(1,2,4,5,8)$ and we get the following where at each
stage the entry governing the modification is underlined while the entries
which are modified italicized:

$\displaystyle\alpha$ $\displaystyle=121242232$ $\displaystyle M(\alpha,1)$
$\displaystyle=\underline{1}21242232$ $\displaystyle M(\alpha,1,2)$
$\displaystyle=1\underline{2}1242232$ $\displaystyle M(\alpha,1,2,4)$
$\displaystyle=1\mathbf{3}1\underline{2}42232$ $\displaystyle
M(\alpha,1,2,4,5)$ $\displaystyle=1312\underline{4}2232$ $\displaystyle
M(\alpha,1,2,4,5,8)$
$\displaystyle=1\mathbf{4}12\mathbf{5}22\underline{3}2=\hat{\alpha}$

More informally, to determine $\hat{\alpha}$, we scan the ascents of $\alpha$
from left to right; at each step, every element strictly to the left of and
weakly larger than the current ascent is incremented by one. The construction
described above can easily be inverted since
$\operatorname{Asc}\alpha=\operatorname{Asc}\hat{\alpha}$. Thus the mapping
$\operatorname{A}_{0}\rightarrow\operatorname{\hat{\operatorname{A}}}_{0}$ by
$\alpha\mapsto\hat{\alpha}$ is a bijection.

It is easy to turn this into a definition of
$\operatorname{\hat{\operatorname{A}}}_{0}$ which is recursive by length and
will be given later (see Definition 3.2). Finally, in [CC23b] it was proved
that

$\operatorname{\hat{\operatorname{A}}}_{0}=\\{\alpha\in\operatorname{Cay}\mid\operatorname{Asc}\alpha=\operatorname{nub}\alpha\\},$
(1)

where

$\operatorname{nub}\alpha=\\{\min\alpha^{-1}(j)\mid 1\leq j\leq\max\alpha\\}$

is the set of positions of leftmost copies. Equation (1) can be equivalently
expressed in terms of Cayley-mesh patterns, introduced by the first author
[Cer21], as

$\operatorname{\hat{\operatorname{A}}}_{0}\;=\;\operatorname{Cay}\left(\leavevmode\hbox
to57.51pt{\vbox to43.28pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@lineto{28.45276pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{42.67914pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{12.0925pt}\pgfsys@lineto{56.90552pt}{12.0925pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{16.36024pt}\pgfsys@lineto{56.90552pt}{16.36024pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{26.31888pt}\pgfsys@lineto{56.90552pt}{26.31888pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{30.58662pt}\pgfsys@lineto{56.90552pt}{30.58662pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@lineto{14.22638pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{42.67914pt}{0.0pt}\pgfsys@lineto{42.67914pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@moveto{16.72638pt}{28.45276pt}\pgfsys@curveto{16.72638pt}{29.83348pt}{15.6071pt}{30.95276pt}{14.22638pt}{30.95276pt}\pgfsys@curveto{12.84566pt}{30.95276pt}{11.72638pt}{29.83348pt}{11.72638pt}{28.45276pt}\pgfsys@curveto{11.72638pt}{27.07204pt}{12.84566pt}{25.95276pt}{14.22638pt}{25.95276pt}\pgfsys@curveto{15.6071pt}{25.95276pt}{16.72638pt}{27.07204pt}{16.72638pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@moveto{30.95276pt}{14.22638pt}\pgfsys@curveto{30.95276pt}{15.6071pt}{29.83348pt}{16.72638pt}{28.45276pt}{16.72638pt}\pgfsys@curveto{27.07204pt}{16.72638pt}{25.95276pt}{15.6071pt}{25.95276pt}{14.22638pt}\pgfsys@curveto{25.95276pt}{12.84566pt}{27.07204pt}{11.72638pt}{28.45276pt}{11.72638pt}\pgfsys@curveto{29.83348pt}{11.72638pt}{30.95276pt}{12.84566pt}{30.95276pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{42.67914pt}{28.45276pt}\pgfsys@moveto{45.17914pt}{28.45276pt}\pgfsys@curveto{45.17914pt}{29.83348pt}{44.05986pt}{30.95276pt}{42.67914pt}{30.95276pt}\pgfsys@curveto{41.29842pt}{30.95276pt}{40.17914pt}{29.83348pt}{40.17914pt}{28.45276pt}\pgfsys@curveto{40.17914pt}{27.07204pt}{41.29842pt}{25.95276pt}{42.67914pt}{25.95276pt}\pgfsys@curveto{44.05986pt}{25.95276pt}{45.17914pt}{27.07204pt}{45.17914pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\leavevmode\hbox
to43.28pt{\vbox to43.28pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@lineto{14.22638pt}{42.67914pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@lineto{28.45276pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{42.67914pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{12.0925pt}\pgfsys@moveto{0.0pt}{12.0925pt}\pgfsys@lineto{0.0pt}{16.36024pt}\pgfsys@lineto{12.0925pt}{16.36024pt}\pgfsys@lineto{12.0925pt}{12.0925pt}\pgfsys@closepath\pgfsys@moveto{12.0925pt}{16.36024pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{12.0925pt}\pgfsys@lineto{42.67914pt}{12.0925pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{16.36024pt}\pgfsys@lineto{42.67914pt}{16.36024pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{26.31888pt}\pgfsys@lineto{42.67914pt}{26.31888pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{30.58662pt}\pgfsys@lineto{42.67914pt}{30.58662pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@lineto{14.22638pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@moveto{16.72638pt}{28.45276pt}\pgfsys@curveto{16.72638pt}{29.83348pt}{15.6071pt}{30.95276pt}{14.22638pt}{30.95276pt}\pgfsys@curveto{12.84566pt}{30.95276pt}{11.72638pt}{29.83348pt}{11.72638pt}{28.45276pt}\pgfsys@curveto{11.72638pt}{27.07204pt}{12.84566pt}{25.95276pt}{14.22638pt}{25.95276pt}\pgfsys@curveto{15.6071pt}{25.95276pt}{16.72638pt}{27.07204pt}{16.72638pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@moveto{30.95276pt}{14.22638pt}\pgfsys@curveto{30.95276pt}{15.6071pt}{29.83348pt}{16.72638pt}{28.45276pt}{16.72638pt}\pgfsys@curveto{27.07204pt}{16.72638pt}{25.95276pt}{15.6071pt}{25.95276pt}{14.22638pt}\pgfsys@curveto{25.95276pt}{12.84566pt}{27.07204pt}{11.72638pt}{28.45276pt}{11.72638pt}\pgfsys@curveto{29.83348pt}{11.72638pt}{30.95276pt}{12.84566pt}{30.95276pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\right).$

In the above pair of forbidden Cayley-mesh patterns, the leftmost one
indicates an ascent that is not a leftmost copy; and the one on the right
stands for a leftmost copy that is not an ascent. Unlike
$\operatorname{A}_{0}$, not every modified ascent sequence is an inversion
sequence. For instance, the modified ascent sequence of $\alpha=1212$ is
$\hat{\alpha}=1312$.

Dukes and Sagan [DS23] have recently introduced _difference $d$ ascent
sequences_. Let $\alpha\in\operatorname{End}_{n}$. Given a nonnegative number
$d\geq 0$, we call $i\in[n]$ a _$d$ -ascent_ if $i=1$ or $i\geq 2$ and

$a_{i}>a_{i-1}-d.$

As with ordinary ascents, we have the $d$-ascent set (or _list_)

$\operatorname{Asc}_{d}\alpha=\\{i\in[n]\mid\text{$i$ is a $d$-ascent of
$\alpha$}\\}.$

and $d$-ascent number

$\operatorname{asc}_{d}\alpha=\\#\operatorname{Asc}_{d}\alpha.$

Note that a $0$-ascent is simply an ascent, while a $1$-ascent is what is
called a weak ascent:

$a_{i}>a_{i-1}-1\,\iff\,a_{i}\geq a_{i-1}.$

The analogue of the definition of an ascent sequence in the weak case is as
expected. Call $\alpha$ a _$d$ -ascent sequence_ if for all $i\in[n]$ we have

$a_{i}\leq 1+\operatorname{asc}_{d}\alpha_{i-1}.$

Once again, the above restriction forces $a_{1}=1$. From now on, denote by
$\operatorname{A}_{d,n}$ the set of $d$-ascent sequences of length $n$.
Clearly, for $d=0$ we recover the set of ascent sequences, while for $d=1$ we
obtain the set of weak ascent sequences of Bényi et al. [BCD23]. Note also
that $\operatorname{Asc}_{d}\alpha\subseteq\operatorname{Asc}_{d+1}\alpha$ for
each $d$, from which the chain of containments

$\operatorname{A}_{0}\subseteq\operatorname{A}_{1}\subseteq\operatorname{A}_{2}\subseteq\operatorname{A}_{3}\subseteq\dots$
(2)

follows immediately.

We now connect $d$-ascent sequences and inversion sequences.

######  Lemma 2.1.

We have

$\operatorname{I}=\bigcup_{d\geq 0}\operatorname{A}_{d}.$

###### Proof.

We will prove that each side of the equality is contained in the other. We
first show that $\operatorname{A}_{d}\subseteq\operatorname{I}$ for all $d\geq
0$ which will give one of the desired inclusions. If $\alpha=a_{1}\ldots
a_{n}\in\operatorname{A}_{d}$ then $a_{1}=1$ as required for an inversion
sequence. For $i\geq 2$, we have

$a_{i}\leq 1+\operatorname{asc}_{d}\alpha_{i-1}\leq 1+(i-1)=i.$

Thus $\alpha\in\operatorname{I}$.

For the other direction, it suffices to show that
$\operatorname{I}_{n}\subseteq\operatorname{A}_{n,n}$. So take
$\alpha=a_{1}\ldots a_{n}\in\operatorname{I}_{n}$. We have $a_{1}=1$ as
needed. And for $i\geq 2$ we have $a_{i-1}\leq i-1\leq n-1$. Hence
$a_{i}>-1\geq a_{i-1}-n$. Thus every index $i\geq 2$ is an $n$-ascent and so

$a_{i}\leq i=1+\operatorname{asc}_{n}\alpha_{i-1}$

showing that $\alpha\in\operatorname{A}_{n,n}$. ∎

We can now calculate the cardinality of certain $\operatorname{A}_{d,n}$.

######  Proposition 2.2.

For all $d\geq 0$ we have

$\\#\operatorname{A}_{d,n}=\begin{cases}n!&\text{if $n\leq d+2$,}\\\
(d+3)!-d!&\text{if $n=d+3$.}\end{cases}$

###### Proof.

By the previous lemma $\operatorname{A}_{d,n}\subseteq\operatorname{I}_{n}$.
Since $\\#I_{n}=n!$, to prove the first statement of the proposition, it
suffices to show that if $n\leq d+2$ then every inversion sequence of length
$n$ is a $d$-ascent sequence.

Let $\alpha\in\operatorname{I}_{n}$ where $n\leq d+2$. We claim that for every
proper prefix $\alpha_{i}$, $i\leq d+1$, we have
$\operatorname{Asc}_{d}\alpha_{i}=[i]$. Indeed, consider any element
$a_{j}\in\alpha_{i}$. Then, since $\alpha$ is an inversion sequence,

$a_{j-1}\leq j-1\leq i-1\leq d.$

Also $a_{j}\geq 1$. So $a_{j-1}-a_{j}\leq d-1<d$, which forces
$j\in\operatorname{Asc}_{d}\alpha_{i}$, proving the claim. Now, for all
$a_{k}\in\alpha$ we have

$a_{k}\leq k=1+\operatorname{asc}_{d}\alpha_{k-1},$

hence $\alpha$ is a $d$-ascent sequence, as desired.

To prove the second part of the proposition, we just need to show that when
$n=d+3$ there are exactly $d!$ elements of $\operatorname{I}_{d+3}$ which are
not $d$-ascent sequences.

Let $\alpha=a_{1}\ldots a_{d+3}$ be such a sequence. We show that the last
three entries of $\alpha$ are

$a_{d+1},a_{d+2},a_{d+3}=d+1,1,d+3,$

while the prefix $\beta=a_{1}\ldots a_{d}$ can be any inversion sequence of
size $d$. If we had $\operatorname{Asc}_{d}(\beta a_{d+1}a_{d+2})=[d+2]$,
then, using an argument like that of the previous paragraph, we would have
$\alpha\in\operatorname{A}_{d}$, which is a contradiction. On the other hand,
it follows from the proof of the first part that $\operatorname{Asc}_{d}(\beta
a_{d+1})=[d+1]$. So it must be that $d+2\not\in\operatorname{Asc}_{d}(\beta
a_{d+1}a_{d+2})$, i.e. $a_{d+2}\leq a_{d+1}-d$. Together with the fact that
$a_{d+1}\leq d+1$ and $a_{d+2}\geq 1$, this forces

$a_{d+1}=d+1\quad\text{and}\quad a_{d+2}=1.$

Now, since we assumed that $\alpha$ is not a $d$-ascent sequence, but we know
that its prefix $\beta a_{d+1}a_{d+2}$ is, it must be that

$a_{d+3}>\operatorname{asc}(\beta a_{d+1}a_{d+2})+1=d+2.$

Since $\alpha\in\operatorname{I}_{d+3}$ we also have $a_{d+3}\leq d+3$. It
follows that there is only one choice for the last element of $\alpha$, namely
$a_{d+3}=d+3$. In the end, we have $\alpha=\beta(d+1)1(d+3)$, where $\beta$ is
any inversion sequence of size $d$. Since there are $d!$ choices for such
$\beta$, the proposition is proved. ∎

##  3 Modified $d$-ascent sequences

We wish to extend the hat map $\alpha\mapsto\hat{\alpha}$, originally defined
on $\operatorname{A}_{0}$, to the set $\operatorname{A}_{d}$. Let
$\alpha\in\operatorname{A}_{d}$, for some $d\geq 0$. The _$d$ -hat_ of
$\alpha$ is defined as

$\mathrm{hat}_{d}(\alpha)=M\bigl{(}\alpha,\operatorname{Asc}_{d}\alpha\bigr{)},$

where $\operatorname{Asc}_{d}\alpha$ is the $d$-ascent list of $\alpha$. The
$d$-hat map is a natural generalization of the hat map, obtained by replacing
ascents with $d$-ascents. As a special case, we have
$\mathrm{hat}_{0}(\alpha)=\hat{\alpha}$ for each
$\alpha\in\operatorname{A}_{0}$. More generally, to compute
$\mathrm{hat}_{d}(\alpha)$ scan the $d$-ascents of $\alpha$ from left to
right; in each step, increment by one every element strictly to the left of
and weakly larger than the current $d$-ascent. From now on, given $d\geq 0$,
we let

$\operatorname{\hat{\operatorname{A}}}_{d}=\mathrm{hat}_{d}(\operatorname{A}_{d})$

denote the set of _modified $d$-ascent sequences_.

Let us set up some standard notation we shall use throughout the rest of this
paper. We will consider $d$-ascent sequences $\alpha=\beta a$, where $a$ is
the last letter of $\alpha$ and $\beta$ is a $d$-ascent sequence of size one
less than $\alpha$. If $d$ is clear from context, we let
$\hat{\alpha}=\mathrm{hat}_{d}(\alpha)$ and
$\hat{\beta}=\mathrm{hat}_{d}(\beta)$. We also use “$+$” as a superscript that
denotes the operation of adding one to the entries $c\geq a$ of a given
sequence, where $a$ is a threshold determined by the context. For instance, we
denote by $\hat{\beta}^{+}a$ the sequence obtained by adding one to each entry
of $\hat{\beta}$ that is greater than or equal to $a$. Clearly, letting $b$
denote the last letter of $\beta$, by definition of $\mathrm{hat}_{d}$ we have
for every $n\geq 1$ and $\alpha\in\operatorname{A}_{d,n}$

$\hat{\alpha}=\left\\{\begin{array}[]{ll}\hat{\beta}a&\mbox{if $a\leq
b-d$,}\\\ \hat{\beta}^{+}a&\mbox{if $a>b-d$.}\end{array}\right.$ (3)

Finally, we will denote the entries of the above sequences by

$\begin{array}[]{lllll}\alpha=a_{1}\ldots
a_{n},&&\hat{\alpha}=a^{\prime}_{1}\ldots a^{\prime}_{n},\\\ \beta=b_{1}\ldots
b_{n-1},&&\hat{\beta}=b^{\prime}_{1}\ldots
b^{\prime}_{n},&&\hat{\beta}^{+}=b^{\prime\prime}_{1}\ldots
b^{\prime\prime}_{n},\end{array}$ (4)

where $n$ is the size of $\alpha$. The behavior of $\mathrm{hat}_{d}$ on the
last two letters of $\alpha\in\operatorname{A}_{d}$ is described more
explicitly in the next lemma.

######  Lemma 3.1.

Let $\alpha=a_{1}\ldots a_{n}\in\operatorname{A}_{d}$, for some $d\geq 0$ and
$n\geq 2$. Let $\mathrm{hat}_{d}(\alpha)=\hat{\alpha}=a^{\prime}_{1}\ldots
a^{\prime}_{n}$. Then

$a^{\prime}_{n-1},a^{\prime}_{n}=\begin{cases}a_{n-1}+1,a_{n}&\text{if
$a_{n-1}-d<a_{n}\leq a_{n-1}$;}\\\ a_{n-1},a_{n}&\text{else.}\end{cases}$

###### Proof.

We use induction on the size of $\alpha$. Let $\alpha=\beta a_{n}$. The last
element of $\hat{\alpha}$ is $a_{n}$ by definition of $\mathrm{hat}_{d}$.
Similarly, the last letter of $\hat{\beta}=\mathrm{hat}_{d}(\beta)$ is
$a_{n-1}$.

Suppose initially that $a_{n}>a_{n-1}-d$. Then $n$ is a $d$-ascent and so
$\hat{\alpha}=\hat{\beta}^{+}a_{n}$. Now, if $a_{n-1}\geq a_{n}$ then
$a^{\prime}_{n-1}=a_{n-1}+1$ and $\hat{\alpha}$ ends with $a_{n-1}+1,a_{n}$.
Otherwise, if $a_{n-1}<a_{n}$ then $a_{n-1}$ will not be incremented and
$\hat{\alpha}$ ends with $a_{n-1},a_{n}$.

Finally, if $a_{n}\leq a_{n-1}-d$ then $n$ is not a $d$-ascent. So in this
case $\hat{\alpha}=\hat{\beta}a_{n}$ and the last two elements are
$a_{n-1},a_{n}$ again. ∎

Our next goal is to provide a recursive definition of
$\operatorname{\hat{\operatorname{A}}}_{d}$ which does not depend on
constructing $\operatorname{A}_{d}$ first. In the classical case, such a
definition of $\hat{\operatorname{A}}_{0}$ is as follows [CC23b], where we use
$\hat{\alpha}$ and $\hat{\beta}$ to denote generic elements of
$\operatorname{\hat{\operatorname{A}}}_{d}$. Note that this definition permits
the computation of an element $\hat{\alpha}$ in $\hat{\operatorname{A}}_{d}$
directly from a given $\hat{\beta}$ in $\hat{\operatorname{A}}_{d}$ without
needing to know $\alpha$ itself.

######  Definition 3.2.

We have $\hat{\operatorname{A}}_{0,0}=\\{\epsilon\\}$ and
$\hat{\operatorname{A}}_{0,1}=\\{1\\}$. Let $n\geq 2$. Then every
$\hat{\alpha}\in\hat{\operatorname{A}}_{0,n}$ is of one of two forms depending
on whether the last letter forms an ascent with the penultimate letter:

  * •

$\hat{\alpha}=\hat{\beta}a$ and $1\leq a\leq b$, or

  * •

$\hat{\alpha}=\hat{\beta}^{+}a$ and $b<a\leq 1+\operatorname{asc}\hat{\beta}$,

where $\hat{\beta}\in\hat{\operatorname{A}}_{0,n-1}$ and the last letter of
$\hat{\beta}$ is $b$.

We wish to highlight a detail that explains why the definition given above is
consistent with letting
$\hat{\alpha}=M\bigl{(}\alpha,\operatorname{Asc}\alpha\bigr{)}$. Given
$\alpha\in\operatorname{A}$, to compute $\hat{\alpha}$ we increase entries in
the current prefix if and only if we encounter an ascent of $\alpha$. On the
other hand, Definition 3.2 is stated directly in terms of the ascents of the
modified sequence, i.e. in terms of $\operatorname{Asc}\hat{\beta}$. Since it
is known [BMCDK10] that

$\operatorname{Asc}\alpha=\operatorname{Asc}\mathrm{hat}_{0}(\alpha),$ (5)

i.e. the ascent set is preserved under the hat map, these two approaches are
in fact equivalent.

In the same spirit, we wish to give a recursive definition of
$\operatorname{\hat{\operatorname{A}}}_{d}$. The problem in generalizing
Definition 3.2 is that in general the $d$-ascent set, as well as its
cardinality, is not preserved under $\mathrm{hat}_{d}$. For instance, for
$d=1$ we have $\mathrm{hat}_{1}(11)=21$ and

$\\{1,2\\}=\operatorname{Asc}_{1}(11)\neq\operatorname{Asc}_{1}(21)=\\{1\\}.$

A suggestion for an alternative approach comes from the classical case $d=0$.
Let $\alpha\in\operatorname{A}_{0}$ and let
$\hat{\alpha}=\mathrm{hat}_{0}(\alpha)$. Then [BMCDK10]

$\operatorname{Asc}\alpha=\operatorname{nub}\hat{\alpha}\quad\text{and}\quad\operatorname{asc}\beta=\max\hat{\alpha}.$
(6)

In fact, the corresponding equalities hold for every $d\geq 0$, as we show in
the next proposition.

######  Proposition 3.3.

Given $d\geq 0$, let $\alpha\in\operatorname{A}_{d}$ and let
$\hat{\alpha}=\mathrm{hat}_{d}(\alpha)$. Then $\hat{\alpha}$ is a Cayley
permutation with

$\operatorname{Asc}_{d}\alpha=\operatorname{nub}\hat{\alpha}\quad\text{and}\quad\operatorname{asc}_{d}\alpha=\max\hat{\alpha}.$

###### Proof.

We use induction on the size of $\alpha$. It is easy to see that the statement
holds if $\alpha$ has length zero or one. Let $n\geq 2$ and let
$\alpha\in\operatorname{A}_{d,n}$. As usual, let $\alpha=\beta a$, for some
$\beta\in\operatorname{A}_{d,n-1}$ and $1\leq a\leq
1+\operatorname{asc}_{d}\beta$. By induction,
$\hat{\beta}=\mathrm{hat}_{d}(\beta)$ is a Cayley permutation with
$\operatorname{Asc}_{d}\beta=\operatorname{nub}\hat{\beta}$ and
$\operatorname{asc}_{d}\beta=\max\hat{\beta}$. Following the definition of
$\mathrm{hat}_{d}$, we consider two possibities according to wheter or not $a$
forms a $d$-ascent with the last letter $b$ of $\beta$.

  * •

Suppose $a\leq b-d$. Then $\hat{\alpha}=\hat{\beta}a$. Note that
$\hat{\alpha}\in\operatorname{Cay}_{n}$ since
$\beta\in\operatorname{Cay}_{n-1}$ and $a\leq b-d\leq\max\beta$. Furthermore,

$\displaystyle\operatorname{Asc}_{d}\alpha$
$\displaystyle=\operatorname{Asc}_{d}\beta=\operatorname{nub}\hat{\beta}=\operatorname{nub}\hat{\alpha}$
and $\displaystyle\operatorname{asc}_{d}\alpha$
$\displaystyle=\operatorname{asc}_{d}\beta=\max\hat{\beta}=\max\hat{\alpha}.$

  * •

Suppose $a>b-d$. Then $\hat{\alpha}=\hat{\beta}^{+}a$. Once again, it is easy
to see that $\hat{\alpha}\in\operatorname{Cay}_{n}$ as follows.

First note that by the definition of $d$-hat and induction we have

$a\leq\operatorname{asc}_{d}\beta+1=\max\hat{\beta}+1$

If $a=\max\hat{\beta}+1$, then $\hat{\beta}^{+}=\hat{\beta}$ and

$\operatorname{Im}\hat{\alpha}=\operatorname{Im}\hat{\beta}\cup\\{a\\}=[\max\hat{\beta}+1]=[\max\hat{\alpha}].$

On the other hand, if $a\leq\max\hat{\beta}$, then the only gap created in
$\hat{\beta}^{+}$ (by lifting the entries $c\geq a$) is filled by $a$. More
formally,

$\displaystyle\operatorname{Im}\hat{\alpha}$
$\displaystyle=\operatorname{Im}\hat{\beta}^{+}\cup\\{a\\}$
$\displaystyle=\\{1,2,\dots,a-1\\}\cup\\{a+1,a+2,\dots,\max(\hat{\beta})+1\\}\cup\\{a\\}$
$\displaystyle=[\max\hat{\beta}+1]$ $\displaystyle=[\max\hat{\alpha}].$

Finally,

$\displaystyle\operatorname{Asc}_{d}\alpha$
$\displaystyle=\operatorname{Asc}_{d}\beta\uplus\\{n\\}$
$\displaystyle=\operatorname{nub}\hat{\beta}\uplus\\{n\\}$
$\displaystyle=\operatorname{nub}\hat{\beta}^{+}\uplus\\{n\\}$
$\displaystyle=\operatorname{nub}\hat{\alpha},$ where the last equality
follows since $a$ is a leftmost copy in $\hat{\alpha}$, and
$\displaystyle\operatorname{asc}_{d}\alpha$
$\displaystyle=\operatorname{asc}_{d}\beta+1=\max\hat{\beta}+1=\max\hat{\alpha}.$

This finishes the proof of the proposition. ∎

The equality $\operatorname{asc}_{d}\beta=\max\mathrm{hat}_{d}(\beta)$ proved
in Proposition 3.3 leads us to the following recursive definition of modified
$d$-ascent sequences, where we use the same notational conventions as in
Definition 3.2.

######  Definition 3.4.

Let $d\geq 0$ be a nonnegative integer. Let
$\hat{\operatorname{A}}_{d,0}=\\{\epsilon\\}$ and
$\hat{\operatorname{A}}_{d,1}=\\{1\\}$. Then, suppose $n\geq 2$. Every
$\hat{\alpha}\in\hat{\operatorname{A}}_{d,n}$ is of one of two forms depending
on whether the last letter forms a $d$-ascent with the penultimate letter:

  * •

$\hat{\alpha}=\hat{\beta}a$ and $1\leq a\leq b-d$, or

  * •

$\hat{\alpha}=\hat{\beta}^{+}a$ and $b-d<a\leq 1+\max\hat{\beta}$,

where $\hat{\beta}\in\hat{\operatorname{A}}_{d,n-1}$ and the last letter of
$\hat{\beta}$ is $b$.

The reader will immediately realize that the previous definition is obtained
by replacing $\operatorname{asc}\hat{\beta}$ with $\max\hat{\beta}$ in
Definition 3.2. When $d=0$, the two definitions are equivalent by equation
(6). Modified $d$-ascent sequences are built recursively by insertion of a new
rightmost entry $a$, which is at most equal to one plus the current maximum;
the parameter $d$ determines the cases where the prefix is rescaled (by adding
one to each entry $c\geq a$). For convenience, the analogous definitions of
$\operatorname{A}_{d}$ and $\operatorname{\hat{\operatorname{A}}}_{d}$ are
illustrated below:

$\displaystyle(\operatorname{A}_{d})\quad\alpha$ $\displaystyle=\beta a,\
1\leq a\leq 1+\operatorname{asc}_{d}\beta.$
$\displaystyle(\operatorname{\hat{\operatorname{A}}}_{d})\quad\hat{\alpha}$
$\displaystyle=\begin{cases}\hat{\beta}a,\ 1\leq a\leq b-d;\\\
\hat{\beta}^{+}a,\ b-d<a\leq 1+\max\hat{\beta}.\end{cases}$

The equality $\operatorname{asc}_{d}\beta=\max\mathrm{hat}_{d}(\beta)$ acts as
a bridge between the two definitions.

Let us end this section with a remark. In general, the set
$\operatorname{\hat{\operatorname{A}}}_{d}$ is not included in
$\hat{\operatorname{A}}_{d+1}$. For instance, we have

$\displaystyle\hat{\operatorname{A}}_{0}$
$\displaystyle=\\{\mathrm{hat}_{0}(11),\mathrm{hat}_{0}(12)\\}=\\{11,12\\}$
and $\displaystyle\hat{\operatorname{A}}_{1}$
$\displaystyle=\\{\mathrm{hat}_{1}(11),\mathrm{hat}_{1}(12)\\}=\\{21,12\\}.$

##  4 Properties of $d$-hat

We devote this section to the study of several aspects related to the $d$-hat
map just introduced.

Recall from Proposition 3.3 that
$\operatorname{nub}\mathrm{hat}_{d}(\alpha)=\operatorname{Asc}_{d}\alpha$.
When $d=0$, using equation (5) we obtain the equality

$\operatorname{nub}\mathrm{hat}_{0}(\alpha)=\operatorname{Asc}\mathrm{hat}_{0}(\alpha)$

characterizing $\operatorname{\hat{\operatorname{A}}}$ as a subset of
$\operatorname{Cay}$ (see equation (1)). Since we have established in
Proposition 3.3 that
$\operatorname{\hat{\operatorname{A}}}_{d}\subseteq\operatorname{Cay}$ for
every $d\geq 0$, a natural question arises:

_Is there an analogous equality characterizing
$\operatorname{\hat{\operatorname{A}}}_{d}$ when $d\geq 1$?_

As mentioned before Proposition 3.3, the equality
$\operatorname{Asc}_{d}\mathrm{hat}_{d}(\alpha)=\operatorname{Asc}_{d}\alpha$
does not hold for $d\geq 1$. However, we show in Proposition 4.3 that one
inclusion holds. First, a simple lemma.

######  Lemma 4.1.

Let $\beta\in\operatorname{End}$ and let $\beta^{+}$ be obtained from $\beta$
by increasing by one each entry greater than or equal to $a$, for some $a\geq
0$. Then for all $d\geq 0$

$\operatorname{Asc}_{d}\beta^{+}\subseteq\operatorname{Asc}_{d}\beta\quad\text{and}\quad\operatorname{Asc}\beta^{+}=\operatorname{Asc}\beta.$

###### Proof.

Let $\beta=b_{1}\ldots b_{n}$ and $\beta^{+}=b^{\prime}_{1}\ldots
b^{\prime}_{n}$, where $b^{\prime}_{i}=b_{i}$, if $b_{i}<a$, and
$b^{\prime}_{i}=b_{i}+1$, if $b_{i}\geq a$. Note that the first position $i=1$
is a $d$-ascent by definition. On the other hand, let $i\geq 2$ and suppose
that $i\in\operatorname{Asc}_{d}\beta^{+}$. We show that
$i\in\operatorname{Asc}_{d}\beta$. For a contradiction, suppose that
$i\notin\operatorname{Asc}_{d}\beta$. More explicitly, we have

$\displaystyle i\notin\operatorname{Asc}_{d}\beta$ $\displaystyle\iff
b_{i}\leq b_{i-1}-d;$ $\displaystyle i\in\operatorname{Asc}_{d}\beta^{+}$
$\displaystyle\iff b^{\prime}_{i}>b^{\prime}_{i-1}-d.$

Comparing the two inequalities forces $b^{\prime}_{i}=b_{i}+1$ and
$b^{\prime}_{i-1}=b_{i-1}$. Therefore, we have $b_{i-1}<a\leq b_{i}$ and

$b_{i}\leq b_{i}+d\leq b_{i-1}<a\leq b_{i},$

which gives us the desired contradiction.

By the previous part of the proposition (and since an ascent is a $0$-ascent),
to prove the remaining equality
$\operatorname{Asc}\beta^{+}=\operatorname{Asc}\beta$ we only need to show
that $\operatorname{Asc}\beta^{+}\supseteq\operatorname{Asc}\beta$. Let
$i\in\operatorname{Asc}\beta$. If $i=1$, then
$i\in\operatorname{Asc}\beta^{+}$. If instead $i\geq 2$, then $b_{i}>b_{i-1}$
and thus $b_{i}$ will be increased in $\beta^{+}$ if $b_{i-1}$ is increased.
In any case, we have $b^{\prime}_{i}>b^{\prime}_{i+1}$, hence
$i\in\operatorname{Asc}\beta^{+}$. This completes the proof. ∎

######  Corollary 4.2.

Let $d\geq 0$. Suppose that $\alpha\in\operatorname{A}_{d}$ and let
$\hat{\alpha}=\mathrm{hat}_{d}(\alpha)$. Then

$\operatorname{Asc}_{d}\hat{\alpha}\subseteq\operatorname{Asc}_{d}\alpha.$

###### Proof.

We use induction on the size $n$ of $\alpha$, taking the case $n\leq 1$ for
granted. Assume $n\geq 2$. Let $\alpha=\beta a$, where
$\beta\in\operatorname{A}_{d,n-1}$ and $1\leq a\leq
1+\operatorname{asc}_{d}\beta$, and let $\hat{\beta}=\mathrm{hat}_{d}(\beta)$.
As usual, we consider two cases according to whether or not the last letter
$b$ of $\beta$ forms a $d$-ascent with $a$.

Suppose first that $1\leq a\leq b-d$. Then $\hat{\alpha}=\hat{\beta}a$, where
$\operatorname{Asc}_{d}\beta\subseteq\operatorname{Asc}_{d}\hat{\beta}$ by
induction. Now by Definition 3.4

$\operatorname{Asc}_{d}\hat{\alpha}=\operatorname{Asc}_{d}\hat{\beta}\subseteq\operatorname{Asc}_{d}\beta=\operatorname{Asc}_{d}\alpha.$

Otherwise, suppose that $b-d<a\leq 1+\operatorname{asc}_{d}\beta$. Then
$\hat{\alpha}=\hat{\beta}^{+}a$. Now using Lemma 4.1 and induction we have

$\operatorname{Asc}_{d}\hat{\alpha}\subseteq\operatorname{Asc}_{d}\hat{\beta}^{+}\cup\\{n\\}\subseteq\operatorname{Asc}_{d}\hat{\beta}\cup\\{n\\}\subseteq\operatorname{Asc}_{d}\beta\cup\\{n\\}=\operatorname{Asc}_{d}\alpha.$

This completes the demonstration. ∎

Combining Proposition 3.3 and Corollary 4.2 immediately gives the following
result.

######  Proposition 4.3.

Let $d\geq 0$. We have, for any
$\hat{\alpha}\in\operatorname{\hat{\operatorname{A}}}_{d}$,

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle\operatorname{Asc}_{d}\hat{\alpha}\subseteq\operatorname{nub}\hat{\alpha}.}\hfill\qed$

###  4.1 Injectivity of $\mathrm{hat}_{d}$

Our next goal is to prove that $d$-hat is injective on $\operatorname{A}_{d}$
for every $d\geq 0$. Let $\alpha\in\operatorname{I}$ be an inversion sequence.
By Lemma 2.1, the quantity

$\operatorname{dmin}\alpha=\min\\{d\geq
0\mid\alpha\in\operatorname{A}_{d}\\}.$

is a nonnegative integer for every $\alpha$. Furthermore, by equation (2) if
$\alpha$ is a $d$-ascent sequence for some $d$, then it is a $k$-ascent
sequence for every $k\geq d$. It is natural to study the set

$H(\alpha)=\\{\mathrm{hat}_{d}(\alpha)\mid d\geq\operatorname{dmin}\alpha\\}$

of all the (meaningful) $d$-hats of $\alpha$. Note that
$H(\alpha)\subseteq\operatorname{Cay}$ by Proposition 3.3. Next, we show that
$H(\alpha)$ is finite.

######  Lemma 4.4.

Let $\alpha\in\operatorname{I}_{n}$. Then $\operatorname{dmin}\alpha\leq n$.
Further, we have $\mathrm{hat}_{d}(\alpha)=\mathrm{hat}_{n}(\alpha)$ for each
$d\geq n$.

###### Proof.

Recall from the proof of Lemma 2.1 that
$\operatorname{I}_{n}\subseteq\operatorname{A}_{n,n}$. The inequality
$\operatorname{dmin}\alpha\leq n$ follows immediately. Finally, let $d\geq n$.
Then

$\operatorname{Asc}_{d}\alpha=\operatorname{Asc}_{n}\alpha=[n]$

and the equality $\mathrm{hat}_{d}(\alpha)=\mathrm{hat}_{n}(\alpha)$ follows
directly from the definition of $d$-hat. ∎

By Lemma 4.4, we have

$H(\alpha)=\left\\{\mathrm{hat}_{d}(\alpha)\mid\operatorname{dmin}\alpha\leq
d\leq|\alpha|\right\\},$

from which the following corollary is obtained immediately.

######  Corollary 4.5.

Let $\alpha$ be an inversion sequence. Then $H(\alpha)$ is finite. ∎

Let us now prove that the sets $H(\alpha)$ are disjoint. The injectivity of
$\mathrm{hat}_{d}$ over $\operatorname{A}_{d}$ will immediately follow as a
corollary.

######  Proposition 4.6.

Let $\alpha$ and $\sigma$ be inversion sequences and suppose that
$H(\alpha)\cap H(\sigma)\neq\emptyset$. Then $\alpha=\sigma$.

###### Proof.

We use induction on the size. The statement clearly holds for inversion
sequences of size $n\leq 1$, so suppose $n\geq 2$. Let $\alpha$ and $\sigma$
be in $\operatorname{I}_{n}$, with $H(\alpha)\cap H(\sigma)\neq\emptyset$. If
$\gamma\in H(\alpha)\cap H(\sigma)$, then

$\mathrm{hat}_{d}(\alpha)=\mathrm{hat}_{k}(\sigma)=\gamma,$

for some $d\geq\operatorname{dmin}\alpha$ and
$k\geq\operatorname{dmin}\sigma$. We prove that $\alpha=\sigma$. Denote by $y$
the last letter of $\gamma$. Note that the last letters of $\alpha$ and
$\sigma$ are equal to $y$ as well. That is, we have $\alpha=\beta y$ and
$\sigma=\tau y$, where $\beta$ and $\tau$ denote the corresponding prefixes of
$\alpha$ and $\sigma$. We consider two cases, according to whether or not $y$
is a leftmost copy in $\gamma$.

Initially, suppose that $n\notin\operatorname{nub}\gamma$. Recall by
Proposition 3.3 that

$\operatorname{Asc}_{d}\alpha=\operatorname{nub}\gamma=\operatorname{Asc}_{k}\sigma.$

In particular, the last position $n$ is neither a $d$-ascent in $\alpha$, nor
a $k$-ascent in $\sigma$. By definition of $\mathrm{hat}_{d}$ and
$\mathrm{hat}_{k}$, we have, respectively,

$\displaystyle\gamma$
$\displaystyle=\mathrm{hat}_{d}(\alpha)=\mathrm{hat}_{d}(\beta)y$ and
$\displaystyle\gamma$
$\displaystyle=\mathrm{hat}_{k}(\sigma)=\mathrm{hat}_{k}(\tau)y.$

This forces $\mathrm{hat}_{d}(\beta)=\mathrm{hat}_{k}(\tau)$ so that
$H(\beta)\cap H(\tau)\neq\emptyset$. By induction, we have $\beta=\tau$ and
consequently

$\alpha=\beta y=\tau y=\sigma.$

Finally, suppose that $n\in\operatorname{nub}\gamma$. The proof is similar to
the previous case, the difference being that here the last position is a
$d$-ascent in $\alpha$, as well as a $k$-ascent in $\sigma$. Therefore,

$\displaystyle\gamma$
$\displaystyle=\mathrm{hat}_{d}(\alpha)=\mathrm{hat}_{d}(\beta)^{+}y$ and
$\displaystyle\gamma$
$\displaystyle=\mathrm{hat}_{k}(\sigma)=\mathrm{hat}_{k}(\tau)^{+}y,$

and thus $\mathrm{hat}_{d}(\beta)^{+}=\mathrm{hat}_{k}(\tau)^{+}$. Since both
$\mathrm{hat}_{d}(\beta)^{+}$ and $\mathrm{hat}_{k}(\tau)^{+}$ are obtained by
rescaling entries $c\geq y$, we have
$\mathrm{hat}_{d}(\beta)=\mathrm{hat}_{k}(\tau)$, and we can finish the proof
as in the previous case. ∎

######  Corollary 4.7.

For each $d\geq 0$, we have a bijection
$\mathrm{hat}_{d}:\operatorname{A}_{d}\to\operatorname{\hat{\operatorname{A}}}_{d}$.
∎

###  4.2 Statistics preserved by $\mathrm{hat}_{d}$

Let us now turn our attention to which statistics are preserved by $d$-hat.
Define the weak descent set of $\alpha$ to be

$\operatorname{wDes}\alpha=\\{i\geq 2\mid a_{i}\leq a_{i-1}\\}$

We also say that $i$ is a right-left minimum index of $\alpha$ if
$a_{i}<a_{j}$ for all $i<j\leq n$. Further, the set of right-left minima pairs
is

$\operatorname{rlMinP}\alpha=\\{(i,a_{i})\mid\text{$i$ is a right-left minimum
index of $\alpha$}\\}.$

The following lemma will be useful.

######  Lemma 4.8.

Let $\alpha=a_{1}a_{2}\ldots a_{n}=\beta a_{n}$ where $n\geq 1$. Then

$\operatorname{rlMinP}(\alpha)=\operatorname{rlMinP}(a_{1}\ldots
a_{k})\uplus\\{(n,a_{n})\\}$

where $k\geq 1$ is the largest right-left minimum index of $\beta$ such that
$a_{k}<a_{n}$. If no such index exists then we let $k=0$ so that
$\operatorname{rlMinP}(a_{1}\ldots
a_{k})=\operatorname{rlMinP}(\emptyset)=\emptyset$.

###### Proof.

Consider what happens in passing from $\operatorname{rlMinP}\beta$ to
$\operatorname{rlMinP}\alpha$. Of course, $(n,a_{n})$ becomes a right-left
minimum pair in $\operatorname{rlMinP}\alpha$ since $a_{n}$ is the last
element of the sequence. Furthermore, any right-left minimum values $a_{i}$ of
$\operatorname{rlMinP}\beta$ with $a_{i}>a_{n}$ will now have a smaller
element to their right and so it will be removed in the transition to
$\operatorname{rlMinP}\alpha$. The remaining pairs of
$\operatorname{rlMinP}\beta$ will be preserved in
$\operatorname{rlMinP}\alpha$. This is equivalent to our claim. ∎

######  Theorem 4.9.

Suppose $\alpha\in\operatorname{I}_{n}$. We have the following for all
$\gamma\in H(\alpha)$:

  1. (a)

$\operatorname{Asc}\gamma=\operatorname{Asc}\alpha$.

  2. (b)

$\operatorname{wDes}\gamma=\operatorname{wDes}\alpha$.

  3. (c)

$\operatorname{rlMinP}\gamma=\operatorname{rlMinP}\alpha$.

###### Proof.

(a) We induct on $n$ where the case $n\leq 1$ is trivial. Let $\alpha=\beta
a$. Pick a $d$ for which $\alpha$ is a $d$-ascent sequence and let
$\hat{\alpha}=\mathrm{hat}_{d}(\alpha)$ and
$\hat{\beta}=\mathrm{hat}_{d}(\beta)$. We follow our usual conventions (3) and
(4) and denote by $b$, $b^{\prime}$ and $b^{\prime\prime}$ the last letter of
$\beta$, $\hat{\beta}$ and $\hat{\beta}^{+}$, respectively. Note that
$b^{\prime}=b$ by Lemma 3.1. By induction, we have

$\operatorname{Asc}\hat{\beta}=\operatorname{Asc}\beta.$

There are now three cases. First suppose that $a\leq b-d$, so that
$\hat{\alpha}=\hat{\beta}a$. From this, the induction hypothesis, and the fact
that $a\leq b=b^{\prime}$ we obtain

$\operatorname{Asc}\hat{\alpha}=\operatorname{Asc}(\hat{\beta}a)=\operatorname{Asc}\hat{\beta}=\operatorname{Asc}\beta=\operatorname{Asc}(\beta
a)=\operatorname{Asc}\alpha.$

For the next two cases we will have $a>b-d$ so that $n$ is a $d$-ascent and
$\hat{\alpha}=\hat{\beta}^{+}a$. If $a\leq b$, then

$b^{\prime\prime}=b^{\prime}+1=b+1>a.$

Thus, using Lemma 4.1,

$\operatorname{Asc}\hat{\alpha}=\operatorname{Asc}(\hat{\beta}^{+}a)=\operatorname{Asc}\hat{\beta}^{+}=\operatorname{Asc}\hat{\beta}=\operatorname{Asc}\beta=\operatorname{Asc}\beta
a=\operatorname{Asc}\alpha.$

Finally, suppose that $a>b$. Then

$b^{\prime\prime}=b^{\prime}=b<a$

and, in a similar manner to the first case,

$\operatorname{Asc}\hat{\alpha}=\operatorname{Asc}\hat{\beta}^{+}\cup\\{n\\}=\operatorname{Asc}\beta\cup\\{n\\}=\operatorname{Asc}\alpha,$

proving the first item.

(b) Directly from the definitions, for all inversion sequences $\alpha$ of
length $n$ we have
$\operatorname{Asc}\alpha\uplus\operatorname{wDes}\alpha=[n]$. So this part
follows immediately from (a).

(c) By induction

$\operatorname{rlMinP}\hat{\beta}=\operatorname{rlMinP}\beta.$

Again, we begin with the case $a\leq b-d$ so that $\hat{\alpha}=\hat{\beta}a$.
By induction and the fact that both $\alpha$ and $\hat{\alpha}$ end in $a$, we
see that the index $k$ in Lemma 4.8 will be the same for both $\alpha$ and
$\hat{\alpha}$. Thus, using the same lemma and the inductive hypothesis,

$\displaystyle\operatorname{rlMinP}\hat{\alpha}$
$\displaystyle=\operatorname{rlMinP}(b^{\prime}_{1}\ldots
b^{\prime}_{k})\uplus\\{(n,a_{n})\\}$
$\displaystyle=\operatorname{rlMinP}(b_{1}\ldots b_{k})\uplus\\{(n,a_{n})\\}$
$\displaystyle=\operatorname{rlMinP}\alpha.$

Now consider what happens when $a>b-d$ and $\hat{\alpha}=\hat{\beta}^{+}a$. We
must relate $\operatorname{rlMinP}\hat{\beta}$ and
$\operatorname{rlMinP}\hat{\beta}^{+}$. By the way $\hat{\beta}^{+}$ is
constructed from $\hat{\beta}$ we see that every pair
$(i,b^{\prime}_{i})\in\operatorname{rlMinP}\hat{\beta}$ is either replaced by
$(i,b^{\prime}_{i}+1)\in\operatorname{rlMinP}\hat{\beta}^{+}$ if
$b^{\prime}_{i}\geq a$ or remains as $(i,b^{\prime}_{i})$ if
$b^{\prime}_{i}<a$. In particular, $\hat{\beta}^{+}a$ and $\hat{\beta}a$ will
have the same index $k$ from Lemma 4.8. Moreover, due to our choice of $k$,

$\operatorname{rlMinP}(b^{\prime\prime}_{1}\ldots
b^{\prime\prime}_{k})=\operatorname{rlMinP}(b^{\prime}_{1}\ldots
b^{\prime}_{k})=\operatorname{rlMinP}(b_{1}\ldots b_{k}).$

The proof is now completed in a manner similar to the first case. ∎

##  5 Modified inversion sequences

Recall from Lemma 2.1 that $\operatorname{I}=\bigcup_{d\geq
0}\operatorname{A}_{d}$. We shall define the set $\operatorname{\hat{I}}$ of
_modified inversion sequences_ as

$\operatorname{\hat{I}}=\bigcup_{d\geq
0}\operatorname{\hat{\operatorname{A}}}_{d}.$ (7)

An alternative way of arriving at $\operatorname{\hat{I}}$ is illustrated in
the next result which follows easily from Lemma 2.1 and Proposition 4.6.

######  Proposition 5.1.

We have the disjoint union

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle\operatorname{\hat{I}}={\biguplus_{\alpha\in\operatorname{I}}}H(\alpha).}\hfill\qed$

By Proposition 3.3, modified inversion sequences are Cayley permutations; that
is, $\operatorname{\hat{I}}\subseteq\operatorname{Cay}$. Further, by
Proposition 4.6 given any $\gamma\in\operatorname{\hat{I}}$ there is a unique
$\alpha\in\operatorname{I}$ such that $\gamma=\mathrm{hat}_{d}(\alpha)$, for
some $d\geq\operatorname{dmin}\alpha$. Note that such $d$ is not unique, but
$\alpha$ is. This allows us to define a map

$h:\operatorname{\hat{I}}\to\operatorname{I}$

by letting $h(\gamma)$ be the only inversion sequence $\alpha$ such that
$\gamma\in H(\alpha)$. We wish to describe $h$ more explicitly. First, let us
recall [BMCDK10] an algorithm to define $h(\gamma)$ in the special case where
$\gamma$ is the modified ascent sequence of $\alpha\in\operatorname{A}_{0}$.
Let $\gamma=g_{1}\ldots g_{n}$ and let
$\operatorname{Asc}\gamma=(i_{1},\dots,i_{k})$. Then:

$\displaystyle\mathtt{for}\;i=i_{k},$ $\displaystyle\dots,i_{1}:$
$\displaystyle\mathtt{for}\;j$ $\displaystyle=1,\dots,i-1:$
$\displaystyle\mathtt{if}\;g_{j}>g_{i}\;\mathtt{then}\;g_{j}:=g_{j}-1.$

The output of the above procedure is the desired ascent sequence $\alpha$.
Since $\alpha\in\operatorname{A}_{0}$, we have
$\operatorname{Asc}\alpha=\operatorname{Asc}\gamma$. The previous algorithm
goes through the $0$-ascents of $\gamma$, from right to left, to determine the
cases where the entries in the prefix need to be decreased. To define $d$-hat,
we have replaced $\operatorname{Asc}\alpha$ with
$\operatorname{Asc}_{d}\alpha$. By Proposition 3.3, we have
$\operatorname{Asc}_{d}\alpha=\operatorname{nub}\gamma$. Therefore, by
replacing $\operatorname{Asc}\gamma$ with $\operatorname{nub}\gamma$ in the
algorithm just given we will obtain the desired generalization of $h$ to the
set $\operatorname{\hat{I}}$. Surprisingly, the definition does not depend on
$d$. Instead of writing the algorithm explicitly, we shall give an equivalent,
recursive description of $h$. Let $h(\epsilon)=\epsilon$, the empty sequence,
and $h(1)=1$. Suppose $n\geq 2$ and let $\gamma=g_{1}\ldots
g_{n}\in\operatorname{\hat{I}}_{n}$. Let $\delta=g_{1}\ldots g_{n-1}$. Then

$h(\gamma)=\begin{cases}h(\delta^{-})g_{n}&\text{if
$n\in\operatorname{nub}\gamma$;}\\\
h(\delta)g_{n}&\text{otherwise,}\end{cases}$

where $\delta^{-}$ is obtained from $\delta$ by decreasing by one each entry
$c>g_{n}$. The map $h:\operatorname{\hat{I}}\to\operatorname{I}$ defined this
way is bijective and

$h\circ\mathrm{hat}_{d}(\alpha)=\alpha\quad\text{for every
$\alpha\in\operatorname{A}_{d}$.}$

We leave the details to the reader.

To obtain a deeper understanding of $\operatorname{\hat{I}}$, it would be
interesting to characterize it as a subset of $\operatorname{Cay}$ in the same
spirit of equation (1) for $\hat{\operatorname{A}}_{0}$. The following
proposition is a first step in this direction.

######  Proposition 5.2.

Let $\gamma\in\operatorname{\hat{I}}$. Then
$\operatorname{Asc}\gamma\subseteq\operatorname{nub}\gamma$. Thus,

$\operatorname{\hat{I}}\subseteq\operatorname{Cay}\left(\leavevmode\hbox
to57.51pt{\vbox to43.28pt{\pgfpicture\makeatletter\hbox{\hskip
0.3pt\lower-0.3pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@lineto{42.67914pt}{42.67914pt}\pgfsys@lineto{42.67914pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{42.67914pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{12.0925pt}\pgfsys@lineto{56.90552pt}{12.0925pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{16.36024pt}\pgfsys@lineto{56.90552pt}{16.36024pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{26.31888pt}\pgfsys@lineto{56.90552pt}{26.31888pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{30.58662pt}\pgfsys@lineto{56.90552pt}{30.58662pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@lineto{14.22638pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{42.67914pt}{0.0pt}\pgfsys@lineto{42.67914pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@moveto{16.72638pt}{28.45276pt}\pgfsys@curveto{16.72638pt}{29.83348pt}{15.6071pt}{30.95276pt}{14.22638pt}{30.95276pt}\pgfsys@curveto{12.84566pt}{30.95276pt}{11.72638pt}{29.83348pt}{11.72638pt}{28.45276pt}\pgfsys@curveto{11.72638pt}{27.07204pt}{12.84566pt}{25.95276pt}{14.22638pt}{25.95276pt}\pgfsys@curveto{15.6071pt}{25.95276pt}{16.72638pt}{27.07204pt}{16.72638pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@moveto{30.95276pt}{14.22638pt}\pgfsys@curveto{30.95276pt}{15.6071pt}{29.83348pt}{16.72638pt}{28.45276pt}{16.72638pt}\pgfsys@curveto{27.07204pt}{16.72638pt}{25.95276pt}{15.6071pt}{25.95276pt}{14.22638pt}\pgfsys@curveto{25.95276pt}{12.84566pt}{27.07204pt}{11.72638pt}{28.45276pt}{11.72638pt}\pgfsys@curveto{29.83348pt}{11.72638pt}{30.95276pt}{12.84566pt}{30.95276pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{42.67914pt}{28.45276pt}\pgfsys@moveto{45.17914pt}{28.45276pt}\pgfsys@curveto{45.17914pt}{29.83348pt}{44.05986pt}{30.95276pt}{42.67914pt}{30.95276pt}\pgfsys@curveto{41.29842pt}{30.95276pt}{40.17914pt}{29.83348pt}{40.17914pt}{28.45276pt}\pgfsys@curveto{40.17914pt}{27.07204pt}{41.29842pt}{25.95276pt}{42.67914pt}{25.95276pt}\pgfsys@curveto{44.05986pt}{25.95276pt}{45.17914pt}{27.07204pt}{45.17914pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\right).$

###### Proof.

Since $\gamma\in\operatorname{\hat{I}}$, there exist
$\alpha\in\operatorname{I}$ and $d\geq\operatorname{dmin}\alpha$ such that
$\gamma=\mathrm{hat}_{d}(\alpha)$. In particular,

$\operatorname{Asc}(\gamma)\subseteq\operatorname{Asc}_{d}(\gamma)\subseteq\operatorname{nub}\gamma,$

where the last set containment is Proposition 4.3. ∎

###  5.1 Maximal $d$-hat

Recall from Lemma 4.4 that $\operatorname{dmin}\alpha\leq n$ for each
$\alpha\in\operatorname{I}_{n}$. By proposition 4.6, for each $n\geq 0$ we
have an injection

$\displaystyle\mathrm{hat}_{n}:\operatorname{I}_{n}\;$
$\displaystyle\longrightarrow\;\operatorname{\hat{I}}_{n}$
$\displaystyle\alpha\;$ $\displaystyle\longmapsto\;\mathrm{hat}_{n}(\alpha).$

Since—again by Lemma 4.4—applying $d$-hat gives the same result for every
$d\geq n$, we will call _max-hat_ the injection

$\displaystyle\mathrm{hat}_{\max}:\operatorname{I}\;$
$\displaystyle\longrightarrow\;\operatorname{\hat{I}}$ $\displaystyle\alpha\;$
$\displaystyle\longmapsto\;\mathrm{hat}_{|\alpha|}(\alpha).$

The main goal of this subsection is to prove that $\mathrm{hat}_{\max}$ maps
$\operatorname{I}$ bijectively to $\operatorname{\mathfrak{S}}$. Namely, we
show that $\mathrm{hat}_{\max}(\alpha)$ is the permutation whose recursive
construction by insertion of a new rightmost entry is encoded by $\alpha$.

We start with a simple lemma.

######  Lemma 5.3.

Let $\alpha\in\operatorname{I}_{n}$. Suppose that $\alpha=\beta a$, for some
$\beta\in\operatorname{I}_{n-1}$ and $1\leq a\leq n$. Then

$\mathrm{hat}_{\max}(\alpha)=\mathrm{hat}_{\max}(\beta)^{+}a.$

###### Proof.

We have:

$\displaystyle\mathrm{hat}_{\max}(\alpha)$
$\displaystyle=\mathrm{hat}_{n}(\beta a)$
$\displaystyle=\mathrm{hat}_{n-1}(\beta)^{+}a$ (since
$\operatorname{Asc}_{n}\alpha=[n]$)
$\displaystyle=\mathrm{hat}_{\max}(\beta)^{+}a$ (by Lemma 4.4).

This concludes the proof. ∎

######  Lemma 5.4.

Let $\alpha\in\operatorname{I}$. Then
$\mathrm{hat}_{\max}(\alpha)\in\operatorname{\mathfrak{S}}$.

###### Proof.

We use induction on the size $n$ of $\alpha$, where the case $n\leq 1$ is easy
to prove. Let $n\geq 2$. Let $\alpha=\beta a$, for some
$\beta\in\operatorname{I}_{n-1}$ and $a\in[n]$. By Lemma 5.3, we have
$\mathrm{hat}_{\max}(\alpha)=\mathrm{hat}_{\max}(\beta)^{+}a$, which is
clearly a permutation since
$\mathrm{hat}_{\max}(\beta)\in\operatorname{\mathfrak{S}}_{n-1}$ by induction.
∎

######  Corollary 5.5.

We have a size-preserving bijection
$\mathrm{hat}_{\max}:\operatorname{I}\to\operatorname{\mathfrak{S}}$.

###### Proof.

By Proposition 4.6 and Lemma 5.4, the map
$\mathrm{hat}_{n}:\operatorname{I}_{n}\to\operatorname{\mathfrak{S}}_{n}$ is
injective for every $n\geq 0$. The theorem follows since it is well known that
$\operatorname{I}_{n}$ and $\operatorname{\mathfrak{S}}_{n}$ are equinumerous.
∎

The behavior of $\mathrm{hat}_{\max}$ on $\operatorname{I}$ can be summarized
by saying that $\alpha$ encodes the construction of
$\mathrm{hat}_{\max}(\alpha)$ by insertion of a new rightmost entry. More
specifically, when we modify $\alpha$ under $\mathrm{hat}_{\max}$, at each
step we increase by one all the entries in the current prefix that are greater
than or equal to the current rightmost one. This step-by-step process is
illustrated below for $\alpha=1224315$:

$\displaystyle 1$ $\displaystyle\longmapsto 1$ $\displaystyle 12$
$\displaystyle\longmapsto 1\underline{2}$ $\displaystyle 122$
$\displaystyle\longmapsto 1\mathbf{3}\underline{2}$ $\displaystyle 1224$
$\displaystyle\longmapsto 132\underline{4}$ $\displaystyle 12243$
$\displaystyle\longmapsto 1\mathbf{4}2\mathbf{5}\underline{3}$ $\displaystyle
122431$ $\displaystyle\longmapsto\mathbf{25364}\underline{1}$ $\displaystyle
1224315$ $\displaystyle\longmapsto
2\mathbf{6}3\mathbf{7}41\underline{5}\;=\;\mathrm{hat}_{\max}(\alpha)$

We end this section with a simple remark. A _flat step_ in $\alpha=a_{1}\ldots
a_{n}\in\operatorname{End}$ is a pair of consecutive equal entries
$a_{i}=a_{i+1}$. Let $\alpha\in\operatorname{I}$ and let
$\gamma=\mathrm{hat}_{\max}(\alpha)$. It is easy to see that $a_{i}=a_{i+1}$
is a flat step in $\alpha$ if and only if in $\gamma$ we have $g_{i}>g_{i+1}$
and no entries $g_{j}$, $j<i$, satisfy $g_{i+1}<g_{j}<g_{i}$. Define the mesh
pattern $\mathfrak{a}$ accordingly as

$\mathfrak{a}=\leavevmode\hbox to43.28pt{\vbox
to43.28pt{\pgfpicture\makeatletter\hbox{\hskip 0.3pt\lower-0.3pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@lineto{14.22638pt}{42.67914pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@lineto{28.45276pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{42.67914pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{14.22638pt}\pgfsys@moveto{0.0pt}{14.22638pt}\pgfsys@lineto{0.0pt}{28.45276pt}\pgfsys@lineto{28.45276pt}{28.45276pt}\pgfsys@lineto{28.45276pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{28.45276pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{14.22638pt}\pgfsys@lineto{42.67914pt}{14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@lineto{42.67914pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{14.22638pt}{0.0pt}\pgfsys@lineto{14.22638pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.6pt}\pgfsys@invoke{
}{}\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@lineto{28.45276pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@moveto{16.72638pt}{28.45276pt}\pgfsys@curveto{16.72638pt}{29.83348pt}{15.6071pt}{30.95276pt}{14.22638pt}{30.95276pt}\pgfsys@curveto{12.84566pt}{30.95276pt}{11.72638pt}{29.83348pt}{11.72638pt}{28.45276pt}\pgfsys@curveto{11.72638pt}{27.07204pt}{12.84566pt}{25.95276pt}{14.22638pt}{25.95276pt}\pgfsys@curveto{15.6071pt}{25.95276pt}{16.72638pt}{27.07204pt}{16.72638pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{14.22638pt}{28.45276pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@moveto{30.95276pt}{14.22638pt}\pgfsys@curveto{30.95276pt}{15.6071pt}{29.83348pt}{16.72638pt}{28.45276pt}{16.72638pt}\pgfsys@curveto{27.07204pt}{16.72638pt}{25.95276pt}{15.6071pt}{25.95276pt}{14.22638pt}\pgfsys@curveto{25.95276pt}{12.84566pt}{27.07204pt}{11.72638pt}{28.45276pt}{11.72638pt}\pgfsys@curveto{29.83348pt}{11.72638pt}{30.95276pt}{12.84566pt}{30.95276pt}{14.22638pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{14.22638pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
The next proposition follows immediately.

######  Proposition 5.6.

The map $\mathrm{hat}_{\max}$ restricts to a bijection between inversion
sequences with no flat steps and permutations avoiding $\mathfrak{a}$. ∎

##  6 Subdiagonal permutations

Recall from Subsection 5.1 that an inversion sequence $\alpha$ encodes the
construction of $\mathrm{hat}_{\max}(\alpha)$ by insertion of a new rightmost
entry. In this section, we restrict $\mathrm{hat}_{\max}$ to the set of ascent
sequences and characterize the resulting set of permutations which have the
following subdiagonal property.

Any permutation $\pi\in\operatorname{\mathfrak{S}}$ factors uniquely by
maximal increasing runs as $\pi=B_{1}B_{2}\ldots B_{k}$, where
$k=n+1-\operatorname{asc}\alpha$. We say that $\pi$ is

$\displaystyle\text{\emph{ir-superdiagonal}},$ $\displaystyle\text{if $c\geq
i$ for each $c\in B_{i}$};$ $\displaystyle\text{\emph{ir-subdiagonal}},$
$\displaystyle\text{if $c\leq n+1-i$ for each $c\in B_{i}$},$

where the prefix “ir” denotes that $\pi$ is decomposed by “increasing runs”.
Clearly, two analogous notions are obtained by replacing maximal increasing
runs with maximal decreasing runs; that is, if $\pi=C_{1}\ldots C_{k}$, where
now the blocks $C_{i}$ are maximally decreasing, we say that $\pi$ is

$\displaystyle\text{\emph{dr-superdiagonal}},$ $\displaystyle\text{if $c\geq
i$ for each $c\in C_{i}$};$ $\displaystyle\text{\emph{dr-subdiagonal}},$
$\displaystyle\text{if $c\leq n+1-i$ for each $c\in C_{i}$}.$

It is easy to see that $\pi$ is ir-subdiagonal if and only if its complement
is dr-superdiagonal; similarly, it is dr-subdiagonal if and only if its
complement is ir-superdiagonal. So it is no restriction to only consider
subdiagonal permutations, denoted by

$\displaystyle\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$
$\displaystyle=\\{\pi:\pi\text{ is ir-subdiagonal}\\};$
$\displaystyle\operatorname{D^{\scalebox{0.5}{$\searrow$}}}$
$\displaystyle=\\{\pi:\pi\text{ is dr-subdiagonal}\\}.$

In the following two subsections, we shall prove that

$\mathrm{hat}_{\max}(\operatorname{A}_{0})=\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}\quad\text{and}\quad\mathrm{hat}_{\max}(\operatorname{wD})=\operatorname{D^{\scalebox{0.5}{$\searrow$}}},$

where $\operatorname{wD}$ denotes the set of weak descent sequences, defined
later. As a result of what was observed in Subsection 5.1, ascent sequences
encode the recursive construction of ir-subdiagonal permutations by successive
insertions of a new rightmost entry. And weak descent sequences encode dr-
subdiagonal permutations in the same way. This construction is reminiscent of
the way ascent sequences encode Fishburn permutations [BMCDK10], the
difference being that in the case of Fishburn permutations a new maximum is
inserted at each step. Note that we have not been able to find bivincular
patterns characterizing $\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$ and
$\operatorname{D^{\scalebox{0.5}{$\searrow$}}}$. Finally, we define an
isomorphism between two generating trees for weak descent sequences and
_primitive ascent sequences_ , defined as those ascent sequences that have no
flat steps.

###  6.1 ir-subdiagonal permutations

Throughout this section, we let $\pi=B_{1}\ldots B_{k}$ be the decomposition
of a given permutation $\pi$ into maximal increasing runs. If $c$ is an entry
of $B_{j}$, $1\leq j\leq k$, we let $\operatorname{ind}_{\pi}(c)=j$ denote the
index of the block of $\pi$ that contains $c$. Letting $\pi=p_{1}\ldots p_{n}$
and $\pi_{i}=p_{1}\ldots p_{i}$, it is easy to see that

$\pi\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}\iff
p_{i}\leq|\pi|+1-\operatorname{ind}_{\pi}(p_{i})$

for each $i$, where

$\operatorname{ind}_{\pi}(p_{i})=i+1-\operatorname{asc}\pi_{i}.$ (8)

The next lemma shows that ir-subdiagonal permutations and ascent sequences
share a similar recursive structure.

######  Lemma 6.1.

Let $\pi=p_{1}\ldots p_{n}\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$
and let $a\in[n+1]$. Then

$\pi^{+}a\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}\iff a\leq
1+\operatorname{asc}\pi.$

###### Proof.

We start by showing that entries in the prefix $\pi^{+}$ satisfy the
subdiagonality constraint in $\pi^{+}a$ if
$\pi\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$. Let $c$ be an entry in
$\pi$ and denote by $c^{+}$ the corresponding entry in $\pi^{+}$. Observe that
$\operatorname{Asc}\pi=\operatorname{Asc}\pi^{+}$. Using equation (8), we
obtain the equality
$\operatorname{ind}_{\pi^{+}a}(c^{+})=\operatorname{ind}_{\pi}(c)$. Using this
equality and the fact that
$\pi\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$ gives

$c^{+}\leq
c+1\leq|\pi|+1-\operatorname{ind}_{\pi}(c)+1=|\pi^{+}a|+1-\operatorname{ind}_{\pi^{+}a}(c^{+}).$

Next we consider the last entry $a$. If $a<p_{n}$, then both $\pi^{+}a$ is ir-
subdiagonal and $a\leq 1+\operatorname{asc}\pi$. Indeed, we have
$\operatorname{ind}_{\pi^{+}a}(a)=\operatorname{ind}_{\pi}(p_{n})+1$ and
$\pi\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$ so that

$a<p_{n}\leq
n+1-\operatorname{ind}_{\pi}(p_{n})=n+2-\operatorname{ind}_{\pi^{+}a}(a)=|\pi^{+}a|+1-\operatorname{ind}_{\pi^{+}a}(a).$

Similarly, using equation (8),

$a<p_{n}\leq
n+1-\operatorname{ind}_{\pi}(p_{n})=n+1-(n+1-\operatorname{asc}\pi)<1+\operatorname{asc}\pi.$

Finally, suppose that $a>p_{n}$. Then
$\operatorname{ind}_{\pi^{+}a}(a)=\operatorname{ind}_{\pi}(p_{n})$. Now
$\pi^{+}a\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$ if and only if
$a\leq|\pi^{+}a|+1-\operatorname{ind}_{\pi^{+}a}(a)$. But by equation (8),
this last inequality is equivalent to

$a\leq
n+2-\operatorname{ind}_{\pi}(p_{n})=n+2-(n+1-\operatorname{asc}\pi)=1+\operatorname{asc}\pi,$

as desired. ∎

######  Theorem 6.2.

Let $\alpha\in\operatorname{I}$ and let
$\hat{\alpha}=\mathrm{hat}_{\max}(\alpha)$. Then

$\alpha\in\operatorname{A}_{0}\iff\hat{\alpha}\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}.$

Therefore, $\mathrm{hat}_{\max}$ restricts to a bijection from
$\operatorname{A}_{0}$ to $\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$.

###### Proof.

We use induction on the size of $\alpha$ where the result is clear for size at
most one. Let $\alpha=\beta a$, for some $\beta\in\operatorname{I}_{n}$. By
Lemma 5.3, we have $\hat{\alpha}=\hat{\beta}^{+}a$. Using induction, we have
that $\beta\in\operatorname{A}_{0}$ if and only if
$\hat{\beta}\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$. Now using
Theorem 4.9 we have

$\alpha\in\operatorname{A}_{0}\iff\ a\leq
1+\operatorname{asc}\beta=1+\operatorname{asc}\hat{\beta}.$

But, by the lemma just proved, the inequality is equivalent to
$\hat{\alpha}=\hat{\beta}^{+}a\in\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$
as desired. ∎

By Theorems 4.6 and 6.2, the set
$\operatorname{D^{\scalebox{0.5}{$\nearrow$}}}$ of ir-subdiagonal permutations
is the bijective image of the set $\operatorname{A}_{0}$ of ascent sequences
under $\mathrm{hat}_{\max}$. Furthermore, by Proposition 5.6 and the previous
result, primitive ascent sequences are in bijection with ir-subdiagonal
permutations avoiding $\mathfrak{a}$. The next corollary follows immediately.

######  Corollary 6.3.

For each $n\geq 0$, the number of ir-subdiagonal permutations of size $n$ is
equal to the $n$th Fishburn number, that is, the number of ascent sequences of
length $n$. Furthermore, the number of ir-subdiagonal permutations avoiding
$\mathfrak{a}$ is equal to the number of primitive ascent sequences (see also
A138265 [OEI]). ∎

###  6.2 dr-subdiagonal permutations and weak descent sequences

Recall that the set of weak descents of $\alpha\in\operatorname{End}$ is

$\operatorname{wDes}\alpha=\\{i\geq 2\mid a_{i}\leq a_{i-1}\\}$

Note that $[n]=\operatorname{wDes}\alpha\uplus\operatorname{Asc}\alpha$ for
every $\alpha\in\operatorname{End}_{n}$; that is, every $i\in[n]$ is either a
weak descent or a strict ascent. The set $\operatorname{wD}$ of _weak descent
sequences_ is defined as

$\operatorname{wD}_{n}=\\{\alpha\in\operatorname{I}_{n}\mid a_{1}=1\text{ and
}a_{i}\leq 1+\operatorname{wdes}\alpha_{i-1}\text{ for each }i\in[n]\\},$

where $\operatorname{wdes}\alpha=|\operatorname{wDes}\alpha|$.

The next result is a counterpart of Theorem 6.2 and states that
$\alpha\in\operatorname{I}$ is a weak descent sequence if and only if
$\mathrm{hat}_{\max}(\alpha)$ is dr-subdiagonal. Its proof is obtained by
simply replicating the steps of Lemma 6.1 and Theorem 6.2, and is thus
omitted.

######  Theorem 6.4.

Let $\pi\in\operatorname{D^{\scalebox{0.5}{$\searrow$}}}$. Then
$\pi^{+}a\in\operatorname{D^{\scalebox{0.5}{$\searrow$}}}$ if and only if
$a\leq 1+\operatorname{wdes}\pi$. Furthermore, if $\alpha\in\operatorname{I}$
and $\hat{\alpha}=\mathrm{hat}_{\max}(\alpha)$, then

$\alpha\in\operatorname{wD}\iff\hat{\alpha}\in\operatorname{D^{\scalebox{0.5}{$\searrow$}}}$

and $\mathrm{hat}_{\max}$ restricts to a bijection from $\operatorname{wD}$ to
$\operatorname{D^{\scalebox{0.5}{$\searrow$}}}$. ∎

We wish to prove that weak descent sequences (and thus dr-subdiagonal
permutations) are equinumerous with primitive ascent sequences. A generating
tree for ascent sequences is encoded by the following generating rule, where
the pair $(a,\ell)$ keeps track of the number of ascents, $a$, and the last
letter, $\ell$:

$\begin{cases}\text{Root: }(1,1)\\\
(a,\ell)\longrightarrow(a,1)(a,2)\ldots(a,\ell-1)(a,\ell)(a+1,\ell+1)(a+1,\ell+2)\ldots(a+1,a+1).\end{cases}$

The above rule encodes the standard construction of ascent sequences by
insertion of a new rightmost entry. The root $(1,1)$ corresponds to the only
ascent sequence of size one, namely the single letter word $1$. Further, if
$\alpha\in\operatorname{A}_{0}$ has $a$ ascents and last letter $\ell$, then
it produces $a+1$ children by insertion of a new rightmost entry $i\in[a+1]$.
If $i\leq\ell$, then the number of ascents remains the same; otherwise, if
$i>\ell$, then a new ascent is created. To obtain a generating rule for
primitive ascent sequences, we remove the child $(a,\ell)$ corresponding to a
flat step and obtain:

$\Omega:\begin{cases}\text{Root: }(1,1)\\\
(a,\ell)\longrightarrow(a,1)(a,2)\ldots(a,\ell-1)(a+1,\ell+1)(a+1,\ell+2)\ldots(a+1,a+1).\end{cases}$

A generating rule for weak descent sequences that uses the number of weak
descents $w$ and the last letter $u$ as parameters is now obtained similarly
as:

$\Theta:\begin{cases}\text{Root: }(0,1)\\\
(w,u)\longrightarrow(w+1,1)(w+1,2)\ldots(w+1,u)(w,u+1)(w,u+2)\ldots(w,w+1).\end{cases}$

In this case, inserting $i\in[w+1]$ creates a new weak descent if and only if
$i\leq u$.

To show that primitive ascent sequences and weak descent sequences are
equinumerous, we shall give a bijection between the generating trees encoded
by the rules $\Omega$ and $\Theta$. Namely, we show that $\Omega$ and $\Theta$
are equivalent under the linear transformation

$\begin{cases}w=a-1\\\ u=a-\ell+1\end{cases}\iff\;\;\,\begin{cases}a-w=1\\\
\ell+u=a+1.\end{cases}$ (9)

Indeed, the root $(a,\ell)=(1,1)$ is mapped to $(w,u)=(0,1)$. Further, assume
that $(a,\ell)$ is mapped to $(w,u)$, i.e. that $w=a-1$ and $u=a+1-\ell$. Then
the children of $(a,\ell)$ are mapped bijectively to the children of $(w,u)$,
since

$\displaystyle(a,1)$ $\displaystyle\,\mapsto\,(a-1,a)=(w,w+1)$
$\displaystyle(a,2)$ $\displaystyle\,\mapsto\,(a-1,a-1)=(w,w)$
$\displaystyle\;\;\vdots$ $\displaystyle(a,\ell-1)$
$\displaystyle\,\mapsto\,(a-1,a-\ell+2)=(w,u+1)$ $\displaystyle(a+1,\ell+1)$
$\displaystyle\,\mapsto\,(a,a-\ell+1)=(w+1,u)$ $\displaystyle(a+1,\ell+2)$
$\displaystyle\,\mapsto\,(a,a-\ell)=(w+1,u-1)$ $\displaystyle\;\;\vdots$
$\displaystyle(a+1,a+1)$ $\displaystyle\,\mapsto\,(a,1)=(w+1,1).$

As a result, we obtain a bijection between the generating tree of primitive
ascent sequences, encoded by $\Omega$, and the generating tree of
$\operatorname{wD}$, encoded by $\Theta$. The next result follows immediately.

######  Corollary 6.5.

For each $n\geq 0$, the number of weak descent sequences of size $n$ is equal
to the is equal to the number of primitive ascent sequences of size $n$. ∎

##  7 Difference Fishburn permutations

Prompted by a question in [DS23], Zang and Zhou [ZZ] have recently introduced
_$d$ -permutations_, defined as follows. Fix $d\geq 0$ and let
$\pi=p_{1}\ldots p_{n}$ be a permutation of $\operatorname{\mathfrak{S}}_{n}$,
with $n\geq 1$. We denote by $\pi^{(k)}$ the subsequence of $\pi$ which
contains the elements $[k]$. For example, if $\pi=641523$ then
$\pi^{(4)}=4123$. The following procedure defines the _$d$ -active elements_
of $\pi$:

  * •

Set $1$ to be a $d$-active element.

  * •

For $k=2,3,\dots,n$, let $k$ be $d$-inactive if $k$ is to the left of $k-1$ in
$\pi$ and there exist at least $d$ elements of $\pi^{(k)}$ between $k$ and
$k-1$ that are $d$-active. Otherwise, $k$ is said to be $d$-active.

Returning to our example $\pi=641523$ with $d=2$ we compute the $d$-active
elements as follows, where such elements are set in boldface. By the initial
condition

$\pi^{(1)}={\bf 1}.$

Next

$\pi^{(2)}={\bf 12}.$

since $2$ is to the right of $1$ and so will be active. Similarly

$\pi^{(3)}={\bf 123}.$

Now

$\pi^{(4)}=4{\bf 123}$

with $4$ not active since the number of active elements between it and $3$ is
$2\geq d$. Clearly

$\pi^{(5)}=4{\bf 1523}.$

Finally

$\pi=\pi^{(6)}={\bf 6}4{\bf 1523}$

where $6$ is active since the number of active elements between it and $5$ is
$1<d$.

Let $\operatorname{Act}_{d}\pi$ denote the set of $d$-active elements of
$\pi$. Furthermore, denote by $\operatorname{AscBot}\pi$ the set

$\operatorname{AscBot}\pi=\\{p_{i}\in[n-1]:p_{i}<p_{i+1}\\}$

of _ascent bottoms_ of $\pi$. Note that these are elements of $\pi$ rather
than positions. Then, $\pi$ is said to be a _$d$ -permutation_ if

$\operatorname{AscBot}\pi\subseteq\operatorname{Act}_{d}\pi,$

and we denote by $\operatorname{F}_{d}$ the set of $d$-Fishburn permutations.
Recall that Fishburn permutations [BMCDK10] are defined as those permutations
avoiding the bivincular pattern

$\operatorname{\mathfrak{f}}=\leavevmode\hbox to40.21pt{\vbox
to40.21pt{\pgfpicture\makeatletter\hbox{\hskip 0.18999pt\lower-0.18999pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{9.95863pt}{0.0pt}\pgfsys@moveto{9.95863pt}{0.0pt}\pgfsys@lineto{9.95863pt}{39.83455pt}\pgfsys@lineto{19.91727pt}{39.83455pt}\pgfsys@lineto{19.91727pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{39.83455pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{9.95863pt}\pgfsys@moveto{0.0pt}{9.95863pt}\pgfsys@lineto{0.0pt}{19.91727pt}\pgfsys@lineto{39.83455pt}{19.91727pt}\pgfsys@lineto{39.83455pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{39.83455pt}{19.91727pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}{}{ {}{}{}{}{ }{
}{ }{ }{ }{
}{}}{}\pgfsys@moveto{0.01001pt}{0.01001pt}\pgfsys@moveto{0.01001pt}{9.95863pt}\pgfsys@lineto{39.82452pt}{9.95863pt}\pgfsys@moveto{0.01001pt}{19.91727pt}\pgfsys@lineto{39.82452pt}{19.91727pt}\pgfsys@moveto{0.01001pt}{29.87592pt}\pgfsys@lineto{39.82452pt}{29.87592pt}\pgfsys@moveto{9.95863pt}{0.01001pt}\pgfsys@lineto{9.95863pt}{39.82452pt}\pgfsys@moveto{19.91727pt}{0.01001pt}\pgfsys@lineto{19.91727pt}{39.82452pt}\pgfsys@moveto{29.87592pt}{0.01001pt}\pgfsys@lineto{29.87592pt}{39.82452pt}\pgfsys@moveto{39.82452pt}{39.82452pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{9.95863pt}{19.91727pt}\pgfsys@moveto{11.70866pt}{19.91727pt}\pgfsys@curveto{11.70866pt}{20.88379pt}{10.92516pt}{21.6673pt}{9.95863pt}{21.6673pt}\pgfsys@curveto{8.99211pt}{21.6673pt}{8.2086pt}{20.88379pt}{8.2086pt}{19.91727pt}\pgfsys@curveto{8.2086pt}{18.95074pt}{8.99211pt}{18.16724pt}{9.95863pt}{18.16724pt}\pgfsys@curveto{10.92516pt}{18.16724pt}{11.70866pt}{18.95074pt}{11.70866pt}{19.91727pt}\pgfsys@closepath\pgfsys@moveto{9.95863pt}{19.91727pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{19.91727pt}{29.87592pt}\pgfsys@moveto{21.6673pt}{29.87592pt}\pgfsys@curveto{21.6673pt}{30.84244pt}{20.88379pt}{31.62595pt}{19.91727pt}{31.62595pt}\pgfsys@curveto{18.95074pt}{31.62595pt}{18.16724pt}{30.84244pt}{18.16724pt}{29.87592pt}\pgfsys@curveto{18.16724pt}{28.9094pt}{18.95074pt}{28.12589pt}{19.91727pt}{28.12589pt}\pgfsys@curveto{20.88379pt}{28.12589pt}{21.6673pt}{28.9094pt}{21.6673pt}{29.87592pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{29.87592pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{29.87592pt}{9.95863pt}\pgfsys@moveto{31.62595pt}{9.95863pt}\pgfsys@curveto{31.62595pt}{10.92516pt}{30.84244pt}{11.70866pt}{29.87592pt}{11.70866pt}\pgfsys@curveto{28.9094pt}{11.70866pt}{28.12589pt}{10.92516pt}{28.12589pt}{9.95863pt}\pgfsys@curveto{28.12589pt}{8.99211pt}{28.9094pt}{8.2086pt}{29.87592pt}{8.2086pt}\pgfsys@curveto{30.84244pt}{8.2086pt}{31.62595pt}{8.99211pt}{31.62595pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{29.87592pt}{9.95863pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
We wish to give an alternative definition of $d$-Fishburn permutations that is
reminiscent of the classical case $d=0$. We say that a permutation $\pi$
contains the _$d$ -Fishburn pattern_, $\operatorname{\mathfrak{f}}_{d}$, if it
contains an occurrence $p_{i}p_{i+1}p_{j}$ of $\operatorname{\mathfrak{f}}$
where $p_{i}$ is $d$-inactive. The other two elements $p_{i+1}$ and $p_{j}$
can be either $d$-active or $d$-inactive. With a slight abuse, we will use the
suggestive notation
$\operatorname{\mathfrak{S}}(\operatorname{\mathfrak{f}}_{d})$ to denote the
set of permutations that do not contain $\operatorname{\mathfrak{f}}_{d}$.

######  Proposition 7.1.

For every $d\geq 0$,

$\operatorname{F}_{d}=\operatorname{\mathfrak{S}}(\operatorname{\mathfrak{f}}_{d}).$

###### Proof.

Let $\pi\in\operatorname{\mathfrak{S}}$. We show that $\pi$ contains
$\operatorname{\mathfrak{f}}_{d}$ if and only if
$\operatorname{AscBot}\pi\not\subseteq\operatorname{Act}_{d}\pi$. Initially,
suppose that $\pi$ contains an occurrence $p_{i}p_{i+1}p_{j}$ of
$\operatorname{\mathfrak{f}}_{d}$. Then $p_{i}\in\operatorname{AscBot}\pi$ and
$p_{i}$ is not $d$-active. Thus,
$\operatorname{AscBot}\pi\not\subseteq\operatorname{Act}_{d}\pi$, as wanted.
On the other hand, suppose that
$\operatorname{AscBot}\pi\not\subseteq\operatorname{Act}_{d}\pi$. That is,
there is an entry $p_{i}$ such that $p_{i}\in\operatorname{AscBot}$ and
$p_{i}\notin\operatorname{Act}_{d}\pi$. Note that $p_{i}<p_{i+1}$. Further,
since $p_{i}\notin\operatorname{Act}_{d}\pi$, by definition of $d$-active site
we have $p_{i}-1=p_{j}$, for some $j>i$. Finally, the triple
$p_{i}p_{i+1}p_{j}$ is an occurrence of $\operatorname{\mathfrak{f}}_{d}$,
finishing the proof. ∎

Zang and Zhou proved that $\operatorname{F}_{0}$ coincides with the set of
Fishburn permutations, while $\operatorname{F}_{1}$ is equal to the set of
weak Fishburn permutations introduced by Bényi et al. [BCD23]. Further, they
showed that $\operatorname{F}_{d}$ is tree-like in the following sense.

Consider a set $\Pi$ of permutations. As usual, let
$\Pi_{n}=\Pi\cap\operatorname{\mathfrak{S}}_{n}$. Say that $\Pi$ is tree-like
if $\Pi_{0}=\\{\epsilon\\}$ (where $\epsilon$ is the empty permutation) and,
for $n\geq 1$, every $\pi\in\Pi_{n}$ is obtained by inserting $n$ into a site
of some $\rho\in\Pi_{n-1}$, called the _parent_ of $\pi$. The spaces between
letters of $\rho$ into which $n$ can be inserted are called the active sites
with respect to $\Pi$, and all other sites of $\rho$ are said to be inactive.
Active sites are labled $1,2,\ldots$ from left to right. The active sites of
$\pi\in\operatorname{F}_{d}$ are called $d$-active sites and are the site
before $\pi$ as well as the sites which lie just after a $d$-active element.

Finally, Zang and Zhou generalized the classical encoding of Fishburn
permutations by ascent sequences to $d$-Fishburn permutations and $d$-ascent
sequences; that is, they defined bijections

$\Phi_{d}:\operatorname{A}_{d}\longrightarrow\operatorname{F}_{d}$

by letting, recursively,

  * •

$\Phi_{d}(\epsilon)=\epsilon$, and

  * •

for $n\geq 1$ if $\alpha=\beta a\in\operatorname{A}_{d,n}$ then
$\Phi_{d}(\alpha)$ is the result of inserting $n$ into the active site active
site of $\Phi_{d}(\beta)$ labeled $a$.

###  7.1 Burge transpose and Fishburn permutations

The set of _Burge words_ is defined as

$\operatorname{Bur}_{n}=\left\\{\binom{u}{\alpha}:u\in\operatorname{WI}_{n},\;\alpha\in\operatorname{Cay}_{n},\;\operatorname{wDes}(u)\subseteq\operatorname{wDes}(\alpha)\right\\},$

where $\operatorname{WI}_{n}$ is the subset of $\operatorname{Cay}_{n}$
consisting of the weakly increasing Cayley permutations. We define a
transposition operation $T$ on $\operatorname{Bur}_{n}$ as follows [CC23b]. To
compute the _Burge transpose_ $w^{T}$ of
$w=\binom{u}{\alpha}\in\operatorname{Bur}_{n}$, turn each column of $w$ upside
down and then sort the columns in ascending order with respect to the top
entry, breaking ties by sorting in weakly decreasing order with respect to the
bottom entry. Observe that $T$ is an involution on $\operatorname{Bur}_{n}$.
Now, let $\operatorname{id}_{n}=12\ldots n$ be the identity permutation. Since
$\operatorname{id}_{n}$ has no weak descents,
$\binom{\operatorname{id}_{n}}{\alpha}$ is a Burge word for every
$\alpha\in\operatorname{Cay}_{n}$. Thus, for any
$\alpha\in\operatorname{Cay}_{n}$, we can always pick $\operatorname{id}_{n}$
as the top row, and we get a map
$\operatorname{\mathtt{t}}:\operatorname{Cay}_{n}\to\operatorname{\mathfrak{S}}_{n}$,
defined by

$\binom{\operatorname{id}}{\alpha}^{\\!T}=\binom{\operatorname{sort}(\alpha)}{\operatorname{\mathtt{t}}(\alpha)},$

for any $\alpha\in\operatorname{Cay}$, where $\operatorname{sort}(\alpha)$ is
obtained by sorting the entries of $\alpha$ in weakly increasing order. If
$\pi\in\operatorname{\mathfrak{S}}$ is a permutation, then
$\operatorname{\mathtt{t}}(\pi)=\pi^{-1}$ (and thus
$\operatorname{\mathtt{t}}$ is surjective). Note that the map
$\operatorname{\mathtt{t}}$ was originally [CC23b] denoted by the letter
$\gamma$.

One of the main advantages of modified ascent sequences and the Burge
transpose is that they give a non-recursive description of the bijection
$\Phi_{0}:\operatorname{A}_{0}\to\operatorname{F}_{0}$. Indeed [BMCDK10], if
$\hat{\alpha}=\mathrm{hat}_{0}(\alpha)$ is the modified ascent sequence of
$\alpha$, then $\operatorname{\mathtt{t}}(\hat{\alpha})$ is the Fishburn
permutation corresponding to $\alpha$ under $\Phi_{0}$. With the ascent
sequence $\alpha=121242232$ of the example before Lemma 2.1, we obtain
$\hat{\alpha}=141252232$ and

$\displaystyle\binom{\operatorname{id}}{\hat{\alpha}}^{\\!T}$
$\displaystyle=\binom{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}{1\ 4\ 1\ 2\ 5\ 2\ 2\ 3\
2}^{\\!T}$ $\displaystyle=\binom{1\ 1\ 2\ 2\ 2\ 2\ 3\ 4\ 5}{3\ 1\ 9\ 7\ 6\ 4\
8\ 2\
5}=\binom{\operatorname{sort}(\hat{\alpha})}{\operatorname{\mathtt{t}}(\hat{\alpha})},$

where $\operatorname{\mathtt{t}}(\hat{\alpha})=\Phi_{0}(\alpha)$.

We wish to use the $d$-hat map to generalize the above construction to every
$d\geq 0$. That is, we shall prove that the diagram

${\operatorname{A}_{d}}$${\operatorname{F}_{d}}$${\hat{\operatorname{A}}_{d}}$$\Phi_{d}$$\mathrm{hat}_{d}$$\operatorname{\mathtt{t}}$
(10)

commutes for every $d\geq 0$ and that all the arrows are size-preserving
bijections. To this end, it will be convenient to let

$\operatorname{Im}_{d}=\operatorname{\mathtt{t}}\bigl{(}\mathrm{hat}_{d}(\operatorname{A}_{d})\bigr{)}.$

Our proof of the commutativity of diagram (10) proceeds in the following
steps: First we show that $\operatorname{\mathtt{t}}$ is injective so that the
composition with $\mathrm{hat}_{d}$ is an injective map. Next we demonstrate
that $\operatorname{Im}_{d}$ has a tree-like structure and describe the active
sites of its permutations. As a corollary, we obtain
$\operatorname{Im}_{d}=\operatorname{F}_{d}$. The equality
$\Phi_{d}=\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}$ then follows by
showing that $\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}$ has a
recursive description that is identical to the one given for $\Phi_{d}$ in
terms of active sites.

Let us start by proving that $\operatorname{\mathtt{t}}$ is injective. For the
rest of this section, given a $d$-ascent sequence $\alpha$, we let
$\hat{\alpha}=\mathrm{hat}_{d}(\alpha)$ denote the $d$-hat of $\alpha$.

######  Proposition 7.2.

For all $d,n\geq 0$, the map
$\operatorname{\mathtt{t}}:\hat{\operatorname{A}}_{d,n}\rightarrow\operatorname{\mathfrak{S}}_{n}$
is injective.

###### Proof.

We fix $d\geq 0$ and use induction on $n$. Let us set up the following
notation for the rest of the proof. We will consider two $d$-ascent sequences
$\alpha$ and $\omega$ in $\operatorname{A}_{d,n}$, where

$\alpha=\beta a\quad\text{and}\quad\omega=\tau w,$

for some $\beta$ and $\tau$ in $\operatorname{A}_{d,n-1}$. We also let $a$,
$b$, $w$ and $t$ denote the last letter of $\alpha$, $\beta$, $\omega$ and
$\tau$, respectively. By definition of $\mathrm{hat}_{d}$, we have

$\displaystyle\hat{\alpha}$ $\displaystyle=\begin{cases}\hat{\beta}a&\text{if
$a\leq b-d$};\\\ \hat{\beta}^{+}a&\text{if $a>b-d$};\\\ \end{cases}$ and
$\displaystyle\hat{\omega}$ $\displaystyle=\begin{cases}\hat{\tau}w&\text{if
$w\leq t-d$};\\\ \hat{\tau}^{+}w&\text{if $w>t-d$}.\\\ \end{cases}$

We assume $\hat{\alpha}\neq\hat{\omega}$ and prove that
$\operatorname{\mathtt{t}}(\hat{\alpha})\neq\operatorname{\mathtt{t}}(\hat{\omega})$.

Assume first that $\beta\neq\tau$. Since the map $\mathrm{hat}_{d}$ is
injective by Proposition 4.7, we have $\hat{\beta}\neq\hat{\tau}$ and by
induction,
$\operatorname{\mathtt{t}}(\hat{\beta})\neq\operatorname{\mathtt{t}}(\hat{\tau})$.
Note that sorting $\binom{\operatorname{id}}{\hat{\beta}}^{T}$ and
$\binom{\operatorname{id}}{\hat{\beta}^{+}}^{T}$ yields the same permutation
in the lower row and similarly for $\hat{\tau}$ and $\hat{\tau}^{+}$. So,
whichever case of the $\mathrm{hat}_{d}$ map we are in, we will be placing $n$
into the two different permutations $\operatorname{\mathtt{t}}(\hat{\beta})$
and $\operatorname{\mathtt{t}}(\hat{\tau})$ to compute
$\operatorname{\mathtt{t}}(\hat{\alpha})$ and
$\operatorname{\mathtt{t}}(\hat{\omega})$. This must result in distinct
permutations, as desired.

Now assume that $\beta=\tau$. Since $\alpha\neq\omega$ it must be that $a\neq
w$ and we can assume, without loss of generality, that $a<w$. If $a\leq b-d$,
then $\binom{\operatorname{id}}{\hat{\alpha}}^{T}$ is computed from
$\binom{\operatorname{id}}{\hat{\beta}}^{T}$ by placing the column
$\binom{a}{n}$ at the beginning of the list of columns with top entry $a$.
Note that such columns must exist because of the given inequality. If $a>b-d$
then $\binom{\operatorname{id}}{\hat{\alpha}}^{T}$ is computed from
$\binom{\operatorname{id}}{\hat{\beta}^{+}}^{T}$ by inserting the column
$\binom{a}{n}$ between the columns with top entry $a-1$ and those with top
entry $a+1$ (if there are any of the latter). In this case there will be no
other columns with top entry $a$. It is now a simple matter of checking to
show that in all possible cases the fact that $a<b$ will force $n$ to be in
$\operatorname{\mathtt{t}}(\hat{\alpha})$ strictly to the left of its
appearance in $\operatorname{\mathtt{t}}(\hat{\omega})$. This completes the
proof of injectivity. ∎

######  Corollary 7.3.

For every $d\geq 0$, the map
$\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}:\operatorname{A}_{d}\rightarrow\operatorname{Im}_{d}$
is a bijection.

###### Proof.

Our claim follows directly from Proposition 4.7, Proposition 7.2 and the
definition of $\operatorname{Im}_{d}$. ∎

######  Lemma 7.4.

For all $d\geq 0$, the set $\operatorname{Im}_{d}$ is tree-like.

###### Proof.

Clearly $\epsilon\in\operatorname{Im}_{d,0}$, so let $n\geq 1$. Pick
$\pi\in\operatorname{Im}_{d,n}$ and suppose
$\pi=\operatorname{\mathtt{t}}(\hat{\alpha})$, for some
$\alpha\in\operatorname{A}_{d}$. Suppose that $\alpha=\beta a$ and consider
$\rho=\operatorname{\mathtt{t}}(\hat{\beta})$. We claim that $\pi$ is obtained
by inserting $n$ in some site of $\rho$ which will prove the theorem. As
usual, there are two cases depending on whether $\hat{\alpha}=\hat{\beta}a$ or
$\hat{\alpha}=\hat{\beta}^{+}a$.

Suppose first that $\hat{\alpha}=\hat{\beta}a$. As in the proof of Proposition
7.2, $\binom{\operatorname{id}}{\hat{\alpha}}^{T}$ is obtained from
$\binom{\operatorname{id}}{\hat{\beta}}^{T}$ by inserting the column
$\binom{a}{n}$ at the beginning of the columns with top entry $a$. This means
that $\pi=\operatorname{\mathtt{t}}(\hat{\alpha})$ is obtained from
$\rho=\operatorname{\mathtt{t}}(\hat{\beta})$ by inserting $n$ in the
corresponding site, which proves the claim in this case.

Consider the second case. Here $\binom{\operatorname{id}}{\hat{\alpha}}^{T}$
is obtained from $\binom{\operatorname{id}}{\hat{\beta}^{+}}^{T}$ by inserting
the column $\binom{a}{n}$ between the columns with upper entry $a-1$ and those
with upper entry $a+1$, there being no columns with upper entry $a$. But since
$\hat{\beta}$ and $\hat{\beta}^{+}$ are order isomorphic, it follows again
that insertion of $n$ in the corresponding site of $\rho$ yields $\pi$. ∎

Since $\operatorname{Im}_{d}$ is tree-like, it is natural to want a
description of the active sites of $\rho\in\operatorname{Im}_{d}$. By
Corollary 7.3, the map
$\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}:\operatorname{A}_{d}\rightarrow\operatorname{Im}_{d}$
is a bijection. If
$\beta=(\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d})^{-1}(\rho)$ then one
could consider all $d$-ascent sequences of the form $\alpha=\beta a$ for
$1\leq a\leq\operatorname{asc}_{d}\beta+1$. Computing the permutations
$\pi=\operatorname{\mathtt{t}}(\hat{\alpha})$ for each such $\alpha$ and
comparing with $\rho$ would accomplish this task. But it would be nice to have
a description of the active sites which can be read off from the permutation
itself as one would do for pattern-avoidance classes. To this end, given
$\rho\in\operatorname{Im}_{d}$, let $\beta\in\operatorname{A}_{d}$ be its
preimage. Now

$\binom{\operatorname{id}}{\hat{\beta}}^{T}=\binom{\operatorname{sort}(\hat{\beta})}{\rho}.$

We shall use the active sites of $\rho$ to define a labeling of the sites of
$\operatorname{sort}(\hat{\beta})$ by letting a site of
$\operatorname{sort}(\hat{\beta})$ be active if and only if the corresponding
site of $\rho$ is active. In this context, active sites refer to the tree-like
structure of $\operatorname{Im}_{d}$ established in Lemma 7.4, and should not
be confused with the active sites with respect to $\operatorname{F}_{d}$. We
will first describe the active sites of $\operatorname{sort}(\hat{\beta})$. To
do so we need the concept of a run in a sequence which is a maximum factor
(subsequence of consecutive elements) consisting of equal elements.

######  Lemma 7.5.

Suppose $\beta\in\operatorname{A}_{d,n-1}$.

  1. $(a)$

The elements of the runs of $\operatorname{sort}(\hat{\beta})$ are
$1,2,\ldots,\operatorname{asc}_{d}\beta$ from left to right.

  2. $(b)$

The active sites of $\operatorname{sort}(\hat{\beta})$ are the sites before,
after, or between its runs.

  3. $(c)$

The number of active sites of $\operatorname{\mathtt{t}}(\hat{\beta})$ is
equal to $\operatorname{asc}_{d}\beta+1$.

###### Proof.

$(a)$ This follows directly from Proposition 3.3.

$(b)$ Suppose $\alpha=\beta a$ where $1\leq
a\leq\operatorname{asc}_{d}\beta+1$. If $a$ does not create a $d$-ascent then
$\binom{\operatorname{id}}{\hat{\alpha}}^{T}$ is obtained from
$\binom{\operatorname{id}}{\hat{\beta}}^{T}$ by inserting the column
$\binom{a}{n}$ at the beginning of the run of $a$’s in
$\operatorname{sort}(\hat{\beta})$. This will be the site before
$\operatorname{sort}(\hat{\beta})$ or the site between the run of $(a-1)$’s
and the run of $a$’s. Now suppose $a$ does cause a $d$-ascent so that
$\hat{\alpha}=\hat{\beta}^{+}a$. Note that the runs of
$\operatorname{sort}(\hat{\beta}$) and $\operatorname{sort}(\hat{\beta}^{+})$
are the same except that the entries in the latter which are greater than or
equal to $a$ have been increased by one. Now
$\binom{\operatorname{id}}{\hat{\alpha}}^{T}$ is obtained from
$\binom{\operatorname{id}}{\hat{\beta}}^{T}$ by inserting the column
$\binom{a}{n}$ after the run of $(a-1)$’s in
$\operatorname{sort}(\hat{\beta}^{+})$. So this will either be between the
runs for $a-1$ and $a+1$ or at the end. This shows that the sites before,
after, or between the runs are indeed active.

To see that these are the only active sites, note that
$|\operatorname{Im}_{d,n}|$ is the sum of the number of active sites over all
elements of $\operatorname{Im}_{d,n-1}$. Since $\operatorname{Im}_{d,n}$ is in
bijection with $\operatorname{A}_{d,n}$ we have that
$|\operatorname{Im}_{d,n}|$ is also the sum of $\operatorname{asc}_{d}\beta+1$
over all $\beta\in A_{d,n-1}$. But in the previous paragraph we showed that
there are at least $\operatorname{asc}_{d}\beta+1$ active sites in every
$\operatorname{sort}(\hat{\beta})$. Since the two sums are equal, we must have
exactly $\operatorname{asc}_{d}\beta+1$ active sites in every
$\operatorname{sort}(\hat{\beta})$. Thus there can be no others.

$(c)$ From Item $(b)$, the number of active sites of
$\operatorname{\mathtt{t}}(\hat{\beta})$ is equal to one plus the number of
runs of $\hat{\beta}$. Our claim follows immediately since there are exactly
$\operatorname{asc}_{d}\beta$ runs by Item $(a)$. ∎

Next we show that the last letter of a $d$-ascent sequence determines the
active site where the maximum of the corresponding permutation in
$\operatorname{Im}_{d}$ is inserted.

######  Lemma 7.6.

Let $d\geq 0$. Let $\alpha\in\operatorname{A}_{d,n}$ and let
$\pi=\operatorname{\mathtt{t}}(\hat{\alpha})\in\operatorname{Im}_{d,n}$. Then
$\pi$ is obtained by inserting $n$ in the $a$th active site of its parent,
where $a$ is the last letter of $\alpha$.

###### Proof.

Suppose that $\alpha=\beta a$, for some $\beta\in\operatorname{A}_{d,n-1}$. As
observed in the proof of Item $(b)$ of Lemma 7.5, the active sites of
$\operatorname{sort}(\hat{\beta})$ are the sites before, after, or between its
runs. Since the column $\binom{a}{n}$ is inserted at the beginning of the run
of $a$’s in $\operatorname{sort}(\hat{\beta})$, or after the last run if no
run of $a$’s exists, it follows immediately that $n$ is inserted in the $a$th
active site of its parent. ∎

We now wish to express the active sites of $\pi\in\operatorname{Im}_{d,n}$ in
terms of its parent $\rho\in\operatorname{Im}_{d,n-1}$. We will call the sites
of $\rho$ which remain between the same two element in $\pi$ common. In
addition, there will be two new sites before and after $n$ in $\pi$. The
following criterion is similar to the one [DS23] for the avoidance class of
the bivincular pattern $\sigma_{d}=(d+2)|(d+3)12\dots d\overline{(d+1)}$.

######  Lemma 7.7.

Suppose $\pi\in\operatorname{Im}_{d,n}$ has parent
$\rho\in\operatorname{Im}_{d,n-1}$. Then each common site is either active in
both $\pi$ and $\rho$ or inactive in both. Also, the site before $n$ is always
active in $\pi$. For the site after $n$, let $s$ and $t$ be the number of
active sites before $n$ in $\pi$ and before $n-1$ in $\rho$, respectively.
Then the site after $n$ is active if and only if

$s>t-d.$

###### Proof.

Let $\alpha=(\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d})^{-1}(\pi)=\beta
a$ and let $\beta$ have last element $b$. From the active sites of $\rho$ we
can determine $\operatorname{sort}(\hat{\beta})$. More precisely, from Lemma
7.5 one can construct $\operatorname{sort}(\hat{\beta})$ by filling in the
elements between the $i$th and $(i+1)$st active sites with $i$’s for each
$i\geq 1$. Moreover, by Lemma 7.6 the number of active sites before $n-1$ is
the last letter of $\beta$.

Now consider what happens when the column $\binom{a}{n}$ is added to
$\binom{\operatorname{id}}{\hat{\beta}}^{T}$. Again we see from the proof of
Lemma 7.5, that wherever this column is inserted, it becomes the beginning of
a run of $a$’s. Now using Item $(b)$ of the lemma, we see that all the common
sites retain their character and that the site to the left of $n$ must be
active.

Finally, look at the site to the right of $n$. From the definition of $s$ and
$t$ as well as the observation at the end of the first paragraph of this
proof, we have $s=a$ and $t=b$. Furthermore, since we only count active sites
before $n$, we can determine $s$ just from knowing the sites of $\rho$ and the
position of $n$ in $\pi$. So if $s\leq t-d$ then $a\leq b-d$ and $a$ does not
create a $d$-ascent. It follows that $\binom{a}{n}$ is placed at the beginning
of run of other $a$’s. So, the site to its right will not be active since it
does not begin a run. On the other hand, if $s>t-d$ then a similar argument
shows that the column is inserted as a run of $a$’s having only one element.
This forces the site to its right to be active and finishes the proof. ∎

To prove that $\operatorname{Im}_{d}=\operatorname{F}_{d}$, we relate active
sites with respect to $\operatorname{Im}_{d}$ with active sites with respect
to $\operatorname{F}_{d}$. To avoid confusion, we will call a site
_$\operatorname{F}_{d}$ -active_ if it is active with respect to
$\operatorname{F}_{d}$, and _$\operatorname{Im}_{d}$ -active_ if it is active
with respect to $\operatorname{Im}_{d}$. We will also need the following lemma
by Zang and Zhou.

######  Lemma 7.8.

[ZZ, Lemma 2.5] Let $d\geq 0$ and $n\geq 1$. Let
$\pi\in\operatorname{\mathfrak{S}}_{n}$ and let $\rho$ be obtained by removing
$n$ from $\pi$. Then $\pi\in\operatorname{F}_{d,n}$ if and only if
$\rho\in\operatorname{F}_{d,n-1}$ and $n$ is placed before $\rho$ or after
some $d$-active element of $\rho$. ∎

By Lemma 7.8, the $\operatorname{F}_{d}$-active sites of
$\rho\in\operatorname{F}_{d}$ are precisely those positions that follow a
$d$-active element of $\rho$, together with the position before the leftmost
entry.

######  Theorem 7.9.

For any $d,n\geq 0$,

$F_{d,n}=\operatorname{Im}_{d,n}.$

Furthermore, a site of $\pi\in\operatorname{F}_{d,n}=\operatorname{Im}_{d,n}$
is $\operatorname{F}_{d}$-active if and only if it is
$\operatorname{Im}_{d}$-active.

###### Proof.

We use induction on $n$, where the claim holds for $n\leq 1$. Let $n\geq 2$
and assume that $\operatorname{F}_{d,n-1}=\operatorname{Im}_{d,n-1}$. By
induction, given $\rho\in\operatorname{F}_{d,n-1}=\operatorname{Im}_{d,n-1}$,
a site of $\rho$ is $\operatorname{F}_{d}$-active if and only if it is
$\operatorname{Im}_{d}$-active. Since both $\operatorname{Im}_{d}$ and
$\operatorname{F}_{d}$ are tree-like, by Lemmas 7.4 and 7.8, respectively, the
equality $\operatorname{F}_{d,n}=\operatorname{Im}_{d,n}$ follows immediately.

Let us now consider a permutation
$\pi\in\operatorname{F}_{d,n}=\operatorname{Im}_{d,n}$. We have to show that a
site of $\pi$ is $\operatorname{F}_{d}$-active if and only if it is
$\operatorname{Im}_{d}$-active. The site before the leftmost entry is active
in both cases by item (b) of Lemma 7.5 and by Lemma 7.8. Now, let
$\rho\in\operatorname{F}_{d,n-1}=\operatorname{Im}_{d,n-1}$ be the father of
$\pi$. By Lemma 7.7 each common site is $\operatorname{Im}_{d}$-active in
$\pi$ if and only if it is $\operatorname{Im}_{d}$-active in $\rho$; and the
new site before $n$ is $\operatorname{Im}_{d}$-active. Similarly, by
definition of $d$-active entry and Lemma 7.8, each of these sites is
$\operatorname{F}_{d}$-active in $\pi$ if and only if it is
$\operatorname{F}_{d}$-active in $\rho$, and $n$ is always placed in an
$\operatorname{F}_{d}$ active site which is directly after an
$\operatorname{F}_{d}$-active element. Since by induction
$\operatorname{F}_{d}$-active and $\operatorname{Im}_{d}$-active sites of
$\rho$ coincide, the desired claim holds for every common site, as well as for
the new site before $n$.

To finish the proof of the theorem, we only need to consider the new site
after $n$. Using the same notation as in Lemma 7.7, let $s$ and $t$ be the
number of $\operatorname{Im}_{d}$-active sites before $n$ in $\pi$ and before
$n-1$ in $\rho$, respectively. By this lemma, the site after $n$ is
$\operatorname{Im}_{d}$-active if and only if $s>t-d$. If $n$ appears to the
right of $n-1$ in $\pi$, then $n$ is $\operatorname{F}_{d}$-active. Moreover,
we have $s\geq t+1$ since the site before $n$ is
$\operatorname{Im}_{d}$-active. Thus

$s\geq t+1>t\geq t-d$

and the site after $n$ is $\operatorname{Im}_{d}$-active, as desired. On the
other hand, suppose that $n$ appears to the left of $n-1$. Write

$\pi=g_{1}\ldots g_{i}\;n\;g_{i+1}\ldots g_{j}\;(n-1)\;g_{j+1}\ldots g_{n-1},$

for some $i\leq j$. We have

$\displaystyle t$ $\displaystyle=\text{$\\#$ $\operatorname{Im}_{d}$-active
sites before $(n-1)$ in $\rho$}$ $\displaystyle=\text{$\\#$
$\operatorname{F}_{d}$-active sites before $(n-1)$ in $\rho$}$ by induction,
and $\displaystyle s$ $\displaystyle=\text{$\\#$
$\operatorname{Im}_{d}$-active sites before $n$ in $\pi$}$
$\displaystyle=\text{$\\#$ $\operatorname{Im}_{d}$-active sites before
$g_{i+1}$ in $\rho$}$ $\displaystyle=\text{$\\#$ $\operatorname{F}_{d}$-active
sites before $g_{i+1}$ in $\rho$}$

where the last step is again by induction. Therefore,

$\displaystyle t-s$ $\displaystyle=\text{$\\#$ $\operatorname{F}_{d}$-active
sites between $g_{i+1}$ and $n-1$ in $\rho$}$ $\displaystyle=\text{$\\#$
$\operatorname{F}_{d}$-active entries in $g_{i+1}\ldots g_{j}$ in $\rho$},$

where at the last step we used Lemma 7.8. Finally, by Lemma 7.7, the site
after $n$ is $\operatorname{Im}_{d}$-active if and only if $s>t-d$.
Rearranging terms gives $t-s<d$ which is equivalent to $n$ being a $d$-active
element by the definition of $d$-active entries. In turn, this is equivalent
to the site after $n$ being $\operatorname{F}_{d}$-active by Lemma 7.8. This
completes the proof. ∎

######  Theorem 7.10.

For any $d\geq 0$,

$\Phi_{d}=\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}.$

###### Proof.

We have established in Theorem 7.9 that the maps $\Phi_{d}$ and
$\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}$ have the same image
$\operatorname{F}_{d}=\operatorname{Im}_{d}$. Let us prove inductively that
$\Phi_{d}=\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}$. Let $\alpha=\beta
a\in\operatorname{A}_{d,n}$, where $\beta\in\operatorname{A}_{d,n-1}$ and
$1\leq a\leq 1+\operatorname{asc}\beta$. By induction, we have

$\Phi_{d}(\beta)=\operatorname{\mathtt{t}}(\mathrm{hat}_{d}(\beta))=:\rho.$

Again by Theorem 7.9, a site of $\rho$ is $\operatorname{F}_{d}$-active if and
only if it is $\operatorname{Im}_{d}$-active. Moreover, the last letter of
$\alpha$ determines the label of the active site where $n$ is inserted both
under $\Phi_{d}$, by definition, and under
$\operatorname{\mathtt{t}}\circ\,\mathrm{hat}_{d}$, by Lemma 7.6. Thus
$\Phi_{d}(\alpha)=\operatorname{\mathtt{t}}(\mathrm{hat}_{d}(\alpha))$,
finishing the proof. ∎

##  8 Pattern avoidance in $\operatorname{F}_{d}$

The introduction and characterization of the $d$-Fishburn permutations opens
the door to pattern avoidance results parameterized by $d$. As an
illustration, we shall study one such instance in some depth, namely the case
of $d$-Fishburn permutations avoiding the classical pattern $213$. First,
recall the bivincular pattern

$\sigma_{d}=(d+2)|(d+3)12\dots d\overline{(d+1)}.$

Zang and Zhou [ZZ, Theorem 2.4] proved that

$\operatorname{F}_{d}\subseteq\operatorname{\mathfrak{S}}(\sigma_{d})$ (11)

for every $d\geq 0$, where for $d=0,1$ equality holds.

######  Proposition 8.1.

We have
$\operatorname{F}_{d}(213)=\operatorname{\mathfrak{S}}(\sigma_{d},213)$.

###### Proof.

The inclusion
$\operatorname{F}_{d}(213)\subseteq\operatorname{\mathfrak{S}}(\sigma_{d},213)$
follows from (11). For the same reason, if $d\leq 1$ we obtain the desired
equality. Now let $d\geq 2$. We shall prove the remaining inclusion
$\operatorname{\mathfrak{S}}(\sigma_{d},213)\subseteq\operatorname{F}_{d}(213)$.
Let $\pi\in\operatorname{\mathfrak{S}}_{d}(\sigma,213)$. For a contradiction,
suppose that $\pi\notin\operatorname{F}_{d}$. That is, $\pi$ contains an
occurrence $p_{i}p_{i+1}p_{j}$ of $\operatorname{\mathfrak{f}}$ where $p_{i}$
is not a $d$-active element. Since $p_{i}$ is not $d$-active, there are at
least $d$ entries $p_{u_{1}},\dots,p_{u_{d}}$, $u_{1}<u_{2}<\cdots<u_{d}$,
between $p_{i+1}$ and $p_{j}$ that are smaller than $p_{j}$ (and $d$-active).
Further, since $d\geq 2$, these must be in increasing order or else they would
create an occurrence of $213$ with $p_{j}$. Thus we have obtained an
occurrence $p_{i}p_{i+1}p_{u_{1}}\ldots p_{u_{d}}p_{j}$ of $\sigma_{d}$, which
is impossible. ∎

In order to enumerate $\operatorname{F}_{d}(213)$, we show that
$\operatorname{\mathfrak{S}}_{n}(\sigma_{d},213)$ is in bijection with the set
of Dyck paths of semilength $n$ that do not contain
$\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ as a factor. Let us start by defining a
bijection $\phi$ from $\operatorname{\mathfrak{S}}_{n}(213)$ to Dyck paths of
semilength $n$. It is simply a tilted version of what is sometimes called
[CK08] the _standard bijection_ from $132$-avoiding permutations to Dyck
paths. Any non-empty permutation $\pi\in\operatorname{\mathfrak{S}}(213)$
decomposes uniquely as

$\pi=p_{1}LR,$

where all the entries in $L$ are larger than $p_{1}$, and all the entries in
$R$ are smaller than $p_{1}$. Then $\phi$ is defined recursively by mapping
the empty permutation to the empty path and letting

$\phi(\pi)=\phi(p_{1}LR)=\mathtt{U}\phi(L)\mathtt{D}\phi(R),$

where here we abuse notation and use the same letter $L$ for the permutation
that is order isomorphic to $L$. Under the bijection $\phi$, the value of the
first letter determines the first return to the $x$-axis.

We show that $\phi$ restricts to a bijection from
$\operatorname{\mathfrak{S}}(\sigma_{d},213)$ to Dyck paths avoiding
$\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ as a factor, for every $d\geq 0$. First
a lemma whose easy proof is omitted.

######  Lemma 8.2.

Let $\pi\in\operatorname{\mathfrak{S}}_{n}(213)$ and let $\rho=\phi(\pi)$ be
the corresponding Dyck path. Then

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle
p_{1}<p_{2}<\cdots<p_{k}\;\iff\;\mathtt{U}^{k}\text{ is a prefix of
$\rho$.}}\hfill\qed$

######  Lemma 8.3.

Let $\pi\in\operatorname{\mathfrak{S}}_{n}(213)$ and let $\rho=\phi(\pi)$ be
the corresponding Dyck path. Then, for any $d\geq 0$,

$\pi\text{ contains
}\sigma_{d}\;\iff\;\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}\text{ is a factor of
$\rho$.}$

###### Proof.

We use induction on $n$, where $n=0$ and $n=1$ are trivial. Assume our claim
holds for $n-1$ where $n\geq 2$ and let
$\pi=p_{1}LR\in\operatorname{\mathfrak{S}}_{n}(213)$. Initially, suppose that
$\pi$ contains an occurrence $p_{i}p_{i+1}p_{u_{1}}\ldots p_{u_{d}}p_{j}$ of
$\sigma_{d}$. If either $p_{j}\in L$ or $p_{i}\in R$, then we can conclude
that $\rho$ contains a factor $\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ by
induction. Otherwise, since entries in $L$ are larger than entries in $R$, it
must necessarily be that $p_{i+1}\in L$ while $p_{u_{1}}$ is contained in $R$.
Moreover, since $p_{j}=p_{i}-1$, we have $i=1$ and $p_{j}$ is the largest
entry in $R$. Now, since $L$ is not empty, the path
$\mathtt{U}\phi(L)\mathtt{D}$ ends with $\mathtt{D}\mathtt{D}$. Furthermore,
since $\pi$ avoids $213$, all the entries preceding $p_{j}$ in $R$ are in
increasing order. Taking $p_{j}$ into account, (at least) the first $d+1$
entries of $R$ are in increasing order. Using Lemma 8.2, it follows that
$\phi(R)$ starts with $\mathtt{U}^{d+1}$. Hence the last two steps of
$\mathtt{U}\phi(L)\mathtt{D}$ form a factor
$\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ with the first $d+1$ steps of
$\phi(R)$, as wanted.

On the other hand, suppose that $\rho$ contains a factor
$\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$. We will show that $\pi$ contains
$\sigma_{d}$. Similarly to the argument in the previous paragraph, if the
whole factor $\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ is contained in either
$\phi(L)$ or $\phi(R)$, then we can conclude the proof by induction.
Otherwise, it must be that the last two steps of $\mathtt{U}\phi(L)\mathtt{D}$
are $\mathtt{D}\mathtt{D}$ and the first $d+1$ steps of $\phi(R)$ are
$\mathtt{U}^{d+1}$. Since $\phi(L)$ is not empty, we have $p_{1}<p_{2}$. Using
Lemma 8.2 once again, we have that the first $d+1$ entries of $R$, say
$p_{u_{1}},\dots,p_{u_{d}},p_{u_{d+1}}$, are in increasing order. Finally, the
maximum entry of $R$ is equal to $p_{1}-1$, and we obtain the desired
occurrence $p_{1}p_{2}p_{u_{1}}\ldots p_{u_{d}}(p_{i}-1)$ of $\sigma_{d}$ in
$\pi$. ∎

For any fixed $d\geq 0$, we shall derive a generating function for the numbers
$\\#\operatorname{F}_{d,n}(213)$. By the preceding proposition we can achieve
this by counting Dyck paths having no $\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$
factor. In fact, we shall derive a generating function for the distribution of
the number of $\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ factors over Dyck paths.
Let us start with the case $d=0$. In the spirit of the cluster method [GJ79,
Wan11], consider Dyck paths in which a subset of the
$\mathtt{D}\mathtt{D}\mathtt{U}$ factors have been marked. For instance,

$\rho=\mathtt{U}\mathtt{U}\mathtt{D}\mathtt{U}\underline{\mathtt{D}\mathtt{D}\mathtt{U}}\mathtt{U}\mathtt{U}\mathtt{D}\mathtt{D}\mathtt{U}\underline{\mathtt{D}\mathtt{D}\mathtt{U}}\mathtt{D}$

has three $\mathtt{D}\mathtt{D}\mathtt{U}$ factors, two of which have been
marked (underlined). Let us encode $\rho$ as a word $\rho^{\prime}$ over the
alphabet $\\{\mathtt{U},\mathtt{D},\mathtt{D}^{\prime}\\}$ by replacing each
marked $\mathtt{D}\mathtt{D}\mathtt{U}$ factor with a $\mathtt{D}^{\prime}$.
In our example we have

$\rho^{\prime}=\mathtt{U}\mathtt{U}\mathtt{D}\mathtt{U}\mathtt{D}^{\prime}\mathtt{U}\mathtt{U}\mathtt{D}\mathtt{D}\mathtt{U}\mathtt{D}^{\prime}\mathtt{D}.$

Note that $\rho^{\prime}$ represents a marked Dyck path if and only if
$\rho^{\prime}$ itself is a Dyck path, when interpreting $\mathtt{D}^{\prime}$
as $\mathtt{D}$, and the height at which any $\mathtt{D}^{\prime}$ step starts
is at least two.

Let
$\mathcal{P}_{0}\in\mathbb{Q}\langle\mathtt{U},\mathtt{D},\mathtt{D}^{\prime}\rangle$
be the formal sum of Dyck paths with two sorts of down steps, $\mathtt{D}$ and
$\mathtt{D}^{\prime}$. By the usual first return decomposition
$\mathcal{P}_{0}$ satisfies

$\mathcal{P}_{0}=1+\mathtt{U}\mathcal{P}_{0}\mathtt{D}\mathcal{P}_{0}+\mathtt{U}\mathcal{P}_{0}\mathtt{D}^{\prime}\mathcal{P}_{0}.$

Let
$\mathcal{Q}_{0}\in\mathbb{Q}\langle\mathtt{U},\mathtt{D},\mathtt{D}^{\prime}\rangle$
be the formal sum of the subset of the paths encoded in $\mathcal{P}_{0}$
defined by requiring that the height at which any $\mathtt{D}^{\prime}$ step
starts is at least two. Then

$\mathcal{Q}_{0}=(\mathtt{U}\mathcal{P}_{0}\mathtt{D})^{*},$

where we use the (Kleene star) convention
$\mathcal{F}^{*}=1+\mathcal{F}+\mathcal{F}^{2}+\dots$. Define the map
$\varphi:\mathbb{Q}\langle\mathtt{U},\mathtt{D},\mathtt{D}^{\prime}\rangle\to\mathbb{Q}[q,x]$
by $\mathtt{U}\mapsto x$, $\mathtt{D}\mapsto 1$, $\mathtt{D}^{\prime}\mapsto
qx$ and extending by linearity. Now, letting
$P_{0}(q,x)=\varphi(\mathcal{P}_{0})$ and
$Q_{0}(q,x)=\varphi(\mathcal{Q}_{0})$, we get the functional equations:

$\displaystyle P_{0}(q,x)$
$\displaystyle=1+xP_{0}(q,x)^{2}+qx^{2}P_{0}(q,x)^{2};$ $\displaystyle
Q_{0}(q,x)$ $\displaystyle=1/(1-xP_{0}(q,x)).$

Note that

$\sum_{\rho}\,(1+q)^{\mathtt{D}\mathtt{D}\mathtt{U}(\rho)}\,x^{|\rho|}\,=\,Q_{0}(q,x),$

where the sum ranges over all Dyck paths, $|\rho|$ is the semilength of
$\rho$, and $\mathtt{D}\mathtt{D}\mathtt{U}(\rho)$ is short for the number of
$\mathtt{D}\mathtt{D}\mathtt{U}$ factors in $\rho$. Indeed, the power series
$Q_{0}(q,x)$ counts Dyck paths with respect to semilength and number of marked
$\mathtt{D}\mathtt{D}\mathtt{U}$ factors, but so does the left-hand side: For
each of the $\mathtt{D}\mathtt{D}\mathtt{U}$ factors there is a choice to be
made, mark it (with a $q$) or leave it unmarked. Thus,

$Q_{0}(q-1,x)\,=\,\sum_{\rho}\,q^{\mathtt{D}\mathtt{D}\mathtt{U}(\rho)}\,x^{|\rho|}$
(12)

is the generating function we seek. In particular, $Q_{0}(-1,x)$ is the
generating function for Dyck paths with no $\mathtt{D}\mathtt{D}\mathtt{U}$
factors.

A similar analysis applies when $d\geq 1$. In this case we consider Dyck paths
$\rho$ in which a subset of the $\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ factors
are marked, and we encode such a path by a word $\rho^{\prime}$ over the
alphabet $\\{\mathtt{U},\mathtt{U}^{\prime},\mathtt{D}\\}$, where
$\mathtt{U}^{\prime}$ represents a marked
$\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ factor. In this way, $\rho^{\prime}$
represents a marked Dyck path if and only if $\rho^{\prime}$ itself is a Dyck
path, when interpreting $\mathtt{U}^{\prime}$ as $\mathtt{U}^{d-1}$, and the
height at which any $\mathtt{U}^{\prime}$ step starts is at least two. As the
reader may have noticed, for the preceding description to make sense in the
special case $d=1$ we need to view $\mathtt{U}^{0}$ as a level-step and in
this case we are really dealing with Motzkin paths rather than Dyck paths.
However, the equations describing the resulting language hold uniformly for
any $d\geq 1$ and this is the reason for not separating out $d=1$ as a special
case.

Let
$\mathcal{P}_{d}\in\mathbb{Q}\langle\mathtt{U},\mathtt{U}^{\prime},\mathtt{D}\rangle$
be be the formal sum of Dyck paths with two sorts of up steps, $\mathtt{U}$
and $\mathtt{U}^{\prime}$, where each $\mathtt{U}^{\prime}$ can be thought of
representing $\mathtt{D}\mathtt{D}\mathtt{U}^{d+1}$ and thus each such step
contributes $d-1$ to the height of the path. By a simple extension of the
first return decomposition we find that

$\mathcal{P}_{d}=1+\mathtt{U}\mathcal{P}_{d}\mathtt{D}\mathcal{P}_{d}+\mathtt{U}^{\prime}\mathcal{P}_{d}(\mathtt{D}\mathcal{P}_{d})^{d-1}.$

Let