% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb,amscd} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \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} % %\makeatletter %\renewcommand \theequation {\ifnum \c@chapter>\z@ \thechapter.\fi %\ifnum \c@section>\z@ \@arabic\c@section.\fi \ifnum %\c@subsection>\z@ \@arabic\c@subsection.\fi\ifnum %\c@subsubsection>\z@ %\@arabic\c@subsubsection.\fi\@arabic\c@equation} %\makeatother \makeatletter%%标号在每一节或小节开始前清零 %\@addtoreset{subsubsection}{section} \@addtoreset{equation}{section} \@addtoreset{figure}{section} \@addtoreset{equation}{subsection} \@addtoreset{equation}{subsubsection} \makeatother \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \renewcommand{\thetheorem}{\arabic{section}.\arabic{theorem}} \renewcommand{\thefigure}{\arabic{section}.\arabic{figure}} \renewcommand{\thetable}{\arabic{section}.\arabic{table}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Linked Partitions and Permutation Tableaux} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{William Y.C. Chen\\ \small Center for Applied Mathematics\\[-0.8ex] \small Tianjin University\\[-0.8ex] \small Tianjin 300072, P.R. China\\ \small\tt chenyc@tju.edu.cn\\ \\[-1ex] Lewis H. Liu\\ \small Center for Combinatorics, LPMC-TJKLC\\[-0.8ex] \small Nankai University\\[-0.8ex] \small Tianjin 300071, P.R. China\\ \small\tt lewis@cfc.nankai.edu.cn\\ \\[-1ex] Carol J. Wang\\ \small Department of Mathematics\\[-0.8ex] \small Beijing Technology and Business University\\[-0.8ex] \small Beijing 100048, P.R. China\\ \small\tt wang$\_$jian@th.btbu.edu.cn } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{May 23, 2013}{XX}\\ \small Mathematics Subject Classifications: 05A05, 05A19} \begin{document} \maketitle\vspace{-.5cm} \begin{abstract} Linked partitions were introduced by Dykema in the study of transforms in free probability theory, whereas permutation tableaux were introduced by Steingr\'{i}msson and Williams in the study of totally positive Grassmannian cells. Let $[n]=\left\{1,2,\ldots\right.$, $\left.n\right\}$. Let $L(n,k)$ denote the set of linked partitions of $[n]$ with $k$ blocks, let $P(n,k)$ denote the set of permutations of $[n]$ with $k$ descents, and let $T(n,k)$ denote the set of permutation tableaux of length $n$ with $k$ rows. Steingr\'{i}msson and Williams found a bijection between the set of permutation tableaux of length $n$ with $k$ rows and the set of permutations of $[n]$ with $k$ weak excedances. Corteel and Nadeau gave a bijection between the set of permutation tableaux of length $n$ with $k$ columns and the set of permutations of $[n]$ with $k$ descents. In this paper, we establish a bijection between $L(n,k)$ and $P(n,k-1)$ and a bijection between $L(n,k)$ and $T(n,k)$. Restricting the latter bijection to noncrossing linked partitions and nonnesting linked partitions, we find that the corresponding permutation tableaux can be characterized by pattern avoidance. % keywords are optional \bigskip\noindent \textbf{Keywords:} linked partition; permutation; descent; permutation tableau. \end{abstract} \section{Introduction} The notion of linked partitions was introduced by Dykema \cite{Dyke07} in the study of the unsymmetrized T-transform in free probability theory. Let $[n]=\{1,2,\ldots,n\}$. A linked partition of $[n]$ is a collection of nonempty subsets $B_1, B_2, \ldots, B_k$ of $[n]$, called blocks, such that the union of $B_1, B_2, \ldots, B_k$ is $[n]$ and any two distinct blocks are nearly disjoint. Two blocks $B_i$ and $B_j$ are said to be nearly disjoint if for any $k \in B_i\cap B_j$, one of the following conditions holds: \begin{itemize}\vspace{-.2cm} \item[(a)] $k=\min(B_i), |B_i|>1$ and $k\neq \min(B_j)$, or\vspace{-.2cm} \item[(b)] $k=\min(B_j), |B_j|>1$ and $k\neq \min(B_i)$.\vspace{-.2cm} \end{itemize} The linear representation of a linked partition was introduced by Chen, Wu and Yan \cite{CWY08}. For a linked partition $\tau$ of $[n]$, list the $n$ vertices in a horizontal line with labels $1,2,\ldots,n$. For a block $B=\{i_1,i_2,\ldots,i_k\}$ with $k\geq 2$ and $i_1\pi_{i+1}$ (resp., $\pi_i<\pi_{i+1}$). Let $P(n,k)$ denote the set of permutations of $[n]$ with $k$ descents, which is counted by the Eulerian number $A(n,k+1)$, see, for example, Stanley \cite{Stanbook}. \begin{theorem}\label{th2} For $n\geq 1$ and $1\leq k\leq n$, there is a bijection $\varphi$ between $L(n,k)$ and $P(n,k-1)$. \end{theorem} \begin{proof} We conduct induction on $n$. If $n=1$, that is, $\tau=\{1\}$. In this case, we have $k=1$. Then we set $\varphi(\tau)=1$, which is a permutation with no descent. So the theorem holds for $n=1$. We now assume that $n\geq 2$ and that the theorem holds for $n-1$. We aim to construct a map $\varphi$ from $L(n,k)$ to $P(n,k-1)$, which is easily seen to be a bijection. To define $\varphi$, let $\tau\in L(n,k)$ be a linked partition of $[n]$ with $k$ blocks and let $\tau'$ denote the linked partition of $[n-1]$ obtained from $\tau$ by removing the vertex $n$ along with the arcs possibly associated to $n$. Starting with $\varphi(\tau')$, we proceed to generate a permutation $\varphi(\tau)$ of $[n]$ with $k-1$ descents. Suppose that $\tau'$ contains $s$ blocks. Notice that $n$ is either a singleton or a destination in $\tau$. If $n$ is a singleton, then it is clear that $s=k-1$; if $n$ is a destination, then we have $s=k$. By the induction hypothesis, $\varphi(\tau')$ is a permutation of $[n-1]$ with $s-1$ descents. Now $\varphi(\tau)$ can be defined by inserting $n$ into the permutation $\varphi(\tau')$. More precisely, let $\varphi(\tau')=\pi_1\pi_2\cdots \pi_{n-1}$. Let $i_1, i_2, \ldots, i_s$ be the minimum elements of blocks in $\tau'$ listed in increasing order, and let $j_1, j_2, \ldots, j_t$ be the destinations of $\tau'$ listed also in increasing order. Clearly, we have $t=n-1-s$. Assume that $m$ is the minimum element in the block of $\tau$ that contains $n$. To ensure that $\varphi$ is a bijection, we need to find a position to insert $n$ into $\varphi(\tau')$ such that the inserting procedure is reversible. There are four cases. \noindent Case 1: $m=i_r$, where $1\leq r\leq s-1$, that is, there is an arc $(i_r,n)$ in the linear representation of $\tau$. Set \begin{equation}\label{eq1} \varphi(\tau)=\pi_1 \pi_2 \cdots \pi_\ell\, n\, \pi_{\ell+1} \cdots \pi_{n-1},\end{equation} where $\ell$ is the $r$-th descent of $\varphi(\tau')$ from left to right. \noindent Case 2: $m=i_s$. Set \[\varphi(\tau)=\varphi(\tau')\,n.\] \noindent Case 3: $m=j_r$, where $1\leq r \leq t$. Set \[\varphi(\tau)=\pi_1 \pi_2 \cdots \pi_\ell\, n\, \pi_{\ell+1} \cdots \pi_{n-1},\] where $\ell$ is the $r$-th ascent in $\varphi(\tau')$ from left to right. \noindent Case 4: $m=n$, that is, $n$ is a singleton in $\tau$. Set \[\varphi(\tau)=n\, \varphi(\tau').\] Clearly, $\varphi(\tau)$ is a permutation of $[n]$ in any of the above cases. It remains to prove that $\varphi(\tau)$ has $k-1$ descents. Here we shall only give the proof for Case 1, since the other cases can be justified by the same reasoning. In Case 1, there is an arc $(m,n)$ in $\tau$, where $m$ is the minimum element of a block of $\tau$. Hence $\tau'$ has the same number of blocks as $\tau$, namely, $\tau'$ belongs to $L(n-1,k)$. By the induction hypothesis, $\varphi(\tau')$ belongs to $P(n-1,k-1)$. It is clear from \eqref{eq1} that $\varphi(\tau)$ has the same number of descents as $\varphi(\tau')$. Thus $\varphi(\tau)$ has $k-1$ descents. It is not difficult to see that the above procedure is reversible. Hence the map $\varphi$ is a bijection, and the proof is complete by induction. \end{proof} For example, Figure \ref{eg1} illustrates the linked partitions of $\{1,2,3\}$ and the corresponding permutations. \begin{figure}[h] \setlength{\unitlength}{0.8cm} \begin{center} \begin{picture}(18.5,2.8) \qbezier(-.4,-0.5)(-0.4,1)(-0.4,2.7)\qbezier(2.6,-0.5)(2.6,1)(2.6,2.7) \qbezier(5.8,-0.5)(5.8,1)(5.8,2.7)\qbezier(9,-0.5)(9,1)(9,2.7) \qbezier(12.2,-0.5)(12.2,1)(12.2,2.7)\qbezier(15.4,-0.5)(15.4,1)(15.4,2.7) \qbezier(18.6,-0.5)(18.6,1)(18.6,2.7) \put(-.4,-.5){\line(1,0){19}} \put(-.4,2.7){\line(1,0){19}} \put(-.4,0.4){\line(1,0){19}}%\put(-2.1,-0.5){\line(0,1){3.2}} %\put(-.8,-0.2){$P(3)$}\put(-1.8,1.2){$\mathcal{L}(3)$} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(0,0){\begin{picture}(0,0) \put(0.6,-0.2){$\footnotesize 123$} \multiput(0,1)(1,0){3}{\circle*{0.15}} \put(-0.1,0.6){$\scriptstyle 1$}\put(0.9,0.6){$\scriptstyle 2$}\put(1.9,0.6){$\scriptstyle 3$} \qbezier(0,1)(0.5,1.5)(1,1)\qbezier(0,1)(1,1.9)(2,1) \put(0.1,1.8){$\footnotesize \{1,2,3\}$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(3.2,0){\begin{picture}(0,0) \put(0.6,-0.2){$\footnotesize 132$} \multiput(0,1)(1,0){3}{\circle*{0.15}} \put(-0.1,0.6){$\scriptstyle 1$}\put(0.9,0.6){$\scriptstyle 2$}\put(1.9,0.6){$\scriptstyle 3$} \qbezier(0,1)(0.5,1.6)(1,1)\qbezier(1,1)(1.5,1.6)(2,1) \put(-0.2,1.8){$\footnotesize \{1,2\}\{2,3\}$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(6.4,0){\begin{picture}(0,0) \put(0.6,-0.2){$\footnotesize 231$} \multiput(0,1)(1,0){3}{\circle*{0.15}} \put(-0.1,0.6){$\scriptstyle 1$}\put(0.9,0.6){$\scriptstyle 2$}\put(1.9,0.6){$\scriptstyle 3$} \qbezier(0,1)(1,1.9)(2,1) \put(0,1.8){$\footnotesize \{1,3\}\{2\}$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(9.6,0){\begin{picture}(0,0) \put(0.6,-0.2){$\footnotesize 312$} \multiput(0,1)(1,0){3}{\circle*{0.15}} \put(-0.1,0.6){$\scriptstyle 1$}\put(0.9,0.6){$\scriptstyle 2$}\put(1.9,0.6){$\scriptstyle 3$} \qbezier(0,1)(.5,1.6)(1,1) \put(0,1.8){$\footnotesize \{1,2\}\{3\}$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(12.8,0){\begin{picture}(0,0) \put(0.6,-0.2){$\footnotesize 213$} \multiput(0,1)(1,0){3}{\circle*{0.15}} \put(-0.1,0.6){$\scriptstyle 1$}\put(0.9,0.6){$\scriptstyle 2$}\put(1.9,0.6){$\scriptstyle 3$} \qbezier(1,1)(1.5,1.6)(2,1) \put(0,1.8){$\footnotesize \{1\}\{2,3\}$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(16,0){\begin{picture}(0,0) \put(0.6,-0.2){$\footnotesize 321$} \multiput(0,1)(1,0){3}{\circle*{0.15}} \put(-0.1,0.6){$\scriptstyle 1$}\put(0.9,0.6){$\scriptstyle 2$}\put(1.9,0.6){$\scriptstyle 3$} \put(-.2,1.8){$\footnotesize \{1\}\{2\}\{3\}$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{picture} \end{center} \caption{Linked partitions of $\{1,2,3\}$ and the corresponding permutations. }\label{eg1} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Linked partitions and permutation tableaux}\label{section3} The objective of this section is to present a bijection between linked partitions of $[n]$ with $k$ blocks and permutation tableaux of length $n$ with $k$ rows. As consequences, we obtain equidistribution properties between linked partitions and permutation tableaux with certain restrictions. For example, we find that the number of permutation tableaux of length $n$ with $k$ rightmost restricted $0$'s is equal to the number of linked partitions of $[n]$ with $k$ transients. Our bijections also lead to some known results on permutation tableaux obtained by Corteel and Nadeau \cite{CorNad09} and Steingr\'{i}msson and Williams \cite{SteWil07}. To construct the bijection between linked partitions and permutation tableaux, we introduce the shape of a linked partition. Let $\tau$ be a linked partition of $[n]$. Using the linear representation of $\tau$, we obtain a sequence $S=s_1s_2\cdots s_n$ by letting $s_i=H$ if $i$ is a destination, and $s_i=V$ otherwise, where $H$ stands for the horizontal step $(-1,0)$ and $V$ stands for the vertical step $(0,-1)$. Consider the sequence $S$ as a lattice path, and let $\lambda$ be the Ferrers diagram of a partition having the lattice path $S$ as its boundary from the top right corner to the bottom left corner. This partition $\lambda$ with empty parts allowed is defined as the shape of the linked partition $\tau$. For example, Figure \ref{taushape} demonstrates the shape of the linked partition in Figure \ref{LP}. %The shape of a linked partition of $[n]$ %is an integer partition $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ with $\lambda_i\geq 0$ .....with .... such that the ith step of the boundary of  is West %(resp. South) if i is a descent (resp. ascent) of . \begin{figure}[h] \begin{center} \setlength{\unitlength}{0.14cm} \begin{picture}(15,35) %\put(2,-2.2){\footnotesize $9$}\put(5.4,1.6){\footnotesize $8$} %\put(7,2.8){\footnotesize $7$}\put(10.4,6.6){\footnotesize $6$} %\put(10.4,11.6){\footnotesize $5$}\put(12,12.8){\footnotesize $4$} %\put(15.4,16.6){\footnotesize $3$}\put(15.4,21.6){\footnotesize $2$} %\put(15.4,26.6){\footnotesize $1$} \put(0,0){\line(0,1){30}}\put(5,0){\line(0,1){30}}\put(10,5){\line(0,1){25}} \put(15,15){\line(0,1){15}}%%画竖线 \put(0,0){\line(1,0){5}}\put(0,5){\line(1,0){10}}\put(0,10){\line(1,0){10}} \put(0,15){\line(1,0){15}}\put(0,20){\line(1,0){15}}\put(0,25){\line(1,0){15}} \put(0,30){\line(1,0){15}}%%画横线 \end{picture} \caption{The shape of linked partition $\{1,2,4\}\{2,3\}\{3,9\}\{5,6\}\{6, 7\}\{8\}$.}\label{taushape} \end{center} \end{figure} The construction of our bijection also requires a fact proved by Corteel and Nadeau \cite{CorNad09} that a permutation tableau is determined by its topmost $1$'s and rightmost restricted $0$'s. By a topmost $1$ we mean the topmost $1$ in a column. A $0$ is said to be restricted if it is below a $1$ in the same column. A rightmost restricted $0$ means the rightmost restricted $0$ in a row. For example, in the permutation tableau in Figure \ref{PT}, the topmost $1$'s are in the cells $(1,4)$, $(1,10)$, $(2,3)$, $(2,8)$ and $(5,6)$, while the rightmost restricted $0$'s are in the cells $(2,10)$, $(5,8)$ and $(7,8)$. To see that a permutation tableau is uniquely determined by its topmost $1$'s and rightmost restricted $0$'s, it suffices to observe the fact that if the positions of topmost $1$'s are given, then all the cells above these positions (in the same columns) are filled with $0$'s; if the positions of the rightmost restricted $0$'s are given, then all the cells to the left of these positions (in the same rows) are filled with $0$'s; and the remaining cells are filled with $1$'s. Let $T(n,k)$ denote the set of permutation tableaux of length $n$ with $k$ rows. We have the following correspondence and the explicit construction is given in the proof. \begin{theorem}\label{th3} For $n\geq 1$ and $1\leq k\leq n$, there is a shape preserving bijection $\phi$ between $L(n,k)$ and $T(n,k)$. \end{theorem} \begin{proof} Let $\tau$ be a linked partition in $L(n,k)$. We construct a permutation tableau $T=\phi(\tau)$ of the same shape as $\tau$. First, we generate the shape $\lambda$ of $\tau$, and label the boundary of $\lambda$ by using the elements of $[n]$ in increasing order from the top right corner to the bottom left corner. Next, we fill the cells of the diagram of $\lambda$ with topmost $1$'s and rightmost restricted $0$'s. Let $i_1$ be the minimum origin in $\tau$, and let $j$ be the largest destination such that there exists a path $(i_1,i_2,\ldots,i_m, j)$ from $i_1$ to $j$ in the linear representation of $\tau$. Then we fill the cell $(i_1,j)$ with $1$. For $\ell=2,\ldots,m$, we fill the cells $(i_\ell,j)$ with $0$. Let $\tau'$ be the linked partition of $[n]$ obtained from $\tau$ by removing the arcs in the path $(i_1,i_2,\ldots,i_m, j)$. Repeating the above process for $\tau'$, we can fill each column with a $1$ possibly along with some $0$'s until there are no arcs left in the linear representation of $\tau$. Finally, we obtain a permutation tableau $T$ for which the $1$'s and $0$'s filled in $\lambda$ are the topmost $1$'s and rightmost restricted $0$'s of $T$, respectively. The inverse map of $\phi$ can be described as follows. Let $T$ be a permutation tableau of length $n$ and shape $\lambda$. We construct a linked partition $\tau$ of $[n]$ such that $T=\phi(\tau)$. For the column labeled with $j$, let $(i_1,j)$ be the cell filled with a topmost $1$ and $(i_2,j), (i_3,j),\ldots, (i_m,j)$ be the cells filled with the rightmost restricted $0$'s. For $\ell=1,2,\ldots,m$, let $(i_{\ell}, i_{\ell+1})$ be an arc in the linear representation of $\tau$, where $i_{m+1}=j$. Note that there is a unique topmost $1$ in each column and at most one rightmost restricted $0$ in each row. Thus, for any vertex $j$ in $\tau$, there is at most one arc whose right-hand endpoint is $j$. This implies that $\tau$ is a linked partition of $[n]$. Moreover, it is not difficult to see that $T$ and $\tau$ have the same shape. This completes the proof. \end{proof} For example, the permutation tableau corresponding to the linked partition in Figure \ref{LP} is given in Figure \ref{phitau}. \begin{figure}[h] \begin{center} \setlength{\unitlength}{0.15cm} \begin{picture}(75,37) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(0,2){\begin{picture}(0,0) \put(2,-2.2){\footnotesize $9$}\put(5.4,1.6){\footnotesize $8$} \put(7,2.8){\footnotesize $7$}\put(10.4,6.6){\footnotesize $6$} \put(10.4,11.6){\footnotesize $5$}\put(12,12.8){\footnotesize $4$} \put(15.4,16.6){\footnotesize $3$}\put(15.4,21.6){\footnotesize $2$} \put(15.4,26.6){\footnotesize $1$} \put(0,0){\line(0,1){30}}\put(5,0){\line(0,1){30}}\put(10,5){\line(0,1){25}} \put(15,15){\line(0,1){15}}%%画竖线 \put(0,0){\line(1,0){5}}\put(0,5){\line(1,0){10}}\put(0,10){\line(1,0){10}} \put(0,15){\line(1,0){15}}\put(0,20){\line(1,0){15}}\put(0,25){\line(1,0){15}} \put(0,30){\line(1,0){15}}%%画横线 %\put(0,-7){$\footnotesize (a)\mbox{ shape of } \tau$} \put(20,15){\vector(1,0){7}} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(30,2){\begin{picture}(0,0) \put(2,-2.2){\footnotesize $9$}\put(5.4,1.6){\footnotesize $8$} \put(7,2.8){\footnotesize $7$}\put(10.4,6.6){\footnotesize $6$} \put(10.4,11.6){\footnotesize $5$}\put(12,12.8){\footnotesize $4$} \put(15.4,16.6){\footnotesize $3$}\put(15.4,21.6){\footnotesize $2$} \put(15.4,26.6){\footnotesize $1$} \put(0,0){\line(0,1){30}}\put(5,0){\line(0,1){30}}\put(10,5){\line(0,1){25}} \put(15,15){\line(0,1){15}}%%画竖线 \put(0,0){\line(1,0){5}}\put(0,5){\line(1,0){10}}\put(0,10){\line(1,0){10}} \put(0,15){\line(1,0){15}}\put(0,20){\line(1,0){15}}\put(0,25){\line(1,0){15}} \put(0,30){\line(1,0){15}}%%画横线 %\put(0,-7){$\footnotesize (b)$} %\put(0,-11){$\footnotesize \mbox{ filled with topmost } 1$}\put(0,-15){$\footnotesize \mbox{ and r.r. }0$} \put(20,15){\vector(1,0){7}} \put(7,6.5){$0$} \put(7,11.5){$1$} \put(2,16.5){$0$} \put(2,21.5){$0$} \put(2,26.5){$1$} \put(12,26.5){$1$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \put(60,2){\begin{picture}(0,0) \put(2,-2.2){\footnotesize $9$}\put(5.4,1.6){\footnotesize $8$} \put(7,2.8){\footnotesize $7$}\put(10.4,6.6){\footnotesize $6$} \put(10.3,11.6){\footnotesize $5$}\put(12,12.8){\footnotesize $4$} \put(15.4,16.6){\footnotesize $3$}\put(15.4,21.6){\footnotesize $2$} \put(15.4,26.6){\footnotesize $1$} \put(0,0){\line(0,1){30}}\put(5,0){\line(0,1){30}}\put(10,5){\line(0,1){25}} \put(15,15){\line(0,1){15}}%%画竖线 \put(0,0){\line(1,0){5}}\put(0,5){\line(1,0){10}}\put(0,10){\line(1,0){10}} \put(0,15){\line(1,0){15}}\put(0,20){\line(1,0){15}}\put(0,25){\line(1,0){15}} \put(0,30){\line(1,0){15}}%%画横线 \put(7,6.5){$0$} \put(7,11.5){$1$} \put(2,16.5){$0$} \put(2,21.5){$0$} \put(2,26.5){$1$} \put(12,26.5){$1$} \put(2,1.5){$1$}\put(2,6.5){$0$} \put(2,11.5){$1$}\put(7,16.5){$0$}\put(7,21.5){$0$}\put(7,26.5){$0$} \put(12,16.5){$1$}\put(12,21.5){$1$} \end{picture} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{picture} \caption{From a linked partition to a permutation tableau.}\label{phitau} \end{center} \end{figure} For the permutation tableau given in Figure \ref{PT}, the corresponding linked partition is given in Figure \ref{PTlp}. \begin{figure}[h] \begin{center} \setlength{\unitlength}{0.7cm} \begin{picture}(10,2.5) \multiput(0,.7)(1,0){11}{\circle*{0.1}} \qbezier(0,.7)(.5,1.2)(1,.7)\qbezier(1,.7)(1.5,1.2)(2,.7) \qbezier(0,.7)(1.5,2.1)(3,.7)\qbezier(1,.7)(2.5,1.9)(4,.7) \qbezier(1,.7)(5,3.7)(9,.7)\qbezier(4,.7)(4.5,1.2)(5,.7) \qbezier(4,.7)(5,1.75)(6,.7)\qbezier(6,.7)(6.5,1.2)(7,.7) \put(-0.1,0){$1$}\put(.9,0){$2$}\put(1.9,0){$3$}\put(2.9,0){$4$}\put(3.9,0){$5$} \put(4.8,0){$6$}\put(5.9,0){$7$}\put(6.9,0){$8$}\put(7.8,0){$9$}\put(8.75,0){$10$} \put(9.75,0){$11$} \end{picture} \caption{The linked partition corresponding to the permutation tableau in Figure \ref{PT}.}\label{PTlp} \end{center} \end{figure} The bijection $\phi$ has the following properties. \begin{corollary} For $n\geq 1$, let $\tau$ be a linked partition of $[n]$, and let $T=\phi(\tau)$. Then the number of arcs in the linear representation of $\tau$ is equal to the total number of topmost $1$'s and rightmost restricted $0$'s in $T$. \end{corollary} \begin{corollary} Assume that $n\geq 2$. \begin{itemize} \item[(1)] For $0\leq k \leq n-2$, the number of linked partitions of $[n]$ with $k$ transients equals the number of permutation tableaux of length $n$ with $k$ rightmost restricted $0$'s; \item[(2)] For $0\leq k \leq n$, the number of linked partitions of $[n]$ with $k$ singletons equals the number of permutation tableaux of length $n$ in which there are $k$ rows that do not contain any topmost $1$ or restricted $0$. \end{itemize} \end{corollary} To conclude this section, we remark that the bijections $\varphi$ and $\phi$ lead to some known results on permutation tableaux. Recall that $P(n,k)$ denotes the set of permutations of $[n]$ with $k$ descents and $T(n,k)$ denotes the set of permutation tableaux of length $n$ with $k$ rows. Let $P'(n,k)$ be the set of permutations of $[n]$ with $k$ excedances, and $T'(n,k)$ be the set of permutation tableaux of length $n$ with $k$ columns. On one hand, since $|P(n,k-1)|=|P(n,n-k)|$, we see that $|T(n,k)|=|P(n,n-k)|$, which is equivalent to the relation $|T'(n,k)|=|P(n,k)|$ given by Corteel and Nadeau \cite{CorNad09}. On the other hand, it is well-known that $|P(n,k-1)|=|P'(n,k)|$, see, for example, Stanley \cite[Chapter 1]{Stanbook}. This implies the relation $|T(n,k)|=|P'(n,k)|$ proved by Steingr\'{i}msson and Williams \cite{SteWil07}. \section{Pattern avoiding permutation tableaux} In this section, we discuss restrictions of the bijection $\phi$ in Section \ref{section3} to noncrossing linked partitions and nonnesting linked partitions, and we characterize the corresponding permutation tableaux by pattern avoidance. We introduce two patterns $I_2$ and $J_2$ as given in Figure \ref{pattern}, where a dot means a topmost $1$ or a rightmost restricted $0$ in a permutation tableau. We choose $I_2$ and $J_2$ to denote these two patterns because $I_t$ and $J_t$ are used to stand for a diagonal chain of length $t$ and an antidiagonal chain of length $t$ in the context of fillings of Ferrers diagrams, see de Mier \cite{DeM07}. \begin{figure}[h] \setlength{\unitlength}{0.13cm} \begin{center} \begin{picture}(20,22) \put(3,7){\thicklines \begin{picture}(0,0) \hspace*{-3cm} %%画竖线 \put(0,0){\line(0,1){17}}\put(5,0){\line(0,1){17}}\put(14,0){\line(0,1){17}} \put(19,0){\line(0,1){17}} %%画横线 \put(0,0){\line(1,0){19}}\put(0,5){\line(1,0){19}}\put(0,12){\line(1,0){19}} \put(0,17){\line(1,0){19}} %%画圆点和星号 \put(2.4,14.2){\circle*{1.1}}\put(16.4,2.2){\circle*{1.1}} \put(8,-7.3){$I_2$} %%画省略号 \put(2.3,7){$\vdots$}\put(16.2,7){$\vdots$}\put(7.5,8.1){$\cdots$} \put(7.5,2.1){$\cdots$}\put(7.5,14.3){$\cdots$} %%写标号ij \put(0.8,-2.8){$j_2$}\put(16,-2.8){$j_1$}\put(19.4,1){$i_2$}\put(19.4,14){$i_1$} \hspace*{5cm} \put(0,0){\line(0,1){17}}\put(5,0){\line(0,1){17}}\put(14,0){\line(0,1){17}} \put(19,0){\line(0,1){17}} %%画横线 \put(0,0){\line(1,0){19}}\put(0,5){\line(1,0){19}}\put(0,12){\line(1,0){19}} \put(0,17){\line(1,0){19}} %%画圆点和星号 \put(16.4,14.2){\circle*{1.1}} \put(2.4,2.2){\circle*{1.1}} \put(8,-7.3){$J_2$} %%画省略号 \put(2.3,7){$\vdots$}\put(16.2,7){$\vdots$}\put(7.5,8.1){$\cdots$} \put(7.5,2.1){$\cdots$}\put(7.5,14.3){$\cdots$} %%写标号ij \put(0.8,-2.8){$j_2$}\put(16,-2.8){$j_1$}\put(19.4,1){$i_2$} \put(19.4,14){$i_1$} \end{picture} }\end{picture} \caption{Patterns $I_2$ and $J_2$.}\label{pattern} \end{center} \end{figure} A permutation tableau that avoids the pattern $I_2$ or the pattern $J_2$ can be defined as follows. Let $T$ be a permutation tableau, and let $T'$ be the permutation tableau obtained from $T$ by replacing the topmost $1$'s and rightmost restricted $0$'s by dots and removing all other $1$'s and $0$'s. We say that $T$ avoids the pattern $I_2$ if $T'$ does not contain four cells $(i_1,j_1)$, $(i_1,j_2)$, $(i_2,j_1)$ and $(i_2,j_2)$, where $i_1