% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments %\usepackage{showkeys} \newtheorem{example}{Example} \newtheorem{Definition}{Definition} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}{Claim} %\newtheorem{remark}{Remark} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{Conjecture}[theorem]{Conjecture} \newtheorem{Problem}[theorem]{Problem} \theoremstyle{definition} \newtheorem{remark}{Remark} \usepackage{amsthm,amsmath,amssymb,url,cite,color} \def\blue{\textcolor{blue}} \def\red{\textcolor{red}} \def\green{\textcolor{green}} %\theoremstyle{definition} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{xca}[theorem]{Exercise} %\theoremstyle{remark} %\newtheorem{remark}[theorem]{Remark} \newenvironment{demo}[1]{% \trivlist \item[\hskip\labelsep {\bf #1.}] }{% \hfill\qedsymbol \endtrivlist } \numberwithin{equation}{section} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\blankbox}[2]{ \parbox{\columnwidth}{\centering \setlength{\fboxsep}{0pt} \fbox{\raisebox{0pt}[#2]{\hspace{#1}}} } } \def\des{\mathrm{des}} \def\ides{\mathrm{ides}} \def\Des{\mathrm{DES}} \def\S{\mathfrak{S}} \def\I{\mathfrak{I}} \def\R{\mathcal{R}} \def\DE{\mathcal{E}} \def\W{\mathcal{W}} \def\dec{\mathrm{dec}} \def\B{\mathfrak{B}} \def\N{\mathbb N} \def\Z{\mathbb Z} \def\Q{\mathbb Q} \def\C{\mathbb C} \def\A{\mathfrak{A}} \def\D{\mathfrak{D}} \def\T{\mathcal{T}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{Proof of Gessel's $\gamma$-positivity conjecture} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Zhicong Lin\\ \small School of Science, Jimei University\\[-0.8ex] \small Xiamen 361021, P.R. China\\ \small CAMP, National Institute for Mathematical Sciences\\[-0.8ex] \small Daejeon 305-811, Republic of Korea\\ \small\tt lin@nims.re.kr\\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{December 17, 2015}{}\\ \small Mathematics Subject Classifications: 05A05, 05A19} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We prove a conjecture of Gessel, which asserts that the joint distribution of descents and inverse descents on permutations has a fascinating refined $\gamma$-positivity. % keywords are optional \bigskip\noindent \textbf{Keywords:} descents; inverse descents; Eulerian polynomials; $\gamma$-positivity \end{abstract} \section{Introduction} Let $\S_n$ denote the set of all permutations of $[n]:=\{1,2,\ldots,n\}$. A permutation $\pi\in\S_n$ will be represented here in one line notation as $\pi=\pi_1\cdots\pi_n$. For a permutation $\pi\in\S_n$, an index $i\in[n-1]$ is a {\em descent} of $\pi$ if $\pi_i>\pi_{i+1}$. Denote by $\des(\pi)$ the number of descents of $\pi$. The descent polynomial on $\S_n$ $$ A_n(t):=\sum_{\pi\in\S_n}t^{\des(\pi)+1} $$ is known as the classical {\em Eulerian polynomial} (cf.~\cite[Section~1.3]{st}) of order $n$. Foata and Sch\"utzenberger~\cite{fs} proved the following beautiful $\gamma$-positivity result, which implies the {\em symmetry} and {\em unimodality} (see~\cite{br2} for definitions) of the Eulerian polynomials. \begin{theorem}[Foata--Sch\"utzenberger] For $n\geq1$, \begin{equation}\label{gam:posi} A_n(t)=\sum_{i=1}^{\lfloor(n+1)/2\rfloor}\gamma_{n,i}t^i(1+t)^{n+1-2i}, \end{equation} where $\gamma_{n,i}$ are nonnegative integers. \end{theorem} Foata and Strehl~\cite{fsh} later constructed an elegant combinatorial proof of~\eqref{gam:posi} via a group action, which has sparked various interesting extensions~\cite{br,chow,dps,lz}. For many other $\gamma$-positivity results and problems arising in enumerative and geometric combinatorics, we refer the reader to the excellent exposition by Petersen~\cite{pe2}. Regarding the joint distribution of descents and inverse descents on permutations, Gessel (see~\cite{br,br2,pe,vi}) has conjectured the following refined $\gamma$-positivity: \begin{Conjecture}[Gessel 2005] \label{gessel} Let \begin{equation*}\label{des:ides} A_n(s,t):=\sum_{\pi\in\S_n}s^{\des(\pi^{-1})+1}t^{\des(\pi)+1}. \end{equation*} Then, for $n\geq1$ \begin{equation}\label{2D-gam} A_n(s,t)=\sum_{i\geq1, j\geq0\atop j+2i\leq n+1}\gamma_{n,i,j}(st)^i(1+st)^{j}(s+t)^{n+1-j-2i}, \end{equation} where $\gamma_{n,i,j}$ are nonnegative integers. \end{Conjecture} These refined Eulerian polynomials $A_n(s,t)$, that we shall call {\em double Eulerian polynomials}, were first studied by Carlitz, Roselle and Scoville~\cite{car}. Conjecture~\ref{gessel} has received considerable attention since the publication of Br\"and\'en~\cite{br} in 2008. The existence of integers $\gamma_{n,i,j}$ satisfying~\eqref{2D-gam} follows from symmetry properties of $A_n(s,t)$ and Lemma~\ref{fund:dou}. The open problem is nonnegativity. For example, we have: \begin{align*} &A_1(s,t)=st,\\ &A_2(s,t)=st(1+st),\\ &A_3(s,t)=st(1+st)^2+2(st)^2,\\ &A_4(s,t)=st(1+st)^3+7(st)^2(1+st)+(st)^2(s+t),\\ &A_5(s,t)=st(1+st)^4+16(st)^2(1+st)^2+6(st)^2(1+st)(s+t)+16(st)^3. \end{align*} In this note, we give a proof of Conjecture~\ref{gessel}. Using Eulerian operators and a homogenized multivariate refinement for $A_n(s,t)$, Visontai~\cite{vi} derived a recurrence for the coefficients $\gamma_{n,i,j}$, from which the nonnegativity does not follow immediately. But surprisingly, we are able to deduce the nonnegativity of $\gamma_{n,i,j}$ from his recurrence. Even more, we characterize completely when the coefficient $\gamma_{n,i,j}$ is positive. Generalizations of Conjecture~\ref{gessel} will also be proved (see Theorems~\ref{gessel:gen} and~\ref{Type:B}). The question of finding a combinatorial proof of expansion~\eqref{2D-gam} is still open. \section{Proof of Conjecture~\ref{gessel}} We shall first provide a new direct approach to the following recurrence relation due to Visontai and then apply it to give a proof of Conjecture~\ref{gessel}. \begin{lemma}[\text{{\bf Theorem~10} of~\cite{vi}}] \label{visontai} Let $n\geq1$. For all $i\geq1$ and $j\geq0$, we have \begin{equation}\label{vison:rec} \begin{split} (n+1)\gamma_{n+1,i,j}&=(n+i(n+2-i-j))\gamma_{n,i,j-1}+(i(i+j)-n)\gamma_{n,i,j}\\ &\quad+(n+4-2i-j)(n+3-2i-j)\gamma_{n,i-1,j-1}\\ &\quad+(n+2i+j)(n+3-2i-j)\gamma_{n,i-1,j}\\ &\quad+(j+1)(2n+2-j)\gamma_{n,i-1,j+1}+(j+1)(j+2)\gamma_{n,i-1,j+2}, \end{split} \end{equation} where $\gamma_{1,1,0}=1$, $\gamma_{1,i,j}=0$ (unless $i=1$ and $j=0$) and $\gamma_{n,i,j}=0$ if $i<1$ or $j<0$. \end{lemma} \begin{proof}We will use the following recurrence of $A_n(s,t)$ computed by Petersen~\cite[Equation (9)]{pe} via the machine of balls in boxes (or 2-D barred permutations): \begin{equation}\label{pe:rec} \begin{split} nA_{n}(s,t)&=(n^2st+(n-1)(1-s)(1-t))A_{n-1}(s,t)\\ &\quad +nst(1-s)\frac{\partial}{\partial s}A_{n-1}(s,t)+nst(1-t)\frac{\partial}{\partial t} A_{n-1}(s,t)\\ &\quad +st(1-s)(1-t)\frac{\partial^2}{\partial s\partial t}A_{n-1}(s,t). \end{split} \end{equation} Let $\Gamma_n(X,Y):=\sum_{i,j}\gamma_{n,i,j}X^iY^j$. Observe that decomposition~\eqref{2D-gam} is equivalent to the following relationship: $$ A_n(s,t)=(s+t)^{n+1}\Gamma_n(X,Y)\qquad\text{with $X=\frac{st}{(s+t)^2}$ and $Y=\frac{1+st}{s+t}$}. $$ Substituting this into~\eqref{pe:rec} and dividing both sides by $(s+t)^{n+1}$, we get \begin{equation}\label{GA:rec} \begin{split} n\Gamma_n(X,Y)&=\alpha_1\Gamma_{n-1}(X,Y)+\alpha_2\frac{\partial \Gamma_{n-1}(X,Y)}{\partial X}+\alpha_3\frac{\partial \Gamma_{n-1}(X,Y)}{\partial Y}\\ &\quad+\alpha_4\frac{\partial^2 \Gamma_{n-1}(X,Y)}{\partial X^2}+\alpha_5\frac{\partial^2 \Gamma_{n-1}(X,Y)}{\partial Y^2}+\alpha_6\frac{\partial^2 \Gamma_{n-1}(X,Y)}{\partial X\partial Y}, \end{split} \end{equation} where \begin{align*} \alpha_1&=\frac{n^2st+(n-1)(1-s)(1-t)}{s+t}+\frac{n^2st(2-s-t)}{(s+t)^2}+\frac{n(n-1)st(1-s)(1-t)}{(s+t)^3}\\ &=(n-1)(Y-1)+n(n-1)XY+(n^2+n)X, \end{align*} \begin{multline*} \alpha_2=\frac{nst}{s+t}\left((1-s)\frac{\partial X}{\partial s}+(1-t)\frac{\partial X}{\partial t}\right)+\frac{nst(1-s)(1-t)}{(s+t)^2}\left(\frac{\partial X}{\partial t}+\frac{\partial X}{\partial s}\right)+\\ +\frac{st(1-s)(1-t)}{s+t}\frac{\partial^2 X}{\partial s\partial t}=(n-1)XY+(6-4n)X^2Y+X-6X^2, \end{multline*} \begin{multline*} \alpha_3=\frac{nst}{s+t}\left((1-s)\frac{\partial Y}{\partial s}+(1-t)\frac{\partial Y}{\partial t}\right)+\frac{nst(1-s)(1-t)}{(s+t)^2}\left(\frac{\partial Y}{\partial t}+\frac{\partial Y}{\partial s}\right)+\\ +\frac{st(1-s)(1-t)}{s+t}\frac{\partial^2 Y}{\partial s\partial t}=(-2n+2)XY^2+2nX-2XY, \end{multline*} \begin{align*} \alpha_4=\frac{st(1-s)(1-t)}{s+t}\frac{\partial X}{\partial s}\frac{\partial X}{\partial t}=4X^3(Y-1)-X^2(Y-1), \end{align*} \begin{align*} \alpha_5=\frac{st(1-s)(1-t)}{s+t}\frac{\partial Y}{\partial s}\frac{\partial Y}{\partial t}=-X(Y-1)+XY^2(Y-1) \end{align*} and \begin{align*} \alpha_6&=\frac{st(1-s)(1-t)}{s+t}\left(\frac{\partial X}{\partial s}\frac{\partial Y}{\partial t}+\frac{\partial Y}{\partial s}\frac{\partial X}{\partial t}\right)=-XY(Y-1)+4X^2Y(Y-1). \end{align*} Extracting the coefficient of $X^iY^j$ in both sides of~\eqref{GA:rec}, we get~\eqref{vison:rec} after shifting the index $n$ by one. \end{proof} The same manipulations above can be applied to deduce the recurrence relations for the $\gamma$-coefficients of two extensions of $A_n(s,t)$ in the next section. It does not follow immediately from recurrence relation~\eqref{vison:rec} that $\gamma_{n+1,i,j}$ is a nonnegative integer: the left-hand side has the multiplicative factor $(n+1)$ and the coefficient $i(i+j)-n$ in the right-hand side may assume negative values. Nevertheless, the crucial observation that $\gamma_{n,i,j}\neq0$ only if when $i(i+j)\geq n$ will lead to the nonnegativity of $\gamma_{n,i,j}$, as stated in the following. \begin{theorem}\label{obser} For $n\geq1$, the coefficients $\gamma_{n,i,j}$ are nonnegative. Moreover, the coefficient $\gamma_{n,i,j}$ is positive if and only if $i\geq1,j\geq0$, $2i+j\leq n+1$ and $i(i+j)\geq n$. \end{theorem} \begin{proof} We will prove this result by induction on $n$ using recurrence relation~\eqref{vison:rec} for the coefficient $\gamma_{n,i,j}$. Clearly, the result is true for $n\leq 5$ by the first formulae produced in the introduction. Suppose that this result is true for some $n$ with $n\geq5$. % , namely, all $\gamma_{n,i,j}$ are nonegative and % $\gamma_{n,i,j}$ is positive if and only if when $i\geq1,j\geq0$, $2i+j\leq n+1$ and $i(i+j)\geq n$. To complete the proof by induction, we need to show that all $\gamma_{n+1,i,j}$ are nonegative and $\gamma_{n+1,i,j}$ is positive if and only if $i\geq1,j\geq0$, $2i+j\leq n+2$ and $i(i+j)\geq n+1$. We need to show the result for $n+1$. We can assume that $i\geq1,j\geq0$ and $2i+j\leq n+2$, otherwise $\gamma_{n+1,i,j}=0$. There are three cases to be considered. {\bf Case~1}: If $i(i+j)= n$, then the inductive hypothesis implies that all $\gamma_{n,i,j-1}$, $\gamma_{n,i-1,j-1}$, $\gamma_{n,i-1,j}$, $\gamma_{n,i-1,j+1}$, $\gamma_{n,i-1,j+1}$, $\gamma_{n,i-1,j+2}$ are $0$ (except $\gamma_{n,i,j}$ may not be zero), since now $$ i(i+j-1)0$. Subcase II: $2i+j= n+2$. In this case, as $$ i(i+j-1)=i(n+1-i)\geq n\quad\text{and}\quad 2i+j-1=n+1, $$ we have $(n+i(n+2-i-j))\gamma_{n,i,j-1}>0$ (again by the inductive hypothesis) in the right-hand side of~\eqref{vison:rec}, and therefore $\gamma_{n+1,i,j}>0$. This ends the proof by induction. \end{proof} For the sake of completeness, we provide a proof of the following fundamental result regarding the basis $$ \mathcal{B}_n:=\{(st)^i(1+st)^j(s+t)^{n-j-2i} : i,j\geq0,j+2i\leq n\}. $$ \begin{lemma}\label{fund:dou} The set $\mathcal{B}_n$ is a basis (over $\Z$) for polynomials $A(s,t)=\sum_{k,l\geq0}^na_{k,l}s^kt^l\in\Z[s,t]$ with symmetries \begin{equation}\label{symme} a_{k,l}=a_{l,k}\quad\text{and}\quad a_{k,l}=a_{n-k,n-l}\quad\text{for all $k,l\geq0$}. \end{equation} \end{lemma} \begin{proof} Clearly, all polynomials in $\mathcal{B}_n$ satisfy the symmetries~\eqref{symme}, as well as their linear combinations. It remains to show that each polynomial with symmetries~\eqref{symme} can be expanded uniquely in $\mathcal{B}_n$. Let $b_{n,i,j}:=(st)^i(1+st)^j(s+t)^{n-j-2i}$. We order the polynomials in $\mathcal{B}_n$ as: $$ \text{$b_{n,i,j}$ is before $b_{n,u,v}$ if $i< u$ or $i=u$ but $jn-i$ or $k=n-i$ but $lk$ or $x=k$ but $y\pi_{i+1}\}+\chi(\pi_1<0).$$ This type B descent statistic was introduced by Brenti~\cite{bre}. Gessel~\cite{vi} noted that the {\em Type B double Eulerian polynomials} $B_n(s,t):=\sum_{\sigma\in\B_n}s^{\des_B(\pi^{-1})}t^{\des_B(\pi)}$ has the generating function \begin{equation}\label{gessel:B} \sum_{i,j\geq0}{2ij+i+j+n\choose n}s^it^j=\frac{B_n(s,t)}{(1-s)^{n+1}(1-t)^{n+1}}. \end{equation} %where $\tau\in\B_n$ is any fixed signed permutation with $\des_B(\tau)=k-1$. %The main result of this note is the following type B analog of Gessel's conjecture~\cite{br,lin,pe,vi}. We have the following type B analog of Conjecture~\ref{gessel}, which also implies the $\gamma$-positivity of $B_n(1,t)$, a result known previously~\cite{chow,dps}. \begin{theorem}[Type B analog of {\bf Conj.~\ref{gessel}}]\label{Type:B} For $n\geq1$, \begin{equation*} B_n(s,t)=\sum_{i,j\geq0\atop j+2i\leq n}\widetilde{\gamma}_{n,i,j}(st)^i(1+st)^{j}(s+t)^{n-j-2i}, \end{equation*} where $\widetilde{\gamma}_{n,i,j}$ are nonnegative integers. Moreover, $\widetilde{\gamma}_{n,i,j}$ is positive if and only if $i,j\geq0$, $2i+j\leq n$ and $2i(i+j+1)+j\geq n$. \end{theorem} For instance, the first few expansions of $B_n(s,t)$ are \begin{align*} B_1(s,t)&=1+st,\\ B_2(s,t)&=(1+st)^2+4st,\\ B_3(s,t)&=(1+st)^3+16st(1+st)+4st(s+t),\\ B_4(s,t)&=(1+st)^4+41st(1+st)^2+30st(s+t)(1+st)+st(s+t)^2+80(st)^2. %B_5(s,t)&=(1+st)^5+85st(1+st)^3+126st(s+t)(1+st)^2+21st(s+t)^2(1+st)+\\ %&\quad+688(st)^2(1+st)+288(st)^2(s+t). \end{align*} We have the following recursion for the type B $\gamma$-coefficients $\widetilde{\gamma}_{n,i,j}$. \begin{lemma} Let $n\geq2$. For all $i,j\geq0$, we have \begin{equation}\label{lin:rec} \begin{split} \quad n\widetilde{\gamma}_{n,i,j}&=(2n-j+2i(n-i-j))\widetilde{\gamma}_{n-1,i,j-1}+(2i(i+j+1)+j+1-n)\widetilde{\gamma}_{n-1,i,j}\\ &\quad+2(n+2-2i-j)(n+1-2i-j)\widetilde{\gamma}_{n-1,i-1,j-1}\\ &\quad+2(n+2i+j)(n+1-2i-j)\widetilde{\gamma}_{n-1,i-1,j}\\ &\quad+(j+1)(4n-2j)\widetilde{\gamma}_{n-1,i-1,j+1}+2(j+1)(j+2)\widetilde{\gamma}_{n-1,i-1,j+2}. \end{split} \end{equation} \end{lemma} \begin{proof} By~\eqref{gessel:B} using similar approach as Lemma~\ref{visontai}. All the computations are routine and tedious which we omit. \end{proof} \begin{proof}[{\bf Proof of Theorem~\ref{Type:B}}] The proof is essentially the same as that of Theorem~\ref{obser} by induction on $n$, but using recursion~\eqref{lin:rec} for $\widetilde{\gamma}_{n,i,j}$ instead. %Clearly, the result is true for $n\leq 4$ by the expansions produced above. Suppose that the statement is true for $n-1$ with $n\geq4$, namely, all $\widetilde{\gamma}_{n-1,i,j}$ are nonnegative and % $\widetilde{\gamma}_{n-1,i,j}$ is positive if and only if when $i,j\geq0$, $2i+j\leq n-1$ and $2i(i+j+1)+j\geq n-1$. To complete the proof by induction, we need to show the statement for $n$. % We can assume that $i,j\geq0$ and $2i+j\leq n$, otherwise $\widetilde{\gamma}_{n,i,j}=0$. We distinguish the following three cases. % % {\bf Case~1}: If $2i(i+j+1)+j=n-1$, then the inductive hypothesis implies that all $\widetilde{\gamma}_{n-1,i,j-1}$, $\widetilde{\gamma}_{n-1,i-1,j-1}$, $\widetilde{\gamma}_{n-1,i-1,j}$, $\widetilde{\gamma}_{n-1,i-1,j+1}$, $\widetilde{\gamma}_{n-1,i-1,j+1}$, $\widetilde{\gamma}_{n-1,i-1,j+2}$ are $0$ (except $\widetilde{\gamma}_{n-1,i,j}$ may not be zero), since now % $$ % 2i(i+j)+j-10$. Subcase II: $2i+j= n$. In this case, as % $$ %2i(i+j)+j-1=2i(n-1-i)+n-1\geq n-1\quad\text{and}\quad 2i+j-1=n-1, % $$ we have $(2n-j+2i(n-i-j))\widetilde{\gamma}_{n-1,i,j-1}>0$ (again by the inductive hypothesis) in the right-hand side of~\eqref{lin:rec}, and therefore $\widetilde{\gamma}_{n,i,j}>0$. %This completes the proof by induction. \end{proof} % %\section{Final remarks} %Foata and Sch\"utzenberger~\cite{fs} proved the stronger result that the $\gamma$-coefficients of Eulerian polynomials enumerate permutations without double descents by the number of descents. An elegant combinatorial proof via a group action was later constructed by Foata and Strehl~\cite{fsh} (see also~\cite{br,lz,pe}). An interesting open problem is to find a combinatorial proof of expansion~\eqref{2D-gam}. %Gessel's conjecture appears to hold in any finite Coxeter group. %For each permutation $\pi\in\S_n$, a value $\pi_i$, $i\in[n]$, is called a {\em double descent} (resp.~{\em double ascent}) of $\pi$ if $\pi_{i-1}>\pi_i>\pi_{i+1}$ (resp.~$\pi_{i-1}<\pi_i<\pi_{i+1}$) with the convention $\pi_0=\pi_{n+1}=+\infty$. Let $\NDD_{n,i}$ denote the set of all permutations in $\S_{n}$ without double descents and with $i-1$ descents. Foata and Sch\"utzenberger~\cite{fs} proved the stronger result that $\gamma_{n,i}$ equals the number of permutations in $\NDD_{n,i}$. A beautiful combinatorial proof that is now called group action proof (see the definition below) was later constructed by Foata and Strehl~\cite{fsh} (see also~\cite{br,pe,swg}). An interesting open problem is to find a combinatorial interpretation for the refined coefficients $\gamma_{n,i,j}$. % %Next, we can give a combinatorial proof of~\eqref{rec:gamm} using the above mentioned interpretation of $\gamma_{n,i}$. Let us recall the {\em Foata--Strehl action} on permutations. Let $\sigma\in\S_n$, for any $x\in[n]$, the {\em$x$-factorization} of $\sigma$ reads %$ %\sigma=w_1 w_2x w_3 w_4, %$ % where $w_2$ (resp.~$w_3$) is the maximal contiguous subword immediately to the left (resp.~right) of $x$ whose letters are all smaller than $x$. Following Foata and Strehl~\cite{fsh} we define the action $\varphi_x$ by % $\varphi_x(\sigma)=w_1 w_3x w_2 w_4$. % For instance, if $x=5$ and $\sigma=65137428\in\S_8$, then $w_1=6,w_2=\emptyset,w_3=13$ and $w_4=7428$. % Thus $\varphi_x(\sigma)=61357428$ (see Fig.~\ref{valhop}). % %\begin{figure} %\setlength {\unitlength} {0.8mm} %\begin {picture} (90,40) \setlength {\unitlength} {1mm} %\thinlines %%\put(24,8){\dashline{1}(-1,0)(-8,0)}%3 %%\put(16,8){\vector(-1,0){0.1}} % %\put(10,14){\dashline{1}(1,0)(20,0)}%5 %\put(30,14){\vector(1,0){0.1}} % %%\put(6,18){\dashline{1}(1,0)(28,0)}%6 %%\put(34,18){\vector(1,0){0.1}} %% %%\put(46,12){\dashline{1}(1,0)(12,0)}%4 %%\put(58,12){\vector(1,0){0.1}} %% %%\put(73,27){\dashline{1}(-1,0)(-76,0)}%8 %%\put(-3,27){\vector(-1,0){0.1}} % % %\put(20,4){\line(-1,1){27}}\put(-7,31){$+\infty$} %\put(10,14){\circle*{1.3}}\put(7,12){$5$} %\put(6,18){\circle*{1.3}}\put(3,16){$6$} %\put(20,4){\circle*{1.3}} %\put(20,4){\circle*{1.3}}\put(19.1,0){$1$} %\put(24,8){\circle*{1.3}}\put(24.5,5.5){$3$} %\put(52,6){\circle*{1.3}}\put(51.2,2){$2$} %\put(20,4){\line(1,1){17}}\put(37,21){\circle*{1.3}} %\put(37,21){\line(1,-1){15}}\put(36.5,22){$7$} %\put(46,12){\circle*{1.3}}\put(44,9){$4$} %\put(52,6){\line(1,1){25}}\put(73,27){\circle*{1.3}}\put(72.5,23.5){$8$} %\put(77,31){$+\infty$} %\end{picture} %\caption{The Foata--Strehl action $\varphi_x$, where $x=5$. %\label{valhop}} %\end {figure} %%Is there a type B analog? % Clearly, for each $x\in[n]$, $\varphi_x$ is an involution on $\S_n$. Moreover, $x$ is a double ascent of $\sigma$ if and only if $x$ is a double descent of $\varphi_x(\sigma)$. Now, we are ready for the combinatorial proof of~\eqref{rec:gamm}. Clearly, all permutations in $\NDD_{n+1,i}$ are obtained from the following three different cases: % \begin{itemize} % \item[(a)] from a permutation $\pi\in\NDD_{n,i}$ by inserting $n+1$ in one of the $i-1$ descent spaces of $\pi$ or in the last space of $\pi$; % \item[(b)] from a permutation $\pi\in\NDD_{n,i-1}$ by inserting $n+1$ in a space of $\pi$, which is not a descent space, not a space just before a descent space, not the first or last space of $\pi$; % \item[(c)] from a permutation $\pi\in\S_n$ with exactly one double descent and $i-1$ descents by inserting $n+1$ just after the unique double descent of $\pi$. % \end{itemize} % It is not hard to see that case~(a) gives $i\gamma_{n,i}$, while case~(b) gives $(n+1-2(i-1))\gamma_{n,i-1}$ permutations to $\NDD_{n+1,i}$. To complete the combinatorial proof of~\eqref{rec:gamm}, it remains to show that case (c) contributes $(n+3-2i)\gamma_{n,i-1}$ permutations to $\NDD_{n+1,i}$. This follows from the fact that the set of permutations in $\S_n$ with exactly one double descent and $i-1$ descents is the disjoint union % $$ %\bigcup_{\sigma\in\NDD_{n,i-1}}\{\varphi_x(\sigma): \text{$x$ is a double ascent of $\sigma$}\}. % $$ % % %Finally, we mention a different combinatorial interpretation of $A_n(s,t)$ due to Foata~\cite{fa} by mean of the so called {\em inversion sequences}. Let $\I_n$ be the set of all inversion sequences of length $n$ defined as %$$ %\I_n:=\{(e_1,\ldots,e_n)\in\Z^n : 0\leq e_i\leq i-1\,\text{for}\, 1\leq i\leq n\}. %$$ %Define the number of {\em ascents} and the number of {\em distinct entries} on each $e\in\I_n$ by %$$ %\asc(e):=|\{i\in[n-1] : e_{i}