Permutation Tableaux, Restricted Set Partitions and Labeled Dyck Paths

Abstract

Permutation tableaux were introduced in the study of totally positive Grassmannian cells, and are connected with the steady state of asymmetric exclusion process, which is an important model from statistical mechanics. In this paper, we firstly establish a shape-preserving involution on the set of permutation tableaux of length $n$, which directly shows that the number of permutation tableaux of length $n$ with $k$ essential 1’s equals the number of permutation tableaux of length $n$ with $n-k$ unrestricted rows. In addition, we introduce three combinatorial structures, called free permutation tableaux, restricted set partitions, and labeled Dyck paths. We discuss the properties of their internal structures and present the correspondence between the set of free permutation tableaux of length $n$ and the set of restricted set partitions of $\{1,2,\dots ,n\}$, and we also give a bijection between the set of restricted set partitions of $\{1,2,\dots ,n\}$ and the set of labeled Dyck paths of length $2n$. Finally, we make a generalization of the latter bijection.