GENERATING TREES AND THE CATALAN AND SCHRODER NUMBERS

A permutation pi is an element of S-n avoids the subpattern tau iff pi has no subsequence having ail the same pairwise comparisons as tau, and we write pi is an element of S-n((t)au). We present a new bijective proof of the well-known result that \S-n(123)\ = \S-n(132)\ = c(n), the nth Catalan number. A generalization to forbidden patterns of length 4 gives an asymptotic formula for the vexillary permutations. We settle a conjecture of Shapiro and Getu that \S-n(3142, 2413)\ = s(n-1), the Schroder number, and characterize the deque-sortable permutations of Knuth, also counted by s(n-1).