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]
Preview
 Text. Filename: Kitaev_Zhang_DAM_2023_Non_overlapping_descents_and_ascents_in_stack_sortable_permutations.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (740kB)| Preview

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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Zhang, Philip B.;
  • 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:17 Nov 2024 01:37
    URI:https://strathprints.strath.ac.uk/id/eprint/87088
CORE (COnnecting REpositories)