2024/02/16 by Mohamed Omar, Omar, Mohamed
Computer Science · Engineering · #05A05 #05A15 #05C20 #Advanced Algebra and Logic #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2402.10443
openalex publication_date 2024/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Building on the work of Grinberg and Stanley, we begin a systematic study of permutations with a prescribed X-descent set. In particular, for a set X ⊆ ℕ2, and I ⊆ [n-1], we study the permutations π∈ \mathfrakSn whose X-descent set is precisely I, meaning (πi,πi+1) ∈ X precisely when i ∈ I. The central focus is enumerating these permutations for a fixed X,I and n: this count is denoted by dX(I;n). We derive a recursion which under expected conditions simplifies to a binomial-type recurrence determined entirely by the values dX(∅;n). This extends the work of Díaz-Lopez et al. on descent polynomials. The resulting reduction shows that the general statistic dX(I;n) is typically governed by the ``descent-free'' quantities dX(∅;n), motivating a closer analysis of these numbers. We observe that dX(∅;n) enumerates Hamiltonian paths in a directed graph canonically associated to X. We then record several families of sets X for which dX(∅;n) is explicit or effectively computable. This includes families with periodicity for which transfer matrix methods apply, and families with succession-type relations where inclusion-exclusion applies. We then investigate the typical behavior of dX(∅;n) from a probabilistic perspective.