Bijections and enumeration Stack-sortable permutation

bijection between binary trees (with nodes numbered left-to-right) , stack-sortable permutations, generated listing same node numbers in preorder

stack-sortable permutations may translated directly , (unlabeled) binary trees, combinatorial class counting function sequence of catalan numbers. binary tree may transformed stack-sortable permutation numbering nodes in left-to-right order, , listing these numbers in order visited preorder traversal of tree: root first, left subtree, right subtree, continuing recursively within each subtree. in reverse direction, stack-sortable permutation may decoded tree in first value x of permutation corresponds root of tree, next x − 1 values decoded recursively give left child of root, , remaining values again decoded recursively give right child.

several other classes of permutations may placed in bijection stack-sortable permutations. instance, permutations avoid patterns 132, 213, , 312 may formed respectively stack-sortable (231-avoiding) permutations reversing permutation, replacing each value x in permutation n + 1 − x, or both operations combined. 312-avoiding permutations inverses of 231-avoiding permutations, , have been called stack-realizable permutations permutations can formed identity permutation sequence of push-from-input , pop-to-output operations on stack.

as knuth (1968) noted, 123-avoiding , 321-avoiding permutations have same counting function despite being less directly related stack-sortable permutations.