Permutations with a Given X-Descent Set

Abstract

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\subseteq {\mathbb{N}}^2$, and $I\subseteq [n-1]$, we study the permutations $\ddot{I}€\in {\mathfrak{S}}_n$ whose $X$-descent set is precisely $I$, meaning $(\ddot{I}{€}_i,\ddot{I}{€}_{i+1})\in X$ precisely when $i\in I$. The central focus is enumerating these permutations for a fixed $X,I$ and $n$: this count is denoted by $d_X(I;n)$. We derive a recursion which under expected conditions simplifies to a binomial-type recurrence determined entirely by the values $d_X(\varnothing ;n)$. This extends the work of Díaz-Lopez et al.\ on descent polynomials. The resulting reduction shows that the general statistic $d_X(I;n)$ is typically governed by the ``descent-free'' quantities $d_X(\varnothing ;n)$, motivating a closer analysis of these numbers. We observe that $d_X(\varnothing ;n)$ enumerates Hamiltonian paths in a directed graph canonically associated to $X$. We then record several families of sets $X$ for which $d_X(\varnothing ;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 $d_X(\varnothing ;n)$ from a probabilistic perspective.

14 pages