Permuted composition tableaux, 0-Hecke algebra and labeled binary trees

We introduce a generalization of semistandard composition tableaux called permuted composition tableaux. These tableaux are intimately related to permuted basement semistandard augmented fillings studied by Haglund, Mason and Remmel. Our primary motivation for studying permuted composition tableaux is to enumerate all possible ordered pairs of permutations (σ1,σ2) that can be obtained by standardizing the entries in two adjacent columns of an arbitrary composition tableau. We refer to such pairs as compatible pairs. To study compatible pairs in depth, we define a 0-Hecke action on permuted composition tableaux. This action naturally defines an equivalence relation on these tableaux. Certain distinguished representatives of the resulting equivalence classes in the special case of two-columned tableaux are in bijection with compatible pairs. We provide a bijection between two-columned tableaux and labeled binary trees. This bijection maps a quadruple of descent statistics for 2-columned tableaux to left and right ascent-descent statistics on labeled binary trees introduced by Gessel, and we use it to prove that the number of compatible pairs is (n+1)n−1.