132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers Original Research Article

We describe the recursive structures of the set of two-stack sortable permutations which avoid 132 and the set of two-stack sortable permutations which contain 132 exactly once. Using these results and standard generating function techniques, we enumerate two-stack sortable permutations which avoid (or contain exactly once) 132 and which avoid (or contain exactly once) an arbitrary permutation τ. In most cases the number of such permutations is given by a simple formula involving Fibonacci or Pell numbers.