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 (https://doi.org/10.1016/j.dam.2023.11.020)

[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

Abstract

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.

  • Item type:Article
    ID code:87088
    Dates:
    Date
    Event
    15 February 2024
    Published
    16 November 2023
    Published Online
    26 October 2023
    Accepted
    18 July 2023
    Submitted
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:27 Oct 2023 11:23
    Last modified:09 Apr 2024 04:24
    URI:https://strathprints.strath.ac.uk/id/eprint/87088
CORE (COnnecting REpositories)