\documentclass{FPSAC2019}

\articlenumber{6}
\addbibresource{6.bib}

\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
%\usepackage{geometry}
%\geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{mathtools}
%\usepackage{amsmath}
%\usepackage{amsthm}
%\usepackage{amssymb}
%\usepackage{verbatim}

\makeatletter

\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}
  \theoremstyle{plain}
  \newtheorem{lem}[thm]{\protect\lemmaname}

\usepackage{microtype}

%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}


%% define your title in the usual way
\title[]{Homomorphisms on noncommutative symmetric functions and permutation enumeration}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[]{Ira M. Gessel\addressmark{1}\thanks{\href{mailto:gessel@brandeis.edu}{gessel@brandeis.edu}. Supported by a grant from the Simons Foundation (\#427060, Ira Gessel).} \and Yan Zhuang\addressmark{2}\thanks{\href{mailto:yazhuang@davidson.edu}{yazhuang@davidson.edu}}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Brandeis University \\
\addressmark{2}Department of Mathematics and Computer Science, Davidson College}

%% 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{We present a unifying framework for deriving permutation enumeration formulas involving restrictions
on descent compositions or permutation statistics describable in terms of descent compositions: these formulas can be
proven by first lifting them to the algebra of noncommutative symmetric functions and then 
applying an appropriate homomorphism. We give several applications of this method including rederivations and
extensions of classical results in the literature as well as new results.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{permutation statistics, noncommutative symmetric functions, descents, inversions, peaks, shuffle-compatibility}


\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}

\makeatother

\usepackage{babel}
  \providecommand{\lemmaname}{Lemma}
\providecommand{\theoremname}{Theorem}

%\addbibresource{bibliography.bib}

\begin{document}
\global\long\def\pk{\operatorname{pk}}
\global\long\def\val{\operatorname{val}}
\global\long\def\des{\operatorname{des}}
\global\long\def\maj{\operatorname{maj}}
\global\long\def\comaj{\operatorname{comaj}}
\global\long\def\st{\operatorname{st}}
\global\long\def\Des{\operatorname{Des}}
\global\long\def\Comp{\operatorname{Comp}}
\global\long\def\QSym{\operatorname{QSym}}
\global\long\def\inv{\operatorname{inv}}
\global\long\def\altdes{\operatorname{altdes}}
\global\long\def\ides{\operatorname{ides}}
\global\long\def\ipk{\operatorname{ipk}}
\global\long\def\Av{\operatorname{Av}}

\maketitle
\setcounter{footnote}{0}

\section{Introduction}

Let $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$ be a permutation in $\mathfrak{S}_{n}$,
the set of permutations of $[n]=\{1,2,\dots,n\}$. Let $\left|\pi\right|$
be the length of $\pi$, so that $\left|\pi\right|=n$ whenever $\pi\in\mathfrak{S}_{n}$.
We say that $i\in[n-1]$ is a \textit{descent} of $\pi\in\mathfrak{S}_{n}$
if $\pi_{i}>\pi_{i+1}$.

Every permutation can be uniquely decomposed into a sequence of maximal
increasing consecutive subsequences\textemdash or equivalently, maximal
consecutive subsequences containing no descents\textemdash which we
call \textit{increasing runs}. For example, the descents of $\pi=85712643$
are 1, 3, 6, and 7, and the increasing runs of $\pi$ are 8, 57, 126,
4, and 3. The composition of $n$ whose parts correspond to the increasing
run lengths of $\pi$ is called the \textit{descent composition} of
$\pi$ and is denoted $\Comp(\pi)$. Thus, $\Comp(\pi)=(1,2,3,1,1)$
for $\pi=85712643$.

There are many classical results in the literature that count permutations
with various restrictions on descent compositions. For example, David
and Barton \cite{David1962} showed that

\begin{equation}
\left[\sum_{n=0}^{\infty}\Big(\frac{x^{mn}}{(mn)!}-\frac{x^{mn+1}}{(mn+1)!}\Big)\right]^{-1}\label{e-lessthanm}
\end{equation}
is the exponential generating function for permutations in which every
increasing run has length less than $m$. Many classical permutation
statistics can also be characterized in terms of their descent composition.
For example, the number of descents of a permutation is exactly one
less than its number of increasing runs.

In a series of recent papers \cite{Gessel2014,Zhuang2016,Zhuang2017,Gessel2018a},
the present authors show that permutation enumeration formulas involving
restrictions on descent compositions (or involving permutation statistics
that can be described in terms of the descent composition) can be
proven under a unifying framework by deriving a lifting of the formula
in the algebra $\mathbf{Sym}$ of noncommutative symmetric functions
and then applying an appropriate homomorphism. We use this very general
method to prove a myriad of new formulas as well as to provide a new
derivation of David and Barton's formula \eqref{e-lessthanm} and
of other formulas previously obtained by Carlitz \cite{Carlitz73},
Chebikin \cite{chebikin}, Elizalde \cite{Elizalde2016}, Elizalde\textendash Noy
\cite{Elizalde2003}, Petersen \cite{Petersen2006,Petersen2007},
Remmel \cite{remmel}, Stanley \cite{Stanley1976,Stanley2008}, and
Stembridge \cite{Stembridge1997}.

The purpose of this extended abstract is to outline this method of
permutation enumeration, summarize some of the work done in the papers
\cite{Gessel2014,Zhuang2016,Zhuang2017,Gessel2018a}, and to describe
new developments in this domain which utilize the theory of shuffle-compatible
permutation statistics. We begin in \cref{sec:preliminaries} by introducing preliminary
definitions and ideas from permutation enumeration and the basic theory
of noncommutative symmetric functions, including a key reciprocity
formula from the first author's Ph.D.\ dissertation \cite{gessel-thesis}
which is used to obtain many noncommutative symmetric function formulas
necessary for our applications. In \cref{sec:ourmethod}, we define three homomorphisms
on noncommutative symmetric functions and demonstrate several applications
of our method using these homomorphisms, including a rederivation
of \eqref{e-lessthanm}. Finally, in \cref{sec:homomorphisms}, we explain how each
``shuffle-compatible descent statistic'' induces a new homomorphism
that can be used to count permutations by the corresponding ``inverse
statistic'', and present a few applications of these homomorphisms
for the descent and peak number statistics.

\section{Preliminaries}\label{sec:preliminaries}

\subsection{\label{s-permenum} Permutation enumeration}

We let $\des(\pi)$ denote the number of descents of $\pi$. The distribution
of the descent number statistic is given by the $n$th \textit{Eulerian
polynomial} $A_{n}(t)$ defined by 
\[
A_{n}(t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}t^{\des(\pi)+1}
\]
for $n\geq1$ and by $A_{0}(t)\coloneqq1$.\footnote{For all families of statistic-encoding polynomials defined in this
extended abstract, we take the convention that the $0$th polynomial
is always defined to be 1.} A related permutation statistic is the number of inversions; an \textit{inversion}
of a permutation $\pi\in\mathfrak{S}_{n}$ is a pair of indices $(i,j)$
with $1\leq i<j\leq n$ such that $\pi_{i}>\pi_{j}$. Then the number
of inversions of $\pi$ is denoted $\inv(\pi)$. For example, the
inversions of $\pi=1432$ are $(2,3)$, $(2,4)$, and $(3,4)$, so
$\inv(\pi)=3$. The joint distribution of the inversion number and
descent number is given by the $n$th $q$-\textit{Eulerian polynomial}
$A_{n}(q,t)$ defined by 

\[
A_{n}(q,t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}q^{\inv(\pi)}t^{\des(\pi)+1}.
\]

We say that $\pi$ is an \textit{alternating} permutation if $\pi_{1}>\pi_{2}<\pi_{3}>\pi_{4}<\cdots$.
It is well known that the number of alternating permutations in $\mathfrak{S}_{n}$
is the $n$th Euler number $E_{n}$ defined by $\sum_{n=0}^{\infty}E_{n}x^{n}/n!=\sec x+\tan x$.
In \cite{chebikin}, Chebikin introduced a variant of the notion of
descents which is closely related to alternating permutations and
the Euler numbers: $i\in[n-1]$ is called an \textit{alternating descent}
of $\pi$ if $i$ is odd and $\pi_{i}>\pi_{i+1}$ or if $i$ is even
and $\pi_{i}<\pi_{i+1}$. We define an \textit{alternating run} of
$\pi$ to be a maximal consecutive subsequence of $\pi$ containing
no alternating descents. For example, the alternating runs of the
permutation 3421675 are 342, 1, and 675.

The notions of alternating descents and alternating runs give rise
to an ``alternating analogue'' for nearly every concept defined in
terms of descents. For example, the alternating descent composition
and the alternating descent number $\altdes$ are defined in the obvious
way. The distribution of the alternating descent number over $\mathfrak{S}_{n}$
is given by the $n$th \textit{alternating Eulerian polynomial} defined
by 
\[
\hat{A}_{n}(t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}t^{\altdes(\pi)+1}.
\]


\subsection{Noncommutative symmetric functions}

\begingroup\emergencystretch=1cm
Let $\mathbb{Q}\langle\langle X_{1},X_{2},\dots\rangle\rangle$ be
the $\mathbb{Q}$-algebra of formal power series in countably many
noncommuting variables $X_{1},X_{2},\dots$. Consider the \textit{ribbon
functions} $\mathbf{r}_{L}\in\mathbb{Q}\langle\langle X_{1},X_{2},\dots\rangle\rangle$
defined as follows. For a composition $L=(L_{1},\dots,L_{k})$, let
\[
\mathbf{r}_{L}\coloneqq\sum_{i_{1},\dots i_{n}}X_{i_{1}}X_{i_{2}}\cdots X_{i_{n}}
\]
where the sum is over all $i_{1},\dots,i_{n}$ satisfying 
\[
\underset{L_{1}}{\underbrace{i_{1}\leq\cdots\leq i_{L_{1}}}}>\underset{L_{2}}{\underbrace{i_{L_{1}+1}\leq\cdots\leq i_{L_{1}+L_{2}}}}>\cdots>\underset{L_{k}}{\underbrace{i_{L_{1}+\cdots+L_{k-1}+1}\leq\cdots\leq i_{n}}}.
\]
Let $\mathbf{Sym}$ denote the vector space with basis $\{\mathbf{r}_{L}\}$;
then $\mathbf{Sym}$ is a graded $\mathbb{Q}$-subalgebra of $\mathbb{Q}\langle\langle X_{1},X_{2},\dots\rangle\rangle$.
The elements of $\mathbf{Sym}$ are called \textit{noncommutative
symmetric functions} and were introduced in the seminal paper \cite{ncsf1}
of Gelfand et al.
\endgroup

In particular, define the noncommutative symmetric function $\mathbf{h}_{n}$
by

\[
\mathbf{h}_{n}\coloneqq\mathbf{r}_{(n)}=\sum_{i_{1}\leq\cdots\leq i_{n}}X_{i_{1}}X_{i_{2}}\cdots X_{i_{n}}
\]
for $n\geq1$ and let $\mathbf{h}_{0}\coloneqq1$. These are noncommutative
versions of the complete symmetric functions $h_{n}$. The $\mathbf{h}_{n}$
are algebraically independent and generate $\mathbf{Sym}$, so to
define a $\mathbb{Q}$-algebra homomorphism on $\mathbf{Sym}$, it
suffices to define the map on the $\mathbf{h}_{n}$. 

In what follows, we will make use of a reciprocity theorem relating
the $\mathbf{h}_{n}$ and $\mathbf{r}_{L}$. This theorem was first
proved in an equivalent form by the first author \cite[Theorem 5.2]{gessel-thesis},
and we call this the ``run theorem'' because it can be used, as we
do here, to prove many formulas counting permutations with restrictions
on increasing runs.
\begin{thm}[Run theorem]
\label{t-runs} Suppose that the sequences $\{v_{n}\}_{n\geq0}$
and $\{w_{n}\}_{n\geq0}$ are related by 
\begin{align*}
\sum_{n=0}^{\infty}v_{n}x^{n} & =\bigg(\sum_{n=0}^{\infty}w_{n}x^{n}\bigg)^{-1}
\end{align*}
where $v_{0}=w_{0}=1$. Then
\[
\sum_{L}w_{L}\mathbf{r}_{L}=\bigg(\sum_{n=0}^{\infty}v_{n}\mathbf{h}_{n}\bigg)^{-1}
\]
where the sum on the left is over all compositions $L$, and $w_{L}$
is defined by $w_{L}\coloneqq w_{L_{1}}w_{L_{2}}\cdots w_{L_{k}}$
where $L=(L_{1},L_{2},\dots,L_{k})$.
\end{thm}

\section{Our method}\label{sec:ourmethod}

\subsection{Set-up: three homomorphisms}

Many results in the next two sections are obtained by applying certain
homomorphisms to various identities involving noncommutative symmetric
functions. The simplest of these homomorphisms is the map $\Phi\colon\mathbf{Sym}\rightarrow\mathbb{Q}[[x]]$
defined by $\Phi(\mathbf{h}_{n})=x^{n}/n!$. We now give an alternating
analogue and a $q$-analogue of $\Phi$. Define the homomorphism $\hat{\Phi}\colon\mathbf{Sym}\rightarrow\mathbb{Q}[[x]]$
by $\hat{\Phi}(\mathbf{h}_{n})=E_{n}x^{n}/n!$ and define the homomorphism
$\Phi_{q}\colon\mathbf{Sym}\rightarrow\mathbb{Q}[[q,x]]$ by $\Phi_{q}(\mathbf{h}_{n})=x^{n}/[n]_{q}!$.

For our applications, we need to determine the effect of these homomorphisms
on the ribbon functions. Let $\beta(L)$ be the number of permutations
with descent composition $L$, let $\hat{\beta}(L)$ be the number of permutations
with alternating descent composition $L$, and let 
\[
\beta_{q}(L)\coloneqq\sum_{\Comp(\pi)=L}q^{\inv(\pi)}
\]
be the polynomial counting permutations with descent composition $L$
by inversion number.
\begin{lem}
\label{l-phirib} Let $L$ be a composition of $n$. We have
\[
\Phi(\mathbf{r}_{L})=\beta(L)\frac{x^{n}}{n!},\quad\hat{\Phi}(\mathbf{r}_{L})=\hat{\beta}(L)\frac{x^{n}}{n!},\quad\mathrm{and}\quad\Phi_{q}(\mathbf{r}_{L})=\beta_{q}(L)\frac{x^{n}}{[n]_{q}!}.
\]
\end{lem}
See \cite{Gessel2014,Zhuang2017} for a proof of \cref{l-phirib}.

\subsection{Example: David and Barton's formula}

The homomorphisms $\Phi$, $\hat{\Phi}$, and $\Phi_{q}$ give us
a general principle that whenever we have an exponential generating
function that counts permutations with a restriction on increasing
run lengths, there is an analogous exponential generating function\textemdash obtained
by replacing $x^{n}/n!$ by $E_{n}x^{n}/n!$\textemdash for counting
permutations with the same restriction on alternating run lengths,
as well as an analogous $q$-exponential generating function\textemdash obtained
by replacing $x^{n}/n!$ by $x^{n}/[n]_{q}!$\textemdash for counting
permutations with the same restriction on increasing run lengths but
also keeping track of the inversion number.

As a first example, let us show how we can derive David and Barton's
formula \eqref{e-lessthanm} as well as an alternating analogue and
a $q$-analogue of \eqref{e-lessthanm} using these three homomorphisms.
First we need the following lemma, which is easily proven using the
run theorem by taking $w_{n}=1$ for all $n<m$ and $w_{n}=0$ for
all $n\geq m$.
\begin{lem}
\label{l-ncsflessthanm} Let $m$ be a positive integer. Then 
\begin{equation}
\sum_{L}\mathbf{r}_{L}=\Big(\sum_{n=0}^{\infty}(\mathbf{h}_{mn}-\mathbf{h}_{mn+1})\Big)^{-1}\label{e-ncsflessthanm}
\end{equation}
where the sum on the left is over all compositions $L$ with all parts
less than $m$.
\end{lem}
Observe that applying the homomorphism $\Phi$ to \eqref{e-ncsflessthanm}
recovers David and Barton's formula \eqref{e-lessthanm}. Applying
$\hat{\Phi}$ to \eqref{e-ncsflessthanm} instead, we obtain an alternating
analogue of \eqref{e-lessthanm}.
\begin{thm}
\label{t-lessthanmalt} Let $m$ be a positive integer, and let $a_{m,n}$
denote the number of permutations in $\mathfrak{S}_{n}$ with all
alternating runs having length less than $m$. Then 
\[
\sum_{n=0}^{\infty}a_{m,n}\frac{x^{n}}{n!}=\left[\sum_{n=0}^{\infty}\Big(E_{mn}\frac{x^{mn}}{(mn)!}-E_{mn+1}\frac{x^{mn+1}}{(mn+1)!}\Big)\right]^{-1}.
\]
\end{thm}
And, applying $\Phi_{q}$ to (\ref{e-ncsflessthanm}) yields a $q$-analogue
of (\ref{e-lessthanm}). Let $\Av_{n}(\underline{12\cdots m})$ denote
the set of $n$-permutations with all increasing runs having length
less than $m$.\footnote{This notation comes from the literature on permutation pattern avoidance;
permutations with all increasing runs having length less than $m$
are precisely the permutations avoiding the monotone consecutive pattern
$\underline{12\cdots m}$.}
\begin{thm}
\label{t-lessthanmq} Let $m$ be a positive integer. Then 
\[
\sum_{n=0}^{\infty}\sum_{\pi\in\Av_{n}(\underline{12\cdots m})}q^{\inv(\pi)}\frac{x^{n}}{[n]_{q}!}=\left[\sum_{n=0}^{\infty}\Big(\frac{x^{mn}}{[mn]_{q}!}-\frac{x^{mn+1}}{[mn+1]_{q}!}\Big)\right]^{-1}.
\]
\end{thm}
\cref{t-lessthanmalt} is new to our approach, whereas \cref{t-lessthanmq} was also recently proven by Elizalde \cite{Elizalde2016} using a $q$-analogue
of the Goulden\textendash Jackson cluster method 
in the context of consecutive pattern avoidance.

\subsection{Example: A generalization of David and Barton's formula}\label{ssec:example_david}

The next main result is motivated by the following question: Since
\[
\left[\sum_{n=0}^{\infty}(-1)^{n}\frac{x^{n}}{n!}\right]^{-1}=\sum_{n=0}^{\infty}\frac{x^{n}}{n!},
\]
\sloppy
do the coefficients of reciprocals of the partial sums of $\sum_{n=0}^{\infty}(-1)^{n}x^{n}/n!$
have a \linebreak combinatorial interpretation? There are negative coefficients
for partial sums with an odd number of terms, but for those with an
even number of terms the reciprocals have all non-negative coefficients,
and here we give a combinatorial interpretation for these coefficients.
Related results can be found in \cite{Gessel2018a}.
\fussy

\begin{thm}
\label{t-expparsum} Let $k$ be a positive integer, and let $b_{k,n}$
be the number of permutations in $\mathfrak{S}_{n}$ in which every
increasing run has length congruent to 0 or 1 modulo $2k$. Then
\[
\sum_{n=0}^{\infty}b_{k,n}\frac{x^{n}}{n!}=\left[\sum_{n=0}^{2k-1}(-1)^{n}\frac{x^{n}}{n!}\right]^{-1}.
\]
\end{thm}
We first state a lemma, which can be obtained via the run theorem
by taking $w_{n}=1$ whenever $n$ is congruent to $0,1,\dots$, or
$m-1$ modulo $km$ and taking $w_{n}=0$ otherwise.
\begin{lem}
\label{l-ncsfmod} Let $m$ and $k$ be positive integers. Then 
\begin{equation}
\sum_{L}\mathbf{r}_{L}=\Big(\sum_{n=0}^{k-1}(\mathbf{h}_{mn}-\mathbf{h}_{mn+1})\Big)^{-1}\label{e-ncsfmod}
\end{equation}
where the sum on the right is over all compositions $L$ where every
part is congruent to $0,1,\dots,$ $or$ $m-1$ modulo $km$.
\end{lem}
Applying the homomorphism $\Phi$ to (\ref{e-ncsfmod}), we obtain
the following.
\begin{thm}
Let $m$ and $k$ be positive integers, and let $c_{k,m,n}$ be the
number of permutations in $\mathfrak{S}_{n}$ in which every increasing
run has length congruent to $0,1,\dots,$ $or$ $m-1$ modulo $km$.
Then 
\begin{equation}
\sum_{n=0}^{\infty}c_{k,m,n}\frac{x^{n}}{n!}=\left[\sum_{n=0}^{k-1}\Big(\frac{x^{mn}}{(mn)!}-\frac{x^{mn+1}}{(mn+1)!}\Big)\right]^{-1}.\label{e-mod}
\end{equation}
\end{thm}
Note that \cref{t-expparsum} follows by setting $m=2$ in
(\ref{e-mod}) and we can recover David and Barton's formula by taking
the limit as $k\rightarrow\infty$ in (\ref{e-mod}). We can also
obtain an alternating analogue and a $q$-analogue of this formula,
but we omit these results here.

\subsection{Example: Eulerian polynomials}

Lastly, we demonstrate how the homomorphisms $\Phi$, $\hat{\Phi}$,
and $\Phi_{q}$ can be used to recover several results relating to
the polynomials $A_{n}(t)$, $\hat{A}_{n}(t)$, and $A_{n}(q,t)$
defined in \cref{s-permenum}. As before, we begin with a noncommutative
symmetric function formula; this one can be obtained from the run
theorem by setting $w_{n}=t$ for all $n\geq1$. 
\begin{lem}
\label{l-ncsfdes} Let $m$ be a positive integer. Then 
\begin{equation}
\sum_{L}t^{l(L)}\mathbf{r}_{L}=(1-t)\Big(1-t\sum_{n=0}^{\infty}(1-t)^{n}\mathbf{h}_{n}\Big)^{-1}\label{e-ncsfdes}
\end{equation}
where the sum on the left is over all compositions $L$, and $l(L)$
denotes the number of parts of $L$.
\end{lem}
Applying $\Phi$ to (\ref{e-ncsfdes}) yields the classical exponential
generating function 
\[
\sum_{n=0}^{\infty}A_{n}(t)\frac{x^{n}}{n!}=\frac{1-t}{1-te^{(1-t)x}}
\]
for Eulerian polynomials. Applying $\hat{\Phi}$ instead yields the
exponential generating function 
\[
\sum_{n=0}^{\infty}\hat{A}_{n}(t)\frac{x^{n}}{n!}=\frac{1-t}{1-t(\sec((1-t)x)+\tan((1-t)x))}
\]
for alternating Eulerian polynomials, proved earlier in an equivalent
form by Chebikin \cite{chebikin}. Finally, applying $\Phi_{q}$ yields
Stanley's \cite{Stanley1976} well-known $q$-exponential generating
function
\[
\sum_{n=0}^{\infty}A_{n}(q,t)\frac{x^{n}}{[n]_{q}!}=\frac{1-t}{1-t\exp_{q}((1-t)x)}
\]
for $q$-Eulerian polynomials, where $\exp_{q}(x)\coloneqq\sum_{n=0}^{\infty}x^{n}/[n]_{q}!$.

\section{Homomorphisms arising from shuffle-compatibility}\label{sec:homomorphisms}

\subsection{Quasisymmetric functions and shuffle-compatibility}

Let $x_{1},x_{2},\dots$ be commuting variables. Then $\QSym$ is
the $\mathbb{Q}$-subalgebra of $\mathbb{Q}[[x_{1},x_{2},\dots]]$
with basis given by the \textit{fundamental quasisymmetric functions}
$\{F_{L}\}_{L\vDash n}$, where
\[
F_{L}\coloneqq\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n}\\
i_{j}<i_{j+1}\,\mathrm{if}\,j\in\Des(L)
}
}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}
\]
and $\Des(L)$ is the descent set of any permutation with descent
composition $L$. The elements of $\QSym$ are called \textit{quasisymmetric
functions} and were introduced by the first author \cite{Gessel1984}.
The algebra $\QSym$ of quasisymmetric functions is closely related
to the algebra $\mathbf{Sym}$ of noncommutative symmetric functions;
for instance, they are dual as Hopf algebras. We will make use of
a natural homomorphism $\tau\colon\mathbf{Sym}\rightarrow\QSym$ given
by 
\[
\tau(\mathbf{r}_{L})=\sum_{\Comp(\pi)=L}F_{\Comp(\pi^{-1})}.
\]
This homomorphism is obtained by composing the canonical inclusion
from $\mathbf{Sym}$ to the Malvenuto\textendash Reutenauer algebra
with the canonical projection from the Malvenuto-Reutenauer
algebra to $\QSym$; see \cite[Section 8]{Grinberg2016} for details.

Recently, the present authors initiated the study of shuffle-compatible
permutation statistics \cite{Gessel2018}. Roughly speaking, a permutation
statistic $\st$ is said to be shuffle-compatible if the distribution
of $\st$ over the ``shuffles'' of two permutations $\pi$ and $\sigma$
depend only on $\st(\pi)$, $\st(\sigma)$, and the lengths of $\pi$
and $\sigma$. We will not need the precise definition of a shuffle-compatible
permutation statistic here, but we note that the descent number is
shuffle-compatible whereas the alternating descent number and inversion
number are not. Other classical permutation statistics known to be
shuffle-compatible include the major index, comajor index, and peak
number.

A permutation statistic is called a \textit{descent statistic} if
it depends only on the descent composition. For example, the descent
number, alternating descent number, major index, comajor index, and
peak number are all descent statistics, but the inversion number $\inv$
is not. Given a descent statistic $\st$, we write $\st(L)$ to mean
the value of $\st$ on any permutation with descent composition $L$.
Thus every descent statistic $\st$ induces an equivalence relation
on the set of compositions in the following way: we say that compositions
$J$ and $K$ are $\st$-\textit{equivalent} if $\left|J\right|=\left|K\right|$
and $\st(J)=\st(K)$. For example, the compositions $J=(3,1,4)$ and
$K=(2,4,2)$ are $\des$-equivalent.

The following is one of our main theorems in \cite{Gessel2018}, relating
the study of shuffle-compatible descent statistics to the theory of quasisymmetric
functions.
\begin{thm}
A descent statistic $\st$ is shuffle-compatible if and only if there
exists a $\mathbb{Q}$-algebra homomorphism $\phi_{\st}:\QSym\rightarrow\text{\ensuremath{\mathcal{A}}}_{\st}$,
where $\text{\ensuremath{\mathcal{A}}}_{\st}$ is a $\mathbb{Q}$-algebra
with basis $\{a_{\alpha}\}$ indexed by $\st$-equivalence classes
$\alpha$ of compositions, such that $\phi_{\st}(F_{L})=a_{\alpha}$
whenever $L\in\alpha$. 
\end{thm}
Here, we note that $\text{\ensuremath{\mathcal{A}}}_{\st}$ is called
the \textit{shuffle algebra} of $\st$ and the multiplication of its
basis elements $a_{\alpha}$ encode the distribution of $\st$ over
shuffles of permutations.

Given a shuffle-compatible descent statistic $\st$, let us define
the homomorphism $\Phi_{\st}$ by $\Phi_{\st}\coloneqq\phi_{\st}\circ\tau$.
As with $\Phi$, $\hat{\Phi}$, and $\Phi_{q}$, we can use the homomorphisms
$\Phi_{\st}$ under the same framework to produce analogous permutation
enumeration formulas for the ``inverse statistic'' corresponding to
$\st$. We shall illustrate this with $\Phi_{\des}$, the homomorphism
arising from the shuffle-compatibility of the descent number.

\subsection{Counting permutations by inverse descents}

The \textit{Hadamard product} $*$ on formal power series in $t$ is
given by 
\[
\Big(\sum_{n=0}^{\infty}a_{n}t^{n}\Big)*\Big(\sum_{n=0}^{\infty}b_{n}t^{n}\Big)=\sum_{n=0}^{\infty}a_{n}b_{n}t^{n}.
\]
Let $\mathbb{Q}[[t*,x]]$ denote the $\mathbb{Q}$-algebra of formal
power series in $t$ and $x$, where the \linebreak multiplication is Hadamard
product in $t$. The shuffle algebra of the descent number is a subalgebra
of $\mathbb{Q}[[t*,x]]$, and we can describe $\Phi_{\des}\colon\mathbf{Sym}\rightarrow\mathbb{Q}[[t*,x]]$
by
\[
\Phi_{\des}(\mathbf{r}_{L})=\sum_{\Comp(\pi)=L}\frac{t^{\ides(\pi)+1}}{(1-t)^{n+1}}x^{n},
\]
where $\ides$ is the \textit{inverse descent number} statistic defined
by $\ides(\pi)\coloneqq\des(\pi^{-1})$. In particular, $\Phi_{\des}(\mathbf{h}_{n})=\Phi_{\des}(\mathbf{r}_{(n)})=tx^{n}/(1-t)^{n+1}$. 

Let 
\[
M_{m,n}^{\ides}(t)\coloneqq\sum_{\pi\in\Av_{n}(\underline{12\cdots m})}t^{\ides(\pi)+1}.
\]
By applying $\Phi_{\des}$ to (\ref{e-ncsflessthanm}), we obtain
\begin{align*}
\sum_{n=0}^{\infty}\frac{M_{m,n}^{\ides}(t)}{(1-t)^{n+1}}x^{n} & =\Bigg[\frac{t}{(1-t)^{2}}x-\sum_{k=1}^{\infty}\Big(\frac{t}{(1-t)^{mk+1}}x^{mk}-\frac{t}{(1-t)^{mk+2}}x^{mk+1}\Big)\Bigg]^{-1},
\end{align*}
where the reciprocal is with respect to the Hadamard product in $t$.
After some
additional algebraic manipulations, we arrive at the following ``Hadamard
product-free'' formula:
\begin{thm}\label{thm:thm11}
Let $m$ be a positive integer and let $\omega\coloneqq e^{2\pi i/m}$.
Then
\begin{align*}
\sum_{n=0}^{\infty}\frac{M_{m,n}^{\ides}(t)}{(1-t)^{n+1}}x^{n} & =m\sum_{k=0}^{\infty}\left[\sum_{j=1}^{m-1}\frac{1-\omega^{-j}}{(1-\omega^{j}x)^{k}}\right]^{-1}t^{k}\\
 & =\sum_{k=0}^{\infty}\left[{\displaystyle \sum_{j=0}^{\infty}}\left({k+jm-1 \choose k-1}x^{jm}-{k+jm \choose k-1}x^{jm+1}\right)\right]^{-1}t^{k}.
\end{align*}
\end{thm}
This is a new result which refines David and Barton's formula by inverse
descents. Note that taking the limit as $m\rightarrow\infty$ and
extracting coefficients of $x^{n}$ recovers the classical identity
${\displaystyle {\textstyle A_{n}(t)/(1-t)^{n+1}=\sum_{k=0}^{\infty}k^{n}t^{k}}}$
for Eulerian polynomials.

Let us discuss one more application of the homomorphism $\Phi_{\des}$.
The $n$th \textit{two-sided Eulerian polynomial} $A_{n}(s,t)$ is
defined by 
\[
A_{n}(s,t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}s^{\des(\pi)}t^{\ides(\pi)}.
\]
The formula 
\begin{equation}
\frac{A_{n}(s,t)}{(1-s)^{n+1}(1-t)^{n+1}}=\sum_{j,k=0}^{\infty}{jk+n-1 \choose n}s^{j}t^{k}\label{e-2sidedes}
\end{equation}
was proven by Carlitz\textendash Roselle\textendash Scoville \cite{Carlitz1966}
and by Petersen \cite{Petersen2013}; applying $\Phi_{\des}$ to (\ref{e-ncsfdes})
leads to a rederivation of this formula.
\subsection{Counting permutations by peaks and inverse peaks}

Given $\pi\in\mathfrak{S}_{n}$, we say that $i$ is a \textit{peak}
of $\pi$ if $2\leq i\leq n-1$ and $\pi_{i-1}<\pi_{i}>\pi_{i+1}$;
let $\pk(\pi)$ be the number of peaks of $\pi$. The peak number
$\pk$ is a shuffle-compatible permutation statistic, so it induces
a homomorphism $\Phi_{\pk}$ which can be used to produce new formulas
counting permutations by ``inverse peaks''. Like the descent number
shuffle algebra, the peak number shuffle algebra is a subalgebra of
$\mathbb{Q}[[t*,x]]$. We can describe $\Phi_{\pk}\colon\mathbf{Sym}\rightarrow\mathbb{Q}[[t*,x]]$
by
\[
\Phi_{\pk}(\mathbf{r}_{L})=\sum_{\Comp(\pi)=L}\frac{2^{2\ipk(\pi)+1}t^{\ipk(\pi)+1}(1+t)^{n-2\ipk(\pi)-1}}{(1-t)^{n+1}}x^{n},
\]
where $\ipk(\pi)\coloneqq\pk(\pi^{-1})$ is the number of inverse
peaks of $\pi$.

We end this paper with an example of a new formula which can be obtained
via the homomorphism $\Phi_{\pk}$. Define the $n$th \textit{two-sided
peak polynomial} $P_{n}(s,t)$ by 
\[
P_{n}(s,t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}s^{\pk(\pi)}t^{\ipk(\pi)}.
\]

\begin{thm}
\label{t-pkdes-1} Let $n$ be a positive integer. Then
\begin{align*}
\frac{1}{4}\left(\frac{(1+s)(1+t)}{(1-s)(1-t)}\right)^{n+1}P_{n}\left(\frac{4s}{(1+s)^{2}},\frac{4t}{(1+t)^{2}}\right) & =\sum_{i,j=0}^{\infty}\sum_{k=0}^{n}{2ij \choose k}{2ij+n-k-1 \choose n-k}s^{i}t^{j}.
\end{align*}
\end{thm}
\acknowledgements{The first author thanks Brendon Rhoades for discussions that led to the results in \cref{ssec:example_david}. The second author thanks Sergi Elizalde for helpful conversations surrounding \cref{thm:thm11}.}

%\bibliographystyle{plain}
%\bibliography{bibliography}
\printbibliography

\end{document}
