Permutations with a Given X-Descent Set

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 $\pi \in \mathfrak{S}_n$ whose $X$-descent set is precisely $I$, meaning $(\pi_i,\pi_{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(\emptyset;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(\emptyset;n)$, motivating a closer analysis of these numbers.

We observe that $d_X(\emptyset;n)$ enumerates Hamiltonian paths in a directed graph canonically associated to $X$.

We then record several families of sets $X$ for which $d_X(\emptyset;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(\emptyset;n)$ from a probabilistic perspective.