\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* 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***] (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}
**