<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[finalversion]{FPSAC2020}
\articlenumber{12}
\addbibresource{fpsac.bib}

\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}

\makeatletter
\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}[section]
\newtheorem{cor}[thm]{\protect\corollaryname}
\newtheorem{lem}[thm]{\protect\lemmaname}
\crefname{lem}{Lemma}{Lemmas}

\usepackage{microtype}
\usepackage{verbatim}

%for commentsâ€”delete when finished
\usepackage[dvipsnames]{xcolor}
\newcommand{\ig}[1]{{\color{RedOrange}IG: #1}}
\usepackage[normalem]{ulem} %\sout for strike-through
\newenvironment{new}{\color{NavyBlue}}{}
%to hide comments (e.g., to check page restriction): uncomment the following
%renewcommand{\ig}[1]{} \renewcommand{\sout}[1]{}


%% 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[Counting permutations by peaks, descents, and cycle type]{Counting permutations by peaks, descents, and cycle type}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Ira Gessel and Yan Zhuang]{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, Waltham, MA, USA \\
\addressmark{2}Department of Mathematics and Computer Science, Davidson College, Davidson, NC, USA}

%% 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 derive a general formula describing the joint distribution of two permutation statistics---the peak number 
and the descent number---over any set of permutations whose quasisymmetric generating function is a symmetric function. 
Our formula involves a certain kind of plethystic substitution on quasisymmetric generating functions. We apply this result 
to cyclic permutations, involutions, and derangements, and to give a generating function formula for counting permutations 
by peaks, descents, and cycle type. We recover as special cases results previously derived by D{\'e}sarm{\'e}nien--Foata, 
Gessel--Reutenauer, Fulman, and Diaconis--Fulman--Holmes.}

%% 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, peaks, descents, cycle type, symmetric functions, plethysm}


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

\makeatother

\usepackage{babel}

  \providecommand{\corollaryname}{Corollary}
  \providecommand{\lemmaname}{Lemma}
\providecommand{\theoremname}{Theorem}

\begin{document}
\global\long\def\pk{\operatorname{pk}}
\global\long\def\des{\operatorname{des}}
\global\long\def\maj{\operatorname{maj}}
\global\long\def\lpk{\operatorname{lpk}}
\global\long\def\Des{\operatorname{Des}}
\global\long\def\Comp{\operatorname{Comp}}
\global\long\def\QSym{\operatorname{QSym}}
\global\long\def\udr{\operatorname{udr}}
\global\long\def\fix{\operatorname{fix}}
\global\long\def\ps{\operatorname{ps}}

\maketitle
\setcounter{footnote}{0}

\section{Introduction}

Let $\pi=\pi(1)\pi(2)\cdots\pi(n)$ be an element of the symmetric
group $\mathfrak{S}_{n}$ of permutations of the set $[n]\coloneqq\{1,2,\dots,n\}$.
We say that $i\in[n-1]$ is a \textit{descent} of $\pi$ if $\pi(i)&gt;\pi(i+1)$.
The \textit{descent set} of $\pi$ is the set of all descents of $\pi$.
Let $\des(\pi)$ denote the number of descents of $\pi$ (i.e., the
size of the descent set) and let $\maj(\pi)$ denote the sum of all
descents of $\pi$. The \textit{descent number} $\des$ and \textit{major
index} $\maj$ are classical permutation statistics whose study dates
back to Percy MacMahon \cite{macmahon}.

The distribution of the descent number over $\mathfrak{S}_{n}$ is
encoded by the $n$th \textit{Eulerian polynomial} 
\[
A_{n}(t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}t^{\des(\pi)+1},
\]
and the joint distribution of the descent number and major index by
the $n$th $q$-\textit{Eulerian polynomial }
\[
A_{n}(q,t)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}q^{\maj(\pi)}t^{\des(\pi)+1}.
\]
MacMahon \cite[Vol. 2, Section IX]{macmahon} proved a formula of
which a special case is
\begin{equation}
\frac{A_{n}(q,t)}{(1-t)(1-tq)\cdots(1-tq^{n})}=\sum_{k=0}^{\infty}[k]_{q}^{n}t^{k},\label{e-qeulerian}
\end{equation}
where $[k]_{q}\coloneqq1+q+q^{2}+\cdots+q^{k-1}$. \eqref{e-qeulerian}
allows one to compute the joint distribution of the descent number
and major index over $\mathfrak{S}_{n}$, but one may also want to
study the joint distribution of these statistics, as well as others,
over certain interesting subsets of $\mathfrak{S}_{n}$. 

We are concerned here with permutation statistics that are determined
by the descent set; these statistics are called \textit{descent statistics}.
Examples include the descent number, major index, and also the ``peak
number'' statistic which is defined below. In many cases, formulas
for distributions of descent statistics can be extracted in a useful
way from quasisymmetric functions. For example, the first author and
Reutenauer proved in \cite[Theorem 5.3]{Gessel1993} (see also \cite[Section 4]{Gessel1984})
that if the quasisymmetric generating function $Q(\Pi)$ of $\Pi\subseteq\mathfrak{S}_{n}$
is a symmetric function (see \cref{ss-qsymgf} for relevant
definitions), then 
\begin{align}
\frac{\sum_{\pi\in\Pi}t^{\des(\pi)+1}q^{\maj(\pi)}}{(1-t)(1-tq)\cdots(1-tq^{n})} &amp; =\sum_{k=0}^{\infty}\ps_{k}(Q(\Pi))t^{k}\label{e-desmaj}
\end{align}
where $\ps_{k}(f)\coloneqq f(1,q,\dots,q^{k-1})$. This formula reduces
to \eqref{e-qeulerian} when $\Pi$ is taken to be $\mathfrak{S}_{n}$.
They then use symmetric function operations to derive from \eqref{e-desmaj}
formulas for the joint distribution of $\des$ and $\maj$ over cyclic
permutations, involutions, and derangements\textemdash which all have
symmetric quasisymmetric generating functions. Later, Jason Fulman
\cite[Theorem 1]{Fulman1998} used \cref{e-desmaj} to derive a formula
for the joint distribution of $\des$, $\maj$, and cycle type over
$\mathfrak{S}_{n}$. These results are notable because the descent
number and major index, like all descent statistics, are statistics
which encode properties of a permutation in one-line representation,
and it is generally  difficult to study distributions of such
statistics while refining by cycle structure.

In our recent paper \cite{Gessel}, we prove several general
formulas analogous to \cref{e-desmaj} for the distributions of various
other descent statistics over any subset of $\mathfrak{S}_{n}$ whose
quasisymmetric generating function is symmetric. These formulas involve plethysm, an operation on symmetric functions which has in recent
decades been extended to more general formal power series rings and
has found numerous applications within algebraic combinatorics. 

This extended abstract is a summary of our results in \cite{Gessel}
with a focus on the peak number statistic $\pk$. Given $\pi\in\mathfrak{S}_{n}$,
we say that $i\in\{2,\dots,n-1\}$ is a \textit{peak} of $\pi$ if
$\pi(i-1)&lt;\pi(i)&gt;\pi(i+1)$, and we let $\pk(\pi)$ denote the number
of peaks of $\pi$. In Section 2, we review some relevant definitions
and results from the theory of symmetric and quasisymmetric functions.
We present our general formula for the joint distribution of $\pk$
and $\des$ in Section 3, followed by applications to cyclic permutations,
involutions, derangements, and more generally, counting permutations
by peaks, descents, and cycle type. Finally, in Section 4 we briefly
discuss our general formulas for two other descent statistics: the
left peak number and the number of up-down runs.

\section{Preliminaries}

\subsection{\label{s-permenum}Symmetric functions and plethysm}

We assume familiarity with basic definitions from the theory of symmetric
functions as described by Stanley \cite[Chapter 7]{Stanley2001}.
In this section we establish notation and  define the
plethysm operation which will be needed for our main result. (See \cite{Loehr2011} for a more comprehensive introductory reference on plethysm.)

We use the notation $\left|\lambda\right|=n$ to indicate that $\lambda$
is a partition of $n$, and we let $l(\lambda)$ denote the number
of parts of $\lambda$. We write $\lambda=(1^{m_{1}}2^{m_{2}}\cdots)$
to mean that $\lambda$ has $m_{1}$ parts of size 1, $m_{2}$ parts
of size 2, and so on; alternatively, we write $\lambda=(\lambda_{1},\lambda_{2},\dots,\lambda_{r})$
to mean that $\lambda$ has parts $\lambda_{1},\lambda_{2},\dots,\lambda_{r}$.
Given a partition $\lambda=(1^{m_{1}}2^{m_{2}}\cdots)$, let $z_{\lambda}\coloneqq1^{m_{1}}m_{1}!\,2^{m_{2}}m_{2}!\cdots$. 

Let $\Lambda$ denote the $\mathbb{Q}$-algebra of symmetric functions
in the variables $x_{1},x_{2},\dots$. 
In particular, we will need 
the complete symmetric functions $h_{n}$,
the elementary symmetric functions $e_{n}$, and the power sum symmetric
functions $p_{\lambda}$. 
We will often work in the ring $\hat\Lambda$ of symmetric functions of unbounded degree (with coefficients in some polynomial ring). In the ring $\hat\Lambda$ we define $H(x)\coloneqq\sum_{n=0}^{\infty}h_{n}x^{n}$
and $E(x)\coloneqq\sum_{n=0}^{\infty}e_{n}x^{n}$ to be the ordinary
generating functions for the $h_{n}$ and the $e_{n}$, respectively.
We also adopt the notation $H\coloneqq H(1)=\sum_{n=0}^{\infty}h_{n}$.

Let $\left\langle \cdot\kern1pt,\cdot\right\rangle \colon\Lambda\times\Lambda\rightarrow\mathbb{Q}$
denote the usual scalar product on symmetric functions which may be
defined by 
\[
\left\langle p_{\lambda},p_{\tau}\right\rangle \coloneqq\begin{cases}
z_{\lambda}, &amp; \text{if }\lambda=\tau,\\
0, &amp; \text{otherwise}
\end{cases}
\]
for all $\lambda$ and $\tau$, and then extending bilinearly.

\begin{comment}
\ig{I think that for this abstract, it's probably better just to define plethysm and not bring in lambda rings. See below for a suggested rewrite.}
We define a \textit{lambda ring} over $\mathbb{Q}$ to be a commutative
$\mathbb{Q}$-algebra $A$ together with a $\mathbb{Q}$-algebra
homomorphism $\psi_{i}\colon A\rightarrow A$ for every $i\in\mathbb{P}$
(the set of positive integers) such that $\psi_{1}$ is the identity
map, and $\psi_{i}\circ\psi_{j}=\psi_{ij}$ for every $i,j\in\mathbb{P}$.
These homomorphisms $\psi_{i}$ are called \textit{Adams operations}.
We define an operation $\Lambda\times A\rightarrow A$, where the
image of $(f,a)\in\Lambda\times A$ is denoted $f[a]$, by these two
properties:
\begin{enumerate}
\item For any $i\geq1$, $p_{i}[a]=\psi_{i}(a)$.
\item For any fixed $a\in A$, the map $f\mapsto f[a]$ is a $\mathbb{Q}$-algebra
homomorphism from $\Lambda$ to $A$.
\end{enumerate}
Throughout this paper, we will take our lambda ring $A$ to be a $\mathbb{Q}$-algebra
of formal power series containing $\Lambda$ as a subalgebra, and
the $i$th Adams operation $\psi_{i}$ to be the result of replacing
each variable with its $i$th power. For a symmetric function $f\in\Lambda$,
this means that $p_{i}[f]=\psi_{i}(f(x_{1},x_{2},\dots))=f(x_{1}^{i},x_{2}^{i},\dots)$
but more generally all other variables are raised to the $i$th power
as well. For example, $p_{i}[qt^{2}p_{m}]=\psi_{i}(qt^{2}p_{m})=q^{i}t^{2i}p_{im}$.
The map $(f,a)\mapsto f[a]$ is called \textit{plethysm}. (Sometimes
the term ``plethysm'' is restricted to the case in which $A=\Lambda$
but we will use it for this more general operation.)
It is important to note that plethysm does not commute with evaluation
of variables. If $\alpha$ is a variable then $p_{n}[\alpha]=\alpha^{n}$,
but if $y$ is a rational number then $p_{n}[y]=y$; thus $\left.p_{n}[\alpha]\right|_{\alpha=y}\neq p_{n}[y]$.
\end{comment}

Let $A$ be a
$\mathbb{Q}$-algebra of formal power series in some set of variables (possibly containing $\Lambda$).
We define an operation $\Lambda\times A\rightarrow A$, where the
image of $(f,a)\in\Lambda\times A$ is denoted $f[a]$, by these two
properties:
\begin{enumerate}
\item For any $i\geq1$, $p_{i}[a]$ is the result of replacing each variable in $a$ with its $i$th power.
\item For any fixed $a\in A$, the map $f\mapsto f[a]$ is a $\mathbb{Q}$-algebra
homomorphism from $\Lambda$ to $A$.
\end{enumerate}
For a symmetric function $f\in\Lambda$,
this means that $p_{i}[f(x_1,x_2,\dots)]=f(x_{1}^{i},x_{2}^{i},\dots)$.  
If $f$ contains other variables than the $x_i$ then they are raised to the $i$th power
as well. For example, if $q$ and $t$ are variables then $p_{i}[qt^{2}p_{m}]=q^{i}t^{2i}p_{im}$.
If $f$ is expressed in terms of the power sums, $p_i[f]$ can be obtained from $f$ by replacing each $p_m$ with $p_{mi}$.
The map $(f,a)\mapsto f[a]$ is called \textit{plethysm}. 
It is important to note that plethysm does not commute with evaluation
of variables. If $\alpha$ is a variable then $p_{n}[\alpha]=\alpha^{n}$,
but if $y$ is a rational number then $p_{n}[y]=y$; thus in this case $\left.p_{n}[\alpha]\right|_{\alpha=y}\neq p_{n}[y]$.

We extend plethysm to a partial map $\hat\Lambda\times A\rightarrow A$ in the obvious way:  if each $f_i$ is in $\Lambda$ then 
$\bigl(\sum_{k=0}^\infty f_i\bigr)[a] \coloneqq \sum_{k=0}^\infty f_i[a]$ as long as both infinite sums converge as formal power series. 

\subsection{\label{ss-qsymgf}Descent compositions, cycle type, and quasisymmetric
generating functions}

We use the notation $L\vDash n$ to indicate that $L$ is a composition
of $n$. Every permutation can be uniquely decomposed into a sequence
of maximal increasing consecutive subsequen\-ces--- or equivalently,
maximal consecutive subsequences containing no descents\textemdash which
we call \textit{increasing runs}. The \textit{descent composition}
of $\pi$, denoted $\Comp(\pi)$, is the composition whose parts are
the lengths of the increasing runs of $\pi$ in the order that they
appear. For example, the increasing runs of $\pi=85712643$ are $8$,
$57$, $126$, $4$, and $3$, so the descent composition of $\pi$
is $\Comp(\pi)=(1,2,3,1,1)$. 

For a composition $L=(L_{1},L_{2},\dots,L_{k})$, let $\Des(L)\coloneqq\{L_{1},L_{1}+L_{2},\dots,L_{1}+\cdots+L_{k-1}\}$.
It is easy to see that if $L$ is the descent composition of $\pi$,
then $\Des(L)$ is the descent set of $\pi$. Recall that the fundamental
quasisymmetric function $F_{L}$ is defined by
\[
F_{L}\coloneqq\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n}\\
i_{j}&lt;i_{j+1}\,\mathrm{if}\,j\in\Des(L)
}
}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}.
\]
Given a set $\Pi$ of permutations, its \textit{quasisymmetric generating
function} $Q(\Pi)$ is defined by 
\[
Q(\Pi)\coloneqq\sum_{\pi\in\Pi}F_{\Comp(\pi)}.
\]

Moreover, given a composition $L=(L_{1},\dots,L_{k})$, let $r_{L}$
denote the skew Schur function of ribbon shape $L$. That is, 
\[
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}}}}&gt;\underset{L_{2}}{\underbrace{i_{L_{1}+1}\leq\cdots\leq i_{L_{1}+L_{2}}}}&gt;\cdots&gt;\underset{L_{k}}{\underbrace{i_{L_{1}+\cdots+L_{k-1}+1}\leq\cdots\leq i_{n}}}.
\]
The following is \cite[Corollary 4]{Gessel1984}.
\begin{thm}
\label{t-QrL} Suppose that $Q(\Pi)$ is symmetric. Then the number
of permutations in $\Pi$ with descent composition $L$ is equal to
$\left\langle Q(\Pi),r_{L}\right\rangle $.
\end{thm}

We say that a permutation $\pi$ has \textit{cycle type} $\lambda=(1^{m_{1}}2^{m_{2}}\cdots)$
if $\pi$ has exactly $m_{1}$ cycles of size 1, $m_{2}$ cycles of
size 2, and so on. Henceforth, cycles of size $i$ are called $i$-\textit{cycles},
1-cycles in particular are called \textit{fixed points}, and the number
of fixed points of a permutation $\pi$ is denoted $\fix(\pi)$. For
$n\in\mathbb{P}$, define the symmetric function $L_{n}$ by 
\begin{equation}
L_{n}\coloneqq\frac{1}{n}\sum_{d\mid n}\mu(d)p_{d}^{n/d}\label{e-cycqgf}
\end{equation}
where $\mu$ is the number-theoretic M{\"o}bius function. Given
a partition $\lambda=(1^{m_{1}}2^{m_{2}}\cdots)$, define $L_{\lambda}$
by 
\[
L_{\lambda}\coloneqq h_{m_{1}}[L_{1}]h_{m_{2}}[L_{2}]\cdots.
\]
The symmetric functions $L_{\lambda}$ are called \textit{Lyndon symmetric
functions}. Gessel and Reutenauer \cite[Theorem 2.1]{Gessel1993}
showed that $L_{\lambda}$ is the quasisymmetric generating function
for the set of permutations with cycle type $\lambda$.
\begin{cor}
The number of permutations $\pi$ with cycle type $\lambda$ and descent
composition $M$ is equal to $\left\langle L_{\lambda},r_{M}\right\rangle $.
\end{cor}


\section{Results}

\subsection{General formula}

Given a variable (or integer) $y\in A$ and an integer $k\in\mathbb{Z}$,
define the homomorphism $\Theta_{y,k}\colon\Lambda\rightarrow\mathbb{Q}[[y]]$
by
\[
\Theta_{y,k}(f)\coloneqq f[k(1-\alpha)]\rvert_{\alpha=-y}.
\]
That is, $\Theta_{y,k}$ first sends a symmetric function $f$ to
the plethystic substitution $f[k(1-\alpha)]$, where $\alpha$ is
a variable, and then evaluates this expression at $\alpha=-y$.

Given a set $\Pi$ of permutations, define
\[
P^{(\pk,\des)}(\Pi;y,t)\coloneqq\sum_{\pi\in\Pi}y^{\pk(\pi)+1}t^{\des(\pi)+1};
\]
this polynomial encodes the joint distribution of $\pk$ and $\des$
over $\Pi$. If $\Pi$ has a symmetric quasisymmetric function $Q(\Pi)$,
then the following theorem allows us to describe this polynomial in
terms of $\Theta_{y,k}(Q(\Pi))$ and in terms of Eulerian polynomials.
\begin{thm}
\label{t-pkdes} Let $\Pi\subseteq\mathfrak{S}_{n}$ and suppose that
its quasisymmetric generating function $Q(\Pi)$ is a symmetric function
with power sum expansion $Q(\Pi)=\sum_{\lambda\vdash n}c_{\lambda}p_{\lambda}$.
Then 
\begin{multline*}
\frac{1}{1+y}\left(\frac{1+yt}{1-t}\right)^{n+1}P^{(\pk,\des)}\left(\Pi;\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt}\right)\\
=\sum_{k=0}^{\infty}\Theta_{y,k}(Q(\Pi))t^{k}=\sum_{\substack{\lambda\vdash n}
}c_{\lambda}\frac{A_{l(\lambda)}(t)}{(1-t)^{l(\lambda)+1}}\prod_{k=1}^{l(\lambda)}(1-(-y)^{\lambda_{k}}).
\end{multline*}
\end{thm}

The full proof of \cref{t-pkdes} is in \cite{Gessel}, but
let us sketch the proof here. We begin by stating three preliminary
lemmas, one concerning plethysm, one giving the power sum expansion
of $(1-tE(y)H)^{-1}$, and one giving the ribbon expansion of $(1-tE(y)H)^{-1}$.
The first two lemmas are proved in \cite{Gessel}, whereas the third
is an immediate consequence of \cite[Lemma 4.1]{Zhuang2017}. 
\begin{lem}
\label{l-scalprodh} Let $f\in A$, let $\alpha$ be a variable, and
let $k\in\mathbb{Z}$. Then $f[k(1-\alpha)]=\left\langle f,H^{k}E(-\alpha)^{k}\right\rangle $.
\end{lem}

\begin{lem}
\label{l-pkdesps}
\[
\frac{1}{1-tE(y)H}=\sum_{\lambda}\frac{p_{\lambda}}{z_{\lambda}}\frac{A_{l(\lambda)}(t)}{(1-t)^{l(\lambda)+1}}\prod_{k=1}^{l(\lambda)}(1-(-y)^{\lambda_{k}}).
\]
\end{lem}

\begin{lem}
\label{l-pkdesrib}
\begin{multline*}
\frac{1}{1-tE(y)H}=\frac{1}{1-t}\\
+\frac{1}{1+y}\sum_{n=1}^{\infty}\sum_{L\vDash n}\left(\frac{1+yt}{1-t}\right)^{n+1}\left(\frac{(1+y)^{2}t}{(y+t)(1+yt)}\right)^{\pk(L)+1}\left(\frac{y+t}{1+yt}\right)^{\des(L)+1}r_{L}.
\end{multline*}
\end{lem}

In \cref{l-pkdesrib}, $\des(L)$ is defined to be $\des(\pi)$
for any permutation $\pi$ with descent composition $L$, and $\pk(L)$
is defined analogously. These are well-defined because the descent
number and peak number are descent statistics; they depend only on
the descent composition. \crefrange{l-scalprodh}{l-pkdesrib}
allow us to derive three expressions for the scalar product $\left\langle Q(\Pi),(1-tE(y)H)^{-1}\right\rangle $:
\begin{enumerate}
\item It follows from \cref{l-scalprodh} that
\[
\left\langle Q(\Pi),\frac{1}{1-tE(y)H}\right\rangle =\sum_{k=0}^{\infty}\left\langle Q(\Pi),E(y)^{k}H^{k}\right\rangle t^{k}=\sum_{k=0}^{\infty}\Theta_{y,k}(Q(\Pi))t^{k}.
\]
\item It follows from \cref{l-pkdesps} that 
\[
\left\langle Q(\Pi),\frac{1}{1-tE(y)H}\right\rangle =\sum_{\lambda\vdash n}c_{\lambda}\frac{A_{l(\lambda)}(t)}{(1-t)^{l(\lambda)+1}}\prod_{k=1}^{l(\lambda)}(1-(-y)^{\lambda_{k}}).
\]
\item It follows from \cref{l-pkdesrib} and \cref{t-QrL} that
\[
\left\langle Q(\Pi),\frac{1}{1-tE(y)H}\right\rangle =\frac{1}{1+y}\left(\frac{1+yt}{1-t}\right)^{n+1}P^{(\pk,\des)}\left(\Pi;\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt}\right).
\]
\end{enumerate}
Equating these three expressions completes the proof of \cref{t-pkdes}.

\subsection{Cyclic permutations}

We say that a permutation of length $n$ is a \textit{cyclic permutation}
(or a \textit{cycle}) if it has cycle type $(n)$. We denote the set
of cyclic permutations of length $n$ by $\mathfrak{C}_{n}$. The
formula below follows immediately from  \cref{t-pkdes}
and \eqref{e-cycqgf}, which is the quasisymmetric generating
function for $\mathfrak{C}_{n}$.
\begin{thm}
\label{t-cycpkdes} Let $n\geq1$. Then
\begin{multline*}
P^{(\pk,\des)}\left(\mathfrak{C}_{n};\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt}\right)\\
=\frac{(1+y)}{n(1+yt)^{n+1}}\sum_{d\mid n}\mu(d)(1-(-y)^{d})^{n/d}(1-t)^{n-n/d}A_{n/d}(t).
\end{multline*}
\end{thm}

Although this formula may seem complicated, it allows for easy computation
of the polynomials $P^{(\pk,\des)}(\mathfrak{C}_{n};y,t)$ in the
following way. First, we replace $y$ with $u$ and $t$ with $v$
in the formula. Then set $y=\frac{(1+u)^{2}v}{(u+v)(1+uv)}$ and $t=\frac{u+v}{1+uv}$;
solving these two equations yield $u=\frac{1+t^{2}-2yt-(1-t)\sqrt{(1+t)^{2}-4yt}}{2(1-y)t}$
and $v=\frac{(1+t)^{2}-2yt-(1+t)\sqrt{(1+t)^{2}-4yt}}{2yt}$. Thus,
we have 
\begin{align*}
P^{(\pk,\des)}(\mathfrak{C}_{n};y,t) &amp; =\frac{(1+u)}{n(1+uv)^{n+1}}\sum_{d\mid n}\mu(d)(1-(-u)^{d})^{n/d}(1-v)^{n-n/d}A_{n/d}(v).
\end{align*}
(All of the formulas given later in this paper can be inverted in
a similar manner, but we will omit the details.) For example, for
$n=5$, we have 
\begin{align*}
 &amp; P^{(\pk,\des)}(\mathfrak{C}_{5};y,t)=\frac{(1+u)}{5(1+uv)^{6}}((1+u)^{5}A_{5}(v)-(1+u^{5})(1-v)^{4}A_{1}(v))\\
 &amp; \qquad\qquad=\frac{1+u}{5(1+uv)^{6}}((1+u)^{5}(v+26v^{2}+66v^{3}+26v^{4}+v^{5})-(1+u^{5})(1-v)^{4}v))\\
 &amp; \qquad\qquad=(y+5y^{2})t^{2}+(y+8y^{2}+3y^{3})t^{3}+(y+5y^{2})t^{4}.
\end{align*}
where the last equality was obtained by substituting in $u=\frac{1+t^{2}-2yt-(1-t)\sqrt{(1+t)^{2}-4yt}}{2(1-y)t}$
and $v=\frac{(1+t)^{2}-2yt-(1+t)\sqrt{(1+t)^{2}-4yt}}{2yt}$ and then
simplifying using Maple. 

Observe that in $P^{(\pk,\des)}(\mathfrak{C}_{5};y,t)$, the coefficient
of $t^{2}$ is equal to the coefficient of $t^{4}$. In fact, for
any $n\in\mathbb{P}$ not congruent to 2 modulo 4, the number of cyclic
permutations of length $n$ with $j$ peaks and $k$ descents is equal
to the number of cyclic permutations of length $n$ with $j$ peaks
and $n-1-k$ descents. This is not easily apparent from the formula
obtained in \cref{t-cycpkdes}, but is a special case of the
following result, which we prove in \cite{Gessel}.
\begin{thm}
\label{t-compsym} Suppose that $\lambda$ is a partition of $n$
with no parts congruent to 2 modulo 4 and that every odd part of $\lambda$
occurs only once. Then the number of permutations of cycle type $\lambda$
with $j$ peaks and $k$ descents is equal to the number of permutations
of cycle type $\lambda$ with $j$ peaks and $n-1-k$ descents.
\end{thm}

Given $\Pi\subseteq\mathfrak{S}_{n}$, let us define 
\[
A(\Pi;t)\coloneqq\sum_{\pi\in\Pi}t^{\des(\pi)+1}\quad\text{and}\quad P^{\pk}(\Pi;t)\coloneqq\sum_{\pi\in\Pi}t^{\pk(\pi)+1}.
\]
Specializing \cref{t-cycpkdes} at $y=0$ yields
\[
A(\mathfrak{C}_{n};t)=\frac{1}{n}\sum_{d\mid n}\mu(d)(1-t)^{n-n/d}A_{n/d}(t),
\]
which is the $q=1$ evaluation of a formula by Gessel and Reutenauer
\cite[Corollary 6.2]{Gessel1993}. Specializing at $y=1$, on the
other hand, yields the formula
\[
P^{\pk}\left(\mathfrak{C}_{n};\frac{4t}{(1+t)^{2}}\right)=\frac{1}{n(1+t)^{n+1}}\sum_{\substack{d\mid n\\
d\textup{ odd}
}
}\mu(d)2^{n/d+1}(1-t)^{n-n/d}A_{n/d}(t).
\]

\subsection{Involutions}

A permutation $\pi$ is called an \textit{involution} if $\pi^{2}$
is the identity permutation, or equivalently, if $\pi$ has no cycles
of size larger than 2. We denote the set of involutions of length
$n$ by~$\mathfrak{I}_{n}$. The quasisymmetric generating function
for all involutions weighted by length and number of fixed points
is known to be
\begin{align}
\sum_{n=0}^{\infty}\sum_{\pi\in\mathfrak{I}_{n}}F_{\Comp(\pi)}z^{\fix(\pi)}x^{n} &amp; =\prod_{i}\frac{1}{1-zxx_{i}}\prod_{i&lt;j}\frac{1}{1-x^{2}x_{i}x_{j}};\label{e-invqgf}
\end{align}
see \cite[Equation (7.1)]{Gessel1993}.

For $\Pi\subseteq\mathfrak{S}_{n}$, let 
\[
P^{(\pk,\des,\fix)}(\Pi;y,t,z)\coloneqq\sum_{\pi\in\Pi}y^{\pk(\pi)+1}t^{\des(\pi)+1}z^{\fix(\pi)}.
\]
In \cite{Gessel}, we use \cref{t-pkdes} and \eqref{e-invqgf}
to derive the following generating function formula for the polynomials
$P^{(\pk,\des,\fix)}(\mathfrak{I}_{n};y,t,z)$.
\begin{thm}
\label{t-Ipkdesfix} 
\begin{multline*}
\frac{1}{1-t}+\frac{1}{1+y}\sum_{n=1}^{\infty}\left(\frac{1+yt}{1-t}\right)^{n+1}P^{(\pk,\des,\fix)}\left(\mathfrak{I}_{n};\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt},z\right)x^{n}\\
=\sum_{k=0}^{\infty}\frac{(1+zxy)^{k}(1+x^{2}y)^{k^{2}}t^{k}}{(1-zx)^{k}(1-x^{2})^{{k \choose 2}}(1-x^{2}y^{2})^{{k+1 \choose 2}}}
\end{multline*}
\end{thm}

Given $\Pi\subseteq\mathfrak{S}_{n}$, let 
\[
P^{(\des,\fix)}(\Pi;t,z)\coloneqq\sum_{\pi\in\Pi}t^{\des(\pi)+1}z^{\fix(\pi)}\quad\text{and}\quad P^{(\pk,\fix)}(\Pi;t,z)\coloneqq\sum_{\pi\in\Pi}t^{\pk(\pi)+1}z^{\fix(\pi)}.
\]
Specializing \cref{t-Ipkdesfix} at $y=0$ yields 
\begin{align*}
\frac{1}{1-t}+\sum_{n=1}^{\infty}\frac{P^{(\des,\fix)}(\mathfrak{I}_{n};t,z)}{(1-t)^{n+1}}x^{n} &amp; =\sum_{k=0}^{\infty}\frac{t^{k}}{(1-zx)^{k}(1-x^{2})^{{k \choose 2}}},
\end{align*}
which is equivalent to Equation (5.5) of D{\'e}sarm{\'e}nien and
Foata \cite{Desarmenien1985} and Equation (7.3) of Gessel and Reutenauer
\cite{Gessel1993}. Specializing at $y=1$ yields the formula
\begin{multline*}
\qquad\frac{1}{1-t}+\frac{1}{2}\sum_{n=1}^{\infty}\left(\frac{1+t}{1-t}\right)^{n+1}P^{(\pk,\fix)}\left(\mathfrak{I}_{n};\frac{4t}{(1+t)^{2}},z\right)x^{n}\\
=\sum_{k=0}^{\infty}\frac{(1+zx)^{k}(1+x^{2})^{k^{2}}t^{k}}{(1-zx)^{k}(1-x^{2})^{{k \choose 2}}(1-x^{2})^{{k+1 \choose 2}}}.\qquad
\end{multline*}

\subsection{Derangements}

Let $\mathfrak{D}_{n}$ denote the set of \textit{derangements}\textemdash permutations
with no fixed points\textemdash of length $n$. The quasisymmetric
generating function for all permutations weighted by length and number
of fixed points is known to be
\begin{align}
\sum_{n=0}^{\infty}\sum_{\pi\in\mathfrak{S}_{n}}F_{\Comp(\pi)}z^{\fix(\pi)}x^{n} &amp; =\frac{H(zx)}{H(x)(1-p_{1}x)};\label{e-snqgf}
\end{align}
see the proof of \cite[Theorem 8.4]{Gessel1993}. Setting $z=0$ in
\eqref{e-snqgf} specializes to derangements.

We prove the following in \cite{Gessel} using \cref{t-pkdes}
and \eqref{e-snqgf}.
\begin{thm}
\label{t-pkdesfix} We have
%\begin{enumerate}
%\item [\normalfont{(a)}] 
\begin{multline*}
\frac{1}{1-t}+\frac{1}{1+y}\sum_{n=1}^{\infty}\left(\frac{1+yt}{1-t}\right)^{n+1}P^{(\pk,\des,\fix)}\left(\mathfrak{S}_{n};\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt},z\right)x^{n}\\
=\sum_{k=0}^{\infty}\frac{(1+zxy)^{k}}{(1-zx)^{k}}\frac{(1-x)^{k}}{(1+xy)^{k}}\frac{t^{k}}{1-k(1+y)x}
\end{multline*}
%\item [\normalfont{(b)}] 
\null\\[-20pt]
and
\begin{multline*}
\frac{1}{1-t}+\frac{1}{1+y}\sum_{n=1}^{\infty}\left(\frac{1+yt}{1-t}\right)^{n+1}P^{(\pk,\des)}\left(\mathfrak{D}_{n};\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt}\right)x^{n}\\
=\sum_{k=0}^{\infty}\frac{(1-x)^{k}}{(1+xy)^{k}}\frac{t^{k}}{1-k(1+y)x}.
\end{multline*}
%\end{enumerate}
\end{thm}

We can also specialize the formulas in \cref{t-pkdesfix} at
$y=0$ and $y=1$ to obtain generating function formulas for the polynomials
$P^{(\des,\fix)}(\mathfrak{S}_{n};t,z)$, $P^{(\pk,\fix)}(\mathfrak{S}_{n};t,z)$,
$A(\mathfrak{D}_{n};t)$, and $P^{\pk}(\mathfrak{D}_{n};t)$; we omit
these formulas here. In particular, the formula obtained for $P^{(\des,\fix)}(\mathfrak{S}_{n};t,z)$
is the $q=1$ evaluation of a formula by Gessel and Reutenauer \cite[Equation (8.3)]{Gessel1993}.

\subsection{Cycle type}

\cref{t-pkdesfix} gave a formula for counting permutations
by the number of fixed points jointly with the peak number and descent
number. We now refine this result by giving a formula for counting
permutations by peaks, descents, and cycle type.

For a permutation $\pi$, let $N_{i}(\pi)$ denote the number of $i$-cycles
in $\pi$. Similarly, given a partition $\lambda$, let $N_{i}(\lambda)$
denote the number of parts of size $i$ in $\pi$. Recall that the
Lyndon symmetric function
\[
L_{\lambda}=h_{m_{1}}[L_{1}]h_{m_{2}}[L_{2}]\cdots
\]
is the quasisymmetric generating function for the set of permutations
with cycle type $\lambda=(1^{m_{1}}2^{m_{2}}\cdots)$. Then 
\begin{align}
1+\sum_{n=1}^{\infty}\sum_{\lambda\vdash n}L_{\lambda}x^{n}\prod_{i=1}^{\infty}z_{i}^{N_{i}(\lambda)} &amp; =\sum_{m_{1},m_{2},\dots}\prod_{i=1}^{\infty}h_{m_{i}}[L_{i}](z_{i}x^{i})^{m_{i}}=\prod_{i=1}^{\infty}\sum_{m_{i}=0}^{\infty}h_{m_{i}}[L_{i}](z_{i}x^{i})^{m_{i}}\label{e-ctypeqgf}
\end{align}
is the quasisymmetric generating function for all permutations refined
by cycle type and length.

Define
\[
F_{n}^{(\pk,\des)}(y,t,z_{1},z_{2},\dots)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}y^{\pk(\pi)+1}t^{\des(\pi)+1}\prod_{i=1}^{\infty}z_{i}^{N_{i}(\pi)},
\]
\[
F_{n}^{\pk}(t,z_{1},z_{2},\dots)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}t^{\pk(\pi)+1}\prod_{i=1}^{\infty}z_{i}^{N_{i}(\pi)},
\]
and 
\[
F_{n}^{\des}(t,z_{1},z_{2},\dots)\coloneqq\sum_{\pi\in\mathfrak{S}_{n}}t^{\des(\pi)+1}\prod_{i=1}^{\infty}z_{i}^{N_{i}(\pi)}.
\]
We prove the next theorem in \cite{Gessel} using \cref{t-pkdes}
and \eqref{e-ctypeqgf}.
\begin{thm}
\label{t-pkdesct}

\begin{multline*}
\frac{1}{1-t}+\frac{1}{1+y}\sum_{n=1}^{\infty}\left(\frac{1+yt}{1-t}\right)^{n+1}F_{n}^{(\pk,\des)}\left(\frac{(1+y)^{2}t}{(y+t)(1+yt)},\frac{y+t}{1+yt},z_{1},z_{2},\dots\right)x^{n}\\
=\sum_{k=0}^{\infty}t^{k}\prod_{i=1}^{\infty}\exp\bigg(\sum_{m_{i}=1}^{\infty}\frac{(z_{i}x^{i})^{m_{i}}}{im_{i}}\sum_{d\mid i}\mu(d)(k(1-(-y)^{dm_{i}}))^{i/d}\bigg).
\end{multline*}
\end{thm}

Now, define the numbers
\[
f_{i,k}\coloneqq\frac{1}{i}\sum_{d\mid i}\mu(d)k^{i/d}\quad\text{and}\quad g_{i,k}\coloneqq\frac{1}{2i}\sum_{\substack{d\mid i\\
i\:\text{odd}
}
}\mu(d)(2k)^{i/d}.
\]
We can specialize \cref{t-pkdesct} at $y=0$ to recover the
formula
\[
\frac{1}{1-t}+\sum_{n=1}^{\infty}\frac{F_{n}^{\des}(t,z_{1},z_{2},\dots)}{(1-t)^{n+1}}x^{n}=\sum_{k=0}^{\infty}t^{k}\prod_{i=1}^{\infty}\left(\frac{1}{1-z_{i}x^{i}}\right)^{f_{i,k}},
\]
which was originally proved by Fulman \cite{Fulman1998}. Specializing
at $y=1$ recovers the formula
\[
\frac{1}{1-t}+\frac{1}{2}\sum_{n=1}^{\infty}\left(\frac{1+t}{1-t}\right)^{n+1}F_{n}^{\pk}\left(\frac{4t}{(1+t)^{2}},z_{1},z_{2},\dots\right)x^{n}=\sum_{k=0}^{\infty}t^{k}\prod_{i=1}^{\infty}\left(\frac{1+z_{i}x^{i}}{1-z_{i}x^{i}}\right)^{g_{i,k}},
\]
originally due to Diaconis, Fulman, and Holmes \cite{Diaconis2013}; see also \cite{Fulman2019}.

\section{Other descent statistics}

Let us call $i\in[n-1]$ a \textit{left peak} of $\pi$ if $i$ is
a peak or if $i=1$ and $\pi(1)&gt;\pi(2)$. A \textit{birun} of $\pi$
is a maximal monotone consecutive subsequence, and an \textit{up-down
run} of $\pi$ is a birun of $\pi$ or the letter $\pi(1)$ if $\pi(1)&gt;\pi(2)$.
Let $\lpk(\pi)$ the number of left peaks of $\pi$, and $\udr(\pi)$
the number of up-down runs of $\pi$.

Define 
\[
P^{\lpk}(\Pi;t)\coloneqq\sum_{\pi\in\Pi}t^{\lpk(\pi)}\quad\text{and}\quad P^{\udr}(\Pi;t)\coloneqq\sum_{\pi\in\Pi}t^{\udr(\pi)}.
\]
The theorem below is an analogue of \cref{t-pkdes} for the
$\lpk$ and $\udr$ statistics; we omit the proof. 
\begin{thm}
\label{t-lpkudr} Let $\Pi\subseteq\mathfrak{S}_{n}$ and suppose
that its quasisymmetric generating function $Q(\Pi)$ is a symmetric
function with power sum expansion $Q(\Pi)=\sum_{\lambda\vdash n}c_{\lambda}p_{\lambda}$.
Then 

\begin{align*}
\frac{(1+t)^{n}}{(1-t)^{n+1}}P^{\lpk}\left(\Pi;\frac{4t}{(1+t)^{2}}\right) &amp; =\sum_{k=0}^{\infty}\Theta_{1,k}(Q(\Pi)[X+1])t^{k}=\sum_{\lambda\vdash n}c_{\lambda}\frac{B_{o(\lambda)}(t)}{(1-t)^{o(\lambda)+1}}
\end{align*}
and
\begin{align*}
 &amp; \frac{(1+t^{2})^{n}}{2(1-t)^{2}(1-t^{2})^{n-1}}P^{\udr}\left(\Pi;\frac{2t}{1+t^{2}}\right)\\
 &amp; \qquad\qquad\qquad\qquad\qquad=\sum_{k=0}^{\infty}\Theta_{1,k}(Q(\Pi))t^{2k}+\sum_{k=0}^{\infty}\Theta_{1,k}(Q(\Pi)[X+1])t^{2k+1}\\
 &amp; \qquad\qquad\qquad\qquad\qquad=\sum_{\substack{\lambda\vdash n\\
\textup{all parts odd}
}
}c_{\lambda}2^{l(\lambda)}\frac{A_{l(\lambda)}(t^{2})}{(1-t^{2})^{l(\lambda)+1}}+t\sum_{\substack{\lambda\vdash n}
}c_{\lambda}\frac{B_{o(\lambda)}(t^{2})}{(1-t^{2})^{o(\lambda)+1}},
\end{align*}
where $o(\lambda)$
is the number of odd parts of $\lambda$ and $B_{n}(t)$ is the $n$th type
$B$ Eulerian polynomial \textup{(}defined, e.g., in \cite[Section 2.3]{Zhuang2017}\textup{)}.
\end{thm}

In \cite{Gessel}, we use \cref{t-lpkudr} to obtain formulas
for the distributions of $\lpk$ and $\udr$ over cyclic permutations,
derangements, and involutions, and for counting permutations by these
statistics jointly with cycle type.

\printbibliography

\end{document}
</pre></body></html>