132-avoiding Two-stack Sortable Permutations, Fibonacci Numbers, and Pell Numbers
Abstract
Description
In 1990 West conjectured that there are $2(3n)!/((n+1)!(2n+1)!)$ two-stack sortable permutations on $n$ letters. This conjecture was proved analytically by Zeilberger in 1992. Later, Dulucq, Gire, and Guibert gave a combinatorial proof of this conjecture. In the present paper we study generating functions for the number of two-stack sortable permutations on $n$ letters avoiding (or containing exactly once) 132 and avoiding (or containing exactly once) an arbitrary permutation $τ$ on $k$ letters. In several interesting cases this generating function can be expressed in terms of the generating function for the Fibonacci numbers or the generating function for the Pell numbers.
17 pages
17 pages