Permutation Tableaux and the Dashed Permutation Pattern 32–1

William Y.C. Chen, Lewis H. Liu

Abstract


We give a solution to a problem posed by Corteel and Nadeau concerning permutation tableaux of length $n$ and the number of occurrences of the dashed pattern 32–1 in permutations on $[n]$. We introduce the inversion number of a permutation tableau. For a permutation tableau $T$ and the permutation $\pi$ obtained from $T$ by the bijection of Corteel and Nadeau, we show that the inversion number of $T$ equals the number of occurrences of the dashed pattern 32–1 in the reverse complement of $\pi$. We also show that permutation tableaux without inversions coincide with L-Bell tableaux introduced by Corteel and Nadeau.


Full Text: PDF