\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}
%\usepackage[notref,notcite]{showkeys} %this shows labels
\usepackage{graphicx}
\usepackage{mathrsfs}  
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\def\beq*{\begin{eqnarray*}}
\def\eeq*{\end{eqnarray*}}
\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\b{\beta}
\def\hb{\widehat{\beta}}
\def\a{\alpha}
\def\ha{\widehat{\alpha}}
\def\hn{\widehat{n}}
\def\hj{\widehat{j}}
\def\hl{\widehat{l}}
\def\hk{\widehat{k}}
\def\haa{\widehat{a}}
\def\hbb{\widehat{b}}
\def\mcP{\mathcal{P}}
\def\mcT{\mathcal{T}}
\def\mcB{\mathcal{B}}
\def\mcS{\mathcal{S}}
\def\n{\noindent}
\def\mbP{\mathbb{P}}
\def\mbE{\mathbb{E}}
\def\mcF{\mathcal{F}}
\def\mcX{\mathcal{X}}
\def\Bin{\operatorname{Bin}}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\newtheorem{case}{Case}
\newtheorem{subcase}{Case}
\numberwithin{subcase}{case}

\title{\bf Corners in Tree--Like Tableaux}


\author{Pawe{\l} Hitczenko\thanks{Partially supported by a grant from 
Simons Foundation (grant \#208766 to Pawe{\l} Hitczenko).}\\
\small Department of Mathematics\\[-0.8ex]
\small Drexel University\\[-0.8ex] 
\small Philadelphia, PA, U.S.A.\\
\small\tt phitczenko@math.drexel.edu\\
\and
Amanda Lohss \\
\small Department of Mathematics\\[-0.8ex]
\small Drexel University\\[-0.8ex] 
\small Philadelphia, PA, U.S.A.\\
\small\tt agp47@drexel.edu\\
}


%FIXXX
\date{\dateline{Nov 17, 2015}{Oct 18, 2016}\\ \small Mathematics Subject Classifications: 05A05, 05A15, 60C05, 60F05}








%\keywords{Tree--like tableaux, permutation tableaux, type--B permutation tableaux}
%\subjclass[2010]{05A05, 05A15, 60C05, 60F05}


\begin{document}

\maketitle

\begin{abstract}
In this paper, we study tree--like tableaux, combinatorial objects which exhibit a natural tree structure and are connected to the partially asymmetric simple exclusion process (PASEP). There was a conjecture made on the total number of corners in tree--like tableaux and the total number of corners in symmetric tree--like tableaux. In this paper, we prove both conjectures. Our proofs are based on the bijection with permutation tableaux or type--B permutation tableaux and consequently, we also prove results for these tableaux.  In addition, we derive the limiting distribution of the number of occupied corners in random tree--like tableaux and random symmetric tree--like tableaux. 

\bigskip\noindent \textbf{Keywords:} tree--like tableaux, permutation tableaux, type--B permutation 

\hspace{1.5cm} tableaux
\end{abstract}

\section{Introduction}
Tree--like tableaux are relatively new objects which were introduced in \cite{ABN}. They are in bijection with permutation tableaux and alternative tableaux but are interesting in their own right as they exhibit a natural tree structure (see \cite{ABN}). They also provide another avenue in which to study the partially asymmetric simple exclusion process (PASEP), an important model from statistical mechanics. See \cite{ABN} and \cite{LZ} for more details on the connection between tree--like tableaux and the PASEP. See also \cite{BUR}, \cite{CN},  \cite{CW4}, \cite{CW3}, \cite{PN}, \cite{SW} and \cite{XV} for more details on permutation and alternative tableaux. 

In the original paper \cite{ABN}, an insertion procedure was introduced which defines a correspondence between tree--like tableaux of size $n$ and tree--like tableaux of size $n+1$ (\cite[Definition 2.2]{ABN}). This correspondence has been the main tool in working with tree--like tableaux. Relevant to this paper, the number of occupied corners in tree--like tableaux and the number of occupied corners in symmetric tree--like tableaux were computed in \cite{LZ} (see Section~\ref{sec:prel} for definitions). In addition, it was conjectured (see Conjectures 4.1 and 4.2 in \cite{LZ}) that the total number of corners in tree--like tableaux of size $n$ is $n!\times\frac{n+4}{6}$ and the total number of corners in symmetric tree--like tableaux of size $2n+1$ is $2^n\times n!\times\frac{4n+13}{12}$.

In this paper, we prove both conjectures.  Our proofs are based on the bijection with permutation tableaux or type--B permutation tableaux and consequently, we also prove results for these tableaux (see Theorems~\ref{thm:exp-c} and~\ref{cornersTB} below for precise statements). It should be noted that Gao et al. were able to prove independently the conjectures for tree--like tableaux using a different method (see \cite[Theorem 4.1]{GGZS} and \cite[Theorem 4.3]{GGZS}).

In addition, we derive the limiting distribution of the number of occupied corners in random tree--like tableaux and random symmetric tree--like tableaux. Laborde Zubieta \cite{LZ} showed  that on average a tree--like tableau has one occupied corner (regardless of the size of the tableau). He also showed that the variance of the number of occupied corners in a random tree--like tableau of size $n$ is $1-2/n$ and obtained similar results for symmetric tree--like tableaux. This suggests that the asymptotic distribution of the number of occupied corners of either type of tableaux is Poisson and 
 we prove that this is, indeed, the case. 

The rest of the paper is organized as follows. In the next section we introduce  the necessary definitions and  notation. Sections~\ref{seccorners}  and ~\ref{sec:symtab} contain the proofs of the conjectures for the tree--like tableaux, and the symmetric tree--like tableaux, respectively. Finally, in Section~\ref{sec:occor}  we present our results on the limiting distributions of the number of occupied corners in tree--like and symmetric tree--like tableaux.

 

\section{Preliminaries}\label{sec:prel}
A {\it Ferrers diagram}, $F$, is a left--aligned sequence of cells with weakly decreasing rows. The {\it half--perimeter} of $F$ is the number of rows plus the number of columns. 
The {\it border edges} of a Ferrers diagram are the edges of the southeast border, and the number of border edges is equal to the half--perimeter. We will occasionally refer to a border edge as a step (south or west). A {\it shifted Ferrers diagram} is a diagram obtained from a Ferrers diagram with $k$ columns by adding $k$ rows above it of lengths $k,(k-1),\dots,1$, respectively. The half--perimeter of the shifted Ferrers diagram is the same as the original Ferrers diagram (and similarly, the border edges are the same).  The right--most cells of added rows are called {\it diagonal cells}. 

Let us recall the following two definitions introduced in \cite{ABN} and \cite{SW}, respectively.
 \begin{definition}\label{T}
A tree--like tableau of size $n$ is a Ferrers diagram of half-perimeter $n+1$ with some cells (called pointed cells) filled with a point according to the following rules:
\begin{enumerate}
\item The cell in the first column and first row is always pointed (this point is known as the root point). \label{T1}
\item Every row and every column contains at least one pointed cell. \label{T2}
\item For every pointed cell, all the cells above are empty or all the cells to the left are empty. \label{T3}
\end{enumerate}
\end{definition}

\begin{definition}\label{P}
A permutation tableau of size $n$ is a Ferrers diagram of half--perimeter $n$ filled with $0$'s and $1$'s according to the following rules: 
\begin{enumerate}
\item There is at least one $1$ in every column. \label{P1}
\item There is no $0$ with a $1$ above it and a $1$ to the left of it simultaneously. \label{P2} 
\end{enumerate}
\end{definition}
We will also need a notion of type--B tableaux originally introduced in \cite{LW}. Our definition follows a more explicit description 
given in \cite[Section~4]{CK}.
\begin{definition}\label{B}
A type--B permutation tableau of size $n$ is a shifted Ferrers diagram of half--perimeter $n$ filled with $0$'s and $1$'s according to the following rules:
\begin{enumerate}
\item There is at least one $1$ in every column. \label{B1}
\item There is no $0$ with a $1$ above it and a $1$ to the right of it simultaneously. \label{B2} 
\item If one of the diagonal cells contains a $0$ (called a diagonal $0$), then all the cells in that row are $0$. \label{B3}
\end{enumerate}
\end{definition}

\begin{figure}[h]
\setlength{\unitlength}{.5cm}
\begin{center}
\begin{picture} (22,8)

\put(3, 8){(i)}
\put(12.5, 8){(ii)}
\put(21, 8){(iii)}
%vertical lines
\put(0,0){\line(0,1){7}}
\put(1,0){\line(0,1){7}}
\put(2,1){\line(0,1){6}}
\put(3,3){\line(0,1){4}}
\put(4,3){\line(0,1){4}}
\put(5,3){\line(0,1){4}}
\put(6,5){\line(0,1){2}}
\put(7,5){\line(0,1){2}}

%horizontal lines
\put(0,7){\line(1,0){7}}
\put(0,6){\line(1,0){7}}
\put(0,5){\line(1,0){7}}
\put(0,4){\line(1,0){5}}
\put(0,3){\line(1,0){5}}
\put(0,2){\line(1,0){2}}
\put(0,1){\line(1,0){2}}
\put(0,0){\line(1,0){1}}

%(LR,UD)
\put(4.3, 3.3){$\bullet$}
\put(5.3, 5.3){$\bullet$}
\put(6.3, 6.3){$\bullet$}
\put(3.3, 6.3){$\bullet$}
\put(2.3, 3.3){$\bullet$}
\put(1.3, 2.3){$\bullet$}
\put(1.3, 4.3){$\bullet$}
\put(1.3, 5.3){$\bullet$}
\put(1.3, 6.3){$\bullet$}
\put(0.3, 3.3){$\bullet$}
\put(0.3, 1.3){$\bullet$}
\put(0.3, 0.3){$\bullet$}
\put(0.3, 6.3){$\bullet$}

%permutation tableaux

%vertical lines
\put(10,1){\line(0,1){6}}
\put(11,2){\line(0,1){5}}
\put(12,4){\line(0,1){3}}
\put(13,4){\line(0,1){3}}
\put(14,4){\line(0,1){3}}
\put(15,6){\line(0,1){1}}
\put(16,6){\line(0,1){1}}

%horizontal lines
\put(10,7){\line(1,0){6}}
\put(10,6){\line(1,0){6}}
\put(10,5){\line(1,0){4}}
\put(10,4){\line(1,0){4}}
\put(10,3){\line(1,0){1}}
\put(10,2){\line(1,0){1}}

%(LR,UD)
\put(10.25, 2.25){$1$}
\put(10.25, 3.25){$0$}
\put(10.25, 4.25){$0$}
\put(10.25, 5.25){$0$}
\put(10.25, 6.25){$0$}

\put(11.25, 6.25){$1$}
\put(11.25, 5.25){$0$}
\put(11.25, 4.25){$1$}

\put(12.25, 6.25){$0$}
\put(12.25, 5.25){$1$}
\put(12.25, 4.25){$1$}

\put(13.25, 6.25){$0$}
\put(13.25, 5.25){$1$}
\put(13.25, 4.25){$1$}

\put(14.25, 6.25){$1$}

\put(15.25, 6.25){$1$}

%typeB


%vertical lines
\put(20,1){\line(0,1){6}}
\put(21,2){\line(0,1){5}}
\put(22,2){\line(0,1){4}}
\put(23,4){\line(0,1){1}}




%horizontal lines
\put(20,7){\line(1,0){1}}
\put(20,6){\line(1,0){2}}
\put(20,5){\line(1,0){3}}
\put(20,4){\line(1,0){3}}
\put(20,3){\line(1,0){2}}
\put(20,2){\line(1,0){2}}

%(LR,UD)
\put(20.25, 6.25){$1$}

\put(20.25, 5.25){$0$}
\put(21.25, 5.25){$0$}

\put(21.25, 4.25){$1$}
\put(20.25, 4.25){$0$}
\put(22.25, 4.25){$1$}

\put(20.25, 3.25){$0$}
\put(21.25, 3.25){$1$}

\put(21.25, 2.25){$0$}
\put(20.25, 2.25){$0$}


\end{picture}

\end{center}
\caption{(i) A tree--like tableau of size $13$. (ii) A permutation tableau of size $12$. (iii) A type-B permutation tableau of size $6$.}
\end{figure}

Let $\mathcal{T}_n$ be the set of all tree--like tableaux of size $n$, $\mathcal{P}_n$ denote the set of all permutation tableaux of size $n$, and $\mathcal{B}_n$ denote the set of all type--B permutation tableaux of size $n$. In addition to these tableaux, we are also interested in {\it symmetric tree--like tableaux}, a subset of tree--like tableaux which are symmetric about their main diagonal (see \cite[Section 2.2]{ABN} for more details). 

As noticed in \cite{ABN}, the size of a symmetric tree--like tableau must be odd, and thus, we let $\mathcal{T}_{2n+1}^{sym}$ denote the set of all symmetric tree--like tableaux of size $2n+1$. It is a well--known fact that $|\mathcal{P}_n|=n!$ and $|\mathcal{B}_n|=2^nn!$. Consequently, $|\mathcal{T}_n|=n!$ and $|\mathcal{T}_{2n+1}^{sym}|=2^nn!$ since by \cite{ABN}, there are bijections between these objects. 
We let  $\mcX_n \in\{\mcT_n, \mcT^{sym}_{2n+1}, \mcP_n,  \mcB_n\}$  be any of the four sets of tableaux defined above. 

In permutation tableaux and type--B permutation tableaux, a {\it restricted $0$} is a $0$ which has a $1$ above it in the same column. An {\it unrestricted row} is a row which does not contain any restricted $0$'s (and for type--B permutation tableaux, 
also does not contain a diagonal $0$). We let $U_n(T)$ denote the number of unrestricted rows in a tableau $T$ of size $n$. It is also convenient to denote a topmost $1$ in a column by $1_{T}$ and a right-most restricted $0$ by $0_{R}$. 

{\it Corners} of a Ferrers diagram (or the associated tableau) are the cells in which both the right and bottom edges are border edges (i.e. a south step followed by a west step). In  tree--like tableaux (symmetric or not) {\it occupied corners} are corners that contain a point.

For convenience, let $M_k$ denote the direction of the $k^{th}$ step (border edge), i.e. $M_k=S$ denotes a south step and $M_k=W$ denotes a west step.
  Thus, 
\begin{equation}\label{eq:corners}
C_n=\sum_{k=1}^{n-1}I_{M_k=S,M_{k+1}=W},
\end{equation}
where $I_A$ is the indicator random variable of the event $A$. 


Our proofs will rely on techniques developed in \cite{CH} (see also \cite{HJ}). These two papers used probabilistic language and we adopt it here, too. Thus, instead of talking about the number of corners in tableaux we let $\mbP_n$  be the uniform probability measure 
on $\mcX_n$
 and consider the random variable $C_n$ on the probability space $(\mcX_n,\mbP_n)$ where $C_n(T)$ is the number of corners of $T$.
A tableau chosen from $\mcX_n$ according to the probability measure $\mbP_n$ is usually referred to as a random tableau of size $n$ and $C_n$ is referred to as the number of corners in a random tableau of size $n$. We let $\mbE_n$ denote the expected value with respect to the measure $\mbP_n$. If $c(\mcX_n)$ denotes the total number of corners in tableaux in $\mcX_n$ then we have the following simple relation:
\be\label{exp}\mbE_nC_n=\frac{c(\mcX_n)}{|\mcX_n|}\quad\mbox{or, equivalently, }\quad c(\mcX_n)=|\mcX_n|\, \mbE_nC_n.\ee 

We will use several properties of permutation tableaux that were derived in \cite{CH}. They were obtained as a consequence of a  recursive argument that constructed $\mcP_n$ (denoted by $\mcT_{n-1}$ in \cite{CH} and \cite{HJ})  by  considering all extensions of 
 tableaux of size $n-1$ to tableaux of size $n$. Specifically, given any tableau in $\mcP_{n-1}$ we can extend it to a tableau of size $n$ by adding a row (south step)  or adding a new column (west step) and filling its entries  with 0 or 1 according to the rules of permutation tableaux. By a simple counting argument, it was shown that there are $2^{U_{n-1}(P)}$ different extensions of a permutation tableau $P\in\mcP_{n-1}$ 
  to a permutation tableau of size $n$ (we refer to \cite{CH} or \cite[Section~2]{HJ} for a detailed explanation but it is clear that   only one of these extensions added a south step to $P$). Using this construction, a relationship between the measures $\mbP_n$ and $\mbP_{n-1}$ was derived in \cite{CH} and is given by \cite[Equation~(5)]{CH}  (see also \cite[Section~2, Equation~(2.1)]{HJ}),
\begin{equation}\label{relmeas}
\mbE_n(X_{n-1})=\frac1n\mbE_{n-1}(2^{U_{n-1}}X_{n-1})
\end{equation}
where $X_{n-1}$ is any random variable defined on $\mbP_{n-1}$. Let us denote by $\mcF_{n-1}$ the $\sigma$-subalgebra on $\mcP_{n}$ obtained by grouping together all tableaux of size $n$ obtained from the same tableau of size $n-1$.  
The conditional distribution of $U_n$ given $\mcF_{n-1}$ was determined to be the following,
\begin{equation}
\mathcal{L}(U_n|\mcF_{n-1})=1+\Bin(U_{n-1}) \label{condbin},
\end{equation}
where $\Bin(m)$ denotes a binomial random variable with parameters $m$ and $1/2$ (see \cite{CH}).



\section{Corners in Tree-Like Tableaux}\label{seccorners}
The main result of this section 
is the proof of the first conjecture of Laborde Zubieta. 
\begin{theorem} (see \cite[Conjecture~4.1]{LZ})\label{thm:conj} For $n\ge2$ we have
\[c(\mcT_n)=n!\times\frac{n+4}6.\]
\end{theorem}
To prove this, we will use the bijection between tree--like tableaux and permutation tableaux. According to Proposition~1.3 of \cite{ABN}, there exists a bijection between permutation tableaux and tree--like tableaux which transforms a tree--like tableau of shape $F$ to a permutation tableau of shape $F'$ which is obtained from $F$ by removing the SW--most edge from $F$ and  the cells of the left--most column (see Figure~\ref{TPB}). 

\begin{figure}[htbp]
\setlength{\unitlength}{0.4cm}%\setlength{linewidth=0.4mm}
\begin{center}
\begin{picture}
(0,0)(7.5,6)\thicklines
%first

%vertical lines
\put(10,0){\line(0,1){4}}
\put(11,1){\line(0,1){3}}
\put(12,1){\line(0,1){3}}
\put(13,3){\line(0,1){1}}

%horizontal lines
\put(10,1){\line(1,0){2}}
\put(10,2){\line(1,0){2}}
\put(10,3){\line(1,0){3}}
\put(10,4){\line(1,0){3}}


\put(10.25, 1.25){$0$}
\put(10.25, 2.25){$0$}
\put(11.25, 2.25){$0$}

\put(11.25, 1.25){$1$}
\put(10.25, 3.25){$1$}
\put(11.25, 3.25){$1$}
\put(12.25, 3.25){$1$}

%second
%(C,R)
%C: 10-17, R: 0-6
%vertical lines

\put(1,0){\line(0,1){4}}
\put(2,0){\line(0,1){4}}
\put(3,1){\line(0,1){3}}
\put(4,1){\line(0,1){3}}
\put(5,3){\line(0,1){1}}



%horizontal lines
\put(1,0){\line(1,0){1}}
\put(1,1){\line(1,0){3}}
\put(1,2){\line(1,0){3}}
\put(1,3){\line(1,0){4}}
\put(1,4){\line(1,0){4}}

\put(6.5,2){$\longleftrightarrow$}
%greek symbols


\put(1.25, 0.25){$\bullet$}
\put(1.25, 3.25){$\bullet$}
\put(2.25, 1.25){$\bullet$}
\put(2.25, 3.25){$\bullet$}
\put(3.25, 3.25){$\bullet$}
\put(3.25, 2.25){$\bullet$}
\put(4.25, 3.25){$\bullet$}

\end{picture}

\vspace{3cm}
\caption{An example of the bijection between permutation tableaux and tree--like tableaux of size $7$.}\label{TPB}
\end{center}

\end{figure}
The number of corners in $F$ is the same as the number of corners in $F'$ if the last edge of $F'$ is horizontal and it is one more than the number of corners in $F'$ if the last edge of $F'$ is vertical. Furthermore, as is clear from a recursive construction described in \cite[Section~2]{CH}, any permutation tableau of size $n$ whose last edge is vertical is obtained as the unique extension of a permutation tableau of size $n-1$. Therefore, there are $(n-1)!$ such   tableaux and we have a simple relation
\begin{equation}\label{corners}c(\mcT_n)=c(\mcP_n)+|\{P\in\mcP_n:\ M_n(P)=S\}|=c(\mcP_n)+(n-1)!.\end{equation}
Thus, it suffices to determine the number of corners in the permutation tableaux of size $n$. Since $|\mcP_n|=n!$, Equation~\eqref{exp} becomes
\be \label{expP} c(\mcP_n)=n!\, \mbE_nC_n.\ee

Combining \eqref{corners} with \eqref{expP} we immediately see that Theorem~\ref{thm:conj} will be proved once we establish the following result.
\begin{theorem}\label{thm:exp-c}
For  permutation tableaux of size $n$ we have
\[\mbE_n C_n=\frac{n+4}6-\frac1n.\]
\end{theorem}
\begin{proof}
In view of \eqref{eq:corners} we are interested in 
\begin{align*}
\mbE_n\left(\sum_{k=1}^{n-1}I_{M_k=S,M_{k+1}=W}\right)=\sum_{k=1}^{n-1}\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right).
\end{align*}
First calculate $\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right)$ using the techniques developed in \cite{CH}. Specifically, if $k+1\le n-1$ then  $I_{M_k=S,M_{k+1}=W}$ is a random variable on $\mcP_{n-1}$. Therefore, by \eqref{relmeas}
\begin{align*}
\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right)&=\frac{1}{n}\mbE_{n-1}\left(2^{U_{n-1}}I_{M_k=S,M_{k+1}=W}\right)\\
&=\frac{1}{n}\mbE_{n-1}\mbE\left(2^{U_{n-1}}I_{M_k=S,M_{k+1}=W}|\mcF_{n-2}\right),
\end{align*}
where $\mcF_{n-2}$ is the $\sigma$--subalgebra on $\mcP_{n-1}$ obtained by grouping into one set all tableaux in $\mcP_{n-1}$ that are obtained by extending the same tableau in $\mcP_{n-2}$ (see Section~\ref{sec:prel}).
Now, if $k+1\leq n-2$ then $I_{M_k=S,M_{k+1}=W}$ is measurable with respect to the $\sigma$-algebra $\mcF_{n-2}$. Thus by the properties of conditional expectation the above is:
\begin{align*}
\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right)&=\frac{1}{n}\mbE_{n-1}I_{M_k=S,M_{k+1}=W}\mbE\left(2^{U_{n-1}}|\mcF_{n-2}\right).\\
\end{align*}
By \eqref{condbin} and the fact that \begin{math}\mbE a^{\Bin(m)}=\left(\frac{a+1}{2}\right)^m\end{math}, we obtain by the same computation as in \cite{HJ} (see (2.2) and (2.3) there),
\begin{align}
\frac{1}{n}\mbE_{n-1}I_{M_k=S,M_{k+1}=W}\mbE\left(2^{U_{n-1}}|\mcF_{n-2}\right)&=\frac{1}{n}\mbE_{n-1}I_{M_k=S,M_{k+1}=W}\mbE\left(2^{1+\Bin(U_{n-2})}|\mcF_{n-2}\right)\nonumber\\
&= \frac{2}{n}\mbE_{n-1}I_{M_k=S,M_{k+1}=W}\left(\frac{3}{2}\right)^{U_{n-2}}\nonumber\\
&=\frac{2}{n(n-1)}\mbE_{n-2}I_{M_k=S,M_{k+1}=W}
3^{U_n-2}\label{binreduction}
\end{align}
where the last step follows from~\eqref{relmeas}.
Iterating $(n-1)-(k+1)$ times, we obtain
\begin{equation}\label{FC}
\frac{2\cdot3\cdot\dots\cdot(n-k-1)}{n(n-1)\cdot\dots\cdot(k+2)}\mbE_{k+1}I_{M_k=S,M_{k+1}=W}\left(n-k\right)^{U_{k+1}}.
\end{equation}
Thus, we need to compute 
\be\label{cond_exp}\mbE_{k+1}I_{M_k=S,M_{k+1}=W}(n-k)^{U_{k+1}}
\ee
for $1\le k\le n-1$ (note that $k+1=n$ gives $\mbE_{n}I_{M_{n-1}=S,M_{n}=W}$ which is exactly the summand omitted earlier by the restriction $k+1\le n-1$). 
 This can be computed as follows. First, by the tower property of the conditional expectation and the fact that $\{M_k=S\}$ is $\mcF_k$--measurable, we obtain  
\[\mbE_{k+1}I_{M_k=S,M_{k+1}=W}(n-k)^{U_{k+1}}=\mbE_{k+1}I_{M_k=S}\mbE(I_{M_{k+1}=W}(n-k)^{U_{k+1}}|\mcF_k).
\]
And now
\[\mbE(I_{M_{k+1}=W}(n-k)^{U_{k+1}}|\mcF_k)=\mbE((n-k)^{U_{k+1}}|\mcF_k)-\mbE(I_{M_{k+1}=S}(n-k)^{U_{k+1}}|\mcF_k)
\]
because the two indicators are complementary. 
By the same computation as above (see \eqref{binreduction}), the first conditional expectation on the right--hand side is
%by the same computation as in \cite{HJ} (see (2.2) and (2.3) there) is 
\be\label{1st}(n-k)\mbE\left((n-k)^{U_{k+1}}|\mcF_k\right)=(n-k)\left(\frac{n-k+1}2\right)^{U_k}.\ee
To compute the second conditional expectation, note that on the set $\{M_{k+1}=S\}$, $U_{k+1}=1+U_k$ so that  
\begin{align*}
\mbE(I_{M_{k+1}=S}(n-k)^{U_{k+1}}|\mcF_k)&=
(n-k)^{1+U_k}\mbE(I_{M_{k+1}=S}|\mcF_k)\\&=(n-k)^{1+U_k}\mbP(I_{M_{k+1}=S}|\mcF_k)\\&=(n-k)^{1+U_k}\frac1{2^{U_k}}\end{align*}
where the last equation follows from the fact that for every tableau $P\in\mcP_k$ only one of its $2^{U_k(P)}$ extensions to a tableau in $\mcP_{k+1}$ has $M_{k+1}=S$ (see Section~\ref{sec:prel} and also \cite{CH, HJ} for more details). Combining with \eqref{1st} yields 
\[ \mbE(I_{M_{k+1}=W}(n-k)^{U_{k+1}}|\mcF_k)=(n-k)\left(\left(\frac{n-k+1}2\right)^{U_k}-\left(\frac{n-k}2\right)^{U_k}\right)
\]
and thus \eqref{cond_exp} equals 
\[(n-k)\mbE_{k+1}\left(I_{M_k=S}\left(\left(\frac{n-k+1}2\right)^{U_k}-\left(\frac{n-k}2\right)^{U_k}\right)\right).
\]
The expression inside the expectation is a random variable on $\mcP_k$ so we can use \eqref{relmeas} to reduce the size by one and obtain that the expression above is 
\[\frac{n-k}{k+1}\mbE_{k}I_{M_k=S}\left(\left(n-k+1\right)^{U_k}-\left(n-k\right)^{U_k}\right).
\]
 Furthermore, 
on the set $\{M_k=S\}$, $U_k=U_{k-1}+1$ so that the above is
\[\frac{n-k}{k+1}\mbE_{k}\left(
\left(\left(n-k+1\right)^{1+U_{k-1}}-\left(n-k\right)^{1+U_{k-1}}\right)\mbE(I_{M_k=S}|\mcF_{k-1})\right),
\]
which, by the same argument as above, equals
\[\frac{n-k}{k+1}\mbE_{k}\left(
\left(\left(n-k+1\right)^{1+U_{k-1}}-\left(n-k\right)^{1+U_{k-1}}\right)\frac1{2^{U_{k-1}}}\right).
\]
After reducing the size one more time we obtain
\begin{equation}
\label{MP}\frac{n-k}{(k+1)k}\left(\mbE_{k-1}
\left(n-k+1\right)^{1+U_{k-1}}-\mbE_{k-1}\left(n-k\right)^{1+U_{k-1}}\right).
\end{equation}
As computed in \cite[Equation~(2.4)]{HJ} for a positive integer $m$ the generating function of $U_m$ is given by
\[
\mbE_m z^{U_m}=\frac{\Gamma(z+m)}{\Gamma(z)m!}.
\]
(There is an obvious omission in (2.4) there; the $z+n$ in the third expression should be $z+n-1$.)
Using this with $m=k-1$ and $z=n-k+1$ and then with $z=n-k$ we obtain
\begin{equation}\label{FP}
E_{k-1}
\left(\left(n-k+1\right)^{1+U_{k-1}}\right)=(n-k+1)\frac{(n-1)!}{(n-k)!(k-1)!}
\end{equation}
and
\be
\mbE_{k-1}\left(\left(n-k\right)^{1+U_{k-1}}\right)=(n-k)
\frac{(n-2)!}{(n-k-1)!(k-1)!}.
\label{SP}
\ee
Combining Equations (\ref{FC}), (\ref{MP}), (\ref{FP}), and (\ref{SP}),
\begin{align*}
\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right)&=\\&\hspace{-2.25cm}\frac{(n-k-1)!(k+1)!}{n!}\cdot\frac{n-k}{k(k+1)}\left(\frac{(n-k+1)(n-1)!}{(k-1)!(n-k)!}-\frac{(n-k)(n-2)!}{(k-1)!(n-k-1)!}\right)\\&\hspace{-2.25cm}=
\frac{n-k+1}{n}-\frac{(n-k)^2}{n(n-1)}.
\end{align*}
Summing from $k=1$ to $n-1$, we get
\begin{align*}
\mbE_nC_n&=\sum_{k=1}^{n-1}\frac{n-k+1}n-\sum_{k=1}^{n-1}\frac{(n-k)^2}{n(n-1)}
=\sum_{j=2}^{n}\frac jn-\sum_{j=1}^{n-1}\frac{j^2}{n(n-1)}\\
&=\frac{n(n+1)}{2n}-\frac1n-\frac{(n-1)n(2n-1)}{6n(n-1)}
=
\frac{n+4}{6}-\frac{1}{n}
\end{align*}
as desired. 
\end{proof}

\section{Corners in Symmetric Tree-Like Tableaux}\label{sec:symtab}
The main result of this section is the proof of the second conjecture of Laborde Zubieta. 
\begin{theorem} (see \cite[Conjecture~4.2]{LZ}) \label{thm:conjB} For $n\ge2$ we have
\[c(\mcT^{sym}_{2n+1})=2^n\times n!\times\frac{4n+13}{12}.\]
\end{theorem}
As in Section~\ref{seccorners}, we will use a bijection between symmetric tree--like tableaux and type--B permutation tableaux to relate the corners of  $\mcT^{sym}_{2n+1}$ to the corners of $\mcB_n$. In Section~2.2 of \cite{ABN}, it was mentioned that there exists such a bijection; however, no details were given. Thus, we give a description of one such bijection which will be useful to us (see Figure~\ref{TBPB}).

\begin{figure}[htbp] 
\setlength{\unitlength}{0.4cm}%\setlength{linewidth=0.4mm}
\begin{center}
\begin{picture}
(0,0)(7,6)\thicklines
%first

%vertical lines
\put(12,0){\line(0,1){5}}
\put(13,1){\line(0,1){4}}
\put(14,2){\line(0,1){2}}

%horizontal lines
\put(12,1){\line(1,0){1}}
\put(12,2){\line(1,0){2}}
\put(12,3){\line(1,0){2}}
\put(12,4){\line(1,0){2}}
\put(12,5){\line(1,0){1}}

\put(12.25, 1.25){$1$}
\put(12.25, 4.25){$1$}
\put(13.25, 2.25){$1$}

\put(12.25, 2.25){$0$}
\put(12.25, 3.25){$0$}
\put(13.25, 3.25){$0$}

%second
%(C,R)
%C: 10-17, R: 0-6
%vertical lines
\put(0,0){\line(0,1){6}}
\put(1,0){\line(0,1){6}}
\put(2,1){\line(0,1){5}}
\put(3,2){\line(0,1){4}}
\put(4,3){\line(0,1){3}}
\put(5,4){\line(0,1){2}}
\put(6,5){\line(0,1){1}}

%horizontal lines
\put(0,6){\line(1,0){6}}
\put(0,5){\line(1,0){6}}
\put(0,4){\line(1,0){5}}
\put(0,3){\line(1,0){4}}
\put(0,2){\line(1,0){3}}
\put(0,1){\line(1,0){2}}
\put(0,0){\line(1,0){1}}

\put(7,2.5){$\longleftrightarrow$}
%greek symbols


\put(0.25, 0.25){$\bullet$}
\put(0.25, 1.25){$\bullet$}
\put(0.25, 4.25){$\bullet$}
\put(0.25, 5.25){$\bullet$}
\put(1.25, 2.25){$\bullet$}
\put(1.25, 5.25){$\bullet$}
\put(2.25, 2.25){$\bullet$}
\put(3.25, 3.25){$\bullet$}
\put(3.25, 4.25){$\bullet$}
\put(4.25, 5.25){$\bullet$}
\put(5.25, 5.25){$\bullet$}

\end{picture}

\vspace{3cm}
\caption{An example of the bijection $F$ as defined in Lemma~\ref{Bijection} between type--B permutation tableaux of size $5$ and symmetric tree--like tableaux of size $11$.}\label{TBPB}
\end{center}

\end{figure}
\begin{lemma}\label{Bijection} 
Consider $F: \mathcal{T}_{2n+1}^{sym}\rightarrow\mathcal{B}_n$ defined by the following rules,
\begin{enumerate}
\item Replace the topmost point in each column with $1_{T}$'s. \label{TR1}
\item Replace the leftmost points in each row with $0_{R}$'s \label{TR2}
\item Fill in the remaining cells according to the rules of type--B permutation tableaux.\label{TR3}
\item Remove the cells above the diagonal.\label{TR4}
\item Remove the first column.\label{TR5}
\end{enumerate}
and $F^{-1}: \mathcal{B}_n\rightarrow\mathcal{T}^{sym}_{2n+1}$ defined by:
\begin{enumerate}
\item Add a column and point all cells except those in a restricted row. \label{BR1}
\item Replace all $0_{R}$'s with points unless 
that $0_{R}$ is in the same row as a diagonal $0$.\label{BR2}
\item Replace all non-diagonal $1_{T}$'s with points.\label{BR3}
\item Delete the remaining numbers, 
add a pointed box in the upper--left--hand corner (the root point), and then add the boxes necessary to make the tableau symmetric.\label{BR4}
\end{enumerate}
Then $F$ is a bijection between $\mathcal{T}^{sym}_{2n+1}$ and $\mathcal{B}_n$.
\end{lemma}
\begin{proof}
First, we show that $F$ and $F^{-1}$ are well--defined. For arbitrary $T\in\mathcal{T}^{sym}_{2n+1}$, each column in $T$ contains a point and thus, there is always a topmost point. Therefore, each column in $F(T)$ contains a $1_{T}$ and Definition~\ref{B}\eqref{B1} is satisfied. The condition \eqref{B2} in Definition~\ref{B}
 is satisfied since the only zeros in $F(T)$ are from the leftmost pointed cells (therefore, there is no topmost one to the left) or from rule~\eqref{TR3} which would not violate this condition. Condition~\eqref{B3} in  Definition~\ref{B}
 is satisfied similarly.
 
For arbitrary $B\in\mathcal{B}_{n}$, $F^{-1}(B)$ satisfies Definition~\ref{T}\eqref{T1} by rule~\eqref{BR4}. Because of symmetry, $F^{-1}(B)$ satisfies Definition~\ref{T}\eqref{T2} if every row contains a point. All restricted rows (excluding rows with a diagonal $0$) will get mapped to a pointed row since the $0_R$ gets pointed by rule~\eqref{BR2}. All unrestricted rows will get pointed in the new column by rule~\eqref{BR1}. 
Now consider the rows which contain a diagonal $0$. There must be a $1_{T}$ in the column below the diagonal $0$ (Definition~\ref{B}\eqref{B1}). This cell will get pointed after applying $F^{-1}$. Therefore, there will be a pointed cell to the right of the diagonal in $F^{-1}(B)$ which is in the same row as the diagonal $0$ after applying rule~\eqref{BR4}. Therefore, all diagonal zero rows also get mapped to pointed rows. Finally, condition Definition~\ref{T}\eqref{T3} is met since points added in the new column clearly have no points to the left of them. In addition, the points which come from a $0_{R}$ have no points to the left of them and the points which come from a $1_{T}$ have no points above them. 

Now to prove $F$ is one-to-one, consider arbitrary $B_1, B_2 \in \mathcal{B}_{n}$ such that $B_1\neq B_2$. If the Ferrers diagrams of $B_1$ and $B_2$ are different, then it is obvious that $F^{-1}\left(B_1\right)\neq F^{-1}\left(B_2\right)$ since these are tree-like tableaux of different shapes. If the Ferrers diagrams are the same, then there must be at least one cell which is labeled differently. Consider the highest, rightmost such cell, say $(i,j)$. W.L.O.G. assume that $B_1(i,j)=0$ and $B_2(i,j)=1$.

Consider two cases.

\begin{case}
$B_1(i,j)=0_R$.
\end{case}
In this case, there exists a cell above $(i,j)$ that is filled with a $1$ in both $B_1$ and $B_2$. By rule~\eqref{BR2}, $F^{-1}(B_1(i,j))$ is pointed but $F^{-1}(B_2(i,j))$ is not since it is not the highest one in its column (note that this $0_R$ can't be on a diagonal $0$ row since we have picked the highest, rightmost point that is different). Therefore, $F^{-1}\left(B_1\right)\neq F^{-1}\left(B_2\right)$.

\begin{case}
$B_1(i,j)\neq 0_R$.
\end{case}
In this case, all cells above $(i,j)$ are filled with $0$'s in both $B_1$ and $B_2$. If such cells exist, by rule~\eqref{BR3} $F^{-1}\left(B_2(i,j)\right)$ is pointed but $F^{-1}\left(B_1(i,j)\right)$ is not since it is not a restricted zero. If there are no cells above $(i,j)$, then $B_1(i,j)=0$ is a diagonal $0$ and thus, none of the cells in this row get pointed. 

But since $B_2(i,j)=1$, this row is either unrestricted and the added cell (from the added column) gets pointed (rule~\eqref{BR1}) or it is a restricted row (and does not contain a diagonal $0$) and the $0_R$ gets pointed (rule~\eqref{BR2}). Therefore, $F^{-1}\left(B_1\right)\neq F^{-1}\left(B_2\right)$.
\end{proof}

As mentioned earlier, Lemma~\ref{Bijection} will allow us to relate the corners of symmetric tree--like tableaux to the corners of type--B permutation tableaux.  To carry out the calculations for type--B permutation tableaux we will develop techniques similar to those developed in \cite{CH} for permutation tableaux. We first briefly describe an extension procedure for $B$--type tableaux  that mimics a construction given in \cite[Section~2]{CH}.
Fix any $B\in\mcB_{n-1}$ and let  $U_{n-1}=U_{n-1}(B)$  be the number of unrestricted rows in $B$. We can extend the size of $B$ to $n$ by inserting a new row or a new column.
 The only way to insert a new row is by adding a south step to the shape. The ways to insert a new column depend on the filling of that column. Any restricted row forces a $0$ in the new cell in that row. The remaining 
$ U_{n-1}+1$ cells (the one additional cell is the diagonal cell on the top row) to be filled with either a $1$ or $0$ so that there is at least one $1$. Thus, there are $2^{U_{n-1}+1}-1$ possible fillings of a new column and $2^{U_{n-1}+1}$ different extensions of our tableau to a type--B tableau of size $n$.    
 Let $U_n$ be the number of unrestricted rows in the extended tableau, $U_n=1,\dots,U_{n-1}+1$. If a row is inserted, then $U_n=U_{n-1}+1$. Since the row is inserted in precisely one of the possible $2^{U_{n-1}+1}$ cases, the (conditional) probability  that $U_n=U_{n-1}+1$  is 
\be\label{probadd}\mbP(U_n=U_{n-1}+1|\mcF_{n-1})=\mbP(M_n=S|\mcF_{n-1})=\frac1{2^{U_{n-1}+1}}.\ee
(Here, analogously to permutation tableaux (see the proof  of Theorem~\ref{thm:exp-c} above or \cite[Section~2]{HJ}) $\mcF_{n-1}$ is a $\sigma$--subalgebra on  $\mcB_n$ obtained by grouping together all tableaux in $\mcB_n$ that are obtained as the extension of the same tableau from $\mcB_{n-1}$.) 

 If a column is inserted, the  number of unrestricted rows depends on two cases. First, if a $1$ is inserted in the new diagonal cell, then any $0$ below it in an unrestricted row becomes restricted. Thus, for the extension to have $k$ unrestricted rows,  there must be $k-1$ $1$'s placed below the diagonal cell and there are $\binom{U_{n-1}}{k-1}$ ways do so. If a $0$ is inserted in the new diagonal cell, then this reduces to adding a column to a permutation tableaux with $U_{n-1}$ unrestricted rows. The number of ways to do so was already found in \cite{CH} and is $\binom{U_{n-1}}{k-1}$.
 Thus, 
\[
\mbP(U_n= k|\mcF_{n-1})=\frac{1}{2^{U_{n-1}+1}}\left(\binom{U_{n-1}}{k-1}+\binom{U_{n-1}}{k-1}\right)=\frac{1}{2^{U_{n-1}}}\binom{U_{n-1}}{k-1}, 
\]
for  $k=1,\dots,U_{n-1}$. This agrees with \eqref{probadd} when $k=U_{n+1}$. Thus, 
\[
\mathcal{L}(U_n|\mcF_{n-1})=1+\Bin(U_{n-1}),
\]
where the left--hand side means the conditional distribution of $U_n$ given $U_{n-1}$ and $\Bin(m)$ denotes a binomial random variable with parameters $m$ and $1/2$. Note that 
this is the same relationship 
as for permutation tableaux (see \cite[Equation~(2.2)]{HJ} or \cite[Equation~4]{CH}).

 As in the case of permutation tableaux, the uniform measure $\mbP_n$ on $\mcB_n$ induces a measure (still denoted by $\mbP_n$) on $\mcB_{n-1}$ via a mapping $\mcB_n\to\mcB_{n-1}$ that assigns to any $B'\in \mcB_n$ the unique tableau of size $n-1$ whose extension is $B'$.
 These two measures on $\mcB_{n-1}$ are not identical, but  the relationship between them can be easily calculated (see \cite[Section~2]{CH} or \cite[Section~2]{HJ} for more details and calculations 
for  permutation tableaux).  Namely,  
\begin{align*}
\mbP_n(B)=2^{U_{n-1}(B)+1}\frac{|\mcB_{n-1}|}{|\mcB_n|}\mbP_{n-1}(B),\quad B\in\mcB_{n-1}.\\
\end{align*}
This relationship implies that for any random variable $X$ on $\mcB_{n-1}$,
\begin{align} 
\mbE_nX&=\frac{2|\mcB_{n-1}|}{|\mcB_n|}\mbE_{n-1}(2^{U_{n-1}(B_{n-1})}X). \label{expBpre}
\end{align}
This allows us to provide a direct proof of the following well known fact,
\begin{proposition}\label{prop:|B_n|}
For all $n\geq0$, $|\mcB_n|=2^nn!$.
\end{proposition}

\begin{proof}
By considering all the extensions of a type--B permutation tableaux of size $n-1$, we have the following relationship,
\[
|\mcB_n|=\sum_{B\in\mcB_{n-1}}2^{U_{n-1}(B)+1}.
\]
Thus,
\begin{align*}
|\mcB_n|&=|\mcB_{n-1}|\mbE_{n-1}\left(2^{U_{n-1}+1}\right)\\
&=2|\mcB_{n-1}|\mbE_{n-1}\mbE\left(2^{U_{n-1}}|U_{n-2}\right)\\
&=2|\mcB_{n-1}|\mbE_{n-1}\mbE\left(2^{1+\Bin(U_{n-2})}|U_{n-2}\right)\\
&=2\cdot2|\mcB_{n-1}|\mbE_{n-1}\left(\frac{3}{2}\right)^{U_{n-2}}\\
&=2\cdot2|\mcB_{n-1}|\frac{2|\mcB_{n-2}|}{|\mcB_{n-1}|}\mbE_{n-2}\left(2^{U_{n-2}}\left(\frac32\right)^{U_{n-2}}\right)\\
&=2^2\cdot2!\,|\mcB_{n-2}|\mbE_{n-2}3^{U_{n-2}}.
\end{align*}
Iterating $n$ times,
\begin{align*}
|\mcB_n|&=2^3\cdot3!\, |\mcB_{n-3}|\mbE_{n-3}4^{U_{n-3}}
=2^{n-1}(n-1)!|\mcB_1|\mbE_1n^{U_1}\\
&=2^nn!,
\end{align*}
where the final equality holds because $|\mcB_1|=2$ and $U_1\equiv 1$.
\end{proof}
Given Proposition~\ref{prop:|B_n|} 
 \eqref{expBpre} reads
\begin{equation}\label{expB}
\mbE_nX=\frac1n\mbE_{n-1}(2^{U_{n-1}(B_{n-1})}X).
\end{equation}
This is exactly the same expression as \cite[Equation~(7)]{CH} which means that the relationship between $\mbE_n$ and $\mbE_{n-1}$ is the same regardless of whether we are considering $\mcP_n$ or $\mcB_n$. Thus, any computation for $B$--type tableaux based on \eqref{expB} will lead to the same expression as the analogous computation for permutation tableaux based on \cite[Equation~(7)]{CH}. 


Now we have the tools necessary to obtain a relationship between corners in symmetric tree--like tableaux and type--B permutation tableaux which is analogous to~\eqref{corners}.
\begin{lemma}\label{lemmaCSTT}
The number of corners in symmetric tree--like tableaux is given by, 
\begin{align}\label{cornersSym}c(\mcT^{sym}_{2n+1})
&=2c(\mcB_n)+2^n(n-1)!+2^{n-1}n!.\end{align}
\end{lemma}
\begin{proof}
The bijection described in Lemma~\ref{Bijection} transforms a tree--like tableau of shape $F$ to a permutation tableau of shape $F'$ that is obtained from $F$ by removing all the cells on and above the diagonal of $F$, removing the SW--most edge from $F$, and removing the cells of the left--most column of $F$ (see Figure~\ref{TBPB} for an example). The number of corners in $F$ is the same as the number of corners in $F'$ unless the last edge of $F'$ is vertical or the first edge of $F'$ is vertical. In the former case, $F$ has two additional corners. In the latter case, $F$ has one additional corner. This leads to the following relationship,
\be \label{rela}
c(\mcT^{sym}_{2n+1})=2c(\mcB_n)+2|\{B\in\mcB_n:\ M_n(B)=S\}|+|\{B\in\mcB_n:\ M_1(B)=W\}|.
\ee
By the extension process described above, it is clear that
\be
|\{B\in\mcB_n:\ M_n(B)=S\}|=|\mcB_{n-1}|=2^{n-1}(n-1)!. \label{lastS}
\ee
In addition,
\[
|\{B\in\mcB_n:\ M_1(B)=W\}|=2^nn!\, \mbE_n(I_{M_1=W}).
\] 
Furthermore, by the same argument as in the proof of Proposition~\ref{prop:|B_n|}:
\begin{align}
\mbE_n(I_{M_1=W})&=\frac1n\mbE_{n-1}(2^{U_{n-1}}I_{M_1=W})
=\frac1n\mbE_{n-1}\left(I_{M_1=W} \mbE(2^{U_{n-1}}|U_{n-2})\right)
\nonumber\\
&=\frac2n \mbE_{n-2}\left(I_{M_1=W}3^{U_{n-2}}\right)
=\frac{(n-1)!}{n!} \mbE_1\left(I_{M_1=W}n^{U_1}\right)
\nonumber\\
&=\frac12.\nonumber %\label{firstW}
\end{align}
Hence
\[
|\{B\in\mcB_n:\ M_1(B)=W\}|=2^{n-1}n!\, 
\] 
and the result is obtained by combining this with~\eqref{rela} and \eqref{lastS}.
\end{proof}

It follows from Lemma~\ref{lemmaCSTT} that to prove Theorem~\ref{thm:conjB}, it suffices to determine the number of corners in type--B permutation tableaux of size $n$. Since $|\mcB_n|=2^nn!$, Equation~\eqref{exp} becomes 
\be \label{expCorns} c(\mcB_n)=2^nn!\, \mbE_nC_n.\ee
Combining \eqref{cornersSym} with \eqref{expCorns}, we immediately see that Theorem~\ref{thm:conjB} will be proved once we establish the following result.
\begin{theorem}\label{cornersTB}
For  type--B permutation tableaux of size $n$ we have
\[\mbE_n C_n=\frac{4n+7}{24}-\frac{1}{2n}.\]\end{theorem}
\begin{proof} 
As in the proof of Theorem~\ref{thm:exp-c} we will compute
\begin{align*}
\mbE_n\left(\sum_{k=1}^{n-1}I_{M_k=S,M_{k+1}=W}\right)=\sum_{k=1}^{n-1}\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right).
\end{align*}
By~\eqref{expB},
\be\label{FCB}
\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right)=\frac{2\cdot3\cdot\dots\cdot(n-k-1)}{n(n-1)\cdot\dots\cdot(k+2)}\mbE_{k+1}I_{M_k=S,M_{k+1}=W}\left(n-k\right)^{U_{k+1}}
\ee
as obtained in \eqref{FC}.  Now, we need to compute 
\be\label{cond_expB}\mbE_{k+1}I_{M_k=S,M_{k+1}=W}(n-k)^{U_{k+1}}=\mbE_{k+1}I_{M_k=S}\mbE(I_{M_{k+1}=W}(n-k)^{U_{k+1}}|\mcF_k)
\ee
for $1\le k\le n-1$. 
 The conditional expectation is,
\[\mbE(I_{M_{k+1}=W}(n-k)^{U_{k+1}}|\mcF_k)=\mbE((n-k)^{U_{k+1}}|\mcF_k)-\mbE(I_{M_{k+1}=S}(n-k)^{U_{k+1}}|\mcF_k)
\]
since the two indicators are complementary. The first conditional expectation  on the right--hand side was computed in Theorem~\ref{thm:exp-c} (see~\eqref{1st}). 
To compute the second conditional expectation, note that on the set $\{M_{k+1}=S\}$, $U_{k+1}=1+U_k$ so that  
\begin{align*}
\mbE(I_{M_{k+1}=S}(n-k)^{U_{k+1}}|\mcF_k)&=
(n-k)^{1+U_k}\mbE(I_{M_{k+1}=S}|\mcF_k)\\&=(n-k)^{1+U_k}\mbP(M_{k+1}=S|\mcF_k)\\&=(n-k)^{1+U_k}\frac1{2^{U_k+1}}\end{align*}
where the last equality follows from~\eqref{probadd}. 
Combining with~\eqref{1st} yields 
\[ \mbE(I_{M_{k+1}=W}(n-k)^{U_{k+1}}|\mcF_k)=(n-k)\left(\left(\frac{n-k+1}2\right)^{U_k}-\frac{1}{2}\left(\frac{n-k}2\right)^{U_k}\right)
\]
and thus \eqref{cond_expB} equals 
\[(n-k)\mbE_{k+1}\left(I_{M_k=S}\left(\left(\frac{n-k+1}2\right)^{U_k}-\frac{1}{2}\left(\frac{n-k}2\right)^{U_k}\right)\right).
\]
The expression inside the expectation is a random variable on $\mcP_k$ so that we can use~\eqref{expB} to obtain
\[\frac{n-k}{k+1}\mbE_{k}I_{M_k=S}\left(\left(n-k+1\right)^{U_k}-\frac{1}{2}\left(n-k\right)^{U_k}\right).
\]
 Furthermore, on the set $\{M_k=S\}$, $U_k=U_{k-1}+1$ so that the above is
\[\frac{n-k}{k+1}\mbE_{k}\left(
\left(\left(n-k+1\right)^{1+U_{k-1}}-\frac{1}{2}\left(n-k\right)^{1+U_{k-1}}\right)\mbE(I_{M_k=S}|\mcF_{k-1})\right),
\]
which, by~\eqref{probadd}, equals
\[\frac{n-k}{k+1}\mbE_{k}\left(
\left(\left(n-k+1\right)^{1+U_{k-1}}-\frac{1}{2}\left(n-k\right)^{1+U_{k-1}}\right)\frac1{2^{U_{k-1}+1}}\right).
\]
After reducing the size one more time we obtain
\begin{equation}
\label{MPB}\frac{n-k}{2(k+1)k}\left(\mbE_{k-1}
\left(n-k+1\right)^{1+U_{k-1}}-\frac12\mbE_{k-1}\left(n-k\right)^{1+U_{k-1}}\right).
\end{equation}
Combining (\ref{FCB}) and (\ref{MPB}) and applying (\ref{FP}) and (\ref{SP}),
\begin{align*}
&\mbE_n\left(I_{M_k=S,M_{k+1}=W}\right)=\\&\hspace{1cm}\frac{(n-k-1)!(k+1)!}{n!}\cdot\frac{n-k}{2k(k+1)}\left(\frac{(n-k+1)(n-1)!}{(k-1)!(n-k)!}-\frac{(n-k)(n-2)!}{2(k-1)!(n-k-1)!}\right)\\&\hspace{1cm}=
\frac{n-k+1}{2n}-\frac{(n-k)^2}{4n(n-1)}.
\end{align*}
Summing from $k=1$ to $n-1$, we get
\begin{align*}
\mbE_nC_n&=\frac12\sum_{k=1}^{n-1}\frac{n-k+1}n-\frac14\sum_{k=1}^{n-1}\frac{(n-k)^2}{n(n-1)}
=\frac12\sum_{j=2}^{n}\frac jn-\frac14\sum_{j=1}^{n-1}\frac{j^2}{n(n-1)}\\
&=\frac{n(n+1)}{4n}-\frac1{2n}-\frac{(n-1)n(2n-1)}{24n(n-1)}
=\frac{4n+7}{24}-\frac{1}{2n}
\end{align*}
as desired. 
\end{proof}

\section{Occupied Corners}\label{sec:occor}
In this section we  study the asymptotic distribution of the number of occupied corners  in random tree--like tableau and random symmetric tree--like tableau.
 Laborde Zubieta \cite{LZ} derived a recurrence for the generating polynomials for the number of occupied corners and used it to obtain the expected value and the  variance of the number of occupied corners in  tree--like tableaux. He also obtained similar results in the symmetric case.
  Building on Laborde Zubieta's work we extend these results and identify the limiting distribution of the number of occupied corners in each of these two cases. 
 
We begin with the following simple statement. 
\begin{proposition}\label{prop:pol_recur}
Let $P_n(x)=\sum_{k=0}^ma_{n,k}x^k$ be a sequence of polynomials  satisfying the recurrence
\begin{equation}\label{pol_rec}
P^{'}_n(x)=f_nP_{n-1}(x)+g_n(x-1)P_{n-1}^{'}(x)
\end{equation}
for some sequences of constants $(f_n)$ and $(g_n)$. We assume that $a_{n,k}\ge0$, $\sum_ka_{n,k}>0$ for every $n\ge 1$, and that  $m=m_n$  may depend on $n$.  Consider a sequence of random variables $X_n$ defined by 
\[\mbP(X_n=k)=\frac{a_{n,k}}{P_n(1)}=\frac{a_{n,k}}{\sum_ja_{n,j}}.\]
If 
\begin{equation}\label{pol_ass}g_n=o(f_n)\quad\mbox{ and}\quad
f_n\frac{P_{n-1}(1)}{P_{n}(1)}\to c>0,\quad \mbox{as}\quad n\to\infty
\end{equation}
then 
\[X_n\stackrel{d}{\rightarrow}\operatorname{Pois}(c)\quad \mbox{as} \quad n\to\infty,
\]
where $\operatorname{Pois}(c)$ is a Poisson random variable with parameter $c>0$.
\end{proposition}

\begin{proof}
By \cite[Theorem~20, Chapter~1]{B} it is enough to  show that for every $r\ge 1$  the factorial moments 
\[\mbE(X_n)_r=\mbE X_n(X_n-1)\dots(X_n-(r-1)),\]
of $(X_n)$ converge to $c^r$ as $n\to\infty$.       
Recall that for a random variable $X$ with generating function $h(x)=\mbE x^X$ we have 
\[\mbE(X)_r=h^{(r)}(1),\]
where $h^{(r)}(x)$ is the $r^{th}$ derivative of $h(x)$. Thus,  we need to show that  
\[\frac{P_n^{(r)}(1)}{P_n(1)}\to c^r,\quad \mbox{as}\quad n\to\infty.\]    
Using \eqref{pol_rec} we have 
\begin{align*}
P_n^{(r)}(x)&=\left(P_n^{'}(x)\right)^{(r-1)}=f_nP_{n-1}^{(r-1)}(x)+g_n\left((x-1)P_{n-1}^{'}(x)\right)^{(r-1)}\\
&=f_nP_{n-1}^{(r-1)}(x)+g_n\left((x-1)P_{n-1}^{(r)}(x)+\binom{r-1}{1}%g_n
P_{n-1}^{(r-1)}(x)\right)
\end{align*}
where in the last step we used Leibniz formula for the differentiation of the product of two functions. 
It follows that 
\begin{align*}
P_n^{(r)}(1)&=\left(f_n+(r-1)g_n\right)P_{n-1}^{(r-1)}(1)
\end{align*}
and, consequently, 
\begin{align*}
\frac{P_n^{(r)}(1)}{P_n(1)}&=(f_n+(r-1)g_n)\frac{P_{n-1}^{(r-1)}(1)}{P_{n}(1)}\\
&=f_n\frac{P_{n-1}(1)}{P_{n}(1)}\left(1+(r-1)\frac{g_n}{f_n}\right)
\frac{P_{n-1}^{(r-1)}(1)}{P_{n-1}(1)}.
\end{align*}
Therefore,
\begin{align*}
\frac{P_n^{(r)}(1)}{P_n(1)}&=\left(\prod_{k=0}^{r-1}f_{n-k}{\frac{P_{n-k-1}(1)}{P_{n-k}(1)}\left(1+(r-k-1)\frac{g_{n-k}}{f_{n-k}}\right)}\right)\frac{P_{n-r}^{(r-r)}(1)}{P_{n-r}(1)}.
\end{align*}
Since the last factor is 1, it follows from \eqref{pol_ass} that for every $r\ge 1$ as 
 $n\rightarrow \infty$,
\begin{align*}
\frac{P_n^{(r)}(1)}{P_n(1)}&\rightarrow c^r
\end{align*}
as desired.
\end{proof}
For occupied corners, Laborde Zubieta obtained \eqref{pol_rec} with $f_n=n$ and $g_n=-2$. Since in that case $P_n(1)=n!$, the assumptions of Proposition~\ref{prop:pol_recur} are clearly satisfied, with $c=1$. Thus we obtain the following.
\begin{corollary} 
As $n\to\infty$,  the limiting distribution of the number of occupied corners in a random tree--like tableau of size $n$ is $\operatorname{Pois}(1)$.
\end{corollary} 
\subsection{Symmetric Tableaux}
For the symmetric tableaux of size $2n+1$, the generating polynomial of the number of occupied corners is 
\[Q_n(x)=\sum_{k\ge0}b_{n,k}x^{2k}\]
where 
\begin{equation}\label{eq:bnk_recur}
2k\cdot b_{n,k}=2[2k\cdot b_{n-1,k}+(n-2(k-1))b_{n-1,k-1}],
\end{equation}
see \cite{LZ}. 
Set 
\[R_n(z)=\sum_kb_{n,k}z^k, \quad\mbox{so that}\quad Q_n(x)=R_n(x^2).\] 
Then \eqref{eq:bnk_recur}
 translates to 
\begin{align*}
2zR^{'}_n(z)&=4zR_{n-1}^{'}(z)+2nzR_{n-1}(z)-4z^2R_{n-1}^{'}(z).
\end{align*}
Therefore,
\[
R^{'}_n(z)=nR_{n-1}(z)+2(1-z)R_{n-1}^{'}(z).
\]
By Proposition~\ref{prop:|B_n|}, $R_n(1)=2^nn!$. Thus, 
the conditions of Proposition~\ref{prop:pol_recur} are satisfied with $f_n=n$, $g_n=-2$, and $c=1/2$.  
 That is, as $n\rightarrow \infty$,
\begin{align*}
\frac{R_n^{(r)}(1)}{R_n(1)}&\rightarrow\left(\frac{1}{2}\right)^r.
\end{align*}
Thus, if $Y_n$ is a random variable with the probability generating function
$R_n(z)/R_n(1)$, 
 then $(Y_n)$ converges in distribution to a $\operatorname{Pois}(1/2)$ random variable. Moreover, since $Q_n(x)/Q_n(1)$ is the probability generating function of $2Y_n$, we have the following.
\begin{corollary}
As $n\to\infty$,  the limiting distribution of the number of occupied corners in a random symmetric tree--like tableau of size $2n+1$ is $2\times\operatorname{Pois}(1/2)$.
\end{corollary}




\begin{thebibliography}{14}

\bibitem{ABN}
J.--C.~Aval, A.~Boussicault, and P.~Nadeau.
\newblock Tree--like tableaux. 
\newblock \textit{Electron. J. Combin.}, 20(4): P34, 2013.

\bibitem{B}
B.~Bollob\'as.
\newblock Random Graphs.
\newblock Academic Press, 1985.

\bibitem{BUR}
A.~Burstein.
\newblock On some properties of permutation tableaux.
\newblock \textit{Ann. Comb.}, 11(3-4): 355-368, 2007.


\bibitem{CH}
S.~Corteel and P.~Hitczenko.
\newblock Expected values of statistics on permutation tableaux.
\newblock In \textit{2007 Conference on Analysis of Algorithms, AofA 07}, Discrete Math. Theor. Comput. Sci. Proc., AH:325-339, 2007.


\bibitem{CK}
S.~Corteel and J.~S.~Kim.
\newblock Combinatorics on permutation tableaux of type A and type B.
\newblock \textit{European J. Combin.},  32(4):563-579, 2011.

\bibitem{CN}
S.~Corteel and P.~Nadeau.
\newblock Bijections for permutation tableaux.
\newblock \textit{European J. Combin.} 30:295-310, 2009.


\bibitem{CW4}
S.~Corteel and L. K.~Williams.
\newblock A Markov chain on permutations which projects to the PASEP.
\newblock \textit{Int. Math. Res. Notes}, Article 17:rnm055, 27pp., 2007.

\bibitem{CW3}
S.~Corteel and L. K.~Williams.
\newblock Tableaux combinatorics for the asymmetric exclusion process.
\newblock \textit{Adv. Appl. Math.}, 39:293-310, 2007.

\bibitem{GGZS}
A. L. L.~Gao, E. X. L.~Gao, P.~Laborde--Zubieta, and B. Y.~Sun.
\newblock Enumeration of corners in tree-like tableaux.
\newblock \arxiv{1511.05456}, 2016. 

%\bibitem{GGZS}
%A.~Gao, E.~Gao, P.~Laborde Zubieta, and B.~Sun.
%\newblock Enumeration of corners in tree-like tableaux and a conjectural $(a,b)$-analogue.
%\newblock \arxiv{1511.05434}, 2016. 

%\bibitem{GGZS2}
%A.~Gao, E.~Gao, P.~Laborde Zubieta, and B.~Sun.
%\newblock Enumeration of corners in symmetric tree-like tableaux.
%\newblock \arxiv{1511.05456}, 2016. 

\bibitem{HJ}
P.~Hitczenko and S.~Janson.
\newblock Asymptotic normality of statistics on permutation tableaux.
\newblock \textit{Contemporary Math.}, 520:83-104, 2010.

\bibitem{LZ}
P.~Laborde Zubieta.
\newblock Occupied corners in tree--like  tableaux.
\newblock  \textit{S\'em. Lothar. Combin.}, 74: Art. B74b, 14, 2015.

%\bibitem{LZpers}
%P.~Laborde Zubieta.
%\newblock Personal communication, 2015.

\bibitem{LW} T.~Lam and L.~Williams. 
\newblock Total positivity for cominuscule Grassmannians.
\newblock\textit { New York J. Math.},  14:  53--99, 2008. 

\bibitem{PN}
P.~Nadeau. 
\newblock The structure of alternative tableaux.
\newblock \textit{J. Combin. Theory Ser. A}, 118(5): 1638-1660, 2011.

\bibitem{SW}
E.~Steingr\'imsson and L.K.~Williams. 
\newblock Permutation tableaux and permutation patterns.
\newblock \textit{J. Combin. Theory Ser. A}, 114(2):211-234, 2007.

\bibitem{XV}
X.~Viennot.
\newblock Alternative tableaux, permutations, and partially asymmetric exclusion process.
\newblock Slides of a talk at the Isaac Newton Institute in Cambridge, 2008.

\end{thebibliography}


\end{document}

