%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{fact}[thm]{Fact}
\newtheorem{ques}[thm]{Question}
\newtheorem{prob}[thm]{Problem}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}

\theoremstyle{remark}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{exam}[thm]{Example}

\usepackage{lipsum}
\usepackage{tikz,young}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb,euscript, mathrsfs,amscd} 
\usepackage{epsfig}
\usepackage{relsize}
\usepackage{blkarray}
\usepackage{multirow}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{ytableau}
\usepackage{caption}
\usepackage{hyperref}
\usepackage{cases}
\usepackage{ragged2e}
\usepackage{enumitem}
\usepackage[normalem]{ulem}
\usepackage{subfigure}
\usepackage{graphicx}

\newcommand\CC{\mathbb{C}}
\newcommand\ZZ{\mathbb{Z}}
\newcommand\frkg{\mathfrak{g}}
\newcommand\HH{\mathcal{H}}
\newcommand\calC{\mathcal{C}}
\newcommand\Spec{\mathcal{S}}

\newcommand\wt{\operatorname{wt}}
\newcommand\ch{\operatorname{ch}}
\newcommand\sh{\operatorname{shape}}
\newcommand\IH{\operatorname{IH}}
\newcommand\End{\operatorname{End}}
\newcommand\Ind{\operatorname{Ind}}
\newcommand\SYT{\operatorname{SYT}}
\newcommand\spann{\operatorname{span}}
\newcommand\Dyck{\operatorname{Dyck}}
\newcommand\LDyck{\operatorname{LDyck}}
\newcommand\NC{\operatorname{NC}}
\newcommand\NN{\operatorname{NN}}
\newcommand\Mat{\operatorname{Mat}}
\newcommand\CI{\operatorname{CI}}
\newcommand\Cr{\operatorname{Cr}}
\newcommand\SL{\operatorname{SL}}
\newcommand\AC{\operatorname{AC}}
\newcommand\rlmin{\operatorname{rlmin}}
\newcommand\cc{\operatorname{c}}
\newcommand\Web{\operatorname{Web}}


\newcommand\NS{\mathsf{N}}
\newcommand\ES{\mathsf{E}}

\newcommand\Des{\operatorname{Des}}

\newcommand\andre{Andr\'e~}

\newcommand\OnlyXmarking[2]
{\draw[very thick] (#1-0.7,#2-0.7)--(#1-0.3,#2-0.3);
\draw[very thick] (#1-0.7,#2-0.3)--(#1-0.3,#2-0.7); }
\newcommand\Xmarking[2]
{\draw[very thick] (#1-0.7,#2-0.7)--(#1-0.3,#2-0.3);
\draw[very thick] (#1-0.7,#2-0.3)--(#1-0.3,#2-0.7);
\draw (#1-1,#2-0.5)--(#1-0.5,#2-0.5);
\draw (#1-0.5,#2-0.5)--(#1-0.5,#2); }
\newcommand\Cross[2]
{
\draw (#1-0.5,#2)--(#1-0.5,#2-1);
\draw (#1,#2-0.5)--(#1-1,#2-0.5);
}
\newcommand\UP[2]
{
\draw (#1-0.5,#2)--(#1-0.5,#2-1);
}\newcommand\EAST[2]
{
\draw (#1,#2-0.5)--(#1-1,#2-0.5);
}
\newcommand\Asmooth[2]
{
\draw (#1,#2-0.5) .. controls (#1-0.45,#2-0.45) and (#1-0.45,#2-0.45) .. (#1-0.5,#2);
\draw (#1-1,#2-0.5) .. controls (#1-0.55,#2-0.55) and (#1-0.55,#2-0.55) .. (#1-0.5,#2-1);
}
\newcommand\Bsmooth[2]
{
\draw (#1-1,#2-0.5) .. controls (#1-0.55,#2-0.45) and (#1-0.55,#2-0.45) .. (#1-0.5,#2);
\draw (#1,#2-0.5) .. controls (#1-0.45,#2-0.55) and (#1-0.45,#2-0.55) .. (#1-0.5,#2-1);
}
\newcommand\Matching[2]
{
\draw (#1,0) to [out=55,in=125] (#2,0);
}

\newcommand\U{\mathsf{U}}
\newcommand\R{\mathsf{R}}
\newcommand\STEP{\mathsf{S}}

\newcommand\SYM{\mathfrak{S}}

\newcommand\qand{\quad\mbox{and}\quad}



%% define your title in the usual way
\title[A Combinatorial Model for the Transition Matrix]{A Combinatorial Model for the Transition Matrix Between the Specht and Web Bases}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[B.-H.~Hwang, J.~Jang, and J.~Oh]{Byung-Hak Hwang\thanks{\href{mailto:byunghakhwang@gmail.com}{byunghakhwang@gmail.com}.}\addressmark{1}, Jihyeug Jang\thanks{\href{mailto:4242ab@gmail.com}{4242ab@gmail.com}. Supported by NRF grant \#2019R1F1A1059081.}\addressmark{2}, \and Jaeseong Oh\thanks{\href{mailto:jsoh@kias.re.kr}{jsoh@kias.re.kr}. Supported by the KIAS Individual Grant (CG083401) at Korea Institute for Advanced Study.}\addressmark{3}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Applied Algebra and Optimization Research Center, Sungkyunkwan University,
South Korea \\ \addressmark{2}Department of Mathematics,
Sungkyunkwan University, South Korea \\ \addressmark{3}Korea Institute for Advanced Study, South Korea }

%% put the date of submission here
\received{November 24, 2021}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We introduce a new class of permutations, called web permutations.
Using these permutations, we provide a combinatorial interpretation for 
entries of the transition between the Specht and web bases,
which answers Rhoades's question.
Furthermore, we study enumerative properties of these permutations.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Specht basis, web basis, Andr\'e permutation, Euler number}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction and the main result}
In this article, we study the transition matrix between two famous bases,
the Specht basis and the web basis, for the irreducible representation of
the symmetric group \( \SYM_{2n} \) indexed by the partition \( (n,n) \).
Motivated by Rhoades's work~\cite{Rho19}, we give a combinatorial interpretation
for entries of the transition matrix as a certain class of permutations,
and present their interesting properties.

For an integer \( n\ge 1 \), let \( \SYM_{2n} \) be the symmetric group on the set
\( [2n] = \{ 1,\dotsc,2n \} \).
It is well known that each irreducible representation of \( \SYM_{2n} \) can be
indexed by a partition of \( 2n \).
For a partition \( \lambda \) of \( 2n \), we then denote
by \( \Spec^\lambda \) the irreducible representation indexed by \( \lambda \), called the \emph{Specht module}.
In this article, we narrow our focus down to the Specht module indexed by the partition \((n,n)\), and two well-studied bases for \( \Spec^{(n,n)} \).

A \emph{standard Young tableau} of shape \( (n,n) \) is an array of integers of shape \( (n,n) \)
whose entries are \( [2n] \), and each row and each column are increasing.

The set of standard Young tableaux of shape \( (n,n) \), denoted by \( \SYT(n,n) \), is an indexing set for
the \emph{Specht basis}
\[
\{ v_T \in \Spec^{(n,n)} \mid \mbox{\( T \) is a standard Young tableau of shape \( (n,n) \)} \}
\]
for \( \Spec^{(n,n)} \). For more details on the Specht basis and
related combinatorics, see \cite{Ful97, Sag01}.

A \emph{(perfect) matching} on \( [2n] \) is a set partition of \( [2n] \) such that
each block has size 2.
We also depict a matching on \( [2n] \) as a diagram consisting of \( 2n \)
vertices and \( n \) arcs where any pair of arcs has no common vertex.
A \emph{crossing} is a pair of arcs \( \{a,c\} \) and \( \{b,d\} \)
with \( a<b<c<d \).
A matching is called \emph{noncrossing} if the matching has no crossing,
and \emph{nonnesting} if there is no pair of arcs \( \{a,d\} \)
and \( \{b,c\} \) with \( a<b<c<d \).

For a matching $M$ and $\{i,j\}\in M$ with $i<j$, $i$ is called an
\emph{opener} and $j$ is called a \emph{closer}. 
Let \( \Mat_{2n} \) (\( \NC_{2n} \) and \( \NN_{2n} \), respectively) stand for
the set of (noncrossing and nonnesting, respectively) matchings on \( [2n] \).

Note that there is an obvious bijection between \( \SYT(n,n) \) and
\( \NN_{2n} \). For \( T\in\SYT(n,n) \), connect two vertices lying
on the same column of \( T \) via an arc, then we obtain a
nonnesting matching. 
Using this correspondence, we index the Specht basis for \( \Spec^{(n,n)} \)
by nonnesting matchings of \( [2n] \):
\[
  \{ v_M \in \Spec^{(n,n)} \mid M\in\NN_{2n} \}.
\]

We now consider the \( 2 \times 2n \) matrix
\[
  z = 
  \begin{bmatrix}
    z_{1,1} & z_{1,2} & \dots & z_{1,2n} \\
    z_{2,1} & z_{2,2} & \dots & z_{2,2n}
  \end{bmatrix},
\]
where \( z_{i,j} \)'s are indeterminates.
For \( 1\le i<j\le 2n \), let \( \Delta_{ij}:=\Delta_{ij}(z) \) be the maximal minor of \( z \) with respect to the \( i \)th and \( j \)th columns,
\textit{i.e.}, \( \Delta_{ij} = z_{1,i} z_{2,j} - z_{1,j} z_{2,i} \).
For a matching \( M\in\Mat_{2n} \), let
\[
\Delta_M := \Delta_M(z) = \prod_{\{i,j\}\in M} \Delta_{ij} \in \CC[z_{1,1},\dotsc,z_{2,2n}].
\]
It is important to note that the polynomials \( \Delta_{ij} \) satisfy the following relation:
For \( 1\le a<b<c<d \le 2n\),
\begin{equation} \label{eq:syzygy}
\Delta_{ac} \Delta_{bd}
  = \Delta_{ab} \Delta_{cd} + \Delta_{ad} \Delta_{bc}.
\end{equation}
We define a vector space \( W_n \) to be the \( \CC \)-span of \( \Delta_M \)
for all \( M\in\Mat_{2n} \).
In \cite{KR84}, it turns out that the set
\begin{equation} \label{eq:basis_NC}
\{ \Delta_{M}\in W_n \mid M\in\NC_{2n} \}
\end{equation}
forms a basis for \( W_n \). We call this basis the \emph{web basis}.

We are now in a position to give the main purpose of this article.
Let \( M_0 \) be the unique matching which is simultaneous noncrossing and
nonnesting, \textit{i.e.}, \( M_0 = \{ \{1,2\},\dotsc,\{2n-1,2n\} \} \).
Due to \cite{RT19}, the isomorphism maps \( \Delta_{M_0} \) to \( v_{M_0} \) up to scalar.
Let \( \varphi \colon W_n \rightarrow \Spec^{(n,n)} \) be the unique isomorphism
with \( \varphi(\Delta_{M_0}) = v_{M_0} \).
We also let \( w_M := \varphi(\Delta_M) \) for each \( M\in\NC_{2n} \).
Then the Specht basis can expand into (the image of) the web basis:
for \( M\in\NN_{2n} \),
\[
  v_M = \sum_{M'\in\NC_{2n}} a_{MM'} w_{M'}.
\]
In \cite{RT19}, Russell and Tymoczko initiated the combinatorial study of
the transition matrix
\[
  A = (a_{MM'})_{M\in\NN_{2n}, M'\in\NC_{2n}}.
\]
They showed the unitriangularity of the matrix.
They also gave some open problems related to their results.
One of them is for positivity of entries of \( A \),
and soon after, Rhoades proved the positivity.
\begin{thm}[\cite{Rho19}]
  The entries \( a_{MM'} \) of the transition matrix \( A \) are
  nonnegative integers.
\end{thm}
Although Rhoades established the positivity phenomenon for entries of \( A \),
he did not find an explicit combinatorial interpretation of the nonnegative integer \( a_{MM'} \), c.f. \cite[Problem 1.3]{Rho19}.
Inspired by his work, we introduce a new family of permutations which
are enumerated by the integers \( a_{MM'} \), and study their enumerative
properties.

Our strategy is based on Rhoades's observation~\cite{Rho19}.
He figured out that the entries \( a_{MM'} \) are related to resolving crossings
of matchings in the following sense:
For a matching \( M\in\Mat_{2n} \), let \( \{ a,c \} \) and \( \{ b,d \} \) be
a crossing pair in \( M \) (if it exists) where \( a<b<c<d \).
Let \( M' \) and \( M'' \) be the matchings identical to \( M \) except that
\( \{ a,b \} \) and \( \{ c,d \} \) in \( M' \), and
\( \{ a,d \} \) and \( \{ b,c \} \) in \( M'' \).
Then, by the relation \eqref{eq:syzygy}, we have
\begin{equation}\label{Eq: web relation}
\Delta_M = \Delta_{M'} + \Delta_{M''}.
\end{equation}
In addition, the number of crossing pairs in \( M' \) (respectively, \( M'' \)) is
strictly less than the number of crossing pairs in \( M \).
Therefore, iterating the resolving procedure gives the expansion of \( \Delta_M \)
in terms of the basis \eqref{eq:basis_NC}.
In other words, when we write 
\begin{equation} \label{eq: web expansion}
  \Delta_M = \sum_{M'\in\NC_{2n}}c_{MM'} \Delta_{M'},
\end{equation}
the coefficient \( c_{MM'} \) is equal to
the number of occurrences of the noncrossing matching \( M' \)
obtained from iterating resolving crossings in \( M \).
Note that the order of the choice of crossing pairs does not affect the expansion of \( \Delta_M \).
Rhoades showed that for \( M\in\NN_{2n} \) and \( M'\in\NC_{2n} \),
the entry \( a_{MM'} \) of the transition matrix equals \( c_{MM'} \).
Hence, to give a combinatorial interpretation of \( a_{MM'} \), we track
the resolving process from a nonnesting matching to noncrossing matchings.

To state our main result, we need some preliminaries. 
A \emph{Dyck path} of length \( 2n \)  is a lattice path from \( (0,0) \)
to \( (n,n) \) consisting of \( n \) north steps \( (1,0) \) and
\( n \) east steps \( (0,1) \) that does not pass below the line \( y=x \).
We write \( \NS \) and \( \ES \) for the north step and the east step,
respectively.
We therefore regard a Dyck path as a sequence of \( \{\NS, \ES\} \) consisting of
\( n \) \( \NS \)'s and \( n \) \( \ES \)'s.
Let \( \Dyck_{2n} \) be the set of Dyck paths of length \( 2n \).
Identifying a Dyck path with the area below the path,
we give a natural partial order on \( \Dyck_{2n} \) by inclusion,
denoted by \( \subseteq \).
In Section~\ref{sec:grid configuration}, we define a map
\( D \colon \Mat_{2n}\rightarrow \Dyck_{2n} \), and by abuse of notation,
a map \( D \colon \SYM_n\rightarrow \Dyck_{2n} \).
No confusion might be caused by this abuse.
We also define a map \( M \colon \SYM_n\rightarrow \NC_{2n} \).
Finally, we introduce a new family of permutations,
called \emph{web permutations}. With these data, we now present our main result.
\begin{thm} \label{thm:main_intro}
  For matchings \( M\in\NN_{2n} \) and \( M'\in\NC_{2n} \),
  the entry \( a_{MM'} \) is equal to the number of web permutations
  \( \sigma \) such that \( D(\sigma)\subseteq D(M) \) and \( M(\sigma)=M' \).
\end{thm}

The article is organized as follows.
In Section~\ref{sec:grid configuration}, we give a new model,
called a grid configuration, for representing matchings.
We then define web permutations from the noncrossing grid configurations,
and prove the main theorem.
In the next two sections, we study some properties of web permutations.
In Section~\ref{sec:characterization}, we give a characterization of
web permutations. We show that web permutations are closely related to
\andre permutations.
Section~\ref{sec:enumeration} provides some interesting enumerative properties
of web permutations.
We also give a conjecture for a relation between certain web permutations
and the Seidel triangle.

\section{Grid configurations and web permutations}
\label{sec:grid configuration}
In this section, we define grid configurations which represent matchings
in a `rigid' setting.
We describe the procedure of resolving crossings within this model.
We then introduce a new class of permutations, called web permutations.
This provides a combinatorial interpretation for the entries \( a_{MM'} \) of the transition
matrix.

Consider an $n$ by $n$ (lattice) grid in the $xy$-plane with corners
$(0,0), (0,n), (n,0)$ and $(n,n)$.
We denote each cell by $(i,j)$ where $i$ and $j$ are the $x$- and $y$-coordinates of its upper-right corner.
Let $\sigma\in\mathfrak{S}_n$ be a permutation. For each $1\le i\le n$, mark the cell \( (i,\sigma(i)) \),
and draw a horizontal line to the left and a vertical line to the top from the marked cell.
We call this the \emph{empty grid configuration} of \( \sigma \).
A cell $(i,j)$ is a \emph{crossing} if
there are both a vertical line and a horizontal line through the cell, 
that is, \( \sigma(i) < j \) and \( i < \sigma^{-1}(j) \).
We denote by \( \Cr(\sigma) \) the set of all crossings of \( \sigma \).
For a subset \( E\subseteq\Cr(\sigma) \),
the \emph{grid configuration} \( G(\sigma,E) \) of a pair \( (\sigma, E) \) is defined to be
the empty grid configuration of \( \sigma \) where each crossing in \( E \)
is replaced by an elbow as shown in Figure~\ref{fig:A crossing to an elbow}.
In particular, the empty grid
configuration of \( \sigma \) is \( G(\sigma,\emptyset) \).
\begin{figure}
  \centering
  \begin{tikzpicture}[scale=1]
  \draw[black!20] (0,0) grid (1,1);
  \Cross{1}{1}
  \node[text width=0.5cm] at (1.5, 0.5) {$\rightarrow$};
  \draw[black!20] (2,0) grid (3,1);
  \Asmooth{3}{1}
  \end{tikzpicture}
  \caption{A crossing to an elbow.}
  \label{fig:A crossing to an elbow}
\end{figure}

For the \( n \) by \( n \) grid configuration, we label leftmost vertical intervals
from bottom to top with 1 through $n$ and uppermost horizontal intervals
from left to right with $n+1$ through $2n$.
With this label of boundary intervals, a grid configuration can be considered
as a matching on \( [2n] \) as follows:
Each strand joining $i$th and $j$th boundary intervals represents
an arc connecting $i$ and $j$;
see Figure~\ref{Fig: The grid configuration G(1324, (1,3),(1,4))}.
We denote by $M(\sigma,E)$ the matching associated to the grid configuration
\( G(\sigma,E) \). For short, we write \( M(\sigma) = M(\sigma, \Cr(\sigma)) \).

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=0.7]
      \node[left] at (0,-1.5) {1};
  \node[left] at (0,-0.5) {2};
  \node[left] at (0,0.5) {3};
  \node[left] at (0,1.5) {4};
  \node[above] at (0.5,2) {5};
  \node[above] at (1.5,2) {6};
  \node[above] at (2.5,2) {7};
  \node[above] at (3.5,2) {8};
  \draw[black!20] (0,-2) grid (4,2);
  \Xmarking{4}{2}\Xmarking{2}{1}\Xmarking{3}{0}\Xmarking{1}{-1}

  \Cross{1}{0}\Cross{2}{2}
  \UP{3}{1}
  \EAST{2}{0}
  \Asmooth{1}{2} \Asmooth{1}{1}
  \Cross{3}{2}

  \Matching{6}{8}\Matching{7}{12}\Matching{9}{11}\Matching{10}{13}
  
  \foreach \i in {1,...,8}{
    \draw [fill] (\i+5,0) circle [radius=0.05] ;
    \node[below] at(\i+5,0) {\i};
  }
  \end{tikzpicture}
  \caption{The grid configuration $G(1324,\{(1,3),(1,4)\})$ and the corresponding matching.}
  \label{Fig: The grid configuration G(1324, (1,3),(1,4))}
\end{figure}

We define a partial order on cells of the $n$ by $n$ grid
by $(x,y)\succ (x',y')$ if either $x<x'$ and $y\ge y'$, or $x=x'$ and $y>y'$.

The relation~\eqref{Eq: web relation} can be interpreted as a relation between grid configurations as follows.
For a permutation \( \sigma \) and \( E\subseteq\Cr(\sigma) \),
let $G(\sigma,E)$ be the grid configuration and $c=(i,j)$ be a maximal crossing in $G(\sigma,E)$.
One way of resolving $c$ results a grid configuration $G(\sigma, E\cup \{c\})$.
This procedure of resolving a crossing is called \emph{smoothing}.
The other way of resolving $c$ results a grid configuration $G(\sigma', E)$,
where $\sigma'$ is defined by 
%\[
  \begin{align*}
  \sigma'(i)&=j,\\
  \sigma'(\sigma^{-1}(j))&=\sigma(i), \text{ and}\\
  \sigma'(k)&=\sigma(k) \text{ for } k\neq i,\sigma^{-1}(j).
  \end{align*}
%\]
This procedure of resolving a crossing is called \emph{switching}.
Note that the crossing sets $\Cr(\sigma)$ and $\Cr(\sigma')$ are not the same. 
Nevertheless, by choosing $c$ to be maximal, crossings not smaller than $c$
(with respect to the partial order) are left unchanged under switching.
In particular, we have \( E\subseteq \Cr(\sigma') \), so switching is well-defined.
We often consider a grid configuration $G$ as the vector $\Delta_{M(G)}$.
Therefore, we can write the relation \eqref{Eq: web relation}
in terms of grid configurations as
\[
  G(\sigma,E)=G(\sigma,E\cup\{c\})+G(\sigma',E).
\]

From the grid configuration $G(id, \emptyset)$, we obtain two grid
configurations by resolving a crossing by smoothing and switching, respectively.
By resolving crossings until there is no crossing left,
we get grid configurations of the form $G(\sigma, \Cr(\sigma))$.
For each remaining grid configuration $G(\sigma, \Cr(\sigma))$,
the permutation $\sigma$ is called a \emph{web permutation} of $[n]$ and
we denote the set of web permutations of $[n]$ by $\Web_n$.
In other words, we have
\begin{equation}\label{Equation: empty grid=sum of grid}
  G(id, \emptyset) = \sum G(\sigma, \Cr(\sigma)),
\end{equation}
where the right hand side is the sum of all grid configurations obtained
by resolving crossings from the grid configuration \( G(id,\emptyset) \)
until there is no crossing left.
This is reminiscent of \eqref{eq: web expansion}.
For example, starting from the grid configuration $G(id,\emptyset)$ for $n=3$,
we have 
\begin{align*}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{1}\Xmarking{2}{2}\Xmarking{3}{3}
        \Cross{1}{2}\Cross{1}{3}\Cross{2}{3}
            \node[circle, fill=red, draw=red, scale=0.3] at (0.5,2.5) {};
    \end{tikzpicture}
  &\begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$=$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{1}\Xmarking{2}{2}\Xmarking{3}{3}
        \Cross{1}{2}\Asmooth{1}{3}\Cross{2}{3}
            \node[circle, fill=red, draw=red, scale=0.3] at (1.5,2.5) {};
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{3}\Xmarking{2}{2}\Xmarking{3}{1}
        \UP{2}{3}\EAST{1}{2}\UP{3}{2}\UP{3}{3}\EAST{1}{1}\EAST{2}{1}
    \end{tikzpicture}\\
    &\begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$=$};
        \end{tikzpicture}\begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{1}\Xmarking{2}{2}\Xmarking{3}{3}
        \Cross{1}{2}\Asmooth{1}{3}\Asmooth{2}{3}
            \node[circle, fill=red, draw=red, scale=0.3] at (0.5,1.5) {};
    \end{tikzpicture}
        \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
            \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{1}\Xmarking{2}{3}\Xmarking{3}{2}
        \Cross{1}{2}\Asmooth{1}{3}\EAST{2}{2}\UP{3}{3}
                    \node[circle, fill=red, draw=red, scale=0.3] at (0.5,1.5) {};
    \end{tikzpicture}
        \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{3}\Xmarking{2}{2}\Xmarking{3}{1}
        \UP{2}{3}\EAST{1}{2}\UP{3}{2}\UP{3}{3}\EAST{1}{1}\EAST{2}{1}
    \end{tikzpicture}\\
    &\begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$=$};
        \end{tikzpicture}    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{1}\Xmarking{2}{2}\Xmarking{3}{3}
        \Asmooth{1}{2}\Asmooth{1}{3}\Asmooth{2}{3}
    \end{tikzpicture}
        \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{2}\Xmarking{2}{1}\Xmarking{3}{3}
        \Asmooth{1}{3}\Asmooth{2}{3}
        \EAST{1}{1}\UP{2}{2}
    \end{tikzpicture}
        \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{1}\Xmarking{2}{3}\Xmarking{3}{2}
        \Asmooth{1}{2}\Asmooth{1}{3}\EAST{2}{2}\UP{3}{3}
    \end{tikzpicture}
        \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{2}\Xmarking{2}{3}\Xmarking{3}{1}
        \Asmooth{1}{3}\EAST{2}{1}\EAST{1}{1}\UP{3}{3}\UP{3}{2}
    \end{tikzpicture}
        \begin{tikzpicture}[scale=0.5]
        \draw[white!20] (0,0) grid (1,3);
        \node[text width=0.5cm] at (0.5, 1.5) {$+$};
        \end{tikzpicture}
    \begin{tikzpicture}[scale=0.5]
        \draw[black!20] (0,0) grid (3,3);
        \Xmarking{1}{3}\Xmarking{2}{2}\Xmarking{3}{1}
        \UP{2}{3}\EAST{1}{2}\UP{3}{2}\UP{3}{3}\EAST{1}{1}\EAST{2}{1}
    \end{tikzpicture}.  
  \end{align*}
Therefore we conclude that $\Web_3=\{123, 213, 132, 231, 321\}$.
The following proposition justifies that web permutations are well-defined. 

\begin{prop} \label{prop:well-def}
  The expansion in \eqref{Equation: empty grid=sum of grid} is unique.
  In other words, the grid configurations appearing in
  \eqref{Equation: empty grid=sum of grid} does not depend on
  the order of resolving procedure (choice of maximal crossings).
  In addition, the permutations $\sigma$ in
  \eqref{Equation: empty grid=sum of grid} are all distinct. 
\end{prop}

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=0.7]
    \draw[black!20] (0,0) grid (5,5);
    \OnlyXmarking{1}{2}\OnlyXmarking{2}{1}\OnlyXmarking{3}{3}\OnlyXmarking{4}{5}\OnlyXmarking{5}{4}
    \draw[line width=0.5mm,blue] (0,0)--(0,2);
    \draw[line width=0.5mm,blue] (0,2)--(2,2);
    \draw[line width=0.5mm,blue] (2,2)--(2,3);
    \draw[line width=0.5mm,blue] (2,3)--(3,3);
    \draw[line width=0.5mm,blue] (3,3)--(3,5);
    \draw[line width=0.5mm,blue] (3,5)--(5,5);
  \end{tikzpicture}
  \caption{The Dyck path \( D(\sigma) \) associated to \( \sigma=21354 \) is
  \( \NS\NS\ES\ES\NS\ES\NS\NS\ES\ES \).}
  \label{fig:D_sigma}
\end{figure}

For a matching $M$, record $\NS$ for openers and $\ES$ for closers reading $M$
from left to right.
This gives the Dyck path $D(M)$ in the $n$ by $n$ grid.
It is known that the two restrictions of the map
\( D \colon \Mat_{2n}\rightarrow \Dyck_{2n} \) to \( \NC_{2n} \) and \( \NN_{2n} \)
are bijections.
To a permutation $\sigma$, we associate the minimum Dyck path \( D(\sigma) \)
where every cell \( (i,\sigma(i)) \) lies below the path;
see Figure~\ref{fig:D_sigma}.

Given a nonnesting matching \( M\in\NN_{2n} \), let \( E(M) \) be the set of
cells in the $n$ by $n$ grid which are above the path $D(M)$.
It is easy to see that the matchings \( M \) and $M(id, E(M))$ coincide.

Similarly to the definition of \( \Web_n \), we consider the equation
\[
  G(id,E(M)) = \sum G(\sigma,\Cr(\sigma)),
\]
where the right hand side is the summation of grid configurations obtained by resolving
crossings in \( G(id,E(M)) \) until there is no crossing.
We then define \( \Web_M \) to be
the set of permutations \( \sigma \) appearing in the right hand side of the above equation.
In particular, \( \Web_n = \Web_M \) where
\( M=\{ \{1,n+1\}, \{2,n+2\},\dotsc, \{n,2n\} \}. \)

Using the above notations, we prove one of our main results that tells us which
web permutations contribute to the entry $a_{MM'}$.
\begin{proof}[Proof of Thereom~\ref{thm:main_intro}]
  By the definition of web permutations, we have 
  \begin{align*}
    a_{MM'} = | \{ \sigma\in \Web_M : M(\sigma) = M' \} |.
  \end{align*}
  Hence it is enough to show that
  \begin{equation}\label{eq:web(M)}
    \Web_M = \{ \sigma\in \Web_n : D(\sigma)\subseteq D(M) \}.
  \end{equation}
  We can obtain the grid configuration \( G(id,E(M)) \) from \( G(id,\emptyset) \) by smoothing crossings in \( E(M) \).
  Since Proposition~\ref{prop:well-def} says that \( \Web_n \) does not depend on the order of resolving processes, we obtain \( \Web_M \subseteq \Web_n \).
  From this, it is clear that
  \begin{align*}
    \Web_M &= \{ \sigma\in \Web_n : E(M)\subseteq \Cr(\sigma)\}  \\
    &= \{ \sigma\in \Web_n : (i,\sigma(i)) \not\in E(M) \mbox{ for all } i \},
  \end{align*}
  which proves the claim \eqref{eq:web(M)}.
\end{proof}

\section{Characterization of web permutations}
\label{sec:characterization}
In this section, we provide a characterization of web permutations.
This characterization depends only on their permutation structure.
Using this characterization, we also prove the results in \cite{IZ21,RT19}.

We begin with recalling two ways to represent permutations.
One way is the \emph{one-line notation} which we have already used,
that is regarding a permutation as a word.
More precisely, for a permutation \( \sigma \colon [n]\rightarrow[n] \),
we write \( \sigma =  \sigma_1 \sigma_2 \dots \sigma_n \)
where \( \sigma_i = \sigma(i) \).
Another way to write permutations is the \emph{cycle notation}.
We give an example;
for the definition, see \cite{Sta12}.
Let \( \sigma = 564132\in\SYM_6 \), then the cycle notation of \( \sigma \) is \( (1,5,3,4)(2,6) \).
We always use parentheses and commas for writing cycles.

To describe our characterization of web permutations, we review the notion of
Andr\'e permutations and define an analogue of them.
We now think of permutations as words consisting of distinct positive integers.
\emph{Andr\'e permutations} are defined recursively as follows.
First, the empty word and each one-letter word are Andr\'e permutations.
For a permutation \( w=w_1 w_2 \cdots w_n \) with \( n\ge 2 \), 
let \( w_k \) be the smallest letter in \( w \). Then \( w \) is an Andr\'e
permutation if both \( w_1 \cdots w_{k-1} \) and \( w_{k+1}\cdots w_{n} \) are 
Andr\'e permutations and \( \max\{w_1,\dotsc,w_{k-1}\} < \max\{w_{k+1},\dotsc,w_n\} \).
Using this notion, we define a cycle analogue of Andr\'e permutations.
\begin{defn} \label{def:Andre cycle}
  Let \( C=(a_1,\dotsc,a_k) \) be a cycle with \( a_1 = \min \{a_1,\dotsc,a_k\} \).
  We say that \( C \) is an \emph{Andr\'e cycle}
  if the permutation \( a_2\cdots a_k \) is an Andr\'e permutation.
\end{defn}

For a cycle \( C=(a_1,\dotsc,a_k) \), we write \( \min C = \min \{a_1,\dotsc,a_k\} \)
and write \( \max C = \max \{a_1,\dotsc,a_k\}\) for short.
The following lemma gives how to obtain a new Andr\'e cycle from old Andr\'e cycles.
\begin{lem} \label{lem:merging}
  Let \( C_1=(a_1,\dotsc,a_k) \) and \( C_2=(b_1,\dotsc,b_\ell) \) be Andr\'e cycles with
  \( a_1 = \min C_1 \) and \( b_1=\min C_2 \).
  If \( a_1<b_1 \) and \( a_k<b_\ell \), then the cycle \( (a_1,\dotsc,a_k, b_1,\dotsc,b_\ell) \) is also an Andr\'e cycle.
\end{lem}


We now show another main result of the article,
which gives a characterization of web permutations.
\begin{thm} \label{thm:web=andre_cycle}
  A permutation \( \sigma \in \SYM_n \) is a web permutation
  if and only if each cycle of \( \sigma \) is an Andr\'e cycle.
\end{thm}


As an application of the characterization, we show that the transition matrix
\( (a_{MM'}) \) is unitriangular with respect to a certain order on \( \NN_{2n} \)
and \( \NC_{2n} \), and determine which entries \( a_{MM'} \) vanish.
These are already known due to Russell--Tymoczko~\cite{RT19} and
Im--Zhu~\cite{IZ21}.

Before we give the vanishing condition,
we first show that the set \( \Web_n \) includes a well-studied class of permutations.
For a permutation \( \sigma = \sigma_1\cdots \sigma_n \),
we say that \emph{\( \sigma \) contains a 312-pattern} if there exist three indices
\( 1\le i<j<k\le n \) such that \( \sigma_j<\sigma_k<\sigma_i \).
A permutation is \emph{312-avoiding} if it does not contain a 312-pattern.
Note that 312-avoiding permutations are a Catalan object. Furthermore,
the restriction of \( D \colon \SYM_n\rightarrow \Dyck_{2n} \) to the set of
312-avoiding permutations of \( [n] \) is a bijection.
\begin{cor}\label{cor:312-avoiding}
  A 312-avoiding permutation is a web permutation.
\end{cor}


Recall that the set \( \Dyck_{2n} \) has a partial order \( \subseteq \),
and there are bijections \( D \) from \( \NN_{2n} \) and from \( \NC_{2n} \) to
\( \Dyck_{2n} \).
Then the maps \( D \) induce a partial order on \( \NN_{2n} \) and \( \NC_{2n} \).
Furthermore, when we choose a total order on \( \Dyck_{2n} \) that completes
the partial order \( \subseteq \), the maps \( D \) give a total order
on \( \NN_{2n} \) and \( \NC_{2n} \).


We now take a total order on \( \Dyck_{2n} \) which completes the partial order
\( \subseteq \), and thus we have the induced total order on
\( \NN_{2n} \) and \( \NC_{2n} \).
We assume that orderings of rows and columns of the transition matrix
\( (a_{MM'}) \) are the decreasing orders with respect to the total order
on \( \NN_{2n} \) and \( \NC_{2n} \).
Then the entry \( a_{MM'} \) is on the diagonal if and only if \( D(M)=D(M') \).

We are now ready to prove the unitriangularity of the transition matrix
$(a_{MM'})$ and the conjecture of Russell and Tymoczko
\cite[Conjecture 5.8]{RT19} concerning the condition of the vanishing entries,
which is later proved by Im and Zhu \cite[Theorem 1.1]{IZ21}.

\begin{cor}[{\cite{IZ21,RT19}}]\label{Cor: unitriangularity}
  Let \( M\in\NN_{2n} \) and \( M'\in\NC_{2n} \).
  Then \( a_{MM'} > 0 \) if and only if \( D(M') \subseteq D(M) \).
  In particular, the transition matrix $(a_{MM'})$ is upper-triangular.
  Moreover, there are ones along the diagonal of the transition matrix,
  and 312-avoiding permutations contribute to the ones.
\end{cor}



\section{Enumeration of web permutations}
\label{sec:enumeration}
In this section, we focus on the number of web permutations. 
We also conjecture that the Seidel triangle can be recovered completely from
the certain classes of web permutations.

We now present another relationship between web permutations and Andr\'e cycles.
Let us first review the Foata transformation \( \widehat{~~} \colon \SYM_n\rightarrow\SYM_n \).
For a permutation $\sigma\in\SYM_n$, the \emph{canonical} cycle notation
of \( \sigma \) is a cycle notation of \( \sigma \) such that its cycles are
sorted based on the smallest element of the cycles and
the smallest element of each cycle is written in the last place of the cycle.
We define \( \widehat{\sigma} \) to be the permutation obtained by dropping 
the parentheses in the canonical cycle notation of \( \sigma \).
A \emph{right-to-left minimum} is an element \( \sigma_i \) such that
\( \sigma_i < \sigma_j \) for all \( j>i \).
Using right-to-left minima of \( \sigma \), one can easily construct the inverse
of the Foata transformation.
Note that the number of cycles of \( \sigma \) equals the number of right-to-left minima of \( \widehat{\sigma} \).

We now introduce a map $\phi \colon \SYM_n \rightarrow \SYM_{n+2}$ as
a slightly modification of the Foata transformation.
For a permutation $\sigma \in \SYM_n$,
define the one-cycle permutation $\phi(\sigma) \in\SYM_{n+2}$ by
\[
  \phi(\sigma):=(1,\widehat{\sigma}_1 +1, \dots, \widehat{\sigma}_n+1, n+2).
\]
It follows immediately from the bijectivity of the Foata transformation
that the map \( \phi \) is injective, and its image \( \phi(\SYM_n) \) is the
set of one-cycle permutations \( \sigma\in\SYM_{n+2} \) with \( \sigma(n+2)=1 \).

The following theorem gives a relation between web permutations and
Andr\'e cycles,
and show that the numbers of web permutations equal Euler numbers.

\begin{thm}\label{thm:webn=Andren+2}
  For \( n\ge 1 \), let \( \AC_{n+2}\subset\SYM_{n+2} \) be the set of
  Andr\'e cycles consisting of \( [n+2] \).
  Then we have \( \phi(\Web_n) = \AC_{n+2} \).
  In particular, the number of web permutations of \( [n] \) is equal to
  the number of Andr\'e cycles consisting of \( [n+2] \).
\end{thm}


\subsection{Euler and Entringer numbers}
In this subsections, we give various enumerative properties of
web permutations using Theorem~\ref{thm:webn=Andren+2}.
We start with recalling Euler numbers.
The \emph{Euler numbers} \( E_n \) are defined via the exponential
generating function \(E(z) := \sum_{n\ge 0} E_n \frac{x^n}{n!} = \sec z + \tan z\).
There are numerous combinatorial objects enumerated by Euler numbers \( E_n \).
Especially, the Euler number \( E_n \) counts Andr\'e permutations of \( [n] \).
For details, see \cite{Sta10}.
We provide another occurrence of Euler numbers.

\begin{cor}
  The Euler number \( E_{n+1} \) enumerates
  the number of web permutations of \( [n] \).
\end{cor}
\begin{proof}
  By definition, the number of Andr\'e permutations of \( [n] \) is equal to
  the number of Andr\'e cycles of \( [n+1] \).
  Then Theorem~\ref{thm:webn=Andren+2} implies the desired result.
\end{proof}

For a permutation \( \sigma \), let \( \cc(\sigma) \) be the number of cycles of
\( \sigma \), and \( \rlmin(\sigma) \) the number of right-to-left minima of
\( \sigma \).
By convention, we set \( \cc(\emptyset) = 0 \) where \( \emptyset \) is
the empty permutation, and \( \Web_0=\{\emptyset\}. \)
We have the following corollary
concerning the distribution of \( \cc(\sigma) \) on \( \Web_n \).
\begin{cor} 
  We have
  \begin{align*}
    \left( \frac{1}{1-\sin z} \right)^t =
      \sum_{n\ge 0} \sum_{\sigma\in \Web_n} t^{\cc(\sigma)} \frac{z^{n}}{n!}.
  \end{align*}
\end{cor}
\begin{proof} 
  In \cite[Proposition~1]{Dis13}, the author showed that 
  \begin{align*}
    \left( \frac{1}{1-\sin z} \right)^t = \sum_{n\ge 1}\sum_{\sigma}
    t^{\rlmin(\sigma)-1} \frac{z^{n-1}}{(n-1)! }
  \end{align*}
  where the inner sum is over all \andre permutations of \( [n] \).
  Therefore the proof follows immediately from Theorem~\ref{thm:webn=Andren+2}.
\end{proof}

We also recall Entringer numbers.
The \emph{Entringer} numbers are given by
the generating function
\[
  \frac{\cos x + \sin x}{\cos (x+y)} = \sum_{m,n \ge 0} E_{m+n,[m,n]} \frac{x^m}{m!} \frac{y^n}{n!},
\]
where \( [m,n] \) is \( m \) if \( m+n \) is odd, and \( n \) otherwise.
We have a counterpart of this refinement.
\begin{cor} 
  The Entringer number \( E_{n,k} \) is equal to the number of web permutations \( \sigma \) of \( [n] \) with \( \sigma_1 = n+1-k \).
\end{cor}
\begin{proof} 
  In \cite[Theorem~1.1]{FH16}, the authors showed that \( E_{n,k} \) equals the
  number of \andre permutations \( \sigma \) of \( [n+1] \) with
  \( \sigma_1 = n+1-k \).
  Combining this fact and Theorem~\ref{thm:webn=Andren+2} gives the proof.
\end{proof}


\subsection{Genocchi numbers and the Seidel triangle}
The Genocchi numbers are well-studied numbers with various combinatorial properties; see \cite{Dum74, LW20}. The Genocchi numbers can be defined
by the \emph{Seidel triangle} as follows \cite{Sei77}.
Recall that the Seidel triangle is an array of integers $(s_{i,j})_{i,j\ge1}$
such that $s_{1,1}=s_{2,1}=1$,
\[
  %\begin{cases}
    s_{2i+1,j} = s_{2i+1,j-1} + s_{2i,j} \mbox{ for } j=1,\dotsc, i+1,
    \text{ and }
    s_{2i,j} = s_{2i,j+1} + s_{2i-1,j} \mbox{ for } j=i,i-1,\dotsc,1,
  %\end{cases}
\]
where $s_{i,j}=0$ for $j<0$ or $j>\lceil i/2\rceil$.
This Pascal type procedure is called the \emph{boustrophedon algorithm}.
The \emph{Genocchi numbers} $g_n$ are defined by
\[
  g_{2n-1}=s_{2n-1,n} \qand g_{2n}=s_{2n,1}.
\]


Recall that we denote by \( M_0 \) for the unique matching which
is simultaneous noncrossing and nonnesting, \textit{i.e.},
\( M_0 = \{ \{1,2\},\dotsc,\{2n-1,2n\} \} \).
To emphasize the size of the matchings, we denote this unique matching of $[2n]$
by $M^{(n)}_0$. Let $f(n)$ be the number of web permutations $\sigma$ of $[n]$
with $M(\sigma)=M^{(n)}_0$.
In \cite{Nak20}, Nakamigawa showed the following theorem.
\begin{thm}[{\cite[Theorem 3.1]{Nak20}}] \label{thm:Geno}
  For \( n\ge 1 \), we have \( f(n)=g_n \).
\end{thm}
Let $f(n,k)$ be the number of web permutations $\sigma$ of $[n]$ such that
\( M(\sigma) = M^{(n)}_0 \) and $\sigma_1=k$.
Obviously, \( f(n)=\sum_{1\le k\le n} f(n,k) \).
Some of these numbers vanish in the following cases.
\begin{prop}\label{prop:web-Genocchi even k=0}
  For $n\ge1$ and $1\le k \le \lfloor n/2\rfloor$, we have $f(n,2k)=0$.  
\end{prop}
\begin{proof}
  Let $\sigma$ be a web permutation of $[n]$ with $\sigma_1=2k$.
  Then considering the grid configuration \( G(\sigma,\Cr(\sigma)) \),
  the associated matching $M(\sigma)$ has an arc connecting $2k$
  and some $j$ with $2k<j$. Since there is the arc connecting $2k-1$ and $2k$
  in $M^{(n)}_0$, we deduce $M(\sigma)\neq M^{(n)}_0$.
\end{proof}

\begin{prop}\label{prop:web-Genocchi odd n,n=0}
  For an odd $n>1$, we have $f(n,n)=0$. 
\end{prop}
\begin{proof}
  Let $\sigma$ be a web permutation of $[n]$ with $\sigma_1=n$.
  To obtain $\sigma$ from the grid configuration $G(id, \emptyset)$,
  the first crossing (at the cell $(1,n)$) should be resolved by switching.
  Then we have two markings at $(1,n)$ and $(n,1)$.
  Observe that the vertical line and horizontal starting from
  the cell $(n,1)$ cannot contain a crossing.
  Therefore, in the procedure of resolving crossings, the markings $(1,n)$
  and $(n,1)$ remains the same. Thus we have $\sigma_n=1$
  and $\{1,2n\}\in M(\sigma)$, which implies that $M(\sigma)\neq M^{(n)}_0$.
\end{proof}

By Propositions~\ref{prop:web-Genocchi even k=0} and \ref{prop:web-Genocchi odd n,n=0}, we have
\(f(n)=\sum_{1\le k \le \lfloor n/2 \rfloor}f(n,2k-1)\).
We now propose a conjecture that the values appearing in the Seidel triangle are $f(n,k)$.
\begin{conj}[Verified up to \( n=6 \)] \label{Conj: Genocchi}
  For \( n\ge 1 \), we have
  \[
    \begin{cases}
      f(2n-1,2k-1)= s_{2n-2, k},\\
      f(2n, 2k-1) = s_{2n-1, n-k+1}.
    \end{cases}
  \]
\end{conj}
This conjecture includes Nakamigawa's result. To elaborate, let \( \sigma \) be a
web permutation of \( [n] \) such that \( M(\sigma)=M^{(n)}_0 \) and
\( \sigma_1 = 1 \). Deleting the cycle \( (1) \) from \( \sigma \) and decreasing
each letter by 1, the resulting permutation is a web permutation of
\( [n-1] \) with \( M(\sigma)=M^{(n-1)}_0 \).
In addition, this correspondence is bijective, so we deduce \( f(n,1) = f(n-1) \).
Thus the conjecture implies Nakamigawa's result \( f(n-1) = g_{n-1} \).


\acknowledgements{The authors are grateful to Jang Soo Kim for several suggestions which improved the manuscript.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
