\documentclass[submission]{FPSAC2017} \articlenumber{52} \addbibresource{52_Kim_Lin.bib} \newtheorem{thm}{Theorem} \newtheorem{lem}{Lemma} \usepackage{lipsum} \usepackage{rotating} \usepackage{tikz} %%%%%%%%%%%%%%%% \def\blue{\textcolor{blue}} \def\red{\textcolor{red}} \def\green{\textcolor{green}} \def\violet{\textcolor{violet}} \def\cyan{\textcolor{cyan}} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{St}[theorem]{Statement} \newtheorem{claim}[theorem]{Claim} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{Fact}[theorem]{Fact} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{?}[theorem]{Problem} \theoremstyle{definition} \newtheorem{Def}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{remark}[theorem]{Remark} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \def\lec{\mathrm{lec}} \def\inv{\mathrm{inv}} \def\aid{\mathrm{aid}} \def\ai{\mathrm{ai}} \def\dc{\mathrm{sw}} \def\rev{\mathrm{rev}} \def\comp{\mathrm{comp}} \def\G{\mathfrak{G}} \def\DES{\mathrm{DES}} \def\st{\mathrm{st}} \def\id{\mathrm{id}} \def\Fix{\mathrm{FIX}} \def\fix{\mathrm{fix}} \def\pix{\mathrm{pix}} \def\rix{\mathrm{rix}} \def\aix{\mathrm{aix}} \def\max{\mathrm{max}} \def\min{\mathrm{min}} \def\cont{\mathrm{cont}} \def\exc{\mathrm{exc}} \def\dd{\mathrm{dd}} \def\des{\mathrm{des}} \def\Des{\mathrm{DES}} \def\maj{\mathrm{maj}} \def\imaj{\mathrm{imaj}} \def\Cont{\mathrm{Cont}} \def\wex{\mathrm{wex}} \def\fmaj{\mathrm{fmaj}} \def\S{\mathfrak{S}} \def\D{\mathfrak{D}} \def\T{\mathfrak{T}} \def\C{\mathfrak{C}} \def\E{\mathcal{E}} \def\R{\mathbb{R}} \def\DE{\mathcal{E}} \def\W{\mathcal{W}} \def\G{\mathfrak{G}} \def\dec{\mathrm{dec}} \def\tot{\mathrm{tot}} \def\single{\mathrm{single}} \def\wlec{\mathrm{wlec}} \def\rinv{\mathrm{rinv}} \def\wpix{\mathrm{wpix}} \def\da{\mathrm{da}} \def\tg{\mathrm{tg}} \def\SCF{\mathrm{SCF}} \def\LG{{L-hook}} \def\FG{{F-hook}} \def\cyc{\mathrm{cyc}} \def\lyc{\mathrm{lyc}} \def\valley{\mathrm{valley}} \def\peak{\mathrm{peak}} \def\cda{\mathrm{cda}} \def\cdd{\mathrm{cdd}} \def\Rix{\mathrm{RIX}} \def\Orb{\mathrm{Orb}} \def\ST{\mathrm{ST}} \def\VID{\mathrm{VID}} \def\LMA{\mathrm{LMA}} \def\LMI{\mathrm{LMI}} \def\RMA{\mathrm{RMA}} \def\RMI{\mathrm{RMI}} \def\BJP{\mathrm{BJP}} \def\AVA{\mathrm{AVA}} \def\lma{\mathrm{lma}} \def\rma{\mathrm{rma}} \def\IDES{\mathrm{IDES}} \def\EUL{\mathrm{EUL}} \def\eul{\mathrm{eul}} \def\last{\mathrm{last}} \def\iasc{\mathrm{iasc}} \def\m{{\bf m}} \def\DIST{\mathrm{DIST}} \def\ZERO{\mathrm{ZERO}} \def\EMA{\mathrm{EMA}} \def\Invcode{\mathrm{Invcode}} \def\Majcode{\mathrm{Majcode}} \def\zero{\mathrm{zero}} \def\ema{\mathrm{ema}} \def\turn{\mathrm{turn}} \def\Red{\mathrm{red}} \def\return{\mathrm{return}} \def\segm{\mathrm{segment}} \def\lma{\mathrm{lma}} \def\lmi{\mathrm{lmi}} \def\neg{\mathrm{neg}} \def\fexc{\mathrm{fexc}} \def\imaj{\mathrm{imaj}} \def\asc{\mathrm{asc}} \def\ASC{\mathrm{ASC}} \def\NDD{\mathrm{NDD}} \def\lrm{\mathrm{lrm}} \def\Dyck{\mathrm{Dyck}} \def\area{\mathrm{area}} \def\rank{\mathrm{rank}} \def\lrm{\operatorname{lrm}} \def\NDW{\operatorname{NDW}} \def\dist{\operatorname{dist}} \def\EXPO{\operatorname{EXPO}} \def\CRI{\operatorname{CRI}} \def\cri{\operatorname{cri}} \def\lmi{\operatorname{lmi}} \def\ides{\operatorname{ides}} \def\max{\operatorname{max}} \def\ROW{\operatorname{ROW}} \def\M{\mathcal{M}} \def\RR{\mathcal{R}} \def\O{\mathcal{O}} \def\P{\mathbb{P}} \def\pos{\operatorname{{\bf pos}}} \def\area{\operatorname{{area}}} \def\I{\operatorname{{\bf I}}} \def\up{\operatorname{{up}}} \def\val{\operatorname{{val}}} \def\s{\operatorname{{\bf s}}} \def\st{\operatorname{st}} \def\mod{\operatorname{mod}} \title[Restricted inversion sequences]{Refined restricted inversion sequences} \author[D. Kim and Z. Lin]{Dongsu Kim\thanks{\href{mailto:dongsu.kim@kaist.ac.kr}{dongsu.kim@kaist.ac.kr}}\addressmark{1} \and Zhicong Lin\thanks{\href{mailto:lin@nims.re.kr}{lin@nims.re.kr}. Supported in part by the National Science Foundation of China grant 11501244.}\addressmark{2}} \address{\addressmark{1}Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, Daejeon 305-701, Republic of Korea\\ \addressmark{2}School of Science, Jimei University, Xiamen 361021, P.R. China \& CAMP, National Institute for Mathematical Sciences, Daejeon 305-811, Republic of Korea} \received{\today} \abstract{Recently, the study of patterns in inversion sequences was initiated by Corteel-Martinez-Savage-Weselcouch and Mansour-Shattuck independently. Motivated by their works and a double Eulerian equidistribution due to Foata (1977), we investigate several classical statistics on restricted inversion sequences that are either known or conjectured to be enumerated by {\em Catalan}, {\em Large Schr\"oder}, {\em Euler} and {\em Baxter} numbers. One of the two highlights of our results is an intriguing bijection between $021$-avoiding inversion sequences and $(2413,4213)$-avoiding permutations, which proves a sextuple equidistribution involving double Eulerian statistics. The other one is a refinement of a conjecture due to Martinez and Savage that the cardinality of $\I_n(\geq,\geq,>)$ is the $n$-th Baxter number, which is proved via the so-called {\em obstinate kernel method} developed by Bousquet-M\'elou.} \keywords{Inversion sequences, ascents, distinct entries, last entry, Schr\"oder numbers, Baxter numbers} \begin{document} \maketitle \section{Introduction} For each $n\geq1$, the set of {\em inversion sequences} of length $n$, denoted $\I_n$, is defined by $\I_n=\{(e_1,e_2,\ldots,e_n): 0\leq e_i\pi_i\}$}|, $$ is a natural coding of $\S_n$. Clearly, the sum of the entries of $\Theta(\pi)$ equals the number of {\em inversions} of $\pi$, i.e., the number of pairs $i\pi_j$. This is the reason why $\I_n$ is named inversion sequences here. Pattern avoidance in permutations has already been extensively studied in the literature (see the book by Kitave~\cite{ki}), while the systematic study of patterns in inversion sequences was initiated only recently in~\cite{cor} and~\cite{mash}. Since both permutations and inversion sequences will be regarded as words over $\N=\{0,1,\ldots\}$, their patterns can be defined in a unified way as follows. For two words $W=w_1w_2\cdots w_n$ and $P=p_1p_2\cdots p_k$ ($k\leq n$) on $\N$, we say that {\em$W$ contains the pattern $P$} if there exist some indices $i_1,\,\leq,\,\geq,\,=,\,\neq,\,-\}^3$, they studied the set $\I_n(\rho_1,\rho_2,\rho_3)$ consisting of those $e\in\I_n$ with no $i,<)=\I_n(021)$ and $\I_n(\geq,-,\geq)=\I_n(000,101,110)$. In \cref{patt}, we summarize some of their enumeration results and conjectures, as well as corresponding classical facts in permutation patterns. \begin{figure} \setlength {\unitlength} {1mm} \begin {picture} (100,50) \setlength {\unitlength} {1mm} \thinlines \put(3,0){\line(1,0){160}}\put(3,50){\line(1,0){160}}\put(13,0){\line(0,1){50}} \put(5,44){$C_n$} \put(18,44){$\I_n(132),\I_n(123)$: classical result~\cite{ki}; $\I_n(\geq,-,\geq)$: conjectured in~\cite{ms}} \put(3,40){\line(1,0){160}} \put(5,30){$S_n$} \put(18,32){$\S_n(2413,3142),\S_n(2413,4213),\S_n(3124,3214)$: classical result~\cite{kre}} \put(18,24){$\I_n(021)$: proved in~\cite{cor,mash}; $\I_n(\geq,\neq,\geq),\I_n(>,-,\geq),\I_n(\geq,-,>)$: proved in~\cite{ms}} \put(3,20){\line(1,0){160}} \put(5,14){$B_n$} \put(18,14){$\S_n(2\underline{41}3,3\underline{14}2)$: classical result~\cite{chung}; $\I_n(\geq,\geq,>)$: conjectured in \cite{ms}} \put(3,4){\text{$E_{n+1}$}} \put(18,4){\text{Simsun permutations of $[n]$: classical result \cite{sun}; $I_n(000)$: proved in~\cite{cor}}} \put(3,10){\line(1,0){160}} \end{picture} \caption{Sets enumerated by $C_n,S_n,B_n$ or $E_{n+1}$. \label{patt}} \end {figure} Based on these results, we will investigate more connections between restricted permutations and inversion sequences by considering several classical statistics that we recall below. For each $\pi\in\S_n$ and each $e\in\I_n$, let $$ \DES(\pi):=\{i\in[n-1]: \pi_i>\pi_{i+1}\}\quad \text{and}\quad\ASC(e):=\{i\in[n-1]: e_i)$ is the $n$-th {\em Baxter number} (denoted $B_n$), which is proved via Bousquet-M\'elou's {\em obstinate kernel method} (see \cref{sec:bax}). \section{Catalan numbers} \label{sec:cat} Let $(\rho_1,\rho_2,\rho_3)$ be a relation triple in $\{(\geq,-,\geq),(\geq,-,>),(\geq,\geq,>)\}$. We introduce the parameter $\cri(e)$ for each $e\in\I_n(\rho_1,\rho_2,\rho_3)$, that we call the {\em {\bf cri}tical value} of $e$, as the minimal integer $c$ such that $(e_1,\ldots,e_n,c)\in\I_{n+1}(\rho_1,\rho_2,\rho_3)$. Note that ``$\cri$'' depends on the relation triple $(\rho_1,\rho_2,\rho_3)$. For example, if we consider $e=(0,1,0,2,2,4)$ as inversion sequence in $\I_6(\geq,-,>)$, then $\cri(e)=2$. However, $\cri(e)=3$ when $e$ is considered as an inversion sequence in $\I_6(\geq,-,\geq)$. The reason to introduce ``$\cri$'' is that if $e\in\I_n(\rho_1,\rho_2,\rho_3)$, then $(e_1,\ldots,e_n,k)$ is in $\I_{n+1}(\rho_1,\rho_2,\rho_3)$ if and only if $\cri(e)\leq k\leq n$. This parameter will play an important role in our study of the {\em Catalan}, {\em Schr\"oder} and {\em Baxter triangles} induced by the statistic ``$\last$''. As a warm-up, we will first show how the critical value can be used to prove that $|\I_n(\geq,-,\geq)|=C_n$, which was conjectured in~\cite{ms}. Let us define the refinement $C_{n,k}:=|\{e\in\I_n(\geq,-,\geq): \last(e)=k\}|$. The following recurrence shows that the numbers $C_{n,k}$ generate the {\em Catalan triangle} that has already been widely studied (see~\href{https://oeis.org/A009766}{OEIS: A009766}). \begin{proposition}\label{cat:tria} For $0\leq k\leq n-1$, we have the three-term recurrence $$ C_{n,k}=C_{n,k-1}+C_{n-1,k}. $$ \end{proposition} \begin{proof} Let $\mathfrak{C}_{n,k}:=\{e\in\I_n(\geq,-,\geq): \last(e)=k\}$. We divide $\mathfrak{C}_{n,k}$ into the disjoint union $\mathfrak{A}_{n,k}\cup\mathfrak{B}_{n,k}$, where $\mathfrak{A}_{n,k}=\{e\in\mathfrak{C}_{n,k}: \cri(e_1,e_2,\ldots,e_{n-1})=k\}$ and $\mathfrak{B}_{n,k}=\mathfrak{C}_{n,k}\setminus\mathfrak{A}_{n,k}$. Since $\cri(e_1,e_2,\ldots,e_{n-1})\leq k-1$ for $e\in\mathfrak{B}_{n,k}$, the mapping that sends $(e_1,e_2,\ldots,e_{n-1},k)$ to $(e_1,e_2,\ldots,e_{n-1},k-1)$ is a bijection from $\mathfrak{B}_{n,k}$ to $\mathfrak{C}_{n,k-1}$. Therefore, the cardinality of $\mathfrak{B}_{n,k}$ is $C_{n,k-1}$ and so it remains to show that $|\mathfrak{A}_{n,k}|=C_{n-1,k}$. Now, we are going to construct a bijection $g:\mathfrak{A}_{n,k}\rightarrow\mathfrak{C}_{n-1,k}$, which will complete the proof of the recurrence for $C_{n,k}$. For each $e\in\mathfrak{A}_{n,k}$, there is a unique index $i$ such that $e_i=k-1$ and $e_{i+1}\leq k-1$. Define $g(e)$ to be the inversion sequence obtained from $e$ by deleting $e_{n-1}$, if $e_{n-1}=n-2$, or by deleting $e_i$, otherwise. For example, we have $g(0,1,1,3,2)=(0,1,1,2)$ while $g(0,1,1,2,2)=(0,1,2,2)$. It is routine to check that $g$ is actually a bijection. \end{proof} \begin{theorem} For $n\geq1$, we have the equidistribution $$ \sum_{\pi\in\S_n(123)}t^{\des(\pi)}=\sum_{e\in\I_n(\geq,-,\geq)}t^{\dist(e)}. $$ \end{theorem} \begin{proof} Let $e\in\I_n(\geq,-,\geq)$. If $t=\max\{i: e_i=i-1\}): \last(e)=k\}|=|\{e\in\I_n(021): \last(e)\equiv k+1 (\mod\,n)\}|. \end{equation} \end{theorem} Note that this result is obviously true for $k=n-1,n-2,n-3$. Let us define the {\em Schr\"oder triangle} $S_{n,k}:=|\{e\in\I_n(\geq,-,>): \last(e)=k\}|$. We have the following simple recurrence for $S_{n,k}$. \begin{lemma}\label{sch:tri} For $0\leq k\leq n-3$, we have the four-term recurrence $$ S_{n,k}=S_{n,k-1}+2S_{n-1,k}-S_{n-1,k-1}. $$ \end{lemma} \begin{proof} As in the Catalan case, we divide the set $\mathcal{S}_{n,k}:=\{\I_n(\geq,-,>):\last(e)=k\}$ into the disjoint union $\mathcal{A}_{n,k}\cup\mathcal{B}_{n,k}$, where $\mathcal{A}_{n,k}:=\{e\in\mathcal{S}_{n,k}: \cri(e_1,\ldots,e_{n-1})=k\}$ and $\mathcal{B}_{n,k}=\mathcal{S}_{n,k}\setminus \mathcal{A}_{n,k}$. Clearly, there is a natural bijection from $\mathcal{B}_{n,k}$ to $\mathcal{S}_{n,k-1}$, which maps $(e_1,\ldots,e_{n-1},k)$ to $(e_1,\ldots,e_{n-1},k-1)$. Therefore, the cardinality of $\mathcal{B}_{n,k}$ is $S_{n,k-1}$ and so it remains to show $|\mathcal{A}_{n,k}|=2S_{n-1,k}-S_{n-1,k-1}$, assuming $k\leq n-3$. To do this, we further divide $\mathcal{A}_{n,k}$ into the disjoint union $\mathcal{C}_{n,k}\cup\mathcal{D}_{n,k}$, where $$ \mathcal{C}_{n,k}:=\{e\in\mathcal{A}_{n,k}: e_{n-1}=n-2,\ \cri(e_1,\ldots,e_{n-2})=k\}\\ $$ and $\mathcal{D}_{n,k}=\mathcal{A}_{n,k}\setminus\mathcal{C}_{n,k}$. Obviously, we have $\{(e_1,\ldots,e_{n-2},e_n): e\in \mathcal{C}_{n,k}\}=\mathcal{A}_{n-1,k}$. Thus, $|\mathcal{C}_{n,k}|=|\mathcal{A}_{n-1,k}|=|\mathcal{S}_{n-1,k}|-|\mathcal{B}_{n-1,k}|=S_{n-1,k}-S_{n-1,k-1}$, which will end the proof once we can define a bijection from $\mathcal{D}_{n,k}$ to $\mathcal{S}_{n-1,k}$. For each $e\in\mathcal{D}_{n,k}$, if $e_i$ is the left-most entry that equals $\cri(e)=k$, then the entries $e_i,e_{i+1},\ldots,e_{n-1}$ of $e$ must satisfy: (i) $e_i=k$ and $e_{i+1}\leq k$; (ii) $k\leq e_{i+2}\leq e_{i+3}\leq\cdots\leq e_{n-1}$, where the inequalities after the entries greater than $k$ are strict. Now removing the right-most entry $e_j$, such that $e_j=k$ and $i\leq j\leq n-1$, from $e$ results in an inversion sequence in $\mathcal{S}_{n-1,k}$ (since $e_{n-1}\leq n-3$) that we denote $f(e)$. For example, we have $f(0,1,2,0,2,2)=(0,1,2,0,2)$, $f(0,1,0,2,2,2)=(0,1,0,2,2)$ and $f(0,1,2,1,3,2)=(0,1,1,3,2)$. We claim that the map $f:\mathcal{D}_{n,k}\rightarrow\mathcal{S}_{n-1,k}$ is a bijection. \end{proof} \begin{proof}[Proof of \cref{thm:sch}] It is not hard to show that the right-hand side of~\eqref{sch:tri} satisfies the same recurrence relation as $S_{n,k}$, which completes the proof of the theorem. \end{proof} One may ask if there is any other interpretation of $S_{n,k}$ in terms of pattern-avoiding permutations. The following conjecture will answer this question completely, if true. \begin{conjecture}\label{schroder:asc} Let $(\sigma,\pi)$ be a pair of patterns of length $4$. Then, $$ S_{n,k}=|\{\pi\in\S_n(\sigma,\pi): \last(\pi)-1=k\}| $$ for any $0\leq k\pi_j\,\, \text{for all $1\leq ji$}\}$. The {\em positions of {\bf zero}s in $e$} is $\ZERO(e):=\{i\in[n]: e_i=0\}$. The {\em positions of the {\bf e}ntries of $e$ that achieve {\bf ma}ximum} is $\EMA(e):=\{i\in[n]: e_i=i-1\}$ and the {\em positions of {\bf r}ight-to-left {\bf mi}nima} of~$e$ is $\RMI(e):=\{i\in[n]: e_ii$}\}$. \subsubsection{A sextuple equidistribution} \label{sec:sex} \begin{figure} \hspace{1.4cm} \scalebox{0.8}{ \begin{tikzpicture}[scale=.5,] \draw[step=1,color=gray] (7,1) grid (14,8); \draw [very thick,color=red](7,1)--(8,1); \draw [very thick](8,2)--(9,2); \draw [very thick,color=red](9,1)--(10,1); \draw [very thick](10,2)--(11,2); \draw [very thick](11,3)--(12,3); \draw [very thick,color=red](12,1)--(13,1); \draw [very thick](13,5)--(14,5); \draw [color=blue](-0.1,0)--(-0.1,0); \draw [color=blue](7,1)--(14,8); \draw(7.5,0.5) node{$0$}; \draw(8.5,0.5) node{$1$}; \draw(9.5,0.5) node{$0$}; \draw(10.5,0.5) node{$1$}; \draw(11.5,0.5) node{$2$}; \draw(12.5,0.5) node{$0$}; \draw(13.5,0.5) node{$4$}; \draw(16,5) node{$\mapsto$}; \draw(15.95,5.6) node{$d$}; \draw[step=1,color=gray] (18,1) grid (25,8); \draw [color=blue](18,1)--(25,8); \draw [very thick,color=red](18,1)--(19,1); \draw [very thick](19,1)--(19,2)--(20,2); \draw [very thick,color=red](20,2)--(21,2); \draw [very thick](21,2)--(22,2)--(22,3)--(23,3); \draw [very thick,color=red](23,3)--(24,3); \draw [very thick](24,3)--(24,5)--(25,5)--(25,8); \end{tikzpicture} } \caption{The outline of inversion sequence $(0,1,0,1,2,0,4)$.\label{fig:outline}} \end{figure} Note that an inversion sequence avoids $021$ if and only if its positive entries are weakly increasing, which inspires the following geometric representation. \begin{Def}[Outline]\label{outline} Recall that a {\em Dyck path} of length $n$ is a lattice path in $\N^2$ from $(0,0)$ to $(n,n)$ using the {\em east step} $(1,0)$ and the {\em north step} $(1,0)$, which does not pass above the line $y=x$. Here a Dyck path will be represented as $d_1d_2\ldots d_n$, where $d_i$ is the height of its $i$-th east step. For each $e\in\I_n(021)$, we associate it with a two-colored Dyck path $d(e)=d_1d_2\ldots d_n$, where the red east steps indicate the positions of zero entries of $e$ like this: $$ d_{i}= \begin{cases} \,\,e_i\quad&\text{if $e_i\neq0$},\\ \,\,k\quad&\text{if $e_i=0$ and $k=\max\{e_1,\ldots,e_i\}$}. \end{cases} $$ For example, if $e=(0,1,0,1,2,0,4)\in\I_7(021)$, then $d(e)$ is the two-colored Dyck path in \cref{fig:outline}. The two-colored Dyck path $d(e)$ is called the {\em outline} of $e$. We introduce the {\em {\bf \em expo}sed positions} of $e$ as $$ \EXPO(e):=\{i: i\notin\mathcal{C}(e) \text{ and $i-d_ii$ }\}, $$ where $\mathcal{C}(e)=\{i:\text{$e_i=0 $ and there is $(a,b)$, $a,-,\geq)}s^{\asc(e)}. $$ This follows from \cref{thm:sex}, the palindromicity of $S_n(t)$ and two more multivariate equidistributions (\cref{equi:1,equi:2}) stated below. First we introduce a set-valued extension of ``$\dist$'' different from ``$\DIST$'': $$ \ROW(e):=\{e_1,e_2,\ldots,e_n\}\setminus\{0\},\ \text{for each $e\in\I_n$}. $$ \begin{theorem}\label{equi:1}For $n\geq1$, we have $$ \sum_{e\in\I_n(\geq,\neq,\geq)}s^{\ROW(e)}t^{\ASC(e)}u^{\last(e)}=\sum_{e\in\I_n(>,-,\geq)}s^{\ROW(e)}t^{\ASC(e)}u^{\last(e)}. $$ \end{theorem} \begin{proof} We can construct a bijection from $\I_n(\geq,\neq,\geq)$ to $\I_n(>,-,\geq)$, which preserves the triple statistics $(\ROW,\ASC,\last)$. Notice that $\I_n(\geq,\neq,\geq)=\I_n(\blue{110},101,201,210)$, while $\I_n(>,-,\geq)=\I_n(\blue{100},101,201,210)$. The idea is to replace iteratively occurrences of pattern $100$ in an inversion sequence in $\I_n(\geq,\neq,\geq)\setminus\I_n(>,-,\geq)$ with those of patterns $110$, the details of which will be omitted here. \end{proof} Recently, Baril and Vajnovszki~\cite{bv} constructed a new coding $\Phi:\S_n\rightarrow\I_n$ satisfying $$ (\VID,\DES,\LMA,\LMI,\RMA)\pi=(\DIST,\ASC,\ZERO,\EMA,\RMI)\Phi(\pi) $$ for each $\pi\in\S_n$. \begin{theorem}\label{equi:2}For $n\geq1$, we have $$ \sum_{\pi\in\S_n(3142,3124)}s^{\VID(\pi)}t^{\DES(\pi)}=\sum_{e\in\I_n(\geq,\neq,\geq)}s^{\DIST(e)}t^{\ASC(e)}. $$ \end{theorem} \begin{proof} We can show that the Baril--Vajnovszki coding $\Phi$ restricts to a bijection between $\S_n(3124,3142)$ and $\I_n(\geq,\neq,\geq)$. The details are omitted here. \end{proof} \begin{remark} Interestingly, we have also been able to show that $\Phi$ restricts to a bijection between $\S_n(2413,4213)$ and $\I_n(021)$. This restricted $\Phi$ does not transform ``$\RMI$'' to ``$\EXPO$'', while our bijection $\Psi$ in \cref{thm:sex} does. \end{remark} \vspace{-3ex} \section{Baxter numbers} \label{sec:bax} A permutation avoiding both {\em vincular patterns} (see~\cite{ki} for the definition) $2\underline{41}3$ and $3\underline{14}2$ is called a {\em Baxter permutation}. It is a result of Chung et al.~\cite{chung} that $$ B_n=|\S_n(2\underline{41}3,3\underline{14}2)|=\frac{1}{{n+1\choose1}{n+1\choose2}}\sum_{k=0}^{n-1}{n+1\choose k}{n+1\choose k+1}{n+1\choose k+2}. $$ The number $B_n$ is known as the $n$-th {\em Baxter number}. Martinez and Savage~\cite{ms} conjectured that $|\I_n(\geq,\geq,>)|=B_n$, which can be refined as follows. \begin{theorem}\label{thm:baxter} For $n\geq1$, we have the equidistribution \begin{equation}\label{bax:equi} \sum_{e\in\I_n(\geq,\geq,>)}u^{n+1-\cri(e)}=\sum_{\pi\in\S_n(2\underline{41}3,3\underline{14}2)}u^{\lma(\pi)+\rma(\pi)}. \end{equation} \end{theorem} \begin{corollary} Define the Baxter triangle as $B_{n,k}:=|\{e\in\I_n(\geq,\geq,>): \last(e)=k\}|$. Then, $$ B_{n,k}=|\{\pi\in\S_{n-1}(2\underline{41}3,3\underline{14}2): \lma(\pi)+\rma(\pi)\geq n-k\}|. $$ \end{corollary} The rest of this section is devoted to a sketch of our proof of \cref{thm:baxter}. For each $e\in\I_n(\geq,\geq,>)$, introduce the {\em parameters} $(p,q)$ of $e$, where $p=m+1-\cri(e)$ and $q=n-m$ with $m=\max\{e_1,\ldots,e_n\}$. After a careful discussion we can obtain the following new rewriting rule (see~\cite{bcfmm} for other known rewriting rules for Baxter families). \begin{lemma}\label{lem:baxeter} Let $e\in\I_n(\geq,\geq,>)$ be an inversion sequence with parameters $(p,q)$. Exactly $p+q$ inversion sequences in $\I_{n+1}(\geq,\geq,>)$ when removing their last entries will become $e$, and their parameters are respectively: \begin{align*} &(p-1,q+1), (p-2,q+1), \ldots, (1,q+1), \\ &(1,q+1), (p+1,q), (p+2,q-1),\ldots, (p+q,1). \end{align*} The order in which the parameters are listed corresponds to the inversion sequences with last entries from $c$ to $n$, where $c=n+1-(p+q)$. \end{lemma} Define the formal power series $F(t;u,v)=F(u,v):=\sum_{n,p,q\geq1}F_{n,p,q}t^nu^pv^q$, where $F_{n,p,q}$ is the number of inversion sequences in $\I_n(\geq,\geq,>)$ with parameters $(p,q)$. We can turn the above lemma into a functional equation as follows. \begin{proposition}We have the following equation for $F(u,v)$: \begin{equation}\label{eq:baxter} \biggl(1+\frac{tv}{1-u}+\frac{tv}{1-v/u}\biggr)F(u,v)=tuv+tuv\biggl(1+\frac{1}{1-u}\biggr)F(1,v)+\frac{tv}{1-v/u}F(u,u). \end{equation} \end{proposition} Let $G(u,v):=\sum_{n\geq1}t^n\sum_{\pi\in\S_n(2\underline{41}3,3\underline{14}2)}u^{\lma(\pi)}v^{\rma(\pi)}$. This formal power series $G(u,v)$ was first introduced and studied by Bousquet-M\'elou~\cite{bo}. Now, \cref{thm:baxter} is equivalent to $G(u,u)=F(u,u)$, which will be established by solving~\eqref{eq:baxter}. \begin{proof}[Proof of \cref{thm:baxter}] It will be convenient to set $w=v/u$ in~\eqref{eq:baxter}. The equation then becomes $$ \biggl(1+\frac{tuw}{1-u}+\frac{tuw}{1-w}\biggr)F(u,wu)=tu^2w+tu^2w\biggl(1+\frac{1}{1-u}\biggr)F(1,wu)+\frac{tuw}{1-w}F(u,u). $$ Further setting $u=1+x$ and $w=1+y$ in the above equation yields \begin{multline}\label{eq:bax} \frac{xy-t(1+x)(1+y)(x+y)}{t(1+x)(1+y)}F(1+x,(1+x)(1+y))\\ =xy(1+x)-(1-x^2)yF(1,(1+x)(1+y))-\widetilde{F}(x), \end{multline} where $\widetilde{F}(x):=xF(1+x,1+x)$. We call the numerator $K(x,y)$ of the coefficient of $F(1+x,(1+x)(1+y))$ the {\em kernel} of the above equation: $$ K(x,y)=xy-t(1+x)(1+y)(x+y). $$ We are going to apply the so-called {\em kernel method} (cf.~\cite{bo}) to this equation. As a polynomial in $y$, the kernel has two roots: $$ Y(x)=\frac{1-t(1+x)(1+\bar{x})-\sqrt{1-2t(1+x)(1+\bar{x})-t^2(1-x^2)(1-\bar{x}^2)}}{2t(1+\bar{x})}, $$ $$ Y'(x)=\frac{1-t(1+x)(1+\bar{x})+\sqrt{1-2t(1+x)(1+\bar{x})-t^2(1-x^2)(1-\bar{x}^2)}}{2t(1+\bar{x})}, $$ where $\bar{x}=1/x$. Only the first root can be substituted for $y$ in~\eqref{eq:bax}, because the term $F(1+x,(1+x)(1+Y'))$ is not a well-defined power series in $t$ (the Taylor expansion of $Y'$ in $t$ does not exist). Now, we will adopt the {\em obstinate kernel method} that was invented by Bousquet-M\'elou~\cite[Section~2.2]{bo} for producing all the pairs $(x,y)$ that can be legally substituted in~\eqref{eq:bax}: those are the pairs $(x,Y), (\bar{x}Y,Y), (\bar{x}Y,\bar{x})$ and their dual $(Y,x), (Y,\bar{x}Y), (\bar{x},\bar{x}Y)$, thanks to the symmetry of the kernel $K(x,y)$. Substituting these 6 pairs into~\eqref{eq:bax} and after some manipulations, we obtain {\small \begin{equation*} \begin{cases} \,\,(x-xY^2)\widetilde{F}(x)-(Y-x^2Y)\widetilde{F}(Y)=(Y-Y^3)(x^2+x^3)-(x-x^3)(Y^2+Y^3), \\ \,\,(Y\bar{x}-Y^3\bar{x})\widetilde{F}(Y\bar{x})-(Y-Y^3\bar{x}^2)\widetilde{F}(Y)=(Y-Y^3)(Y^2\bar{x}^2+Y^3\bar{x}^3)-(Y\bar{x}-Y^3\bar{x}^3)(Y^2+Y^3), \\ \,\,(Y\bar{x}-Y\bar{x}^3)\widetilde{F}(Y\bar{x})-(\bar{x}-Y^2\bar{x}^3)\widetilde{F}(\bar{x})=(\bar{x}-\bar{x}^3)(Y^2\bar{x}^2+Y^3\bar{x}^3)-(Y\bar{x}-Y^3\bar{x}^3)(\bar{x}^2+\bar{x}^3). \end{cases} \end{equation*} } By eliminating $\widetilde{F}(Y)$ and $\widetilde{F}(Y\bar{x})$, we get a relation between $\widetilde{F}(x)$ and $\widetilde{F}(\bar{x})$: \begin{equation}\label{main:baxe} \widetilde{F}(x)+\widetilde{F}(\bar{x})=\frac{Y(1+x)(x^4-2Yx^3+2Y^2x-2Y+1)}{x^2(Y-1)(Y-x)}. \end{equation} But $\widetilde{F}(x)=xF(1+x,1+x)$ is a formal power series in $t$ with coefficients in $x\N[x]$, while $\widetilde{F}(\bar{x})$ is a formal power series in $t$ with coefficients in $\bar{x}\N[\bar{x}]$. Therefore, the positive part in $x$ of the right hand side of~\eqref{main:baxe} is exactly $\widetilde{F}(x)$. On the other hand, it has been showed in~\cite[Corollary~3]{bo} that if we let $\widetilde{G}(x):=xG(1+x,1+x)$, then \begin{equation} \frac{x-2t(1+x)^2}{t(1+x)^2}\widetilde{G}(x)=x^2-2R(x), \end{equation} where $R(x)=xG(1+x,1)$. Combining with the relation between $R(x)$ and $R(\bar{x})$ proved in~\cite[Eq.~(8)]{bo}: $$ R(x)+R(\bar{x})=\bar{x}^2Y(1+x^3-xY), $$ we have \begin{align*}\label{eq:bousquet} \widetilde{G}(x)+\widetilde{G}(\bar{x})&=\frac{t(1+x)^2}{x-2t(1+x)^2}(x^2+\bar{x}^2-2(R(x)+R(\bar{x})))\\ &=\frac{t(1+x)^2}{x-2t(1+x)^2}(x^2+\bar{x}^2-2\bar{x}^2Y(1+x^3-xY)). \end{align*} To check that $\frac{t(1+x)^2}{x-2t(1+x)^2}(x^2+\bar{x}^2-2\bar{x}^2Y(1+x^3-xY))$ equals the right hand side of~\eqref{main:baxe} is routine by Maple, which proves that $\widetilde{F}(x)=\widetilde{G}(x)$. This completes the proof. \end{proof} Since the proof of equidistribution~\eqref{bax:equi} uses the obstinate kernel method based on the formal power series, it is natural to ask for a bijective proof. \vspace{-2ex} %%%%%%%%%%%%%%%%%%%%%%% \section{Euler numbers} %%%%%%%%%%%%%%%%%%%%%%% \subsection{Entringer--Eulerian statistics on $\I_n(000)$} As introduced by Simion and Sundaram~\cite{sun}, a permutation $\pi\in\S_n$ is called a {\em Simsun permutation} if it has no double descents, even after removing $n,n-1,\ldots,k$ for any $k$. Let $RS_n$ be the set of all Simsun permutations in $\S_n$. Using the statistic ``$\last$'', we refine a result \cite[Corollary~2]{cor} by Corteel et al. \begin{theorem}Let $\asc(\pi):=n-1-\des(\pi)$ for each $\pi\in\S_n$. Then, $$ \sum_{\pi\in RS_n} t^{\asc(\pi)}u^{\last(\pi)}=\sum_{e\in\I_n(000)}t^{\dist(e)}u^{\last(e)+1}. $$ \end{theorem} \begin{proof} By combining the simple bijection in~\cite[Theorem~7]{cor} from $\I_n(000)$ to {\em$0$-$1$-$2$-increasing trees} with $n+1$ vertices and a special ordering of the {\em increasing tree representation} of permutations due to Maria Monks (see~\cite[Page~198]{st}). \end{proof} It also follows from the simple bijection in~\cite[Theorem~7]{cor} and a result of Poupard~\cite[Proposition~1]{pou} that the statistic ``$\last+1$'' is {\em Entrianger}. Can the generating function for this Entrianger--Eulerian pair be calculated? \subsection{Double Eulerian distribution on $\I_n(000)$} As an application of Foata's V-code and S-code, we can prove the following double Eulerian equidistribution. \begin{theorem}\label{dou:sim} Let $\iasc(\pi):=\asc(\pi^{-1})$ for each $\pi\in\S_n$. Then, $$ \sum_{\pi\in RS_n} s^{\iasc(\pi)}t^{\asc(\pi)}=\sum_{e\in\I_n(000)}s^{\asc(e)}t^{\dist(e)}. $$ \end{theorem} The details for the proof of a set-valued extension of \cref{dou:sim} will be reported in a full version of this abstract. \printbibliography \end{document}