Multi-Statistic Enumeration of Two-Stack Sortable Permutations

Using Zeilberger's factorization of two-stack-sortable permutations, we write a functional equation --- of a strange sort --- that defines their generating function according to five statistics: length, number of descents, number of right-to-left and left-to-right maxima, and a fifth statistic that is closely linked to the factorization. Then, we show how one can translate this functional equation into a polynomial one. We thus prove that our five-variable generating function for two-stack-sortable permutations is algebraic of degree 20. 1 Introduction The aim of this paper is twofold. Our first intention is to draw attention on the factorization of two-stacksortable permutations described by Zeilberger in [22]. Among other advantages, this factorization preserves many standard statistics defined on permutations, and hence, constitutes an efficient first step for their enumeration. We thus obtain a functional equation --- of a strange kind --- that defines a five-variable generating f..