Stack sortable permutations

AbstractThe class SSn of stack sortable permutations is known to be in 1-1 correspondence with the set of n-noded binary trees. We use this correspondence to show that many properties of a binary tree are related to different types of monotonic subsequences in the corresponding permutation. Expressions are derived for the average length of these subsequences over the class SSn. Also, it is shown that SSn is directly related to special types of interval and comparability graphs