2-stack sortable permutations with a given number of runs

1997/05/16 by Miklós Bóna, Bóna, Miklós
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.math/9705220

arxiv created 1997/05/16 · arxiv updated 2009/11/30

Abstract

Using earlier results we prove a formula for the number W_(n,k) of 2-stack sortable permutations of length n with k runs, or in other words, k-1 descents. This formula will yield the suprising fact that there are as many 2-stack sortable permutations with k-1 descents as with k-1 ascents. We also prove that W_(n,k) is unimodal in k, for any fixed n.

Related

• Generalizations of two-stack-sortable permutations
• Permutations sortable by n-4 passes through a stack
• Counting 3-Stack-Sortable Permutations
• 2-stack pushall sortable permutations
• Passing through a stack k times