Generating trees and the Catalan and Schröder numbers Original Research Article

A permutation π ϵ Sn avoids the subpattern τ iff π has no subsequence having all the same pairwise comparisons as τ, and we write π ϵ Sn(τ). We present a new bijective proof of the well-known result that /vbSn(123)/vb = /vbSn(132)/vb = cn, 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 /vbSn(3142,2413)/vb = sn -1, the Schröder number, and characterize the deque-sortable permutations of Knuth, also counted by sn - 1.