Minimal permutations with dd descents

Recently, Bouvel and Pergola initiated the study of a special class of permutations, minimal permutations with a given number of descents, which arise from the whole genome duplication–random loss model of genome rearrangement. In this paper, we show that the number of minimal permutations of length 2d−12d−1 with dd descents is given by 2d−3(d−1)cd2d−3(d−1)cd, where cdcd is the dd-th Catalan number. For fixed nn, we also derive a recurrence relation on the multivariate generating function for the number of minimal permutations of length nn counted by the number of descents, and the values of the first and second elements of the permutation. For fixed dd, on the basis of this recurrence relation, we obtain a recurrence relation on the multivariate generating function for the number of minimal permutations of length nn with n−dn−d descents, counted by the length, and the values of the first and second elements of the permutation. As a consequence, the explicit generating functions for the numbers of minimal permutations of length nn with n−dn−d descents are obtained for d≤5d≤5. Furthermore, we show that for fixed d≥1d≥1, there exists a constant adad such that the number of minimal permutations of length nn with n−dn−d descents is asymptotically equivalent to addnaddn, as n→∞n→∞.