2-stack sortable permutations with a given number of runs

Miklós Bóna

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 wi…