  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 $(\sigma_1,\sigma_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}$.
