Distribution of the inversion statistic on run-sorted permutations
Abstract
Let π=π1⋯ πn be a permutation. We say that π is run-sorted if π1=1 and the entries immediately following the descent positions of π form an increasing sequence. Let ℛn denote the set of run-sorted permutations of length n, which has cardinality given by the Bell number Bn−1 for all n ≥ 1. In this paper, we consider the joint distribution An(q,u) on ℛn for the parameters tracking the numbers of inversions and runs leading to a new polynomial generalization of the Bell numbers. Among our results, we find a general recurrence for An(q,u), from which one may derive explicit formulas for the total numbers of inversions or runs in all the members of ℛn as well as for the sign-balance on ℛn of either parameter. A simple expression for the Eulerian generating function for An(q,1) may be found upon making use of Gessel's q-exponential formula which can be extended to general u. Finally, a formula is found by a direct argument for the maximum number of inversions within a member of ℛn.
Related
- Inversion-descent enumerators of underline321-avoiding permutations
- Residual structure and growing inversion-monotonicity regions for 1324-avoiding permutations
- The Distribution of Double Deficiencies in Pattern-Avoiding Permutations
- Stochastic Inversion of Multivariate Uniform-Distribution-Preserving Transformations
- Sorted Mutability as an Entropic Functional: Theory and Two Applications
BibTeX
@misc{mansour2026distribution,
title = {{Distribution of the inversion statistic on run-sorted permutations}},
author = {Toufik Mansour and Olivia Nabawanda and Mark Shattuck},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28674},
eprint = {2609.28674},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28674},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Distribution of the inversion statistic on run-sorted permutations
AU - Toufik Mansour
AU - Olivia Nabawanda
AU - Mark Shattuck
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28674
UR - https://arxiv.org/abs/2609.28674
AB - Let π=π_1⋯ π_n be a permutation. We say that π is run-sorted if π_1=1 and the entries immediately following the descent positions of π form an increasing sequence. Let ℛ_n denote the set of run-sorted permutations of length n, which has cardinality given by the Bell number B_n−1 for all n ≥ 1. In this paper, we consider the joint distribution A_n(q,u) on ℛ_n for the parameters tracking the numbers of inversions and runs leading to a new polynomial generalization of the Bell numbers. Among our results, we find a general recurrence for A_n(q,u), from which one may derive explicit formulas for the total numbers of inversions or runs in all the members of ℛ_n as well as for the sign-balance on ℛ_n of either parameter. A simple expression for the Eulerian generating function for A_n(q,1) may be found upon making use of Gessel's q-exponential formula which can be extended to general u. Finally, a formula is found by a direct argument for the maximum number of inversions within a member of ℛ_n.
ER -