Non-overlapping descents and ascents in stack-sortable permutations

Kitaev, Sergey and Zhang, Philip B. (2024) Non-overlapping descents and ascents in stack-sortable permutations. Discrete Applied Mathematics, 344. pp. 112-119. ISSN 0166-218X (

[thumbnail of Kitaev-Zhang-DAM-2023-Non-overlapping-descents-and-ascents-in-stack-sortable-permutations] Text. Filename: Kitaev_Zhang_DAM_2023_Non_overlapping_descents_and_ascents_in_stack_sortable_permutations.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 16 November 2024.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (740kB) | Request a copy


The Eulerian polynomials An(x) give the distribution of descents over permutations. It is also known that the distribution of descents over stack-sortable permutations (i.e. permutations sortable by a certain algorithm whose internal storage is limited to a single stack data structure) is given by the Narayana numbers 1/n(n k)(n k+1) . On the other hand, as a corollary of a much more general result, the distribution of the statistic “maximum number of non-overlapping descents”, MND, over all permutations is given by ∑ n,k≥0 Dn,kxk tn/n! = et /1−x(1+(t−1)et) . In this paper, we show that the distribution of MND over stack-sortable permutations is given by 1/n+1 ( n+1 2k+1)(n+k k ) . We give two proofs of the result via bijections with rooted plane (binary) trees allowing us to control MND. Moreover, we show combinatorially that MND is equidistributed with the statistic MNA, the maximum number of non-overlapping ascents, over stack-sortable permutations. The last fact is obtained by establishing an involution on stack-sortable permutations that gives equidistribution of 8 statistics.