
\documentclass[finalversion]{FPSAC2020}
\articlenumber{36}
%\articlenumber{FPSAC20_Pan}
%\addbibresource{FPSAC20_Pan.bib}
%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{dsfont}
\usepackage{amsmath, amsthm,amssymb}
\usepackage{extarrows}
\usepackage{epic}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{pict2e}
\usepackage{tikz}
\usetikzlibrary{arrows}
\pgfarrowsdeclarecombine{triang}{triang}%
{triangle 90}{triangle 90}{triangle 90}{triangle 90}
%%%%%%%%%%
\def\blue{\textcolor{blue}}
\def\red{\textcolor{red}}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{Ex}[thm]{Example}
\newtheorem*{pb}{Problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%5
\makeatletter
\newcommand{\rmnum}[1]{\romannumeral#1}
%\newcommand{\Rmnum}[1]{\expandafter\@slowromancap\roman%numeral#1@}
\newcommand{\Rmnum}[1]{(#1)}
\makeatother

\numberwithin{equation}{section}
%\renewcommand{\baselinestretch}{1.2}%%%
%\newcommand{\nt}{\par\noindent{\it Note. }}
%\newcommand{\qu}{\par\noindent{\it Question. }}
%\newcommand{\pf}{\par\noindent{\it Proof. }}
%\newcommand{\rmk}{\par\noindent{\it Remark. }}
%\newcommand{\ex}{\par\noindent{\it Example. }}
\newcommand{\subtitle}[1]{\par\medskip\noindent{\bf #1.}}
\def\la{\lambda}
\DeclareMathOperator\toht{(31\mhyphen 2)}
\DeclareMathOperator\thto{(2\mhyphen 31)}
\DeclareMathOperator\thot{(2\mhyphen 13)}
%----------------------------------------------------------------------------------------
\newcommand\qbin[2]{{#1 \brack #2}_{q}}
\newcommand\qmultinomial[2]{{#1 \brack #2}_{q}}
\newcommand\set[1]{\left\{#1\right\}}
\newcommand\abs[1]{\left|#1\right|}
\newcommand\gen[1]{\left<#1\right>}
\newcommand\floor[1]{\left\lfloor#1\right\rfloor}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\S{\mathfrak{S}}
\def\D{\mathcal{D}}
\def\And{\mathfrak{D}}
\def\andd{\mathrm{d}}
\def\seg{\mathrm{Seg}}
%%%%%%%%%%%%%
\def\M{\mathfrak{M}}
\def\H{\mathfrak{H}}
\def\I{\mathfrak{I}}
%%%%%%%%%%
\DeclareMathOperator\first{\mathsf{first}}
\DeclareMathOperator\last{\mathsf{last}}
\DeclareMathOperator\EB{EB}
\DeclareMathOperator\SE{SE}
\DeclareMathOperator\NE{NE}
\DeclareMathOperator\ER{ER}
%%%%%%%%%%%%
\DeclareMathOperator\inv{inv}
\DeclareMathOperator\exc{exc}
\DeclareMathOperator\cyc{cyc}
\DeclareMathOperator\wex{wex}
\DeclareMathOperator\Des{Des}
\DeclareMathOperator\des{des}
\DeclareMathOperator\asc{asc}
\DeclareMathOperator\ndes{ndes}
\DeclareMathOperator\dd{dd}
\DeclareMathOperator\da{da}
\DeclareMathOperator\peak{pk}
\DeclareMathOperator\valley{val}
\mathchardef\mhyphen="2D
\DeclareMathOperator\les{(31\mhyphen 2)}
\DeclareMathOperator\less{(13\mhyphen 2)}
\DeclareMathOperator\res{(2\mhyphen 13)}
\DeclareMathOperator\ress{(2\mhyphen 31)}
\DeclareMathOperator\LES{31\mhyphen 2}
\DeclareMathOperator\LESS{13\mhyphen 2}
\DeclareMathOperator\RES{2\mhyphen 13}
\DeclareMathOperator\RESS{2\mhyphen 31}
%\def\DD{\mathrm{\mathcal{G}}}
\def\DD{\mathrm{DD}}
\def\DE{\mathrm{DE}}
%%%%%%%%%%%%%%%%%%%%%%%
\def\312{\les}
\def\132{\less}
%\def\213{\res}
\def\231{\ress}
%%%%%%%%%%%%%
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\S{\mathfrak{S}}
\def\B{\mathfrak{B}}
\def\D{\mathfrak{D}}
\def\A{\mathfrak{A}}
\def\M{\mathfrak{M}}
\def\H{\mathfrak{H}}
%\usepackage{hyperref}
%\usepackage{cite}% cite together.
%\usepackage[backref=page]{hyperref}


%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%

%% define your title in the usual way
\title[Br\"and\'en's $(p, q) $-Eulerian polynomials and Andr\'e permutations]{The $\gamma $-coefficients of Br\"and\'en's $(p, q) $-Eulerian polynomials and Andr\'e permutations}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Qiong Qiong Pan and Jiang Zeng]{Qiong Qiong Pan\thanks{\href{mailto:qpan@math.univ-lyon1.fr}{qpan@math.univ-lyon1.fr}. 
 }\addressmark{1}
\and  Jiang Zeng\thanks{\href{mailto:zeng@math.univ-lyon1.fr}{zeng@math.univ-lyon1.fr}.}\addressmark{1}}
%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1}Univ Lyon, Universit\'e Claude Bernard Lyon 1, CNRS, Institut Camille Jordan, Villeurbanne, France}
%% put the date of submission here
\received{\today}
%% leave this blank until submitting a revised version
%\revised{}
%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{In 2008 Br\"and\'en proved  a $(p,q)$-analogue of the 
 $\gamma$-expansion formula for  
Eulerian polynomials and conjectured the divisibility of 
the $\gamma$-coefficient $\gamma_{n,k}(p,q)$  by $(p+q)^k$.  As a follow-up, in 2012
Shin and Zeng  showed  that  the fraction $\gamma_{n,k}(p, q)/(p + q)^k$ is a polynomial in $\N[p,q]$.
The aim of this paper is to  give a combinatorial interpretation of  the  latter polynomial  in terms of
 Andr\'e permutations, a class of objects  first defined and studied by Foata, 
 Sch\"utzenberger and Strehl in the 1970s. It turns out that our result provides an 
 answer to  a recent  open problem  of  Han, which was the impetus of this paper.
}  

%% put your French abstract here, or comment this out if you don't have one
%\resume{Il est bien connu que les polyn\^omes de pic de permutations et les polyn\^omes de descente sont connect\'es via une transformation quadratique. En reformulant cette derni\`ere formule avec 
%les pics de cycle et les exc\'edances du cycle de permutation, nous pouvons prouver une s\'erie de formules g\'en\'erales exprimant des polyn\^omes \'enum\'eratives des permutations par diverses statistiques d'exc\'edance en termes de polyn\^omes eul\'eriens raffin\'es.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Eulerian polynomials, $\gamma$-coefficients,  Andr\'e permutations.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\addbibresource{FPSAC20_Pan.bib}

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
The Euler number $E_n$, namely the coefficient of $x^n/n!$ in the expansion of $\sec(x)+\tan(x)$,
is well studied and has many combinatorial interpretations and  different refinements; see~\cite{FS73, Vi81, GSZ,  SZ12, JV14}.  It was  Andr\'e  who  first  proved  that $E_n$ is the number of alternating permutations $a_1\ldots a_n$ of $12\ldots n$, i.e., $a_1>a_2<\cdots$.
Among the many remarkable identities for the Euler numbers there is the less known J-type continued fraction 
\begin{align}\label{ES-CF}
\sum_{n=0}^\infty E_{n+1}x^n=\cfrac{1}{1-x-\cfrac{x^2}{1-2x-\cfrac{3x^2}{1-3x-\cfrac{6x^2}{1-4x-\cfrac{10x^2}{1-\cdots}}}}}.
\end{align}
Recently, 
 Han~\cite{Han19}  considered a  $q$-version of \eqref{ES-CF} and 
 asked for a combinatorial interpretation for the corresponding $q$-Euler numbers $E_n(q)$ (see \eqref{q-ES-D} below).  Motivated by  Han's question, we shall study the more general polynomials $D_n(p,q,t)$ defined by the following continued fraction, which is a $(p,q)$-analogue of (1.1):
\begin{align}\label{pq-shift}
\sum_{n=0}^\infty D_{n+1}(p,q,t)x^n
=\cfrac{1}{1-x-\cfrac{\binom{2}{2}_{p,q} t\,x^2}{1-[2]_{p,q} x-
\cfrac{\binom{3}{2}_{p,q}t\,x^2}{1-[3]_{p,q} x-\cfrac{\binom{4}{2}_{p,q}t\,x^2}{1-[4]_{p,q} x-\cfrac{\binom{5}{2}_{p,q} t\,x^2}{1-\cdots}}}}},
\end{align}
where  the $(p,q)$-analogue of $n$ is defined by

\[
 [n]_{p,q}=\frac{p^n-q^n}{p-q}=\sum_{i+j=n-1}p^iq^j \qquad (n\in \N)
 \]
  and the $(p,q)$-analogue of the binomial coefficient $\binom{n}{k}$ is defined by
\[
\binom{n}{k}_{p,q}=\frac{[n]_{p,q}\ldots [n-k+1]_{p,q}}{[1]_{p,q}\ldots [k]_{p,q}}\qquad (0\leq k\leq n).
\]
Comparing  \eqref{ES-CF} and \eqref{pq-shift}  yields that 
\[
D_{n}(1,1,1)=E_{n} \qquad (n\geq 1).
\]
The $q$-Euler number $E_n(q)$  of Han~\cite{Han19} can be expressed  as
\begin{align}\label{q-ES-D}
E_n(q):=D_{n}(1,q,1)=D_{n}(q,1,1)\qquad  (n\geq 1).
\end{align} 

 The first few values of  $D_n(p,q,t)$  are $D_1(p,q,t)=D_2(p,q,t)=1$.
 It turns out that the polynomials $D_n(p,q,t)$ are related to the $\gamma$-coefficients of 
Br\"and\'en's  $(p,q)$-analogue of Eulerian polynomials~\cite{Bra08}.  In this paper we shall interpret
$D_n(p,q,t)$ 
 in terms of  \emph{Andr\'e permutations}, which were introduced and studied by Foata, Sch\"utzenberger and  Strehl~\cite{FS73, FS74, FS76} in the 1970s.
There are three ingredients in our proof:    
the  connection of these polynomials with the $\gamma$-coefficients of  Br\"and\'en's $(p,q)$-analogue of Eulerian polynomials~\cite{Bra08}, Shin-Zeng's  continued fraction expansion  of  the $\gamma$-coefficients of generalized Eulerian polynomials~\cite{SZ12} and a new action on the permutations without double descents.


 For  a  permutation $\sigma:=\sigma_1\sigma_2\ldots \sigma_n$ of $[n]$,
the \emph{descent number}  $\des\sigma$ is the number of descent positions, i.e. $i<n$ such that  $\sigma_i>\sigma_{i+1}$, and the \emph{excedance number}  $\exc\sigma$ is the number of excedance
 positions, i.e. $i\in [n]$ such that  $\sigma_i>i$.
 Let $\S_n$ be the set of permutations  of $[n]:=\set{1,\dots,n}$.
Thanks to  the work of MacMahon~\cite{Mac15} and Riordan~\cite{Ri51} we can define 
 the Eulerian polynomials $ A_n(t)$ by
 $$
 A_n(t)=\sum_{\sigma\in \S_n} t^{\des\sigma}=\sum_{\sigma\in \S_n} t^{\exc\sigma}.
 $$
 The following $\gamma$-decompositions for $A_n(t)$ are well-known~\cite[Section~4]{FS73}.
\begin{thm} [Foata and Sch\"utzenberger]
\begin{align}
A_n(t)&=\sum_{k=0}^{\lfloor{n/2\rfloor}}\gamma_{n,k} t^k (1+t)^{n-1-2k}\label{eulerian:gamma}\\
&=\sum_{k=0}^{\lfloor{n/2\rfloor}}2^kd_{n,k} t^k (1+t)^{n-1-2k}, \label{eulerian:andre}
\end{align}
where  $\gamma_{n,k}=2^kd_{n,k}$ and   $d_{n,k}$ are positive integers satisfying  the recurrence
\begin{align}
 \and_{1,0}&=1\quad \textrm{and for $n\geq 2$, $k\geq 0$},\nonumber\\
 \andd_{n,k}&=(k+1)\andd_{n-1,k}+(n-2k)\andd_{n-1,k-1}.
 \end{align} 
Moreover, the sum $\sum_k d_{n,k}$ is precisely the Euler number $E_n$.
\end{thm}

In the last two decades even though  many refinements of \eqref{eulerian:gamma} have been found in combinatorics and geometry (see \cite{ PRW,  Pe15, At18,SW20}), 
similar extension of  \eqref{eulerian:andre} does not seem to be known. 
In this paper we will provide two 
refinements  of  \eqref{eulerian:andre} (see \eqref{gamma-d} and \eqref{gamma-qd}).

 
 %%%%%%%%%%%%%%%%%

\begin{defn}
For  a permutation $\sigma=\sigma_1\ldots \sigma_n$ of $[n]$ with  $\sigma_0=\sigma_{n+1}=0$,  the  entry $\sigma_i$ is 
\begin{itemize}
\item a \emph{peak}  if $\sigma_{i-1} < \sigma_{i}$ and $\sigma_{i} > \sigma_{i+1}$;
\item a \emph{valley}  if $\sigma_{i-1} > \sigma_{i}$ and $\sigma_{i} < \sigma_{i+1}$;
\item a \emph{double ascent}  if $\sigma_{i-1} < \sigma_{i}$ and $\sigma_{i} < \sigma_{i+1}$;
\item a \emph{double descent} if $\sigma_{i-1} > \sigma_{i}$ and $\sigma_{i} > \sigma_{i+1}$.
\end{itemize}
\end{defn}
Let $\peak\sigma$ (resp. $\valley \sigma$, $\da\sigma$, $\dd\sigma$) denote  the number of peaks (resp. valleys, double ascents, double descents) in~$\sigma$. 
Note that $\des\sigma=\valley\sigma+\dd\sigma$ and $\peak \sigma=\valley \sigma+1$.
Let $\mathcal{G}_{n,k}=\{\sigma\in \S_n: \valley\sigma=k, \dd\sigma=0\}$.  

\begin{defn}
For a permutation $\sigma$ of $[n]$,  let  $\sigma_{[k]}$ be the \emph{subword} of $\sigma$ consisting of $1,\dots, k$ in the order they appear in $\sigma$. Then, 
the  permutation $\sigma$ is an  Andr\'e permutation 
if $\sigma_{[k]}$ has no double descents (and ends with an ascent) for all $1\leq k\leq n$.
\end{defn}
 Let $\And_n$ be the set of Andr\'e permutations of  $[n]$ and
let $\And_{n,k}$ be the set of Andr\'e permutations of $[n]$ with $k$ descents. 


\begin{prop}[\cite{FS73,FS76}]
The coefficients $\gamma_{n,k}$  and $d_{n,k}$ 
equal  the cardinalities of $\mathcal{G}_{n,k}$ and  $\And_{n,k}$, respectively.
\end{prop}
For  $\sigma = \sigma_1 \dots \sigma_n \in \S_n$,
the statistic $\les \sigma$ %(resp.  $\less \sigma$ )
 is the number of pairs $(i,j)$ such that $2\leq i<j\leq n$ and $ \sigma_{i-1}>\sigma_j>\sigma_i$.
% (resp.  $ \sigma_{i-1}<\sigma_j<\sigma_i$). 
 Similarly,
the statistic $\res\sigma $ %(resp. $\ress \sigma $)
is the number of pairs $(i,j)$ such that $1\leq i<j\leq n-1$ and $\sigma_{j+1}>\sigma_i>\sigma_j$. %(resp. $\sigma_{j+1}<\sigma_i<\sigma_j$).
 In 2008 Br\"and\'en~\cite{Bra08} defined  a $(p,q)$-analogue of Eulerian polynomials and 
proved a $(p,q)$-analogue of \eqref{eulerian:gamma}. In this paper we shall use  the following 
 variant  of Br\"and\'en's $(p,q)$-Eulerian polynomials
in \cite{SZ12}
\begin{align}
A_n(p,q,t):=\sum_{\sigma\in \S_n} p^{\res \sigma} q^{\les \sigma}t^{\des\sigma}.
\end{align}
For $0\leq k\leq (n-1)/2$ define the $(p,q)$-analogue of  
$\gamma_{n,k}$ and $d_{n,k}$ in \eqref{eulerian:gamma} and \eqref{eulerian:andre} by
\begin{align} 
\gamma_{n,k}(p,q)&=\sum_{\sigma\in \mathcal{G}_{n,k}} p^{\res \sigma} q^{\les \sigma},\label{eq:combin}\\
d_{n,k}(p,q)&=\sum_{\sigma\in \And_{n,k}}p^{\res\sigma}q^{\312\sigma-k}.
\end{align} 
Our main results are the following two theorems.
\begin{thm} \label{thm:main1} We have 
\begin{align}
A_n(p,q,t)&=\sum_{k=0}^{\lfloor{(n-1)/2\rfloor}}\gamma_{n,k}(p,q)
t^{k}(1+t)^{n-1-2k}\label{gamma-pq}\\
&=\sum_{k=0}^{\lfloor{(n-1)/2\rfloor}}(p+q)^k\andd_{n, k}(p,q)\label{gamma-d}
t^{k}(1+t)^{n-1-2k}.
\end{align}
\end{thm}
\begin{rem}
An equivalent $\gamma$-expansion of \eqref{gamma-pq} was  proved  by Br\"and\'en~\cite{Bra08} using the \emph{modified Foata-Stehl} action.  
The divisibility of  $\gamma_{n,k}(p,q)$ by $(p+q)^k$ was conjectured by 
Br\"and\'en~(\emph{op.cit.}) and proved by Shin and Zeng~\cite{SZ12} using the combinatorial theory of
continued fractions.
\end{rem}
\begin{thm}\label{thm:main2}  We have 
\begin{align}
D_{n}(p,q,t)&=\sum_{k=0}^{\lfloor (n-1)/2\rfloor} \andd_{n,k}(p,q)t^k\label{eq:1}\\
&=\sum_{\sigma\in \And_{n}}p^{\res\sigma}q^{\312\sigma-\des\sigma}t^{\des\sigma}.\label{eq:2}
\end{align}
\end{thm}
\begin{rem}
It is not difficult to see that $\312\sigma\geq \des\sigma$ for any 
$\sigma\in \And_n$, see (iii) of \cref{x-fact-andre}. 
\end{rem}

Combining \cref{thm:main1} with Theorem~1 in \cite{SZ16}, which is \eqref{gamma-q} below, 
 we derive a $q$-analogue of 
\eqref{eulerian:gamma} and \eqref{eulerian:andre}.
\begin{cor} We have 
\begin{align}
\sum_{\sigma\in \S_n} q^{(\inv -\exc)\sigma}t^{\exc\sigma}
&=\sum_{k=0}^{\lfloor{(n-1)/2\rfloor}}\gamma_{n,k}(q^2,q)
t^{k}(1+t)^{n-1-2k}\label{gamma-q}\\
&=\sum_{k=0}^{\lfloor{(n-1)/2\rfloor}}(1+q)^k\andd_{n, k}(q)
t^{k}(1+t)^{n-1-2k},\label{gamma-qd}
\end{align}
where 
\[
\andd_{n, k}(q)=\sum_{\sigma\in \And_{n,k}}q^{2\res\sigma+\312\sigma}.
\]
\end{cor}

\medskip

By \eqref{q-ES-D} and \cref{thm:main2} we derive  two interpretations for Han's $q$-Euler numbers\cite{Han19}.
%%%%%%%%%%%%%%%%%%%%
\begin{cor} We have 
\begin{align}
E_{n}(q)&=\sum_{\sigma\in \And_{n}}q^{\res\sigma}\\
&=\sum_{\sigma\in \And_{n}}q^{\312\sigma-\des\sigma}.
\end{align}
\end{cor}
In Section~3 we shall give a simple sum  formula for $D_n(1,-1,t)$ (cf. \cref{formula(-1)}).
%%%%%%%%%%%
\section{Proof outlines of main Theorems}
\subsection{Some basic definitions and results}
The following definition was given as a lemma in~\cite[Lemma~1]{FS74}.
\begin{defn}
Let $w = x_1x_2 ... x_n$ ($n > 0$) be a permutation and $x$ be one of
the letters $x_i$ ($1 < i< n$). Then $w$ has a unique factorization $(w_1 , w_2 , x, w_4, w_5)$ of length $5$, called its $x$-factorization, which is characterized by the three
properties
\begin{itemize}
\item[(i)] $w_1$ is empty or its last letter is less than $x$;
\item[(ii)] $w_2$ (resp. $w_4$) is empty or all its letters are greater than $x$;
\item[(iii)] $w_5$ is empty or its first letter is less than $x$.
\end{itemize}
\end{defn}

We can  charactrize Andr\'e permutations in terms of $x$-factorization~\cite{FS73}.
\begin{prop}\label{x-fact-andre}
A permutation $\sigma\in\S_n$ is an Andr\'e permutation  
if it is empty or satisfies the following:
\begin{itemize}
\item[(i)]
$\sigma$ has no double descents,
\item[(ii)]
$n-1$ is not a descent position, i.e. $\sigma_{n-1}<\sigma_n$,
\item[(iii)]
If $\sigma_i$ is a valley of $\sigma$ with  $\sigma_i$-factorization 
$(w_1, w_2, \sigma_i, w_4, w_5)$, then  $\min(w_2)>\min(w_4)$, i.e.,
the minimum letter of $w_2$ is larger than the minimum letter of $w_4$.
\end{itemize}
\end{prop}
 The next theorem follows from the work of \cite{Bra08, FS76}.
%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%
\begin{thm}\label{c1}
For any $\tilde{\sigma}\in\S_n$ without double decent, we have
$$
\sum_{\sigma\in \mathsf{Orb}(\tilde{\sigma})}p^{\res\sigma}q^{\312\sigma}
t^{\des\sigma}=p^{\res\tilde{\sigma}}
q^{\312\tilde{\sigma}}t^{\des\tilde{\sigma}}(1+t)^{n-1-2\des\tilde{\sigma}}.
$$
\end{thm}
%%%%%%%%%%%%%%%%%%%%%%
Let   $A_n(p,q,t,u,v,w)$  be   the generalized   Eulerian polynomials defined by
\begin{align}\label{eq:dfA}
A_n(p,q,t,u,v,w) := \sum_{\sigma\in \S_n} p^{\res \sigma} q^{\les \sigma}  t^{\des\sigma}u^{\da\sigma} v^{\dd\sigma}w^{\valley\sigma}.
\end{align}
As $\des=\valley+\dd$ we derive the 
following generalization of  \eqref{gamma-pq} from \cref{c1}.
This was first proved in \cite{SZ12} by using combinatorial theory  of 
continued fractions.  
\begin{cor}\label{coro: gamma} For the $\gamma$-coefficients $\gamma_{n,k}(p,q)$ in 
\eqref{eq:combin} we have 
\begin{equation}\label{eq:gamma}
A_n(p,q,t,u,v,w)= \sum_{k=0}^{\floor{(n-1)/2}} \gamma_{n,k}(p,q) (tw)^k (u+vt)^{n-1-2k}.
\end{equation}
\end{cor}
 %%%%%%%%%%
\subsection{New action on permutations without double descent}
Let $\DD_n$ be the set of permutations of $[n]$ without double descent.
For any permutation $\sigma\in \DD_n$ and $x\in [n]$ we shall  identify 
 $\sigma$ with its $x$-factorization, i.e., $\sigma=(w_1, w_2, x, w_4, w_5)=w_1\, w_2\, x\, w_4\, w_5$, and 
 let  $y_1:=\min(w_2),\, y_2:=\min(w_4)$.
 A valley  $x$ of $\sigma$ is said to be
\begin{itemize}
\item \emph{good} (resp. \emph{bad})  if $y_1>y_2$ (resp. $y_1<y_2$); 
\item of   \emph{type I} 
if $\min(y_1,y_2)$ is a peak or double ascent,
\item of   \emph{type II} if $\min(y_1,y_2)$ is a valley.
\end{itemize}
We  denote by $\mathsf{Val}\,\sigma$ the set of valleys of 
$\sigma$.
\begin{prop}
Let  $\sigma\in \DD_n$ and $x\in \mathsf{Val}\,\sigma$ with $y=\min(y_1,y_2)$. 
\begin{itemize}
\item[(i)]
If  $y$ is a peak, then $w_4=y$ (resp. $w_2=y$) if  $y_1>y_2$ (resp. $y_1<y_2$).
\item[(ii)]
If  $y$ is a double ascent,  then $w_4=yw_4''$  (resp. $w_2=yw_2''$) 
with  $w_2'', w_4''\neq \epsilon$ if  $y_1>y_2$ (resp. $y_1<y_2$).
\item[(iii)]
If $y$ is a valley, then  $w_4=w_4'yw_4''$ (resp. $w_2=w_2'yw_2''$) with $w_2', w_2'', w_4', w_4''\neq \epsilon$ if  $y_1>y_2$ (resp. $y_1<y_2$).
\end{itemize}
\end{prop}

\begin{defn}\label{def:action}
For $\sigma\in \DD_n$ and each $x\in \mathsf{Val}\,\sigma$ with $y=\min(y_1,y_2)$, we define its
 transform $\varphi(\sigma, x)$ as follows:
\begin{itemize}
\item[(i)]
If $y$ is a peak, then 
\[
\varphi(\sigma, x)=\begin{cases}
(w_1,y,x,w_2,w_5)& \textrm{if}\quad y=y_2,\\
(w_1,w_4,x, y,w_5)&\textrm{if}\quad y=y_1.
\end{cases}
\]

%%%%%%%%%%%%%%%%
\item[(ii)]
If $y$ is a double ascent,  then  
\[
\varphi(\sigma, x)=\begin{cases}
(w_1,yw_2,x,w'',w_5)& \textrm{if}\quad y=y_2\; \text{and} \; w_4=yw'',\\
(w_1,w'',x, yw_4,w_5)&\textrm{if}\quad y=y_1\; \text{and} \; w_2=yw''.
\end{cases}
\]
%
%%%%%%%%%%%%%%%%%%%
\item[(iii)]
If $y$ is a valley, then   
\[
\varphi(\sigma, x)=\begin{cases}
(w_1,w_2yw',x,w'', w_5)& \textrm{if}\quad y=y_2\; \text{and} \; w_4=w'yw'',\\
(w_1,w',x, w''yw_4,w_5)&\textrm{if}\quad y=y_1\; \text{and} \; w_2=w'yw''
\end{cases}
\]
with $w', w''\neq \epsilon$.
\end{itemize}
\end{defn}
Obviously this transformation switches $y$ from left  to right or  right to left of $x$
and  $\varphi(\varphi(\sigma, x),x)=\sigma$.
We record the basic properties of this transformation in the following proposition.
%
%%%%%%%%%%%%%%%%%%%%%






%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{prop}\label{Q2}
If  $\sigma\in\DD_{n,k}$ and $x\in \mathsf{Val}\,\sigma$,  then $\varphi(\sigma, x)\in \DD_{n,k}$ 
and 
\begin{align}\label{eq:123x}
\begin{split}
\res\varphi(\sigma, x)&=\begin{cases}
\res\sigma+1& \text{if $x$ is good} \\
\res\sigma-1& \text{if $x$ is bad};
\end{cases}\\
\les\varphi(\sigma, x)&=\begin{cases}
\les\sigma-1& \text{if $x$ is good}\\
\les\sigma+1& \text{if $x$ is bad}.
\end{cases}
\end{split}
\end{align}
\end{prop}
%%%%%%%%%%%%%%


Next we define the transform $\varphi(\sigma, S)$ for  any subset $S$ of $\mathsf{Val}(\sigma)$ with
 $\sigma\in \DD_n$.
%%%%%%%%%%%%%%%%
\begin{defn} Let $\sigma\in \DD_n$.
For  any $S\subseteq \mathsf{Val}\,\sigma$, 
let  $\{S_1,S_2\}$ be the partition of $S$ such that  
\begin{itemize}
\item[(1)]
$S_1$ is the subset of $S$  consisting of valleys of type I, say $i_1, \ldots, i_l$;
%whose  corresponding $y$ is a peak or a double ascent;
\item[(2)] 
$S_2$  is  the subset of $S$ consisting of valleys of type II, say $j_k<\cdots< j_2<j_1$.
\end{itemize}
Define the transforms 
\begin{align*}
\varphi(\sigma,S_1)&=\varphi(i_l, \ldots, \varphi(i_2, \varphi(i_1, \sigma))),\\
\varphi(\sigma,S_2)&=\varphi(j_k, \ldots, \varphi(j_2, \varphi(j_1, \sigma))),\\
\varphi( \sigma,S)&=\varphi(\varphi(\sigma, S_1), S_2).
\end{align*}
\end{defn}
%%%%%%
\begin{rem}
 The  image $\varphi(\sigma, S_1)$ is independent of the order  of $i_1, \ldots, i_l$ while 
 $\varphi(\sigma, S_2)$ is defined for the elements of $S_2$ in the decreasing order  $j_1>j_2> \ldots >j_1$.
\end{rem}
%%%%%%
\begin{prop}\label{Q3}
If  $\sigma\in\And_{n,k}$ and $S\subseteq \mathsf{Val}(\sigma)$, 
then $\tau:=\varphi(\sigma,S)\in \DD_{n,k}$ is well defined and 
\begin{align}\label{eq:s-tau}
S=\{x\in \mathsf{Val}(\tau)\,|\, \textrm{$x$ is a bad guy}\}.
\end{align}
\end{prop}
%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%
For any set $S$ we denote by $ 2^{S} $  the set of all subsets of $S$. 
In what follows,
for $\sigma\in  \DD_{n,k}$ we will identify  $\mathsf{Val}(\sigma)$ with  $[k]$ under the map
$a_i\mapsto i$ for $i\in [k]$ if $\mathsf{Val}(\sigma)$ consists of $a_1<a_2<\ldots<a_k$,  and identify 
any subset $S\in  \mathsf{Val}(\sigma)$ with its image $S'\in 2^{[k]}$. Thus we will use $2^{[k]}$ instead of 
$2^{ \mathsf{Val}(\sigma)}$.
\begin{prop}\label{key1}
The map 
$\varphi:   \And_{n,k}\times 2^{[k]}\to \mathcal{G}_{n,k}$ is  a bijection 
 such that   for $(\sigma,S)\in   \And_{n,k}\times 2^{[k]}$ we have 
\begin{equation} \label{prop}
\begin{split}
\res\sigma +|S|& = \res\varphi(\sigma, S),\\
\312\sigma -|S|& = \312\varphi(\sigma, S).
\end{split}
\end{equation}
\end{prop}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of \cref{thm:main1}}
Clearly \eqref{gamma-pq}  is a special case of \cref{coro: gamma}, and 
\eqref{gamma-d} is equivalent to
\begin{align}\label{eq:equiv}
(p+q)^k \,\sum_{\sigma\in \And_{n,k}}p^{\res\sigma}q^{\les\sigma-k}=
\sum_{\sigma\in \DD_{n,k}}p^{\res\sigma}q^{\les\sigma}.
\end{align}
As $(p+q)^k=\sum_{S\in 2^{[k]}}p^{|S|}q^{k-|S|}$ we can rewrite the above identity as
$$
\sum_{(\sigma,S)\in  \And_{n,k}\times 2^{[k]} }p^{\res\sigma+|S|}q^{\les\sigma-|S|}=
\sum_{\sigma\in \DD_{n,k}}p^{\res\sigma}q^{\les\sigma}.
$$
The result  follows  from \cref{key1}.
\qed

%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of \cref{thm:main2}}
%%%%%%%%%%%%%%%%%%%%
We shall use 
the J-type continued fraction  as a  formal power series defined by
 $$
\sum_{n=0}^\infty \mu_nt^n=\cfrac{1}{1-b_0 t-\cfrac{\lambda_1 t^2}
{1-b_1 t-\cfrac{\lambda_2t^2}{1-\cdots}}},
 $$ 
 where $(b_n)$ and $(\lambda_{n+1})$ ($n\geq 0$) are two sequences in a commutative ring.
When $b_n=0$ we obtain the S-type  continued fraction:
$$
\sum_{n=0}^\infty \mu_nt^n=\cfrac{1}{1-\cfrac{\lambda_1 t}{1-\cfrac{\lambda_2 t}{1-\cdots}}}.
 $$ 

%%%%%
Recall   the following continued fraction expansion formula from  \cite[(28)]{SZ12}:
\begin{equation} \label{eq:master}
\begin{split}
\sum_{n\ge1}& A_n(p,q,t,u,v,w)x^{n-1}=\\
&\dfrac{1}
{1-(u+tv)[1]_{p,q}x-\dfrac{[1]_{p,q}[2]_{p,q}twx^2}
{1-(u+tv)[2]_{p,q}x-\dfrac{[2]_{p,q}[3]_{p,q}twx^2}
{\cdots}}}
\end{split}
\end{equation}
with $b_n=(u+tv)[n+1]_{p,q}$ and $\la_n=[n]_{p,q}[n+1]_{p,q}tw$.

By \cref{thm:main1} and  substituting  $(t,u,v, w)$ with $(p+q, 0, 1,t)$ in \eqref{eq:gamma}, 
we obtain
$$
A_n(p,q,p+q, 0, 1,t)=(p+q)^{n-1}\sum_{k=0}^{\lfloor (n-1)/2\rfloor}d_{n,k}(p, q)t^k.
$$
Thus, substituting  $(t,u,v, w)$ with $(p+q, 0, 1,t)$ in \eqref{eq:master} and replacing $x$ by $x/(p+q)$ we obtain
the same continued fraction in \eqref{pq-shift}.  This proves \eqref{eq:1}.
\qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{An explicit formula for $D_n(1,-1,t)$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A \emph{Motzkin path}  of length  $n$ is a sequence of points 
$\eta:=(\eta_0, \ldots, \eta_n)$  in the integer plane 
$\mathbb{Z}\times\mathbb{Z}$  such that 
\begin{itemize}
\item $\eta_0=(0,0)$ and $\eta_n=(n,0)$,
\item $\eta_i-\eta_{i-1}\in \{(1,0), (1, 1), (1,-1)\}$,
\item $\eta_i:=(x_i, y_i)\in \N\times \N$ for $i=0,\ldots, n$.
\end{itemize}
In other words, a Motzkin path of length $n$ is a lattice path starting at $(0,0)$, ending at $(n,0)$, 
and never going below the $x$-axis, consisting of up-steps $\mathsf{U}=(1,1)$, level-steps $\mathsf{L}=(1,0)$, and down-steps
$\mathsf{D}=(1,-1)$. 
Let $\mathcal{MP}_n$ be the set of Motzkin paths of length $n$.
Clearly we can  identify 
 Motzkin paths of length $n$ with words $w$ on 
 $\{\mathsf{U, L, D}\}$ of length $n$ such that all prefixes of $w$ 
 contain no more $\mathsf{D}$'s than $\mathsf{U}$'s and the number of $\mathsf{D}$'s equals the number of $\mathsf{D}'s$.
The height of a step $(\eta_i, \eta_{i+1})$ is the coordinate of the starting point $\eta_i$.
Given a Motzkin path $p\in \mathcal{MP}_n$ and two sequences 
$(b_i)$ and $(\lambda_i)$  of a commutative ring $\mathrm{R}$, 
we weight   
each up-step by 1, and each level-step (resp. down-step)   at height $i$ by 
$b_i$ (resp. $\lambda_i$) and  define the weight $w(p)$ of $p$  by 
  the product of the weights of all its steps. 
  The following result of Flajolet~\cite{Fl80} is our starting point.

%%%%%%%%%%%%%%%%%%
\begin{lem}[Flajolet]\label{flajolet} We have 
$$
\sum_{n=0}^{\infty}\left(\sum_{p\in \mathcal{MP}_n}w(p)\right)t^n
=\cfrac{1}{1-b_0t-\cfrac{\lambda_1t^2}{1-b_1t-\cfrac{\lambda_2t^2}{1-b_2t-\cdots}}}.
$$
\end{lem}

A Motzkin path without level-steps is called a \emph{Dyck path}, 
and a Motzkin path without level-steps at odd height is called
an \emph{Andr\'e path}.  
We denote by $\mathcal{AP}_{n, k}$ the set of Andr\'e paths of half-length $n$ with $k$ level-steps, 
and 
$\mathcal{DP}_n$ the set of Dyck paths of half length $n$.
%%%%%%%%%%%%%%%
\begin{lem}\label{Euler-Flajolet} Let $b_{i}=0$  ($i\geq 0$) 
and $\lambda_{i}=\lfloor \frac{i+1}{2}\rfloor$ ($i\geq 1$). Then 
 \[
 n!=\sum_{p\in \mathcal{MP}_n}w(p).
 \]
 In other words,  the factorial $n!$ is the generating polynomial of $\mathcal{DP}_n$.
\end{lem}
\begin{rem}
A bijective proof of Euler's formula \eqref{Euler-Flajolet}  is known, see  \cite[(4.9)]{PZ19}.
\end{rem}
%%%%%%%%%%%%%%%
\begin{lem}\label{lem1} Let $b_{2i}=1$, $b_{2i+1}=0$  ($i\geq 0$) 
and $\lambda_{k}=\lfloor \frac{k+1}{2}\rfloor {t}$ ($i\geq 1$). Then 
 \[
 D_{n+1}(1,-1, t)=\sum_{p\in \mathcal{AP}_n}w(p).
 \]
 In other words,  the polynomial $D_{n+1}(1,-1, t)$ is the generating polynomial of 
 Andr\'e paths of length $n$.
\end{lem}

 Let 
\[
\mathcal{Y}_{n,k}:=\{(y_1, \ldots, y_{k+1})\in \N^{k+1}: y_1+\cdots +y_{k+1}=n-2k \}.
\]
%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{lem}\label{lem2} For $0\leq k\leq \lfloor{n/2}\rfloor$,
there is an explicit bijection $\psi: \mathcal{AP}_{n, n-2k}\to \mathcal{Y}_{n,k}\times \mathcal{DP}_{k}$ such that 
if   $\psi(u)=(y,p)$ with for $u\in \mathcal{AP}_{n, n-2k}$ and  $(y,p)\in \mathcal{Y}_{n,k}\times  \mathcal{DP}_{k}$ then
$w(u)=w(p)$, where the weight is associated to the sequences $(b_i)$ and $(\lambda_i)$
with $b_{2i}=1$, $b_{2i+1}=0$  ($i\geq 0$),  
and $\lambda_{k}=\lfloor \frac{k+1}{2}\rfloor {t}$ ($i\geq 1$).
\end{lem}
\begin{proof} 
Since an Andr\'e  path (word)  on $\{\mathsf{U, D, L}\}$ has only level-steps 
at even height and starts from height 0, so the subword 
  between two consecutive level-steps $\mathsf{L}$'s must be of even length and is  a word on the alphabet  $\{\mathsf{UU}, \mathsf{DD}, \mathsf{UD}, \mathsf{DU}\}$.
Thus, 
any Andr\'e word $u\in \mathcal{AP}_{n, n-2k}$  can be  written  
in a unique way as follows:
$$
u=\mathsf{L}^{y_1}w_1\mathsf{L}^{y_2}w_2\ldots w_k\mathsf{L}^{y_{k+1}}\quad\textrm{with}\quad  w_i\in \{\mathsf{UU, DD, UD, DU}\}.
$$ 
Let  
$y:=(y_1, \ldots, y_{k+1})$ and
$p:=w_1\ldots w_k$. As the  path $p$ is obtained by removing out all  the level-steps $\mathsf{L}$'s from  the Andr\'e path $u$, each step in $p$ keeps 
the same height in $u$, and $(y,p)\in \mathcal{Y}_{n,k}\times  \mathcal{DP}_{k}$,
Let $\psi(u)=(y, p)$. It is clear that this is the desired bijection.
\end{proof}

\begin{thm}\label{formula(-1)} For $n\geq 1$ we have 
\begin{align}\label{t-Han}
D_{n}(1,-1,t)=\sum_{k=0}^{n-1}\binom{n-1-k}{ k}k!t^k.
\end{align}
\end{thm}
\begin{proof}[Proof of \cref{formula(-1)}]
By \cref{lem1,lem2} we have 
\[
D_{n+1}(1,-1, t)=\sum_{k\geq 0}\sum_{(y,p)\in \mathcal{Y}_{n,k}\times \mathcal{DP}_{k}}w(p).
\]
Since the cardinality of $\mathcal{Y}_{n,k}$  is $\binom{n-k}{k}$, and 
the generating polynomial of $\mathcal{DP}_k$ is equal to $k! t^k$ by \cref{Euler-Flajolet}, summing over all
 $0\leq k\leq \lfloor{n/2}\rfloor$ we obtain \cref{t-Han}.
\end{proof}

\begin{rem}
The full-length paper for this extended abstract is available at \cite{PZ19}.
\end{rem}


\printbibliography




\end{document}
