\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{enumerate}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\usepackage{tikz-dependency}
\usepackage{tikz}

\hyphenation{Richard}
\hyphenation{Ehrenborg}
\hyphenation{Hetyei}
\hyphenation{Margaret}
\hyphenation{Readdy}

\newcommand{\orange}[1]{\marginpar{\textcolor{orange}{\tiny #1}}}

\newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}}

\newenvironment{proof_qed}{\noindent {\bf Proof:}}
                          {\vspace{-2mm}}
\newenvironment{proof_}[1]{\noindent {\bf #1}}
                          {{\qed}}


\newcommand{\SSSS}{{\mathfrak S}}

\newcommand{\Ppp}{{\mathbb P}}
\newcommand{\Rrr}{{\mathbb R}}
\newcommand{\Zzz}{{\mathbb Z}}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\DP}{DP}
\DeclareMathOperator{\SP}{SP}
\DeclareMathOperator{\Head}{Head}
\DeclareMathOperator{\Tail}{Tail}
\DeclareMathOperator{\tw}{tw}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf A Bijective Answer to a Question of Simion}
\vskip 1cm
\Large
Richard Ehrenborg\\
Department of Mathematics \\
University of Kentucky\\
Lexington, KY 40506-0027\\
USA \\
\href{mailto:richard.ehrenborg@uky.edu}{\tt richard.ehrenborg@uky.edu} \\
\ \\
G\'abor Hetyei\\
Department of Mathematics and Statistics \\
UNC-Charlotte\\
Charlotte, NC 28223-0001\\
USA \\
\href{mailto:ghetyei@uncc.edu}{\tt ghetyei@uncc.edu}\\
\ \\
Margaret Readdy\\
Department of Mathematics \\
University of Kentucky\\
Lexington, KY 40506-0027\\
USA \\
\href{mailto:margaret.readdy@uky.edu}{\tt margaret.readdy@uky.edu}
\end{center}

\newpage

\begin{abstract}
We present a bijection between balanced Delannoy paths of length~$2n$ and
the faces of the $n$-dimensional Simion type~$B$ associahedron.
This polytope is also known as the Bott-Taubes polytope and the cyclohedron.
This bijection takes a path with $k$ up steps (and $k$ down steps) to a 
$(k-1)$-dimensional face of the Simion type~$B$ associahedron.
We give two presentations of this bijection, one recursive and
one non-recursive.
\end{abstract}


\section{Introduction}

Simion constructed a type $B$ associahedron $Q^{B}_{n}$
whose facets correspond to centrally symmetric triangulations of a
regular $(2n+2)$-gon; see~\cite{Simion}.
The vertices correspond to $B$-diagonals,
that is, pairs of diagonals that are centrally symmetric.
This polytope
is also known as
the Bott-Taubes polytope~\cite{Bott_Taubes}
and
the cyclohedron~\cite{Stasheff}.
We follow Simion's convention and view this polytope $Q^{B}_{n}$
as a simplicial polytope.

Simion observed that 
the number of $(k-1)$-dimensional
faces of
the type~$B$ associahedron is
given by 
\begin{equation}
f_{k-1}(Q^{B}_{n})
=
\binom{n}{k}
\cdot
\binom{n+k}{k} .
\label{equation_face_numbers}
\end{equation}
Simion asked if there is a combinatorial proof of this identity.
A combinatorial interpretation for the right-hand side of
equation~\eqref{equation_face_numbers}
is 
the number of lattices paths
between $(0,0)$ and $(2n,0)$ taking 
$k$ up steps $(1,1)$,
$k$ down steps $(1,-1)$,
and
$n-k$ horizontal steps $(2,0)$.
Such paths are known as {\em balanced Delannoy paths}.
We provide a bijection between the faces
of the type~$B$ associahedron
and balanced Delannoy paths.

Our approach is based upon the
paper~\cite{Ehrenborg_Hetyei_Readdy},
where the Simion type $B$ associahedron $Q^{B}_{n}$
is shown to be a pulling triangulation of the
Legendre polytope.
This polytope, also known as the full type $A$ root polytope,
is the convex hull of the set
$\{e_{i} - e_{j} \: : \: 1 \leq i, j \leq n+1, i \neq j \}$.
Hence it is natural to encode the vertices
of the polytope $Q^{B}_{n}$
with the pairs $(i,j)$ where $i,j \in \{1,2, \ldots, n+1\}$ and $i \neq j$.
We view these pairs as directed edges on the vertex set
$\{1,2, \ldots, n+1\}$.
We call these directed edges {\em arrows}
to be consistent with~\cite{Ehrenborg_Hetyei_Readdy}
and not to overuse the term edge.
Thus a face of the 
type~$B$ associahedron~$Q^{B}_{n}$
corresponds to a digraph
on the vertex set~$\{1,2, \ldots, n+1\}$.


In the paper~\cite{Ehrenborg_Hetyei_Readdy}
a condition is given on pairs of arrows when
their associated $B$-diagonals cross.
Reformulating this condition
yields a description
of those digraphs that correspond to faces
of $Q^{B}_{n}$;
see 
Proposition~\ref{proposition_facial_digraphs}.
We call these digraphs {\em facial}.

After preliminaries,
in Section~\ref{section_bijection} we
give a bijection between paths that never go
below the $x$-axis, known as Schr\"oder paths,
and facial digraphs with the
extra condition that all the arrows are directed
backwards. Next, we extend this bijection to all digraphs
and facial digraphs.
This presentation of the bijection
is recursive.
In Section~\ref{section_non-recursive_description}
we reformulate this presentation
to obtain a non-recursive description
of the bijection.
Lastly, we end with concluding remarks.


\section{Preliminaries}
\label{section_preliminaries}

\subsection{The Simion type \texorpdfstring{$B$}{B} associahedron}

Following Simion~\cite{Simion}, for a centrally symmetric convex $(2n+2)$-gon
label its vertices in the clockwise
order with $1$, $2$, \ldots, $n$, $n+1$, $\overline{1}$, $\overline{2}$,
\ldots, $\overline{n}$,  $\overline{n+1}$. 
Let~$\Gamma_{n}^{B}$ denote the simplicial complex whose  
$n \cdot (n+1)$ vertices arise from the $B$-diagonals of the
$(2n+2)$-gon, that is,
(i)~diagonals joining antipodal pairs of points, and
(ii)~antipodal pairs of noncrossing diagonals. 
In the first case, the diagonals are pairs of the form
$\{i,\overline{i}\}$ satisfying $1\leq i\leq n+1$.
In the second case, the $B$-diagonals
are either of the form
$\{\{i,j\},\{\overline{i},\overline{j}\}\}$ with $1\leq
i<i+1<j\leq n+1$ or of the form $\{\{i,\overline{j}\}, 
\{\overline{i},j\}\}$ with $1\leq j< i\leq n+1$.
Throughout the paper we identify~$\overline{i}$ with $i+n+1$.
The simplicial complex~$\Gamma_{n}^{B}$ is then the family of sets of pairwise
noncrossing $B$-diagonals. 


Simion~\cite[Theorem 1]{Simion}
showed that the
simplicial complex $\Gamma_{n}^{B}$ is the boundary complex of an
$n$-dimensional convex polytope $Q_{n}^{B}$, now known as
the {\em Simion type $B$ associahedron}. 
See  Proposition~1
and Corollary~1 in~\cite{Simion}
for Simion's computation of the $f$- and $h$-vectors
of this polytope.


\newcommand{\Bpoint}[2]
{({#2*sin((#1-1)*360/22)}, {#2*cos((#1-1)*360/22)})}
\newcommand{\Bdiagonal}[2]
{\draw[line width=0.3mm] \Bpoint{#1}{3} --\Bpoint{#2}{3};
\draw[line width=0.3mm] \Bpoint{#1+11}{3} --\Bpoint{#2+11}{3};}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\draw(0,0) circle (3);
\foreach \i in {0,1, ..., 21}
{\draw \Bpoint{\i}{3} -- \Bpoint{\i}{3.2};};
\foreach \i in {1,2, ..., 11}
{\draw \Bpoint{\i}{3.45} node {$\i$};};
\foreach \i in {1,2, ..., 11}
{\draw \Bpoint{\i+11}{3.45} node {$\overline{\i}$};};
\Bdiagonal{1}{4}
\Bdiagonal{8}{15}
\Bdiagonal{9}{15}
\Bdiagonal{5}{16}
\Bdiagonal{7}{16}
\Bdiagonal{5}{7}
\Bdiagonal{9}{11}
\Bdiagonal{9}{12}
\end{tikzpicture}
\end{center}
\caption{A set of $B$-diagonals corresponding to a $7$-dimensional
face of  $Q^{B}_{10}$.}
\label{figure_one}
\end{figure}






We define an {\em arrow} to be pair $(i,j)$ where $1 \leq i, j \leq n+1$
and $i \neq j$. 
We call $i$ the {\em tail} of the arrow~$(i,j)$
and
$j$ the {\em head} of the arrow.
An arrow $(i,j)$ is a {\em forward arrow} if $i < j$
and
a {\em backward arrow} if $i > j$.
Two undirected arcs
$\{a,b\}$ and $\{c,d\}$ {\em cross}
if $a < c < b < d$ or $c < a < d < b$
where we assume $a<b$ and $c<d$.
Furthermore, the arc~$\{a,b\}$ {\em nests} the arc $\{c,d\}$
if $a < c < d < b$
where we again assume $a<b$ and $c<d$.
These two concepts naturally lift to arrows.



Define a bijection between $B$-diagonals and
arrows as follows.

\begin{definition}
For a $B$-diagonal $\{\{u,v\}, \{u+n+1, v+n+1\}\}$
where $1 \leq u \leq n+1$, $u < v \leq u+n+1$
and the addition $v+n+1$ is modulo $2n+2$,
let the associated arrow be
$(w,u)$ where
$w \equiv v-1 \bmod n+1$
and
$1 \leq w \leq n+1$.
The case of two antipodal points is covered when $v = u+n+1$.
The resulting arrow is $(u-1,u)$ when $2 \leq u \leq n+1$ and the arrow is
$(n+1,1)$ when $u=1$.
\label{definition_B-diagonal_arrow}
\end{definition}





From the proof of Proposition~5.5 in~\cite{Ehrenborg_Hetyei_Readdy},
we have the following result.

\begin{proposition}
A non-empty digraph on the node set $\{1,2, \ldots, n+1\}$
represents a proper face of
the Simion type~$B$ associahedron~$Q_{n}^{B}$
exactly when the following conditions are satisfied:
\vspace*{-4 mm}
\begin{enumerate}[(1)]
\item There are no crossings between arrows.
\item Forward arrows nest.
\item A backward arrow cannot nest a forward arrow.
\item No head of an arrow is the tail of another arrow.  
\end{enumerate}  
\vspace*{-4 mm}
\label{proposition_facial_digraphs}
\end{proposition}  
We call such a set of arrows a {\em facial} digraph.
An example of a facial digraph is shown in Figure~\ref{figure_facial}.


Let $P$ be a polytope with a vertex $v$.
We can {\em pull} the vertex $v$, that is, we consider
the convex hull of the polytope $P$ and a new point $w$,
where $\stackrel{\longrightarrow}{vw}$ is a small vector in general position pointing 
outwards from the polytope.
Given a polytope $P$ and an ordering of its
vertices $v_{1}, v_{2}, \ldots, v_{m}$, we can pull
all the vertices in this given order.
Namely, pick a real number $0 < \epsilon < 1$.
When pulling the $i$th vertex, pull it 
a distance of $\epsilon^{i}$.
The resulting polytope $Q$ is simplicial, that is,
the boundary of $Q$ is a triangulation
of the boundary of the polytope $P$.
Furthermore, the combinatorics of $Q$ only depends on
the original polytope~$P$ and the pulling order of the vertices.
The idea of pulling triangulation is due to
Hudson~\cite[Lemma~1.4]{Hudson}.
See
Athanasiadis~\cite[End of Section~2]{Athanasiadis},
Hetyei~\cite[Section~2.3]{Hetyei_Legendre}
and Stanley~\cite[Lemma~1.1]{Stanley_decompositions},
for modern treatments,
as well as
the book by de Loera, Rambau, and Santos~\cite{deLoera_Rambau_Santos}
for other types of triangulations.



We identify the arrow $(i,j)$ with the point $e_{j}-e_{i}$ in
$(n+1)$-dimensional Euclidean space. The convex hull
of these $n \cdot (n+1)$ points forms a convex polytope
known as the {\em Legendre polytope}~\cite{Hetyei_Legendre}.
This polytope is also known as the full root polytope of type $A$;
see~\cite{Ardila_Beck_Hosten_Pfeifle_Seashore,Cho}.
Hetyei proved that any pulling triangulation of the Legendre
polytope yields a simplicial polytope whose
$f$-vector is given by~\eqref{equation_face_numbers};
see~\cite{Hetyei_Legendre}.
In the paper~\cite{Ehrenborg_Hetyei_Readdy}
the authors show that there is a pulling triangulation
of Legendre polytope such that the resulting polytope
is the Simion type $B$ associahedron.
Proposition~\ref{proposition_facial_digraphs}
arises from understanding this pulling triangulation.




\section{A bijection between the faces of
  \texorpdfstring{$\Gamma_{n}^{B}$}{GnB} and Delannoy paths} 
\label{section_bijection}

In this section we establish a bijection between
the faces of $\Gamma_{n}^{B}$ and
balanced Delannoy paths of length $2n$ in such a way that
$(k-1)$-dimensional faces correspond to Delannoy paths with $k$
up steps, thus answering Simion's question.
The study of Delannoy paths has a long history.
See~\cite{Banderier_Schwer}
for a comprehensive survey.

\begin{definition}
A {\em balanced Delannoy path} of length $2n$ is a lattice path starting at $(0,0)$,
ending at $(2n,0)$
and using only steps of the following three types:
up steps $(1,1)$,
down steps $(1,-1)$
and horizontal steps $(2,0)$. 
A {\em Schr\"oder path} is a balanced Delannoy path that
never goes below the horizontal axis.   
\label{definition_Delannoy_Schroder}
\end{definition}
More generally, a {\em Delannoy path} is a path taking the steps
$(1,1)$, $(1,-1)$ and $(2,0)$ with no condition where the path ends.
In this paper we only work with balanced Delannoy paths.




Let $U$, $D$ and $H$
denote the up, down and horizontal steps, respectively.
Let the {\em length} of the
letters $U$ and $D$ each to be $1$, whereas the length of the letter 
$H$ be $2$.
Note that the length of a word is the sum of the lengths of its letters.
For example, the word
$DUUHH$ has length $7$.
A Delannoy path is uniquely encoded by a word
in these three letters.
We call the associated word a {\em Delannoy word}.
A balanced Delannoy path of length $2n$
corresponds to a word
in which the number $k$ of occurrences of $U$ is the
same as the number of occurrences of $D$,
and the number of occurrences of~$H$ is $n-k$.
We call such a word {\em balanced}.
Hence the number of Delannoy paths of length $2n$ with $k$ up steps is
given by the multinomial coefficient
$\binom{n+k}{k, k, n-k} = \binom{n+k}{k}\binom{n}{k}$,
which is
the same as the number of $(k-1)$-dimensional faces in
the Simion type~$B$ associahedron $Q_{n}^{B}$;
see equation~\eqref{equation_face_numbers}.
A {\em Schr\"oder word} is a balanced Delannoy word
such that the associated path never goes below the horizontal axis.   
Let~$\alpha \cdot \beta$ denote the concatenation of
the two words $\alpha$ and~$\beta$.


Let $\Ppp$ be the set of positive integers ordered by the natural order.  
We will consider facial digraphs~$A$ on a finite subset $V$ of the positive integers.
Recall that the definition of a facial digraph is the conditions appearing in
Proposition~\ref{proposition_facial_digraphs}.
We view a digraph $A$
as a pair consisting of a node set $V=V(A)$ and an arrow set $E=E(A)$.
For a facial digraph $A$ 
on a non-empty finite set of nodes $V$
and $W \subseteq V$ let~$A_{W}$ denote the
induced subgraph on $W$.




\newcommand{\backwardarrow}[2]
{\node[anchor=east] at #1 (text) {};
\node[anchor=west] at #2 (description) {};
\draw[line width=0.3mm] (description) edge[out=135,in=45,->] (text);}

\newcommand{\forwardarrow}[2]
{\node[anchor=east] at #1 (text) {};
\node[anchor=west] at #2 (description) {};
\draw[line width=0.3mm] (description) edge[out=135,in=45,<-] (text);}

\begin{figure}[t]
\begin{center}
\begin{tikzpicture}
\foreach \x in {1,...,11}
\node at (\x,0) {\small $\x$};

\backwardarrow{(1+0.1,0.1)}{(3-0.1,0.1)}
\backwardarrow{(5+0.1,0.1)}{(6-0.1,0.1)}
\backwardarrow{(9+0.1,0.1)}{(10-0.1,0.1)}
\backwardarrow{(9+0.1,0.3)}{(11-0.1,0.3)}

\forwardarrow{(3+0.1,0.1)}{(8-0.1,0.1)}
\forwardarrow{(3+0.1,0.2)}{(9-0.1,0.2)}
\forwardarrow{(4+0.1,0.1)}{(5-0.1,0.1)}
\forwardarrow{(4+0.1,0.2)}{(7-0.1,0.2)}

\end{tikzpicture}
\end{center}
\caption{The facial digraph 
corresponding to the set of $B$-diagonals in Figure~\ref{figure_one}.}
\label{figure_facial}
\end{figure}


Let $A$ be a facial digraph of backward arrows
on a non-empty finite set of nodes $V \subseteq \Ppp$
and let~$v$ be the minimal element of $V$. 
We define the {\em Schr\"oder word} $\SP(A)$
of the facial digraph $A$
by the following recursive definition.
\begin{itemize}
\item[(i)] If the set $V$ only consists of one node,
that is, $V = \{v\}$, let $\SP(A)$ be the empty word~$\epsilon$.
\item[(ii)]
If the minimal node $v$ is an isolated node of $A$, let 
$\SP(A)$ be the concatenation
$H \cdot \SP(A_{V-\{v\}})$.
\item[(iii)]
Lastly, when the node $v$ is not isolated then since $v$ is the
least element, there is necessarily a backward
arrow $(x,v)$ going into $v$. Let $w$ be the smallest node
such that $(w,v)$ is an arrow of $A$, that is,
$w = \min(\{x \in V \: : \: (x,v) \in A\})$.
Define $\SP(A)$ by
$$    
\SP(A)
=
U \cdot
\SP(A_{V \cap (v,w]})
\cdot D \cdot
\SP(A_{V - (v,w]}) .
$$
\end{itemize}

\begin{lemma}
Let $A$ be a facial digraph on a set of nodes of size $n+1$
consisting of exactly $k$ backward arrows.
The Schr\"oder word $\SP(A)$ then has length $2n$
and has exactly $k$ copies of the letters $U$ and $k$ copies of the letters $D$.
\label{lemma_easy_observation}
\end{lemma}
\begin{proof}
Both statements follow by induction on $n$.   
The first statement follows from the fact that
the two sets of nodes
$V \cap (v,w]$ and $V - (v,w]$
are complements of each other.
The second statement follows
by observing that the noncrossing property ensures that each arrow in $A$
is either the arrow~$(w,v)$,
an arrow in $A_{V \cap (v,w]}$,
or an arrow in $A_{V - (v,w]}$.
\end{proof}



\begin{proposition}
The map $\SP$ is a bijection between
the set of all facial digraphs consisting only of backward arrows
on the set of $n+1$ nodes and all Schr\"oder words of length $2n$. 
\label{proposition_backwards}
\end{proposition}
\begin{proof}
Given a Schr\"oder word $\alpha$ of length $2n$
and a node set 
$V = \{v_{1} < v_{2} < \cdots < v_{n+1}\}$,
the inverse map is computed recursively as follows.
If $\alpha$ is the empty word~$\epsilon$ then
the inverse image is the isolated node~$v_{1}$.
If the word $\alpha$ begins with $H$, that is,
$\alpha = H \cdot \beta$ where $\beta$ has length $2n-2$,
compute the inverse image of $\beta$ on the nodes
$\{v_{2},v_{3}, \ldots, v_{n+1}\}$
and add the node $v_{1}$ as an isolated node.
Otherwise factor $\alpha$ uniquely as
$U \cdot \beta \cdot D \cdot \gamma$,
where $\beta$ and~$\gamma$ are
Schr\"oder words of lengths $2p$ and $2n-2p-2$,
respectively.
Compute the inverse image of $\beta$
on the nodes $\{v_{2},v_{3}, \ldots, v_{p+2}\}$.
Similarly, compute the inverse image of $\gamma$ on the nodes
$\{v_{1}, v_{p+3}, v_{p+4}, \ldots, v_{n+1}\}$. Take the union of these
two digraphs and add the backward arrow~$(v_{p+2},v_{1})$.
\end{proof}



We now extend the bijection $\SP$ to all facial digraphs.
In order to do so we introduce a
{\em twisting operation $\tw$}
on each digraph $A$ that has a forward arrow from the least element
$v \in V$ to the largest element $w \in V$. The {\em twisted digraph}
$\tw(A)$ is a digraph on the node set $V - \{v\}$ with arrow set
$$
E(\tw(A))
=
E(A_{V - \{v\}})
\:
\cup
\:
\{(w,z) \: : \: (v,z) \in A, z \neq w\}.
$$
In other words, we remove the least node $v$ and replace each forward
arrow $(v,z)$ starting at $v$ with a backward arrow $(w,z)$.
Note that
there is no backward arrow $(z,v)$ in $A$ as $v$ is the tail of 
the forward arrow $(v,w)$.
\begin{lemma}
Let $V$ be a node set whose smallest (respectively, largest) node is $v$
(respectively, $w$).
The twisting map is a bijection from the set of facial digraphs on the set $V$
containing the forward arrow $(v,w)$ to the set of facial digraphs on
the set $V - \{v\}$.
\label{lemma_twisting}
\end{lemma}
\begin{proof}
We claim that the twisted digraph $\tw(A)$ is a facial digraph.
Note that the restriction~$A_{V - \{v\}}$ is a facial digraph.
If there are no forward arrows in $A$ of the form $(v,z)$ where $z < w$,
the equality $\tw(A) = A_{V - \{v\}}$ holds and the claim is true.
Hence assume that there are forward arrows of the form~$(v,z)$.
We need to show that the digraph remains facial after adding the
backward arrow $(w,z)$.
We verify conditions (1) through (4) of
Proposition~\ref{proposition_facial_digraphs}
in order.
If the arrow $(w,z)$ crosses an arrow~$(x,y)$
then the arrow~$(v,z)$ already crossed this arrow in $A$,
verifying condition~(1).
Since we did not introduce any new forward arrows, 
condition~(2) holds vacuously.
Assume that the backward arrow~$(w,z)$ nests a forward arrow $(x,y)$.
Then the forward arrows $(v,z)$ and $(x,y)$ did not nest in $A$,
verifying~(3). Condition~(4) holds directly, proving the claim.

The twisting map is one-to-one. The inverse has 
the node set $V(\tw^{-1}(B)) = V(B) \cup \{v\}$ and
the arrow set is given by
$$
E(\tw^{-1}(B))
=
\{(v,w)\}
\:
\cup
\:
E(B_{V \cap (v,w)})
\:
\cup
\:
\{(v,z) \: : \: (w,z) \in B\} ,
$$
where $V \cap (v,w)$ denotes the intersection
of the set $V$ with the open interval $(v,w)$.
Note that in case the node $w$ was a `tail node',
the inverse map switches it back to being a `head node'.
\end{proof}







We now extend the bijection $\SP$ to a map $\DP$
which applies to all facial digraphs.
Let $A$ be facial digraph on the node set $V$.
Furthermore, let $v$ and $w$ be the minimal, respectively, the
maximal node of the node set~$V$,
that is,
$v = \min(V)$ and $w = \max(V)$.


\begin{itemize}
\item[(i)]
If the facial digraph $A$ has no forward arrows,
let $\DP(A) = \SP(A)$.

\item[(ii)]
If the facial digraph $A$ has a forward arrow,
let $(x,y)$ be the forward arrow which nests the other forward arrows.
Since $v \leq x < y \leq w$,
observe that the digraphs
$A_{V \cap [v,x]}$ and $A_{V \cap [y,w]}$
have no forward arrows.
Define $\DP(A)$ to be the concatenation
$$
\DP(A)
=
\SP(A_{V \cap [v,x]})
\cdot D \cdot  
\DP(\tw(A_{V \cap [x,y]}))
\cdot U \cdot  
\SP(A_{V \cap [y,w]}) .
$$
\end{itemize}
As an extension of Lemma~\ref{lemma_easy_observation}
we have the following lemma.
\begin{lemma}
Let $A$ be a facial digraph on a set $V$ of $n+1$ nodes
and assume that $A$ consists of $k$ arrows.
Then the balanced Delannoy word $\DP(A)$ has length $2 n$
and has exactly $k$ copies of the letters~$U$ and~$D$, respectively.
\end{lemma}
\begin{proof}
We only have to prove the lemma for the second case defining $\DP$.
Assume that
$V \cap [v,x]$ and $V \cap [y,w]$
have cardinalities $a$ and $b$, respectively.
Then the middle part
$V \cap [x,y]$ has size $n-a-b+3$.
Thus 
$\tw(A_{V \cap [x,y]})$ has $n-a-b+2$ nodes.
Hence the total length is
$2 \cdot (a-1) + 2 \cdot (n-a-b+1) + 2 \cdot (b-1) + 2 = 2 n$.
For the second case of the lemma, assume that the restricted digraphs
$A_{V \cap [v,x]}$ and $A_{V \cap [y,w]}$
have $c$ and $d$ arrows, respectively.
Since there is no arrow nesting the forward arrow~$(x,y)$,
the middle digraph $A_{V \cap [x,y]}$ has $k-c-d$ arrows.
Thus the twisted digraph has one less arrow,
namely $k-c-d-1$.
Hence the total number of $U$ letters
is $c + (k-c-d-1) + d + 1 = k$, proving the second claim.
\end{proof}

We now extend Proposition~\ref{proposition_backwards}
to all facial digraphs.
\begin{theorem}
The map $\DP$ is a bijection between
the set of all facial digraphs 
on a set of $n+1$ nodes and the set of all balanced Delannoy words of
length $2n$.
\label{theorem_forwards_and_backwards}
\end{theorem}
\begin{proof}
The inverse of the map $\DP$ is computed as follows.
Let $\alpha$ be a balanced Delannoy word of length $2n$
and $V$ be a node set $\{v_{1} < v_{2} < \cdots < v_{n+1}\}$.
If the Delannoy word $\alpha$ is a Schr\"oder word, apply the inverse map of
Proposition~\ref{proposition_backwards}.
Otherwise, we can factor the Delannoy word $\alpha$ uniquely 
as $\beta \cdot D \cdot \gamma \cdot U \cdot \delta$,
where $\gamma$ is a balanced Delannoy word,
and $\beta$ and~$\delta$ are Schr\"oder words.
Note that the factor $\beta \cdot D$ is uniquely
determined by the fact it is the shortest initial
segment in which the number of $D$ letters exceeds the number of $U$ letters,
in other words, the encoded path ends with the first down
step going below the horizontal axis.
By a symmetric argument, 
$U \cdot \delta$ is the shortest final segment with
one more~$U$ than the number of~$D$'s.
Assume that $\beta$, $\gamma$ and
$\delta$ have lengths $2p$, $2q$ and~$2n-2p-2q-2$, respectively.
Apply the inverse map from the proof of
Proposition~\ref{proposition_backwards}
to the words $\beta$ and $\delta$
to obtain
digraphs on $\{v_{1},v_{2}, \ldots, v_{p-1}\}$,
respectively
$\{v_{p+q+2}, v_{p+q+3}, \ldots, v_{n+1}\}$.



By recursion, apply the inverse of $\DP$ to $\gamma$ to obtain a facial
digraph on the node set $\{v_{p+2}, v_{p+3}, \ldots$, $v_{p+q+2}\}$.
Then apply the inverse of the twisting map to the digraph thus
obtained. Finally, take the union of these three digraphs.
\end{proof}

\begin{figure}[t]
\begin{center}
\begin{tikzpicture}
\foreach \x in {1,...,11}
\node at (\x,0) {\small $\x$};

\backwardarrow{(1+0.1,0.1)}{(3-0.1,0.1)}
\backwardarrow{(5+0.1,0.1)}{(6-0.1,0.1)}
\backwardarrow{(5+0.1,0.3)}{(7-0.1,0.3)}
\backwardarrow{(8+0.1,0.1)}{(9-0.1,0.1)}
\backwardarrow{(9+0.1,0.1)}{(10-0.1,0.1)}
\backwardarrow{(9+0.1,0.3)}{(11-0.1,0.3)}

\end{tikzpicture}
\end{center}
\caption{The modified set of arrows obtained from the set in
  Figure~\ref{figure_facial}.}
\label{figure_twisted}
\end{figure}



\section{A non-recursive description of the bijection}
\label{section_non-recursive_description}

We now give non-recursive description of the bijection $\DP$.
First we encode a facial digraph with a multiset of
indexed letters.
\begin{definition}
\label{definition_multiset}  
Given a facial digraph $A$ on the node set $V$,
define the {\em associated multiset $M(A)$}
with elements from the set of indexed letters
$\{D_{x}, U_{x}, H_{x} \: : \: x \in \Ppp\}$
by the following three steps:
\begin{enumerate}
\item
For each $x < \max(V)$ which is a maximum element in
a weakly connected component 
we add the letter $H_{x}$ 
to the multiset $M(A)$.

   
\item
For each tail $x$ of a forward arrow,
consider the set
$\Head(x)=\{y>x \: : \: (x,y)\in A\}$, that is, the set of
heads of forward arrows with tail $x$.
Add a copy of the letter~$D_{x}$ to~$M(A)$,
also add a copy of the letter~$U_{w}$ for
$w=\max(\Head(x))$.
Remove the forward arrow~$(x,w)$.
For each remaining $y \in \Head(x)$ that is less than
$w$, replace the forward arrow $(x,y)$ with the backward arrow
$(w,y)$. The resulting set of arrows has only backward arrows.  

\item
For each head $y$ of a backward arrow,
consider the set
$\Tail(y) = \{x>y \: : \: (x,y) \in A\}$,
that is, the set of
tails of backward arrows with head $y$.
Add a copy of $U_{y}$ to~$M(A)$.
Also add a copy of $D_{x}$ for $x \in \Tail(y)$
and add a copy of $U_{x}$ for
all but the maximum element of $\Tail(y)$.
\end{enumerate}
\end{definition}  


\begin{example}
{\rm
For the facial set of arrows $A$ shown in
Figure~\ref{figure_facial},
in the first step we add the letters $H_{2}$ and $H_{7}$ to $M(A)$.
In the second step we add the letters
$D_{3}$, $U_{9}$, $D_{4}$, and~$U_{7}$ to~$M(A)$,
and we remove the forward arrows $(3,9)$ and $(4,7)$.
We also replace $(3,8)$ with~$(9,8)$ and $(4,5)$ with $(7,5)$. 
We obtain the set of backward arrows shown in
Figure~\ref{figure_twisted}.
Note that this set of arrows does not need to be
facial anymore: in our example, $9$ is the head of $(10,9)$ and $(11,9)$
and it is also the tail of $(9,8)$. 
Finally, in step three we add the letters
$U_{1}$, $D_{3}$, $U_{5}$, $D_{6}$,
$U_{6}$, $D_{7}$, $U_{8}$, $D_{9}$,
$U_{9}$, $D_{10}$, $U_{10}$, and $D_{11}$ to~$M(A)$. 
We end up with the multiset
$$
M(A)=
\{
U_{1},
H_{2},
D_{3},
D_{3}, 
D_{4},
U_{5}, 
D_{6},
U_{6}, 
D_{7}, 
U_{7}, 
H_{7},
U_{8}, 
D_{9},
U_{9},
U_{9}, 
D_{10}, 
U_{10}, 
D_{11}
\} .
$$
}
\end{example}
Define a linear order on the
indexed letters by the inequalities
$D_{x} < U_{x} < H_{x} < D_{x+1}$
for all positive integers $x$.
We obtain the lattice path as follows.
\begin{proposition}
The balanced Delannoy word $\DP(A)$ is
obtained from the multiset $M(A)$ by reading the
indexed letters in order and then omitting the subscripts.
\label{proposition_bijection_explicit}
\end{proposition}
For the set of arrows shown in Figure~\ref{figure_facial}, we
obtain the word
$$UHDDDUDUDUHUDUUDUD.$$
The lattice path encoded by this
word is shown in Figure~\ref{figure_lattice_path}. 
\begin{figure}[t]
\begin{center}  
\begin{tikzpicture}
\draw (-5,0) node (v1) {} -- (-4.5,0.5) -- (-3.5,0.5) -- (-3,0) -- (-2.5,-0.5) -- (-2,-1) -- (-1.5,-0.5) -- (-1,-1) -- (-0.5,-0.5) -- (0,-1) -- (0.5,-0.5) -- (1.5,-0.5) -- (2,0) -- (2.5,-0.5) -- (3,0) -- (3.5,0.5) -- (4,0) -- (4.5,0.5) -- (5,0) node (v2) {};
\draw [dashed] (v1) edge (v2);
\node at (-5,-0.2) {(0,0)};
\node at (-3,-0.5) {(4,0)};
\node at (3.2,-0.3) {(16,0)};
\node at (5,-0.2) {(20,0)};
\end{tikzpicture}
\end{center}
\caption{The lattice path associated to the digraph
in Figure~\ref{figure_facial}.}
\label{figure_lattice_path}
\end{figure}

Recall that a {\em weakly connected component} of a digraph
is a connected component in the graph obtained by
disregarding the direction of the arrows.
In our facial digraphs, the weakly connected components are trees. 

A quick outline of a proof of
Proposition~\ref{proposition_bijection_explicit}
is as follows.
First prove the statement for facial digraphs without forward arrows.
In this case, each nonmaximal element $x$ of $\Tail(y)$
contributes two consecutive letters $D_{x} U_{y}$.
Next, observe that
a digraph and its twisted digraph have
the same weakly connected components.
Furthermore, the arrows that moved under the
twisted operation still have the same set of heads.
Hence, after recording the horizontal steps in step~(1)
we may perform all twisting operations simultaneously
in step~(2).
We leave the remaining details to the reader.


\section{Concluding remarks}

The faces of the type $B$ associahedron $Q^{B}_{n}$
have a natural order by inclusion. What is the image of this order
under our bijection? Is there a different ordering of the balanced 
Delannoy paths that would yield a more natural order preserving bijection?



\section{Acknowledgments}

We would like to thank the referee for helping substantially
improve the presentation.
The first and third author thank the Institute for Advanced Study in
Princeton, New Jersey,
for a research visit in Summer 2018.
This work was partially supported by grants from the
Simons Foundation
(\#429370 to Richard~Ehrenborg,
\#245153 and \#514648 to G\'abor~Hetyei, \#206001 and \#422467 to
Margaret~Readdy). 

\newcommand{\journal}[6]{ #1, #2, \emph{#3} {\bf #4} (#5), #6.}
\newcommand{\book}[4]{ #1, \emph{#2}, #3, #4.}
\newcommand{\bookf}[5]{ #1, \emph{#2}, #3, #4, #5.}


\begin{thebibliography}{99}

\bibitem{Ardila_Beck_Hosten_Pfeifle_Seashore}
\journal{F.\ Ardila, M.\ Beck, S.\ Ho\c{s}ten,
             J.\ Pfeifle, and K.\ Seashore}
         {Root polytopes and growth series of root lattices}
         {SIAM J.\ Discrete Math.}
         {25}{2011}{360--378} 
 
\bibitem{Athanasiadis}
\journal{C.\ Athanasiadis}
         {$h^*$-vectors, Eulerian polynomials
          and stable polytopes of graphs}
         {Electron.\ J.\ Combin.}
         {11 (2)}{2004}{Paper R6}

\bibitem{Banderier_Schwer}
\journal{C.\ Banderier and S.\ Schwer}
            {Why Delannoy numbers?}
            {J.\ Statist.\ Plan.\ Inference}
            {135}{2005}{40--54}

\bibitem{Bott_Taubes}
\journal{R.\ Bott and C.\ Taubes}
            {On the self-linking of knots. Topology and physics}
            {J.\ Math.\ Phys.}
            {35}{1994}{5247--5287}

\bibitem{Cho}
\journal{S.\ Cho}
           {Polytopes of roots of type $A_n$}
           {Bull.\ Austral.\ Math.\ Soc.}
           {59}{1999}{391--402}
         
\bibitem{deLoera_Rambau_Santos}
\bookf{J.\ A.\ de Loera, J.\ Rambau, and F.\ Santos}
          {Triangulations: Structures for Algorithms and Applications}
          {Algorithms Comput.\ Math.\ vol.\ 25}
          {Springer-Verlag}
          {2010} 

\bibitem{Ehrenborg_Hetyei_Readdy}
\journal{R.\ Ehrenborg, G.\ Hetyei, and M.\ Readdy}
            {Simion's type $B$ associahedron is a pulling triangulation
             of the Legendre polytope}
            {Discrete Comput.\ Geom.}
            {60}{2018}{98--114}

\bibitem{Hetyei_Legendre}
\journal{G.\ Hetyei}
           {Delannoy orthants of Legendre polytopes}
           {Discrete Comput.\ Geom.}
           {42}{2009}{705--721} 

\bibitem{Hudson}
J.\ F.\ P.\ Hudson,
{\it Piecewise Linear Topology},
W.\ A.\ Benjamin, Inc., 1969.

\bibitem{Simion}
\journal{R.\ Simion}
            {A type-B associahedron}
            {Adv.\ in Appl.\ Math.} 
            {30}{2003}{2--25}

\bibitem{Stanley_decompositions}
\journal{R.\ P.\ Stanley}
             {Decompositions of rational convex polytopes}
             {Ann.\ Discrete Math.}
             {6}{1980}{333--342}            
            
\bibitem{Stasheff}
\journal{J.\ Stasheff}
            {From operads to ``physically'' inspired theories}
            {Contemp.\ Math.}
            {202}{1997}{53--81}
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 52B05; Secondary 05A15, 05E45, 52B12. 


\noindent \emph{Keywords: } Delannoy number, type $B$ associahedron,
Bott-Taubes polytope, Schr\"oder path, $f$-vector.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A006318},
\seqnum{A008288},
\seqnum{A008459}, and
\seqnum{A063007}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 26 2018;
revised versions received  October 15 2018; December 13 2018.
Published in {\it Journal of Integer Sequences}, December 18 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}