Recurrence formula for the Eulerian and derangement polynomial

Question

For the Eulerian polynomial $$A_n(x)=\sum_{\pi\in S_n}x^{\mathrm{des}(\pi)}$$ it is well known, that we have the nice recurrence formula $$A_n(x)=\sum_{k=0}^{n-1}\binom{n}{k}A_k(x)(x-1)^{n-1-k}.$$ I would like to prove a similar formula for the derangement polynomial $$d_n(x)=\sum_{\pi\in \mathcal{D}_n}x^{\mathrm{exc}(\pi)},$$ where $\mathcal{D}_n$ is the set of derangements, i.e. permutations without a fixed point and $\mathrm{exc}$ is the number of excedances, i.e. positions with $\pi(i)>i$.

My question: Is there a combinatorial and constructive proof for the recurrence formula for the Eulerian polynomial? Especially, I am looking for a map $S_i\to S_n$ which gives us the right multiplicities (and hopefully also works for the derangements).

All the literature I found so far (for example Petersen's new book on Eulerian numbers) only works with the function and some other recurrences itself to get to this recurrence. Maybe something similar would be possible for $d_n(x)$ but a combinatorial way is preferred.

To prove the recurrence from the polynomial itself (i.e. by analytic methods) Petersen is using the identity $$A_n(x)=(1-x)^{n+1}\sum_{k\geq0}(k+1)^n x^k.$$ Is there a similar formula known for $d_n(x)$?

Thanks!

Richard

Answer 1

Actually, I found a recurrence formula and we proved it indirectly in our paper (https://link.springer.com/article/10.1007/s00454-018-9986-z) and I proved in pure combinatorial terms in my thesis (https://osnadocs.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-2017091316258?mode=full&locale=en)

The formula states $$ d_n(x)=\sum_{k=0}^{n-2}\binom{n}{k}d_k(x)(x+\dots+x^{n-1-k}). $$

Answer 2

I don't know whether this question is still of interest, but I just spotted a recurrence formula for the derangement polynomial in "On derangement polynomials of type B. II" by Chak-On Chow, Journal of Combinatorial Theory, Series A, 116 (2009) 816–830. It involves a derivative and a subtraction, so it may not be what the OP would like. It reads $$d_{n+1}(q) = nq\left(d_n(q) + d_{n−1}(q)\right) + q(1 − q)d_n ^\prime (q)$$ for $n>1$, with $d_0(q) := 1$ and $d_1(q) := 0$. There are some references given for this to papers of Zhang which I cannot find online.

Answer 3

To add to Balazs' answer, the paper 'Exceedingly Deranging' by Mantaci and Rakatondrajao gives interesting results about this particular polynomial.

The coefficients $d_{n,k}$ of this polynomial, which is the no. of derangements with $k$ excedances, satisfy $$d_{n,k}=(n − 1)d_{n−2,k−1} + (n − k)d_{n−1,k−1} + kd_{n−1,k}.$$

Some of the other results in the paper include the fascinating $$i_{n,k}-p_{n,k}=(-1)^n$$ where $i_{n,k},p_{n,k}$ are the no. of odd and even derangements in $\mathcal{D}_n$ with $k$ excedance respectively.

The polynomial $d_n(x)=\sum_{\pi\in \mathcal{D}_n}x^{\mathrm{exc}(\pi)}$ is pretty well studied now. There are various results now about the $q$-analogue of this polynomial $d_n(x,q)=\sum_{\pi\in \mathcal{D}_n}x^{\mathrm{exc}(\pi)}q^{\mathrm{maj}-\mathrm{exc}(\pi)}.$ These can be found in Shareshian and Wachs's 'Eulerian quasi-symmetric functions','Chromatic quasisymmetric functions'.

The three variable distributions $(\mathrm{fix},\mathrm{exc},\mathrm{maj}), (\mathrm{pix},\mathrm{lec},\mathrm{inv}),(\mathrm{rix},\mathrm{des},\mathrm{aid})$ are all equidistributed on the Symmetric group $\mathfrak{S}_n$