The structure of alternative tableaux (Q533344): Difference between revisions

A \textit{shape} is a Ferrers diagram with possibly empty rows or columns. An \textit{alternative tableau} (introduced by Xavier Viennot) is a shape with a partial filling of the cells with left arrows (\(\leftarrow\)) and up arrows (\(\uparrow\)), such that all cells pointed to by an arrow are empty. A \textit{permutation tableau} (introduced by A. Postnikov) is a shape with every cell filled by 0 or 1 so that {\parindent=6mm \begin{itemize}\item[(i)]each column contains at least one 1; and \item[(ii)]no cell filled by a 0 has simultaneously a 1 above it in the same column, and a 1 to its left in the same row. \end{itemize}} From the author's abstract: ``We exhibit a simple recursive structure for alternative tableaux, from which we can easily deduce a number of enumerative results. We also give bijections between these tableaux and certain classes of labelled trees. Finally, we exhibit a bijection with permutations and relate it to some other bijections that (have) already appeared in the literature.'' The author notes that \textit{A. Burstein} [``On some properties of permutation tableaux'', Ann.\ Comb.\ 11, No.\ 3--4, 355--368 (2007; Zbl 1141.05002)] has ``previously arrived at essentially the same forest structure that results from our decomposition.''