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]=\{1,2,\ldots,n\}$. 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.
['William Y. C. Chen', 'Lewis H. Liu', 'Carol J. Wang']
Linked Partitions and Permutation Tableaux