% 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)<n,\quad (i-1)(i+j-2)<n, \quad(i-1)(i+j+1)<n.
 $$
 Thus, $\gamma_{n+1,i,j}=0$ if $i(i+j)= n$. 
 
 {\bf Case~2}: 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}$ and $\gamma_{n,i-1,j+2}$, including $\gamma_{n,i,j}$,  are $0$, which forces $\gamma_{n+1,i,j}=0$. 
 
 {\bf Case 3}: If  $i(i+j)\geq n+1$, then we need further to distinguish two subcases. Subcase I: $2i+j\leq n+1$.        
 In this case, the expression $(i(i+j)-n)\gamma_{n,i,j}$ in the right-hand side of~\eqref{vison:rec} is positive by the inductive hypothesis, and so $\gamma_{n+1,i,j}>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 $j<v$}
$$
so that the term $s^{n-i}t^{i+j}$ does not appear in any polynomial after $b_{n,i,j}$ in this order. Let $\mathcal{A}_n$ be the set of all polynomials in $\Z[s,t]$ with symmetries~\eqref{symme}.
We say  a polynomial $A(s,t)\in\mathcal{A}_n$ has \emph{complexity} 
$$(\lfloor(n+2)/2\rfloor-i)(\lfloor(n+3)/2\rfloor-i)-j$$ if it contains the term $s^{n-i}t^{i+j}$ but  does not contain any term $s^kt^l$ satisfying  $k>n-i$ or $k=n-i$ but $l<i+j$. For such a polynomial $A(s,t)$, consider the polynomial $A(s,t)-a_{n-i,i+j}b_{n,i,j}$ (obviously in $\mathcal{A}_n$). The complexity of this new polynomial reduces at least by one, since the term $s^{n-i}t^{i+j}$ vanishes. Therefore, by induction on the complexity, we can show that each polynomial from $\mathcal{A}_n$ can be expanded uniquely in $\mathcal{B}_n$.
%
%%For each $A(s,t)\in\mathcal{A}_n$, consider the term $s^kt^l$ in $A(s,t)$ such that any term $s^xt^y$ satisfying $x>k$ or $x=k$ but $y<l$ is not exist in $A(s,t)$. 
%%
%%We can write $k=n-i$ and $l=i+j$ for some $i,j\geq0$. It is routine to check that the coefficients of the polynomial $A(s,t)-a_{k,l}b_{n,i,j}$ preserves the symmetries of $A(s,t)$. 
%
%%Since each term in $\{s^kt^l,s^lt^k,s^{n-l}t^{n-k},s^{n-k}t^{n-l}\}$ has coefficient $a_{k,l}$ in $A(s,t)$ by the symmetries~\eqref{symme}, we can suppose  that $k\geq l$ and $k\geq n-l$
%%
%%
%%For any $k,l\geq0$, each term in $\{s^kt^l,s^lt^k,s^{n-l}t^{n-k},s^{n-k}t^{n-l}\}$ has coefficient $a_{k,l}$ in $A(s,t)$ by the symmetries~\eqref{symme}. Thus, we can suppose that $k\geq l$ and $k\geq n-l$. Now, there exists integers $i,j\geq0$ such that $k=n-i$ and $l=i+j$.
\end{proof}





\section{Generalizations} 

Fix a positive integer $k\leq n$. Define the {\em generalized double Eulerian polynomial} $A_n^{(k)}(s,t)$ by the identity 
\begin{equation}\label{gen:ges}
\sum_{i,j\geq0}{ij+n-k\choose n}s^it^j=\frac{A_n^{(k)}(s,t)}{(1-s)^{n+1}(1-t)^{n+1}}.
\end{equation}
The generalized double Eulerian polynomials  first arise implicitly in~\cite{mie}. Gessel~\cite{vi} (see also~\cite{ge}) further noticed that the generalized double Eulerian polynomials have the following nice interpretation
$$
A_n^{(k)}(s,t)=\sum_{\pi\in\S_n}s^{\des(\pi^{-1})+1}t^{\des(\pi\sigma)+1},
$$
where $\sigma\in\S_n$ is any fixed permutation with $\des(\sigma)=k-1$.  Note that $A_n^{(1)}(s,t)=A_n(s,t)$. This suggests the following more general form of $\gamma$-positivity, first appeared as Conjecture~10.2 (also due to Gessel) in~\cite{br}.

\begin{theorem}[Generalization of {\bf Conj.~\ref{gessel}}]\label{gessel:gen}
For $n\geq1$ and $1\leq k\leq n$, we have
\begin{equation}\label{2D-gam:gen}
A_n^{(k)}(s,t)=\sum_{i\geq1, j\geq0\atop j+2i\leq n+1}\gamma_{n,i,j}^{(k)}(st)^i(1+st)^{j}(s+t)^{n+1-j-2i},
\end{equation}
where $\gamma_{n,i,j}^{(k)}$ are nonnegative integers.
\end{theorem}

For $s=1$ or $t=1$, expansion~\eqref{2D-gam:gen} reduces to  the classical result~\eqref{gam:posi} with 
$
\gamma_{n,i}=\sum_{j\geq0}\gamma_{n,i,j}^{(k)}
$.
Thus, the coefficients $\gamma_{n,i,j}^{(k)}$ are refinements of the  triangle $\gamma_{n,i}$. 
We decompose the proof of Theorem~\ref{gessel:gen} into the following three lemmas. 

\begin{lemma}\label{peter:gen}
 The generalized double Eulerian polynomial $A_n^{(k)}(s,t)$ satisfies the recurrence relation
\begin{equation}\label{gendou:rec}
\begin{split}
nA_{n}^{(k)}(s,t)&=(n^2st+(n-k)(1-s)(1-t))A_{n-1}^{(k)}(s,t)\\
&\quad +nst(1-s)\frac{\partial}{\partial s}A_{n-1}^{(k)}(s,t)+nst(1-t)\frac{\partial}{\partial t} A_{n-1}^{(k)}(s,t)\\
&\quad +st(1-s)(1-t)\frac{\partial^2}{\partial s\partial t}A_{n-1}^{(k)}(s,t),
\end{split}
\end{equation}
where 
\begin{equation}\label{ascent}
A_{k}^{(k)}(s,t)=\sum_{\pi\in\S_k}s^{\des(\pi^{-1})+1}t^{k-\des(\pi)}=t^{k+1}A_{k}(s,1/t).
\end{equation}
\end{lemma}
\begin{proof} In the special case when $\sigma=k(k-1)\cdots21$, we have $\des(\pi\sigma)=k-1-\des(\pi)$ for each $\pi\in\S_k$ and~\eqref{ascent} follows. For simplicity,  the left-hand side of~\eqref{gen:ges} is denoted as $F_n^{(k)}(s,t)$.
%, that is,
%$$
%F_n^{(k)}(s,t)=\sum_{i,j\geq0}{ij+n-k\choose n}s^it^j=\frac{A_n^{(k)}(s,t)}{(1-s)^{n+1}(1-t)^{n+1}}.
%$$
Since
\begin{align*}
n{ij+n-k\choose n}&=(ij+n-k)\frac{(ij+n-k-1)!}{(n-1)!(ij-k)!}\\
&=ij{ij+n-k-1\choose n-1}+(n-k){ij+n-k-1\choose n-1},
\end{align*}
we have 
\begin{align*}
nF_n^{(k)}(s,t)&=\sum_{i,j\geq0}n{ij+n-k\choose n}s^it^j\\
&=\sum_{i,j\geq0} ij{ij+n-k-1\choose n-1}s^it^j+\sum_{i,j\geq0}(n-k){ij+n-k-1\choose n-1}s^it^j\\
&=st\frac{\partial^2}{\partial s\partial t}F_{n-1}^{(k)}(s,t)+(n-k)F_{n-1}^{(k)}(s,t).
\end{align*}
Substituting $F_n^{(k)}(s,t)=A_n^{(k)}(s,t)(1-s)^{-n-1}(1-t)^{-n-1}$ into the above relation, we get~\eqref{gendou:rec} after simplification.
\end{proof}

\begin{lemma}
Fix a positive integer $k$. Let $n\geq k$. Then, for all $i\geq1$ and $j\geq0$
\begin{equation}\label{gen:rec}
\begin{split}
(n+1)\gamma_{n+1,i,j}^{(k)}&=(n+1-k+i(n+2-i-j))\gamma_{n,i,j-1}^{(k)}\\
&\qquad+(i(i+j)-(n+1-k))\gamma_{n,i,j}^{(k)}\\
&\quad+(n+4-2i-j)(n+3-2i-j)\gamma_{n,i-1,j-1}^{(k)}\\
&\quad+(n+2i+j)(n+3-2i-j)\gamma_{n,i-1,j}^{(k)}\\
&\quad+(j+1)(2n+2-j)\gamma_{n,i-1,j+1}^{(k)}+(j+1)(j+2)\gamma_{n,i-1,j+2}^{(k)},
\end{split}
\end{equation}
where $\gamma_{k,i,j}^{(k)}=\gamma_{k,i,k+1-2i-j}$.
\end{lemma}

\begin{proof}
Follows from Lemma~\ref{peter:gen} by the same manipulations as  the proof of 
Lemma~\ref{visontai}. Note that $\gamma_{k,i,j}^{(k)}=\gamma_{k,i,k+1-2i-j}$ is equivalent to~\eqref{ascent}.
\end{proof}

%\begin{remark}
If we sum up both side of~\eqref{gen:rec} for all possible $j$, then we go back to the recurrence relation for $\gamma_{n,i}$~\cite[Remarque~5.3]{fs}:
\begin{equation*}\label{rec:gamm}
\gamma_{n+1,i}=i\gamma_{n,i}+2(n+3-2i)\gamma_{n,i-1}.
\end{equation*}
%\end{remark}
Note that in recurrence~\eqref{gen:rec} the integer $i(i+j)-(n+1-k)$ may assume negative value. The nonnegativity  of coefficients $\gamma_{n,i,j}^{(k)}$ is confirmed by the following lemma based on Theorem~\ref{obser}.
\begin{lemma} Fix a positive integer $k$. Let $n\geq k$. Then, for $i\geq1,j\geq0$ and $2i+j\leq n+1$:
\begin{itemize}
\item[(i)] all the coefficients $\gamma_{n,i,j}^{(k)}$ are nonnegative;
\item[(ii)] the coefficient $\gamma_{n,i,j}^{(k)}$ vanishes if  $i(i+j)<n+1-k$.
\end{itemize}
\end{lemma}
We will prove this result by induction on $n$ (for $n\geq k$)  using recurrence relation~\eqref{gen:rec} for  the generalized coefficients $\gamma_{n,i,j}^{(k)}$.
\begin{proof} As $\gamma_{k,i,j}^{(k)}=\gamma_{k,i,k+1-2i-j}$, the two statements are true for $n=k$ by Theorem~\ref{obser}. Suppose that this result is true for some $n$ with $n\geq k$. We need to show the two statements for $n+1$. It suffices to show statement (ii) in view of recurrence~\eqref{gen:rec}. We distinguish two cases. 

 {\bf Case~1}: If $i(i+j)= n+1-k$, then the  inductive hypothesis implies that all $\gamma_{n,i,j-1}^{(k)}$, $\gamma_{n,i-1,j-1}^{(k)}$, $\gamma_{n,i-1,j}^{(k)}$, $\gamma_{n,i-1,j+1}^{(k)}$, $\gamma_{n,i-1,j+1}^{(k)}$, $\gamma_{n,i-1,j+2}^{(k)}$  vanish (except $\gamma_{n,i,j}^{(k)}$ may be positive), since now 
 $$
 \max\{i(i+j-1), (i-1)(i+j-2), (i-1)(i+j+1)\}<n+1-k.
 $$
 Thus, $\gamma_{n+1,i,j}^{(k)}=0$ if $i(i+j)= n+1-k$. 
 
 {\bf Case~2}: If $i(i+j)<n+1-k$, then the  inductive hypothesis implies that all $\gamma_{n,i,j-1}^{(k)}$, $\gamma_{n,i-1,j-1}^{(k)}$, $\gamma_{n,i-1,j}^{(k)}$, $\gamma_{n,i-1,j+1}^{(k)}$, $\gamma_{n,i-1,j+1}^{(k)}$ and $\gamma_{n,i-1,j+2}^{(k)}$, including $\gamma_{n,i,j}^{(k)}$,  vanish, which forces $\gamma_{n+1,i,j}^{(k)}=0$. 
 
Thus, the proof is completed by induction.
\end{proof}

\subsection{Type B analog}

Consider the {\em Type B Coxeter group} $\B_n$, whose elements are regarded as  signed permutations of $[n]$.
 The {\em type B descent} statistic of $\pi\in\B_n$, denoted $\des_B(\pi)$, is defined as
$$\des_B(\pi):=\#\{i\in[n-1]:\pi_i>\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-1<n-1,\quad2(i-1)(i+j+2)+j+2=2i(i+j+1)-j-2<n-1.
% $$
% Thus, $\widetilde{\gamma}_{n,i,j}=0$ if $2i(i+j+1)+j=n-1$. 
% 
% {\bf Case~2}: 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}$ and $\widetilde{\gamma}_{n-1,i-1,j+2}$, including $\widetilde{\gamma}_{n-1,i,j}$,  are $0$, which forces $\widetilde{\gamma}_{n,i,j}=0$. 
% 
% {\bf Case 3}: If  $2i(i+j+1)+j\geq n$, then we need further to distinguish two subcases. Subcase I: $2i+j\leq n-1$.        
% In this case, the expression $(2i(i+j+1)+j+1-n)\widetilde{\gamma}_{n-1,i,j}$ in the right-hand side of~\eqref{lin:rec} is positive by the inductive hypothesis, and so $\widetilde{\gamma}_{n+1,i,j}>0$. 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}<e_{i+1}\}|\quad\text{and}\quad\dst(e):=|\{e_i : i\in[n]\}|.
%$$
%In~\cite{fa}, Foata showed bijectively the equidistribution: 
%$$
%\sum_{\pi\in\S_n}s^{\des(\pi^{-1})+1}t^{\des(\pi)+1}=\sum_{e\in\I_n}s^{\dst(e)}t^{\asc(e)+1}.
%$$
%Note that this equidistribution in the special $s=1$ case is well-known, while the $t=1$ case is due to Dumont~\cite{du}. It is desirable to see if either one of the two models can be used to give a combinatorial proof of recurrence~\eqref{pe:rec}. Such a proof might shed light on finding the combinatorial interpretation for $\gamma_{n,i,j}$. 
%
%\section*{Acknowledgement}
%I wish to thank Xiaoxian Tang, whose computer data leads to the observation of Theorem~\ref{obser}. Thanks also to Jiang Zeng for bringing the paper of Foata~\cite{fa} to my attention and to Ange Bigeni  for several discussions at the initial stage of this work. 
%


\subsection*{Acknowledgement}
I thank Ira M. Gessel, T. Kyle Petersen and Jiang Zeng for their comments. I also would like to thank the referees for their suggestions to improve the paper. This work was partially supported by the National Science Foundation of China grant 11501244.



\begin{thebibliography}{99}

\bibitem{br} P. Br\"and\'en, Actions on permutations and unimodality of descent polynomials, European J. Combin., {\bf29} (2008), 514--531. 

\bibitem{br2} P. Br\"and\'en, Unimodality, log-concavity, real-rootedness and beyond, {\em Handbook of Enumerative Combinatorics}, CRC Press Book. \href{http://arxiv.org/abs/1410.6601}{(arXiv:1410.6601)}

\bibitem{bre} F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin., {\bf15} (1994), 417--441.

\bibitem{car} L. Carlitz, D.P. Roselle and R.A. Scoville, Permutations and sequences with repetitions by number of increases, J. Combinatorial Theory, {\bf1} (1966), 350--374. 

\bibitem{chow} C.-O. Chow, On certain combinatorial expansions of the Eulerian polynomials, Adv. in Appl. Math., {\bf 41} (2008), 133--157.

\bibitem{dps} K. Dilks, T.K. Petersen and J.R. Stembridge, Affine descents and the Steinberg torus,  Adv. in Appl. Math., {\bf42} (2009), 423--444.

\bibitem{fs} D. Foata and M.-P. Sch\"utzenberger, {\em Th\'eorie g\'eom\'etrique des polyn\^omes eul\'eriens},  Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, Berlin, 1970.

\bibitem{fsh} D. Foata and V. Strehl, Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers, Math. Z., {\bf137} (1974), 257--264.

\bibitem{ge} I.M. Gessel, Multipartite $P$-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983), 289--317, Contemp. Math., 34, Amer. Math. Soc., Providence, RI, 1984. 


\bibitem{lz} Z. Lin and J. Zeng, 
The $\gamma$-positivity of basic Eulerian polynomials via group actions, 
J. Combin. Theory, Ser.  A, {\bf135} (2015), 112--129.


\bibitem{mie} B. Mielnik and J. Pleba\'nski, 
Combinatorial approach to Baker--Campbell--Hausdorff exponents, 
Ann. Inst. H. Poincar\'e, Sect. A (N.S.), {\bf12} (1970), 215--254. 

\bibitem{pe} T.K. Petersen, Two-sided Eulerian numbers via balls in boxes, Math. Mag., {\bf86} (2013),  159--176. 

\bibitem{pe2}T.K. Petersen,  {\em Eulerian numbers}. With a foreword by Richard Stanley. Birkh\"auser Advanced Texts: Basler Lehrb\"ucher. Birkh\"auser/Springer, New York, 2015.


\bibitem{st} R.P. Stanley, {\em Enumerative combinatorics}, Vol. 1, Cambridge University Press, Cambriage, 1997.

\bibitem{vi} M. Visontai, Some remarks on the joint distribution of descents and inverse descents, Electron. J. Combin., {\bf20} (2013), \#P52.




\end{thebibliography}
\end{document}
