Counting permutations with a fixed number of descents and an extra condition

Question

I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.

Determine the number of permutations $\sigma\in \mathfrak{S}_{n}$ such that $\sigma$ has exactly $k$ descents and such that in the segment $\sigma_1\sigma_2\cdots\sigma_s$ there are at most $t$ descents.

A clarification: a descent in a permutation $\sigma\in \mathfrak{S}_n$ is an index $i\in [n-1]$ such that $\sigma_i > \sigma_{i+1}$.

At first glance one can think of "choosing" the first $s$ numbers for $\sigma$ (inline notation) and counting in how many ways one can reorder them so that there are $0\leq j\leq t$ descents in that part, and then order the remaining $n-s$ numbers producing $k-j$ descents. Namely, do something like $$ \sum_{j=0}^t \binom{n}{s} A_{s,j} A_{n-s,t-j},$$ where $A_{n,k} = \#\{\sigma\in \mathfrak{S}_n : \operatorname{des}(\sigma) = k\}$ is the classical Eulerian number.

This, however, does not work because we lose track of how the numbers $\sigma_s$ and $\sigma_{s+1}$ compare (that could introduce an extra descent).

By pretending a "closed formula" I intend a (possibly multiple) sum of products of binomial, Stirling and Eulerian numbers.

Answer 1

This question requires a refinement of Eulerian numbers. Namely, let $A_{n,k,\ell}$ be the number of permutations of order $n$ with $k$ descents and ending in element $\ell$. Under subtracting each element of a permutation from $n+1$, we get a property $A_{n,k,\ell}=A_{n,n-1-k,n+1-\ell}$. Similarly, denoting by $A'_{n,k,\ell}$ the number of permutations of order $n$ with $k$ descents and starting with element $\ell$, we have $A'_{n,k,\ell} = A_{n,n-1-k,\ell}$ (by reading permutations backwards).

Then an answer to the question can be given by the following formula: $$\sum_{j=0}^t \sum_{\ell=1}^n \sum_{f=\ell+1}^n \sum_{u+v+w=s-1} \binom{\ell-1}u\binom{f-\ell-1}v\binom{n-f}w A_{s,j,u+1} A'_{n-s,k-j,f-1-u-v}$$ $$+\sum_{j=0}^t \sum_{\ell=1}^n \sum_{f=1}^{\ell-1} \sum_{u+v+w=s-1} \binom{f-1}u\binom{\ell-f-1}v\binom{n-\ell}w A_{s,j,u+v+1} A'_{n-s,k-j-1,f-u},$$ where $\ell$ stands for $\sigma_s$, $f$ stands for $\sigma_{s+1}$, and $u,v,w$ are the number of elements of $\sigma_1,\dots,\sigma_{s-1}$ in each of the three subintervals of $[1,n]$ obtained by removal of $\ell$ and $f$. As explained above, we have $$A'_{n-s,k-j,f-1-u-v} = A_{n-s,n-s-1-(k-j),f-1-u-v} = A_{n-s,k-j,n+1-f-w}$$ and $$A'_{n-s,k-j-1,f-u} = A_{n-s,n-s-1-(k-j-1),f-u} = A_{n-s,k-j-1,n-s+1-f+u}.$$ So, it now amounts to having a formula for $A_{n,k,\ell}$.

---

First, we have a recurrence formula for $n\geq\ell>1$: $$A_{n,k,\ell} = A_{n,k,\ell-1} + A_{n-1,k,\ell-1} - A_{n-1,k-1,\ell-1},$$ which translated into a linear first-order ODE: $$(1-z)\frac{\partial}{\partial x} F(x,y,z) = z(1-y)F(x,y,z) + yz\frac{y-1}{y - e^{(y-1)x}} - z^2 \frac{y-1}{y - e^{(y-1)xz}}$$ for the generating function: $$F(x,y,z) := \sum_{n,k,\ell\geq 0} A_{n,k,\ell}\frac{x^n}{n!} y^k z^\ell.$$ From its solution, we obtain the following formula: $$A_{n,k,\ell} = \begin{cases} \left\langle n-1\atop k\right\rangle & \text{if }\ell=n\\ (-1)^n \sum\limits_{j=1}^n (-1)^j j^{n-\ell} (j-1)^{\ell-1} \bigg( (-1)^k\binom{n}{k+j} - \binom{n}j\bigg) & \text{if }\ell < n. \end{cases} $$