# Permutation Statistics in Conjugacy Classes
of the Symmetric Group111This work was completed in part at the 2022 Graduate
Research Workshop in Combinatorics, which was supported in part by NSF grant
#1953985 and a generous award from the Combinatorics Foundation. ML was
partially supported by J. A. Grochow’s NSF award CISE-2047756 and the
University of Colorado Boulder, Department of Computer Science Summer Research
Fellowship. MY was partially supported by the University of Denver’s
Professional Research Opportunities for Faculty Fund 80369-145601. We wish to
thank Sara Billey for suggesting excedances and Yan Zhuang for bringing
[CJZ20] to our attention.

Michael Levet  Department of Computer Science, University of Colorado Boulder
Kevin Liu  Department of Mathematics, University of Washington  Jesse Campion
Loth  Department of Mathematics, Simon Fraser University  Eric Nathan Stucky
Department of Information Technology & Sciences, Champlain College  Sheila
Sundaram  Pierrepont School, Westport, CT, USA  Mei Yin  Department of
Mathematics, University of Denver

###### Abstract

We introduce the notion of a _weighted inversion statistic_ on the symmetric
group, and examine its distribution on each conjugacy class. Our work
generalizes the study of several common permutation statistics, including the
number of inversions, the number of descents, the major index, and the number
of excedances. As a consequence, we obtain explicit formulas for the first
moments of several statistics by conjugacy class. We also show that when the
cycle lengths are sufficiently large, the higher moments of arbitrary
permutation statistics are independent of the conjugacy class. Fulman (J.
Comb. Theory Ser. A., 1998) previously established this result for major index
and descents. We obtain these results, in part, by generalizing the techniques
of Fulman (ibid.), and introducing the notion of permutation constraints. For
permutation statistics that can be realized via _symmetric_ constraints, we
show that each moment is a polynomial in the degree of the symmetric group.

Keywords. permutation statistics, inversions, descents, excedances, weighted
inversion statistic, moments, permutation constraints

2020 AMS Subject Classification. 05A05, 05E05, 60C05

##  1 Introduction

Let $S_{n}$ denote the symmetric group of permutations on
$[n]=\\{1,2,\dots,n\\}$. A statistic on $S_{n}$ is a map
$X:S_{n}\to\mathbb{R}$. The _distribution_ of $X$ on $S_{n}$ is the function
$(x_{k})_{k\in\mathbb{R}}$, where $x_{k}$ is mapped to the number of
permutations $\omega\in S_{n}$ such that $X(\omega)=k$, i.e.,
$x_{k}=|X^{-1}(k)|$. Perhaps the best known statistics are the numbers of
descents, the major index, and the inversion number of a permutation (see
[Sta97, Sta99]).

We study the distributions of statistics on fixed conjugacy classes of
$S_{n}$. These distributions are known exactly for some classical statistics:
Gessel and Reutenauer [GR93, Theorems 5.3, 5.5, 6.1] gave a generating
function for the joint distribution of descents and major index by conjugacy
class. Brenti [Bre93] gave the generating function by conjugacy class for the
excedance statistic in terms of the Eulerian polynomials. Some asymptotic
results are also known: Fulman [Ful98] showed that descents and major index
exhibit an asymptotically normal distribution on conjugacy classes with
sufficiently large cycles. Kim and Lee [KL20] subsequently extended this
result to any conjugacy class of $S_{n}$.

We focus on the properties of the moments of these distributions. Fulman
[Ful98] showed that for partitions $\lambda\vdash n$ with each
$\lambda_{i}>2\ell$, the $\ell$th moment for descents of the conjugacy class
$C_{\lambda}$ is the same as for the entire symmetric group. In particular,
this implies that the moments for descents and major index on a conjugacy
class $C_{\lambda}$ are dependent only on the smaller part sizes of $\lambda$.
Fulman provided two proofs of this – one using generating functions and the
other a purely combinatorial proof that leveraged the structure of descent
sets. This paper will establish similar dependence results for all permutation
statistics, not just those with special descent structure.

Inspired by the combinatorial proof of [Ful98, Theorem 3], we define a
framework that allows us to calculate the first moment for multiple families
of permutation statistics. It turns out that the first moment for all these
statistics is only dependent on the number of parts of size one and two in
$\lambda$. The higher moments of these statistics are, in general, difficult
to calculate explicitly. Remarkably, this framework allows us to show that the
higher moments of all permutation statistics depend only on the small part
sizes of $\lambda$.

Finally, we show that for a natural class of permutation statistics (see
Theorem 7.26) that include inversions, permutation patterns, and excedances,
these moments are polynomial in $n$. Using these polynomiality results and
data for small values of $n$, we can explicitly calculate some higher moments
of some permutation statistics. Gatez and Pierson [GP22] established the
analogous result for a different generalization of permutation patterns. While
our generalization and that of Gaetz and Pierson [GP22] agree for permutation
patterns on certain conjugacy classes, it is not clear that they both capture
the same family of permutation statistics.

Main results. In this paper, we study the uniform distribution of various
permutation statistics on individual conjugacy classes. Our analysis of the
uniform distribution of a very large class of permutation statistics is
accomplished by the introduction of two notions: weighted inversion statistics
(Section 4) and (symmetric) permutation constraints (Section 7) on $S_{n}$. In
fact, the classically defined inversions, descents, and major index are
specific instances of weighted inversion statistics. While the notion of a
weighted inversion statistic is new, the notion of a permutation constraint
can be traced back to [Ful98, Theorem 3]. The notion of a permutation
constraint is quite powerful, allowing us to reason about arbitrary
permutation statistics. Although symmetric constraints do not appear to
include all weighted inversion statistics, they are still quite general,
capturing inversions, permutation pattern statistics, and excedances.

We first examine the expected values of weighted inversion statistics on
individual conjugacy classes, obtaining the following independence result.

######  Theorem 1.1.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$. The expected
value of any weighted inversion statistic in the conjugacy class $C_{\lambda}$
indexed by $\lambda$ depends only on $n$, $a_{1}$, and $a_{2}$.

In the process of proving Theorem 1.1, we are able to derive explicit formulas
for the expected values for several permutation statistics in individual
conjugacy classes. See Table 1 for a summary of our results, as well as a
comparison to the first moments of these statistics on the entire symmetric
group.

statistic | $\lambda=(1^{a_{1}}2^{a_{2}}\ldots)\vdash n$ | $\lambda_{i}\geq 3\ \forall i$ | $\lambda=(1^{a_{1}}2^{a_{2}})$ |  $\lambda=(2^{a_{2}})$ | All of $S_{n}$
---|---|---|---|---|---
$\operatorname{des}$ | $\frac{n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}}{2n}$ | $\frac{n-1}{2}$ | $\frac{n^{2}-a_{1}^{2}}{2n}$ | $\frac{n}{2}$ |  $\frac{n-1}{2}$
$\operatorname{maj}$ | $\frac{n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}}{4}$ | $\frac{n(n-1)}{4}$ | $\frac{n^{2}-a_{1}^{2}}{4}$ | $\frac{n^{2}}{4}$ |  $\frac{n^{2}-n}{4}$
$\operatorname{inv}$ | $\frac{3n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}-2na_{1}}{12}$ | $\frac{n(3n-1)}{12}$ | $\frac{(3n+a_{1})(n-a_{1})}{12}$ | $\frac{n^{2}}{4}$ |  $\frac{n^{2}-n}{4}$
$\operatorname{baj}$ | $\frac{(n+1)(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1})}{12}$ | $\frac{n(n^{2}-1)}{12}$ | $\frac{(n+1)(n^{2}-a_{1}^{2})}{12}$ | $\frac{n^{2}(n+1)}{12}$ | $\frac{1}{4}\binom{n+1}{3}$
$\operatorname{baj}-\operatorname{inv}$ | $\frac{(n-2)(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1})}{12}$ | $\frac{n(n-1)(n-2)}{12}$ | $\frac{(n-2)(n^{2}-a_{1}^{2})}{12}$ | $\frac{n^{2}(n-2)}{12}$ |  $\frac{1}{4}\binom{n}{3}$
$\operatorname{cdes}$ | $\frac{n^{2}-n+2a_{2}-a_{1}^{2}+3a_{1}-2}{2(n-1)}$ | $\frac{(n+1)(n-2)}{2(n-1)}$ | $\frac{n^{2}-a_{1}^{2}+2a_{1}-2}{2(n-1)}$ | $\frac{n^{2}-2}{2(n-1)}$ |  $\frac{n}{2}$
$\widetilde{\operatorname{exc}}$ | $\frac{n+a_{1}}{2}$ | $\frac{n}{2}$ | $\frac{n+a_{1}}{2}=a_{1}+a_{2}$ | $\frac{n}{2}=a_{2}$ |  $\frac{n+1}{2}$
$\operatorname{exc},\operatorname{aexc}$ | $\frac{n-a_{1}}{2}$ | $\frac{n}{2}$ | $\frac{n-a_{1}}{2}=a_{2}$ | $\frac{n}{2}=a_{2}$ |  $\frac{n-1}{2}$
$\operatorname{cdasc},\operatorname{cddes}$ | $\frac{n-a_{1}-2a_{2}}{6}$ | $\frac{n}{6}$ | $0$ | $0$ | $\frac{n-2}{6}$
$\operatorname{cval},\operatorname{cpk}$ | $\frac{n-a_{1}+a_{2}}{3}$ | $\frac{n}{3}$ | $\frac{n-a_{1}}{2}=a_{2}$ | $\frac{n}{2}=a_{2}$ | $\frac{2n-1}{6}$
Table 1: Expected values of various statistics in the conjugacy class
$C_{\lambda}$ and in $S_{n}$.

######  Remark 1.2.

The generating function, expected value, and variance of $\operatorname{des}$
appear in Riordan [Rio14, p. 216], while the generating function and expected
value of $\operatorname{inv}$ are due to Rodrigues ([Rod39, p. 237], [Sta97,
Notes for Chapter 1]).

The Mahonian statistics maj and inv are equidistributed over $S_{n}$ by
MacMahon [Mac16], with a bijective proof via Foata’s second fundamental
transformation [Foa68].

The Eulerian statistics exc and des are equidistributed over $S_{n}$ [Mac04],
[Sta97, Proposition 1.4.3] with a bijective proof via the first fundamental
transformation [Rio14, FS70, Sta97].

When considering conjugacy classes where all cycles have length at least $3$,
we generalize the combinatorial algorithm of Fulman [Ful98, Theorem 3].
Precisely, we consider the notion of a permutation constraint, which allows us
to specify values of a permutation for certain elements of the domain. We then
analyze the structure of the corresponding directed graph (see Section 7).
Remarkably, the notion of permutation constraint allows us to reason about
arbitrary permutation statistics.

We now turn our attention to the higher moments of arbitrary permutation
statistics. For a permutation statistic $X$ and a partition $\lambda\vdash n$,
denote $\mathbb{E}_{\lambda}[X]$ to be the expected value of $X$ taken over
the conjugacy class $S_{n}$ indexed by $\lambda$.

######  Theorem 1.3.

Let $X$ be a permutation statistic that is realizable over a constraint set of
size $m$, and let $k\geq 1$. If $\lambda\vdash n$ has all parts of size at
least $mk+1$, then $\mathbb{E}_{\lambda}[X^{k}]$ is independent of $\lambda$.

######  Remark 1.4.

As descents are weighted permutation statistics of size $2$, our results in
Table 1 and Theorem 1.3 imply [Ful98, Theorem 2] as a corollary.

In Section 7 we consider the class of permutation statistics realizable over
symmetric constraint sets. Starting with a single symmetric constraint
statistic on $S_{n_{0}}$, one can construct its _symmetric extensions_ to
$S_{n}$ with $n\geq 1$. This class of permutation statistics is quite broad –
including a number of well-studied statistics such as
$\widetilde{\operatorname{exc}},\operatorname{exc},\operatorname{aexc}$ which
have size $1$;
$\operatorname{inv},\operatorname{cdasc},\operatorname{cddes},\operatorname{cval},\operatorname{cpk}$
which have size $2$; and $\mathrm{ile}$ which has size $\leq 3$. For a full
account of these statistics, see Sections 4, 5, and 7, as well as [BS21].

######  Theorem 1.5.

Fix $k,m\geq 1$. Let $(\lambda_{n})$ be a sequence of partitions, where
$\lambda_{n}\vdash n$ and all parts of $\lambda_{n}$ have size at least
$mk+1$. Let $(X_{n})$ be a symmetric extension of a symmetric permutation
statistic $X=X_{n_{0}}$ induced by a constraint set of size $m$. There exists
a polynomial $p_{X}(n)$ depending only on $X$ such that
$p_{X}(n)=\mathbb{E}_{\lambda_{n}}[X_{n}^{k}]$.

######  Remark 1.6.

In the proof of Theorem 1.5 (see Theorem 7.26), we are able to control both
the degree and leading coefficient of these polynomials.

######  Remark 1.7.

After proving Theorem 1.5, we came across a result for permutation patterns
due to Gaetz and Pierson [GP22, Theorem 1.2], who generalized a previous
result of Gaetz and Ryba [GR20, Theorem 1.1(a)]. While Gaetz and Ryba utilized
partition algebras and character polynomials to obtain their result, the proof
technique employed by Gaetz and Pierson was purely combinatorial. In
particular, the method of Gaetz and Pierson is quite similar to our techniques
for establishing Theorem 1.5.

We show in Section 7 that permutation pattern statistics (in which we track
the number of occurrences of a given permutation pattern within a specified
permutation) are a special case of symmetric permutation constraint statistics
– in fact, for infinitely many $m$, there exists a permutation pattern that
can be realized by a symmetric constraint set of size $m$ – but the latter is
a more general class of statistics. Permutation patterns require that the
constraints induce permutations on the occurrences of the pattern. For
instance, an occurrence of the $213$-pattern in the permutation $\omega$ is a
triple $x,y,z$ that occurs in the order $x\cdots y\cdots z$, with $y<x<z$.

Our more general symmetric permutation constraint statistics, however, need
not induce sub-permutations. For instance, we are able to specify triples
$x,y,z$ such that $y<x<z$ and $y$ appears before both $x$ and $z$, without
specifying the relative ordering of $x$ and $z$. With this in mind, a
comparison of Theorem 1.5 and [GP22, Theorem 1.2] shows that these two results
agree on permutation pattern statistics for conjugacy classes $C_{\lambda}$
where all parts have sufficiently large size.

######  Remark 1.8.

Theorem 1.5 has practical value in explicitly computing higher moments for
individual conjugacy classes. Namely, if we compute $\mathbb{E}_{(n)}[X^{k}]$
for the class of $n$-cycles in $S_{n}$, taken over
$\deg(\mathbb{E}_{(n)}[X^{k}])+1$ terms starting from $n=mk+1$, then we can
use polynomial interpolation to obtain a closed form solution for
$\mathbb{E}_{(n)}[X^{k}]$. Moreover, in light of Theorem 1.3, this moment for
full cycles is identical to $\mathbb{E}_{\lambda}[X^{k}]$, provided all parts
of $\lambda$ are at least $mk+1$.

Further related work. There has been considerable work on constructing
generating functions for permutation statistics.

It is well known, for instance, that the inversion and major index statistics
admit the same distribution on the entire symmetric group, with the
$q$-factorial as the generating function. Permutations with the $q$-factorial
as their generating function are called Mahonian. A general account of
Mahonian statistics can be found here [Foa77]. It is known that Mahonian
statistics are asymptotically normal with mean $\binom{n}{2}/2$ and variance
$[n(n-1)(2n+5)]/72$ [Foa77].

For a permutation $\omega$, let $\text{Des}(\omega)$ be the set of descents in
$\omega$ (that is, the set of indices $i$ such that $\omega(i)>\omega(i+1)$).
Let $d(\omega):=|\text{Des}(\omega)|+1$. The Eulerian polynomials as defined
in [Sta97] serve as the generating functions for $d(\omega)$ (see [Mac15,
Rio14]). See [FS70] for a detailed treatment of the properties of Eulerian
polynomials. It is known that $d(\omega)$ is asymptotically normally
distributed on $S_{n}$, with mean $(n+1)/2$ and variance $(n-1)/12$ under the
condition that the number of $i$-cycles vanishes asymptotically for all $i$
(an early reference is [Rio14, p. 216]; see also Fulman [Ful98], who in turn
cites unpublished notes of Diaconis and Pitman [DP86]). We note that descents
also have connections to sorting and the theory of runs in permutations
[Knu98, Section 5], as well as to models of card shuffling [DMP95, BD92,
DG19].

Outline of paper. We start in Section 2 by outlining necessary definitions and
notation. In Section 3, we establish some results on the first moments of
descents and major index that demonstrate some of the techniques that we apply
in conjugacy classes of the symmetric group. In Sections 4 and 5, we establish
results on first moments in conjugacy classes of the symmetric group,
including Theorem 1.1 and Table 1. We then apply these results to the entire
symmetric group in Section 6. We conclude in Section 7 by defining permutation
constraint statistics and establishing general results on their moments in
conjugacy classes.

##  2 Preliminaries

We outline some definitions and results that will be used throughout our work.
We start with three well-known statistics.

######  Definition 2.1.

Let $\omega$ be a permutation in the symmetric group $S_{n}$.

  1. 1.

A _descent_ of $\omega$ is an index $i\in[n-1]$, such that
$\omega(i)>\omega(i+1).$ We write

$\operatorname{Des}(\omega)=\\{i:\omega(i)>\omega(i+1)\\}$

for the set of descents. We write
$\operatorname{des}(\omega):=|\operatorname{Des}(\omega)|$ for the number of
descents of $\omega$. Following [Ful98], we also denote
$d(\omega):=\operatorname{des}(\omega)+1$.

  2. 2.

The _major index_ $\operatorname{maj}(\omega)$ of $\omega$ is the sum of its
descents:

$\operatorname{maj}(\omega):=\sum_{i\in\operatorname{Des}(\omega)}i.$

  3. 3.

An _inversion_ of $\omega$ is a pair of indices $(i,j)$ such that $1\leq
i<j\leq n$ and $\omega(i)>\omega(j)$. We write

$\operatorname{Inv}(\omega)=\\{(i,j):i<j,\text{ but }\omega(i)>\omega(j)\\}$

for the set of inversions. The _inversion number_
$\operatorname{inv}(\omega):=|\operatorname{Inv}(\omega)|$ is the number of
inversions of $\omega$.

Denote by $C_{\lambda}$ the conjugacy class of the symmetric group $S_{n}$
indexed by the integer partition $\lambda$ of $n$. The following fact is well
known, e.g., [Sta97] (or [DF91]).

######  Proposition 2.2.

The order of the centralizer of an element of cycle type $\lambda$ is
$z_{\lambda}=\prod_{i}i^{a_{i}}a_{i}!$, where $\lambda$ has $a_{i}$ parts
equal to $i,$ $i\geq 1$. For $\lambda\vdash n$, the order of the conjugacy
class $C_{\lambda}$ is thus $\frac{n!}{z_{\lambda}}$.

Throughout this paper, we will use $\operatorname{Pr}_{S_{n}}$ and
$\operatorname{Pr}_{\lambda}$ to denote probabilities in $S_{n}$ and
$C_{\lambda}$ (with respect to the uniform measure). We similarly use
$\mathbb{E}_{S_{n}}$ and $\mathbb{E}_{\lambda}$ for expected values on the
corresponding probability spaces.

##  3 Warm-up: first moments of descents and major index

Fulman [Ful98] previously determined the expected number of descents for all
conjugacy classes of $S_{n}$ without restriction to cycle types. In this
section, we give an elementary, bijective proof for the expected number of
descents in conjugacy classes where each cycle has length at least $3$. While
our result does not fully encompass that of Fulman, our technique of
conjugating by an involution provides a much simpler bijective proof.
Furthermore, we will employ this technique in subsequent sections (see Section
4.1).

######  Definition 3.1.

Let $\lambda\vdash n$ have all parts of size at least 2. Define:

$\displaystyle\tau_{i,j}:C_{\lambda}\rightarrow C_{\lambda}$
$\displaystyle\tau_{i,j}(\omega)=(i\,j)\omega(i\,j).$

######  Lemma 3.2.

For any fixed $i,j\in[n]$ and $\lambda$, $\tau_{i,j}$ is an involution on
$C_{\lambda}$.

###### Proof.

Since $C_{\lambda}$ is closed under conjugating by permutations, the map is
certainly well defined. Also, applying it twice to any $\omega$ gives
$(i\,j)(i\,j)\omega(i\,j)(i\,j)=\omega$. ∎

Fulman previously established the following.

######  Theorem 3.3 ([Ful98, Theorem 2]).

For a partition $\lambda$ of $n$ with $n_{i}$ $i$-cycles, let $C_{\lambda}$ be
the conjugacy class corresponding to $\lambda$. Then

  1. 1.

$\mathbb{E}_{\lambda}[\operatorname{des}]=\frac{n-1}{2}+\frac{n_{2}-\binom{n_{1}}{2}}{n}$;

  2. 2.

Fix $k\geq 0,$ and assume all parts of $\lambda$ have size at least $2k+1$.
Then the $k$th moments of $\operatorname{des}(\omega)$ over $C_{\lambda}$ and
over the full symmetric group $S_{n}$ are equal, i.e.

$\mathbb{E}_{\lambda}[\operatorname{des}^{k}]=\mathbb{E}_{S_{n}}[\operatorname{des}^{k}].$

######  Remark 3.4.

In [Ful98, Theorem 2], Fulman considered $\operatorname{des}(\omega)$ for part
(1) and $d(\omega)=\operatorname{des}(\omega)+1$ for part (2). This differs
with Theorem 3.3, where we consider $\operatorname{des}(\omega)$ in both parts
(1) and (2).

Lemma 3.2 gives the following simple proof of the following restricted case of
Theorem 3.3 (1). In fact, we will actually obtain the entirety of Theorem 3.3
(1) using generalizations of this technique in Section 4.

######  Observation 3.5.

Suppose that all part sizes of $\lambda$ are at least $3$. Then applying
$\tau_{i,i+1}$ gives a bijection between permutations in $C_{\lambda}$ with a
descent at position $i$, and those without.

######  Corollary 3.6.

Let $\lambda\vdash n$ such that each $\lambda_{i}\geq 3$. We have that:

$\mathbb{E}_{\lambda}[\operatorname{des}]=\frac{n-1}{2}.$

###### Proof.

The previous proposition gives us that the probability of having a descent at
any position $i$ is $1/2$. There are $n-1$ possible positions for a descent,
so the result follows. ∎

##  4 Weighted inversion statistics

In this section, we consider _weighted inversion statistics_ , which contain
descents, major index, and the usual inversions as special cases. We will give
an explicit formula for the mean on $C_{\lambda}$ of the indicator function of
$(i,j)$ being an inversion. We then use this to derive a general formula for
the expected value of any weighted inversion statistic on $C_{\lambda}$. We
start with definitions.

######  Definition 4.1.

Let $\omega\in S_{n}$, and let $1\leq i<j\leq n$. Define $I_{i,j}$ to be the
indicator function for an inversion at $(i,j)$, i.e., $I_{i,j}(\omega)=1$ if
$\omega(i)>\omega(j)$ and $I_{i,j}(\omega)=0$ otherwise.

A _weighted inversion statistic_ in $S_{n}$ is any statistic that can be
expressed in the form $\sum_{1\leq i<j\leq n}\text{wt}(i,j)I_{i,j}$, where
$\text{wt}(i,j)\in\mathbb{R}$ for all $i,j$.

######  Remark 4.2.

Observe that descents, major index, and inversions are three examples of
weighted inversion statistics. These can respectively be expressed as
$\operatorname{des}(\omega)=\sum_{i=1}^{n-1}I_{i,i+1}(\omega)$,
$\operatorname{maj}(\omega)=\sum_{i=1}^{n-1}i\cdot I_{i,i+1}(\omega)$, and
$\operatorname{inv}(\omega)=\sum_{1\leq i<j\leq n}I_{i,j}(\omega)$. In
general, if $X=\sum_{1\leq i<j\leq n}\text{wt}(i,j)I_{i,j}$ is a weighted
inversion statistic, we can use linearity to express

$\mathbb{E}_{\lambda}[X]=\sum_{1\leq i<j\leq
n}\text{wt}(i,j)\mathbb{E}_{\lambda}[I_{i,j}]=\sum_{1\leq i<j\leq
n}\text{wt}(i,j)\operatorname{Pr}_{\lambda}[I_{i,j}=1].$ (4.1)

Hence, if we can explicitly formulate
$\mathbb{E}_{\lambda}[I_{i,j}]=\operatorname{Pr}_{\lambda}[I_{i,j}=1]$, then
we can calculate $\mathbb{E}_{\lambda}[X]$. This approach also allows us to
obtain similar results for other permutation statistics, such as excedances
and cyclic descents.

###  4.1 Inversion indicator functions

In this subsection, we consider the expected value of $I_{i,j}$ in
$C_{\lambda}$ for any $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash
n$. Our main result will be an explicit formula in terms of $n$, $a_{1}$,
$a_{2}$, and the difference $j-i-1$. Surprisingly, the expected value of
$I_{i,j}$ depends on $a_{1}$ and $a_{2}$ but is independent of
$a_{3},\ldots,a_{n}$, and depends on $i$ and $j$ through their difference
$j-i$ but not the actual values of $i$ and $j$ themselves.

One of our main tools will be applying the map $\tau_{ij}$, as introduced in
Section 3. Observe that for $\omega\in C_{\lambda}$,

$\tau_{ij}(\omega)(i)=\begin{cases}\omega(j)&\text{ if
$\omega(j)\notin\\{i,j\\}$}\\\ j&\text{ if $\omega(j)=i$}\\\ i&\text{ if
$\omega(j)=j$}\end{cases}\qquad\tau_{ij}(\omega)(j)=\begin{cases}\omega(i)&\text{
if $\omega(i)\notin\\{i,j\\}$}\\\ i&\text{ if $\omega(i)=j$}\\\ j&\text{ if
$\omega(i)=i$.}\end{cases}$

Motivated by the above cases, we partition $C_{\lambda}$ into five sets based
on $i$ and $j$:

$\begin{split}\Omega_{1}^{ij}&=\\{\omega\in
C_{\lambda}:\omega(i),\omega(j)\notin\\{i,j\\}\\},\\\
\Omega_{2}^{ij}&=\\{\omega\in C_{\lambda}:\omega(i)=j,\omega(j)=i\\},\\\
\Omega_{3}^{ij}&=\\{\omega\in C_{\lambda}:\omega(i)=i,\omega(j)=j\\},\\\
\Omega_{4}^{ij}&=\\{\omega\in C_{\lambda}:\omega(i)=j,\omega(j)\neq
i\\}\cup\\{\omega\in C_{\lambda}:\omega(i)\neq j,\omega(j)=i\\},\\\
\Omega_{5}^{ij}&=\\{\omega\in C_{\lambda}:\omega(i)=i,\omega(j)\neq
j\\}\cup\\{\omega\in C_{\lambda}:\omega(i)\neq i,\omega(j)=j\\}.\end{split}$
(4.2)

Using the Law of Total Probability, we can decompose

$\begin{split}\operatorname{Pr}_{\lambda}[I_{i,j}=1]=\sum_{k=1}^{5}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{k}^{ij}]\cdot\operatorname{Pr}_{\lambda}[I_{i,j}(\omega)=1\mid\omega\in\Omega_{k}^{ij}].\end{split}$
(4.3)

We can explicitly compute the quantities in this sum.

######  Lemma 4.3.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, fix $i<j$ in
$[n]$, and define $\Omega_{k}=\Omega_{k}^{ij}$ as in (4.2). Then

  1. 1.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]=\frac{2a_{2}}{n(n-1)},$

  2. 2.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}]=\frac{a_{1}(a_{1}-1)}{n(n-1)},$

  3. 3.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{4}]=\frac{2}{n-1}\cdot\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right),$
and

  4. 4.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{5}]=\frac{2a_{1}}{n}\cdot\left(1-\frac{a_{1}-1}{n-1}\right).$

###### Proof.

We proceed as follows.

  1. 1.

We first note that if $a_{2}=0$, then $\omega$ has no $2$-cycles. As
$\Omega_{2}^{ij}$ is precisely the set of permutations of $C_{\lambda}$
containing the $2$-cycle $(ij)$, we have that
$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]=0$, which agrees with the
formula given.

If instead $a_{2}>0$, then $(ij)$ forming a cycle implies that the remaining
$n-2$ elements have cycle type $(1^{a_{1}},2^{a_{2}-1},\ldots,n^{a_{n}})$.
Then the probability that $(ij)$ forms a $2$-cycle is given by:

$\frac{|C_{(1^{a_{1}},2^{a_{2}-1},\ldots,n^{a_{n}})}|}{|C_{(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})}|}=\frac{2a_{2}}{n(n-1)},$

recalling that the formulas for the centralizer sizes are given by Proposition
2.2.

  2. 2.

By definition, $\Omega_{3}^{ij}$ contains the permutations of $C_{\lambda}$
with fixed points at positions $i$ and $j$. Thus, if $a_{1}\in\\{0,1\\}$, then
$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}]=0$, which agrees with the
formula given.

If instead $a_{1}>1$, then the probability that $(i)$ and $(j)$ form
$1$-cycles is given by

$\frac{|C_{(1^{a_{1}-2},2^{a_{2}},\ldots,n^{a_{n}})}|}{|C_{(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})}|}=\frac{a_{1}(a_{1}-1)}{n(n-1)}.$

  3. 3.

We first consider $\\{\omega\in C_{\lambda}:\omega(i)=j,\omega(j)\neq i\\}$.
Using the Law of Total Probability, we decompose
$\operatorname{Pr}_{\lambda}[\omega(i)=j,\omega(j)\neq i]$ into the sum of the
following terms:

$\operatorname{Pr}_{\lambda}[i\text{ is in a 1 cycle of
}\omega]\cdot\operatorname{Pr}_{\lambda}[\omega(i)=j,\omega(j)\neq i|i\text{
is in a 1 cycle of }\omega],$ $\operatorname{Pr}_{\lambda}[i\text{ is in a 2
cycle of }\omega]\cdot\operatorname{Pr}_{\lambda}[\omega(i)=j,\omega(j)\neq
i|i\text{ is in a 2 cycle of }\omega],$ $\operatorname{Pr}_{\lambda}[i\text{
is not in a 1 or 2 cycle of
}\omega]\cdot\operatorname{Pr}_{\lambda}[\omega(i)=j,\omega(j)\neq i|i\text{
is not in a 1 or 2 cycle of }\omega].$

The first two terms are 0, and hence we need only compute the third term.
Observe that

$\operatorname{Pr}_{\lambda}[i\text{ is in a 1 cycle of
}\omega]=\frac{|C_{(1^{a_{1}-1},2^{a_{2}},\ldots,n^{a_{n}})}|}{|C_{(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})}|}=\frac{a_{1}}{n}.$

Using our result from (1),

$\operatorname{Pr}_{\lambda}[i\text{ is in a 2 cycle of }\omega]=\sum_{k\neq
i}\operatorname{Pr}_{\lambda}[\omega(i)=k,\omega(k)=i]=\frac{2a_{2}}{n}.$

Hence, $\operatorname{Pr}_{\lambda}[i\text{ is not in a 1 or 2 cycle of
}\omega]=1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}$.

Finally, consider conjugation by $\rho=(i)(1,2,\ldots,i-1,i+1,\ldots,n)$ on
the elements in $\Omega_{4}$. Since $\rho$ acts by replacing each element of a
cycle by its image under $\rho$, it induces bijections among the sets

$\\{\omega\in C_{\lambda}:\omega(i)=k,i\text{ is not in a $1$ or $2$ cycle of
}\omega\\}$

for $k\in[n]\setminus\\{i\\}$. Hence, $\\{\omega\in C_{\lambda}:i\text{ is not
in a 1 or 2 cycle of }\omega\\}$ decomposes into $n-1$ sets of the same size
based on the image of $i$.

We conclude that

$\operatorname{Pr}_{\lambda}[\omega(i)=j,\omega(j)\neq i|i\text{ is not in a 1
or 2 cycle of }\omega]=\frac{1}{n-1}.$

Combined, we have that

$\operatorname{Pr}_{\lambda}[\omega(i)=j,\omega(j)\neq
i]=\frac{1}{n-1}\cdot\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right).$

Repeating this argument over $\\{\omega\in C_{\lambda}:\omega(i)\neq
j,\omega(j)=i\\}$ and adding the two terms implies (3).

  4. 4.

We similarly first consider $\\{\omega\in
C_{\lambda}:\omega(i)=i,\omega(j)\neq j\\}$. Then

$\begin{split}\operatorname{Pr}_{\lambda}[\omega(i)=i,\omega(j)\neq
j]&=\operatorname{Pr}_{\lambda}[\omega(i)=i]\cdot\operatorname{Pr}_{\lambda}[\omega(j)\neq
j|\omega(i)=i]\\\
&=\frac{a_{1}}{n}\cdot\left(1-\operatorname{Pr}_{\lambda}[\omega(j)=j|\omega(i)=i]\right)\\\
&=\frac{a_{1}}{n}\cdot\left(1-\frac{a_{1}-1}{n-1}\right).\end{split}$

Repeating this argument over $\\{\omega\in C_{\lambda}:\omega(i)\neq
i,\omega(j)=j\\}$ and adding this to the expression above implies the result.
∎

######  Remark 4.4.

The preceding lemma gives an explicit formula for
$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{1}]$ using
$1-\sum_{k=2}^{5}\operatorname{Pr}[\omega\in\Omega_{k}]$. We will not need
this explicit formulation.

######  Lemma 4.5.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, fix $i<j$ in
$[n]$, and define $\Omega_{k}=\Omega_{k}^{ij}$ as in (4.2). Then

  1. 1.

$\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{1}]=\frac{1}{2}$,

  2. 2.

$\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{2}]=1$,

  3. 3.

$\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{3}]=0$,

  4. 4.

$\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{4}]=\frac{1}{2}+\frac{j-i-1}{2(n-2)}$,
and

  5. 5.

$\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{5}]=\frac{1}{2}-\frac{j-i-1}{2(n-2)}$.

######  Remark 4.6.

A priori, it was not intuitively clear to us why:

$\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)\mid\omega\in\Omega_{4}]+\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)\mid\omega\in\Omega_{5}]=1.$

Prior to proving Lemma 4.5, we first highlight our intuition here. If $k<i$ or
$k>j$, then conjugating by $(ij)$ interchanges elements that have $(i,j)$ as
an inversion to ones that do not. If $i<k<j$, then we have to track choices
for $k$ and “adjust” the probability from $1/2$. The $(j-i-1)/[2(n-2)]$ term
accounts for this. Precisely, in $\Omega_{4}$, conjugating by $(ij)$
interchanges permutations that both have an inversion at $(i,j)$, and in
$\Omega_{5}$, conjugating by $(ij)$ interchanges permutations that both do not
have an inversion at $(i,j)$.

###### Proof of Lemma 4.5.

  1. 1.

Note that the map $\tau_{ij}$ induces a bijection between the sets
$\\{\omega\in\Omega_{1}:\omega(i)>\omega(j)\\}$ and
$\\{\omega\in\Omega_{1}:\omega(i)<\omega(j)\\}$ that partition $\Omega_{1}$.
Hence, these two sets must have the same size, and we conclude (1).

  2. 2.

This follows immediately from the definition of inversion and the images of
$i$ and $j$ in the set $\Omega_{2}$.

  3. 3.

This follows immediately from the definition of inversion and the images of
$i$ and $j$ in the set $\Omega_{3}$.

  4. 4.

Observe that we can partition

$\\{\omega\in C_{\lambda}:\omega(i)=j,\omega(j)\neq
i\\}=\bigsqcup_{k\notin\\{i,j\\}}\\{\omega\in
C_{\lambda}:\omega(i)=j,\omega(j)=k\\}.$

Now consider conjugation by

$(i)(j)(1,2,\ldots,i-1,i+1,\ldots,j-1,j+1\ldots,n)$

on $\Omega_{4}$. As in the proof of Lemma 4.3, this induces bijections among
the sets $\\{\omega\in C_{\lambda}:\omega(i)=j,\omega(j)=k\\}$ for each
$k\in[n]\setminus\\{i,j\\}$, and hence each of these disjoint sets has the
same size. Additionally, $\tau_{ij}$ induces a bijection between $\\{\omega\in
C_{\lambda}:\omega(i)=j,\omega(j)=k\\}$ and $\\{\omega\in
C_{\lambda}:\omega(i)=k,\omega(j)=i\\}$. Combining these two observations, we
see that grouping elements by the images of $i$ and $j$ partitions
$\Omega_{4}$ into $2(n-2)$ sets of the same size. Observe that the images of
$i$ and $j$ are sufficient for determining if $(i,j)\in\operatorname{Inv}(w)$.
When $\omega(i)=j$, $\omega(j)$ must be in
$\\{1,2,\ldots,j-1\\}\setminus\\{i\\}$ to have an inversion at $(i,j)$. When
$\omega(j)=i$, $\omega(i)$ must be in $\\{i+1,\ldots,n\\}\setminus\\{j\\}$ to
have an inversion at $(i,j)$. Hence,

$\begin{split}\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{4}]=\frac{(j-2)+(n-i-1)}{2(n-2)}=\frac{(n-2)+(j-i-1)}{2(n-2)}=\frac{1}{2}+\frac{j-i-1}{2(n-2)}.\end{split}$

  5. 5.

We can again partition $\Omega_{5}$ into $2(n-2)$ sets of the same size based
on the image of $i$ and $j$. If $\omega(i)=i$, $\omega(j)$ must be in
$\\{1,2,\ldots,i-1\\}$ to produce an inversion at $(i,j)$. If $\omega(j)=j$,
then $\omega(i)$ must be in $\\{j+1,\ldots,n\\}$ to produce an inversion at
$(i,j)$. Hence,

$\begin{split}\operatorname{Pr}_{\lambda}[(i,j)\in\operatorname{Inv}(\omega)|\omega\in\Omega_{5}]&=\frac{(i-1)+(n-j)}{2(n-2)}=\frac{(n-2)+(1+i-j)}{2(n-2)}=\frac{1}{2}-\frac{j-i-1}{2(n-2)}.\qed\end{split}$

We have now established explicit formulas for all of the quantities in (4.2).
Combining these, we compute the expected value of $I_{i,j}$ on $C_{\lambda}$.

######  Lemma 4.7.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$. For any $i<j$ in
$[n]$,

$\begin{split}\operatorname{Pr}_{\lambda}[I_{i,j}=1]=\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}+(j-i-1)\cdot\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}.\end{split}$

###### Proof.

Define $\Omega_{k}=\Omega_{k}^{ij}$ as in (4.2). Starting with (4.3) and using
Lemma 4.5, $\operatorname{Pr}_{\lambda}[I_{i,j}=1]$ can be expressed as a sum
of the following five terms:

  1. (i)

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{1}]\cdot\frac{1}{2}$,

  2. (ii)

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]\cdot\left(\frac{1}{2}+\frac{1}{2}\right)$,

  3. (iii)

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}]\cdot\left(\frac{1}{2}-\frac{1}{2}\right)$,

  4. (iv)

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{4}]\cdot\left(\frac{1}{2}+\frac{j-i-1}{2(n-2)}\right)$,
and

  5. (v)

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{5}]\cdot\left(\frac{1}{2}-\frac{j-i-1}{2(n-2)}\right)$.

We group terms with positive $1/2$ coefficients, use the fact that
$C_{\lambda}$ is a disjoint union of $\\{\Omega_{k}\\}_{k=1}^{5}$, and apply
Lemma 4.3 to obtain

$\begin{split}&\frac{1}{2}\sum_{k=1}^{5}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{k}]+\frac{1}{2}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]-\frac{1}{2}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}]+\frac{j-i-1}{2(n-2)}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{4}]-\frac{j-i-1}{2(n-2)}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{5}]\\\
&=\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}+\frac{j-i-1}{(n-1)(n-2)}\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)-\frac{a_{1}(j-i-1)}{n(n-2)}\left(1-\frac{a_{1}-1}{n-1}\right).\\\
&=\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}+(j-i-1)\cdot\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}.\qed\end{split}$

###  4.2 First moment

We now apply our results on $\mathbb{E}_{\lambda}[I_{i,j}]$ to calculate
$\mathbb{E}_{\lambda}[X]$ for any weighted inversion statistic. We start with
our main theorem on weighted inversion statistics.

######  Theorem 4.8.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, and let
$X=\sum_{1\leq i<j\leq n}\text{wt}(i,j)I_{i,j}$ be a weighted inversion
statistic. Also set $\alpha_{n}(X):=\sum_{1\leq i<j\leq n}\text{wt}(i,j)$, and
$\beta_{n}(X):=\sum_{1\leq i<j\leq n}(j-i-1)\text{wt}(i,j)$. Then

$\mathbb{E}_{\lambda}[X]=\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}\right)\cdot\alpha_{n}(X)+\left(\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}\right)\cdot\beta_{n}(X).$

###### Proof.

Note that $\alpha_{n}(X)$ and $\beta_{n}(X)$ are independent of the partition
$\lambda$. We start with (4.1) and apply Lemma 4.7 to see that
$\mathbb{E}_{\lambda}[X]$ is given by

$\begin{split}&\sum_{1\leq i<j\leq
n}\text{wt}(i,j)\operatorname{Pr}_{\lambda}[I_{i,j}(\omega)=1]\\\
&=\sum_{1\leq i<j\leq
n}\text{wt}(i,j)\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}+(j-i-1)\cdot\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}\right)\\\
&=\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}\right)\cdot\sum_{1\leq
i<j\leq
n}\text{wt}(i,j)+\left(\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}\right)\cdot\sum_{1\leq
i<j\leq n}\text{wt}(i,j)(j-i-1).\qed\end{split}$

######  Corollary 4.9.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$. The expected
value of any weighted inversion statistic in $S_{n}$ is independent of
$a_{3},\ldots,a_{n}$.

We can apply the preceding theorem to obtain the expected number of some
common statistics. Note that part (1) of the following corollary was
previously established by Fulman [Ful98].

######  Corollary 4.10.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, $n\geq 2$. Then

  1. 1.

$\mathbb{E}_{\lambda}[\operatorname{des}]=\frac{1}{2n}\left(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}\right)$,

  2. 2.

$\mathbb{E}_{\lambda}[\operatorname{maj}]=\frac{1}{4}\left(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}\right),$

  3. 3.

$\mathbb{E}_{\lambda}[\operatorname{inv}]=\frac{1}{12}\left(3n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}-2na_{1}\right).$

In particular, in the case that $a_{1}=a_{2}=0$, we have that
$\mathbb{E}_{\lambda}[\operatorname{des}]=\frac{n-1}{2}$,
$\mathbb{E}_{\lambda}[\operatorname{maj}]=\frac{n(n-1)}{4}$, and
$\mathbb{E}_{\lambda}[\operatorname{inv}]=\frac{3n^{2}-n}{12}$.

###### Proof.

We use Theorem 4.8 for all three statistics $X$.

  1. 1.

The descent statistic $\operatorname{des}$ is defined by $\text{wt}(i,i+1)=1$
for $i\in\\{1,2,\ldots,n-1\\}$, and $\text{wt}(i,j)=0$ otherwise. Hence
$\alpha_{n}(X)=$ $\sum_{1\leq i<j\leq n}\text{wt}(i,j)=(n-1)$ and
$\beta_{n}(X)=$ $\sum_{1\leq i<j\leq n}\text{wt}(i,j)(j-i-1)=0$. Then

$\mathbb{E}_{\lambda}[\operatorname{des}]=\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}\right)\cdot(n-1)=\frac{1}{2n}{\left(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}\right)}.$

  2. 2.

The major index is defined by $\text{wt}(i,i+1)=i$ and $\text{wt}(i,j)=0$
otherwise. Now $\alpha_{n}(X)=$ $\sum_{1\leq i<j\leq
n}\text{wt}(i,j)={n\choose 2}$ and $\beta_{n}(X)=$ $\sum_{1\leq i<j\leq
n}\text{wt}(i,j)(j-i-1)=0$. Then

$\mathbb{E}_{\lambda}[\operatorname{maj}]=\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}\right)\cdot{n\choose
2}=\frac{1}{4}\left(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}\right).$

  3. 3.

Finally, the inversion statistic is defined by $\text{wt}(i,j)=1$ for all
$i,j$. Then $\alpha_{n}(X)=$ $\sum_{1\leq i<j\leq n}\text{wt}(i,j)={n\choose
2}$, and using the substitution $k=j-i-1$, we find that $\beta_{n}(X)=$
$\sum_{1\leq i<j\leq n}\text{wt}(i,j)(j-i-1)$ is given by

$\begin{split}\sum_{1\leq i<j\leq
n}(j-i-1)=\sum_{i=1}^{n-1}\sum_{k=0}^{n-i-1}k=\sum_{i=1}^{n-1}\binom{n-i}{2}=\binom{n}{3}.\end{split}$

Combined, we see that

$\begin{split}\mathbb{E}_{\lambda}[\operatorname{inv}]&=\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}\right)\cdot{n\choose
2}+\left(\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}\right)\cdot{n\choose
3}\\\
&=\frac{1}{12}\left(3n^{2}-n+2a_{2}-a_{1}^{2}+a_{1}-2na_{1}\right).\qed\end{split}$

###  4.3 Baj

In this subsection, we consider the curious permutation statistic
$\operatorname{baj}$ that was introduced by Zabrocki [Zab03].

######  Definition 4.11 ([Zab03]).

Let $\omega\in S_{n}$. Define

$\operatorname{baj}(\omega)\coloneqq\sum_{i\in\operatorname{Des}(\omega)}i(n-i).$

The statistic $\operatorname{baj}-\operatorname{inv}$ is the Coxeter length
function restricted to coset representatives of the extended affine Weyl group
of type $A_{n-1}$ modulo translations by coroots. It has a nice generating
function over the symmetric group, due to Stembridge and Waugh [SW98].
Furthermore, in [BKS20], using this generating function, a formula for the
$d$th cumulant is given [BKS20, Corollary 3.4], and it is shown that the
asymptotic distribution of $\operatorname{baj}-\operatorname{inv}$ on $S_{n}$
is normal.

Observe that $\operatorname{baj}$ is a weighted inversion statistic for the
choice $\text{wt}(i,i+1)=i(n-i)$ and $\text{wt}(i,j)=0$ for $j\neq i+1$. Using
Theorem 4.8, we obtain the following.

######  Proposition 4.12.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, $n\geq 2$. Then

$\mathbb{E}_{\lambda}[\operatorname{baj}]=\frac{1}{12}(n+1)(n^{2}-n+2a_{2}-a_{1}^{2}+a_{1})=\frac{1}{3}(n+1)\mathbb{E}_{\lambda}[\operatorname{maj}].$

###  4.4 Cyclic descents

Cyclic descents were introduced by Paola Cellini [Cel98]. While these are not
weighted inversion statistics, a small adjustment of the methods of the
previous subsections allows us to compute the first moment of cyclic descents
on $C_{\lambda}$.

######  Definition 4.13 ([Cel98]).

The _cyclic descent set_ of a permutation $\omega\in S_{n}$ is defined to be
the set

$\operatorname{cDes}(\omega):=\\{1\leq i\leq
n:\omega(i)>\omega(i+1)\subset[n]\\},$

with the convention $\omega(n+1):=\omega(1)$. Let
$\operatorname{cdes}(\omega):=|\operatorname{cDes}(\omega)|.$

######  Theorem 4.14.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, $n\geq 2$. Then

$\mathbb{E}_{\lambda}[\operatorname{cdes}]=\frac{n}{2}+\frac{a_{2}-\binom{a_{1}}{2}}{n-1}+\frac{a_{1}-1}{n-1},$

and hence the expected value of cyclic descents is independent of the
conjugacy class if $a_{1}=a_{2}=0$.

###### Proof.

Writing $J_{n}$ for the random variable which equals 1 if
$n\in\operatorname{cDes}(\omega)$ and 0 otherwise, we have

$\mathbb{E}_{\lambda}[\operatorname{cdes}]=\sum_{1\leq i\leq
n-1}\operatorname{Pr}_{\lambda}[I_{i,i+1}=1]+\operatorname{Pr}_{\lambda}[J_{n}=1]\\\
=\mathbb{E}_{\lambda}[\operatorname{des}]+\operatorname{Pr}_{\lambda}[J_{n}=1].$
(4.4)

From Lemma 4.7 we have

$\operatorname{Pr}_{\lambda}[I_{1,n}=1]=\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}+\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)}=\frac{1}{2}+\frac{\binom{a_{1}}{2}-a_{2}-n(a_{1}-1)}{n(n-1)}.$

Now $n$ is a cyclic descent if and only if $\omega(n)>\omega(1)$, i.e., if and
only if $(1,n)$ is _not_ an inversion. Hence we have

$\begin{split}\operatorname{Pr}_{\lambda}[J_{n}=1]=1-\operatorname{Pr}_{\lambda}[I_{1,n}=1]=\frac{1}{2}+\frac{a_{2}-\binom{a_{1}}{2}+n(a_{1}-1)}{n(n-1)}.\end{split}$
(4.5)

From Corollary 4.10, we have

$\mathbb{E}_{\lambda}[\operatorname{des}]=\frac{n-1}{2}+\frac{a_{2}-\binom{a_{1}}{2}}{n}.$
(4.6)

Equation (4.4) now gives the result. ∎

##  5 Cyclic permutation statistics

In this section, we apply the techniques from Section 4 to the cases of
several other permutation statistics that are not weighted inversion
statistics. Such permutation statistics include cyclic descents and
excedances. We call these cyclic permutation statistics, to reflect the fact
that, in general, the value of the statistic can be read directly from the
cycles in its cycle decomposition.

In particular, we show that, once again, the expected values depend on at most
the number of fixed points and $2$-cycles in the cycle type.

###  5.1 Excedances

An _excedance_ of $\omega$ is any index $i\in[n]$ such that $\omega(i)>i$. A
_weak excedance_ of $\omega$ is any index $i\in[n]$ such that $\omega(i)\geq
i$. An _anti-excedance_ [BS21] of $\omega$ is any index $i\in[n]$ such that
$\omega(i)<i$. Clearly $i$ is an excedance of $\omega$ if and only if
$\omega(i)$ is an anti-excedance of $\omega^{-1}$, and conjugacy classes in
$S_{n}$ are closed with respect to taking inverses, so for any fixed conjugacy
class, excedance and anti-excedance are equidistributed.

Let $\operatorname{exc}(\omega)$ (respectively
$\widetilde{\operatorname{exc}}(\omega),\operatorname{aexc}(\omega)$) denote
the number of excedances (respectively weak excedances, anti-excedances) of
the permutation $\omega$. While these are not weighted inversion statistics,
the methods of Section 4 can be adapted to calculate their expected values in
$C_{\lambda}$.

######  Theorem 5.1.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})$. Then

$\mathbb{E}_{\lambda}[\operatorname{exc}]=\frac{1}{2}(n-a_{1})=\mathbb{E}_{\lambda}[\operatorname{aexc}]\text{
and
}\mathbb{E}_{\lambda}[\widetilde{\operatorname{exc}}]=\frac{1}{2}(n+a_{1}).$

###### Proof.

Express $\operatorname{exc}(\omega)=\sum_{j=1}^{n}I_{j}(\omega)$, where
$I_{j}$ is the indicator random variable on an excedance at position $j$.
Fixing $j$, partition $C_{\lambda}$ into the two sets $\Omega_{1}=\\{w\in
C_{\lambda}:\omega(j)=j\\}$ and $\Omega_{2}=\\{w\in C_{\lambda}:\omega(j)\neq
j\\}$. Then

$\operatorname{Pr}_{\lambda}[I_{j}=1]=\operatorname{Pr}_{\lambda}[\omega\in\Omega_{1}]\cdot\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{1}]+\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]\cdot\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{2}].$

Observe that
$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{1}]=\frac{a_{1}}{n}$ and
$\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{1}]=0$. For
$\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{2}]$, we can
partition

$\Omega_{2}=\bigsqcup_{k\neq j}\\{w\in\Omega_{2}:w(j)=k\\}.$

Conjugation by $(j)(1,2,\ldots,j-1,j+1,\ldots,n)$ induces bijections among
these sets, and thus they all must have the same size. Observe that in $n-j$
of the $n-1$ sets, an excedance at $j$ occurs. Hence,

$\operatorname{Pr}_{\lambda}[I_{j}=1]=\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]\cdot\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{2}]=\left(1-\frac{a_{1}}{n}\right)\cdot\frac{n-j}{n-1}.$

For the excedance statistic, we conclude that

$\begin{split}\mathbb{E}_{\lambda}[\operatorname{exc}]=\sum_{j=1}^{n}\operatorname{Pr}_{\lambda}[I_{j}=1]=\sum_{j=1}^{n}\left(1-\frac{a_{1}}{n}\right)\cdot\frac{n-j}{n-1}=\left(\frac{n-a_{1}}{n}\right)\cdot\frac{1}{n-1}\cdot{n\choose
2}=\frac{1}{2}(n-a_{1}).\end{split}$

We have already noted that for every fixed conjugacy class $C$, excedance and
anti-excedance are equidistributed on $C$. For the weak excedance statistic
$\mathrm{\widetilde{exc}}(\omega),$ by definition, the only change in the
above argument is that
$\operatorname{Pr}_{\lambda}[\widetilde{I}_{j}(\omega)=1|\omega\in\Omega_{1}]=1$
where $\widetilde{I}_{j}$ is the weak excedance indicator function. Hence

$\operatorname{Pr}_{\lambda}[\widetilde{I_{j}}(\omega)=1]=\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1]+\frac{a_{1}}{n},$
(5.1)

and

$\mathbb{E}_{\lambda}[\widetilde{\operatorname{exc}}]=\mathbb{E}_{\lambda}[\operatorname{exc}]+a_{1}=\frac{1}{2}(n+a_{1}).\qed$

######  Corollary 5.2.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})$. Then the expected values
of $\operatorname{exc},\widetilde{\operatorname{exc}}$ and
$\operatorname{aexc}$ are independent of $a_{2},\ldots,a_{n}$. In particular,
when $a_{1}=0$, we have that
$\mathbb{E}_{\lambda}[\operatorname{exc}]=\mathbb{E}_{\lambda}[\operatorname{aexc}]=\mathbb{E}_{\lambda}[\widetilde{\operatorname{exc}}]=\frac{n}{2}$.

###  5.2 Cyclic double ascents and cyclic valleys

Several recent papers [CJZ20, BS21] consider statistics derived from the
excedance statistic. In [CJZ20], the following statistics are defined for
$\omega\in S_{n}$. The element $i\in[n]$ is a

  1. 1.

_cyclic valley_ of $\omega$ if $\omega^{-1}(i)>i<\omega(i)$;

  2. 2.

_cyclic peak_ of $\omega$ if $\omega^{-1}(i)<i>\omega(i)$;

  3. 3.

_cyclic double ascent_ of $\omega$ if $\omega^{-1}(i)<i<\omega(i)$; and

  4. 4.

_cyclic double descent_ of $\omega$ if $\omega^{-1}(i)>i>\omega(i)$.

A cyclic double ascent (respectively, cyclic double descent) coincides with
the _linked excedance_ (respectively, _linked anti-excedance_) defined in
[BS21]. We follow the notation of [CJZ20], and write
$\operatorname{cval}(\omega)$ (respectively, $\operatorname{cpk}(\omega)$) for
the number of cyclic valleys (respectively, cyclic peaks) of $\omega$. Also
write $\operatorname{Cval}(\omega)$ (respectively,
$\operatorname{Cpk}(\omega)$) for the _set_ of cyclic valleys (respectively,
cyclic peaks) of $\omega$. Clearly $i$ is a cyclic valley of $\omega$ if
either $i$ is the smaller letter in a 2-cycle, or if $i$ appears in a cycle of
$\omega$ of length at least 3. In the latter case the cycle containing $i$
must be of the form $(\ldots j\,i\,k\ldots)$ for $j>i<k$. Let $\rho$ be the
reversing involution defined by $\rho(i)=n+1-i$. Since the corresponding cycle
of $\rho\,\omega\rho^{-1}$ is $(\ldots,n+1-j,\,n+1-i,\,n+1-k,\ldots)$, it
follows that

$i\in\\{1,\ldots,n-1\\}\text{ is a cyclic valley of }\omega\iff
n+1-i\in\\{2,\ldots,n\\}\text{ is a cyclic peak of }\rho\,\omega\rho^{-1},$

and hence cyclic valleys and cyclic peaks are equidistributed over a fixed
conjugacy class. The same argument shows that cyclic double descents and
cyclic double ascents are equidistributed over a fixed conjugacy class.

The number of cyclic double ascents (respectively cyclic double descents) in a
permutation $\omega$ is denoted $\operatorname{cdasc}(\omega)$ (respectively,
$\operatorname{cddes}(\omega)$). Also, the _set_ of cyclic double ascents
(respectively cyclic double descents) in a permutation $\omega$ is denoted
$\operatorname{Cdasc}(\omega)$ (respectively, $\operatorname{Cddes}(\omega)$).

Now observe that our methods apply to the statistics
$\operatorname{cdasc}(\omega)$, $\operatorname{cval}(\omega)$ and
$\operatorname{cddes}(\omega)$, $\operatorname{cpk}(\omega)$ as well. Let
$I_{j}$ be the indicator function for a cyclic double ascent at index $j$ and
decompose $\operatorname{cdasc}(\omega)=\sum_{j=2}^{n-1}I_{j}(\omega)$. Let
$I^{v}_{j}$ be the indicator function for a cyclic valley at $j$, and write
$\operatorname{cval}(\omega)=\sum_{j=1}^{n-1}I^{v}_{j}(\omega)$. Define the
sets

$\begin{split}\Omega_{1}^{j}&=\\{\omega\in C_{\lambda}:\text{ $j$ is in a
$1$-cycle}\\},\\\ \Omega_{2}^{j}&=\\{\omega\in C_{\lambda}:\text{ $j$ is in a
$2$-cycle}\\},\\\ \Omega_{3}^{j}&=\\{\omega\in C_{\lambda}:\text{ $j$ is not
in a $1$-cycle or $2$-cycle}\\}.\end{split}$ (5.2)

Similar arguments as before imply the following results. First, we have the
analogue of Lemma 4.3.

######  Lemma 5.3.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, fix $j\in[n]$,
and define $\Omega_{k}=\Omega_{k}^{j}$ as in (5.2). Then

  1. 1.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{1}]=\frac{a_{1}}{n}$,

  2. 2.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}]=\frac{2a_{2}}{n}$, and

  3. 3.

$\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}]=1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}$.

###### Proof.

The proof follows the same arguments as Lemma 4.3. ∎

######  Theorem 5.4.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$. Then

  1. 1.

$\mathbb{E}_{\lambda}[\operatorname{cdasc}]=\frac{n-a_{1}-2a_{2}}{6}=\mathbb{E}_{\lambda}[\operatorname{cddes}]$
and

  2. 2.

$\mathbb{E}_{\lambda}[\operatorname{cval}]=\frac{n-a_{1}+a_{2}}{3}=\mathbb{E}_{\lambda}[\operatorname{cpk}].$

###### Proof.

Fix $j$ and observe that if $\omega\in\Omega_{1}^{j}\cup\Omega_{2}^{j}$, then
$j$ is not a cyclic double ascent of $\omega$. Also, $j$ is a cyclic valley of
$\omega$ only if $\omega\in\Omega_{2}^{j}\cup\Omega_{3}^{j}$. Hence, by the
Law of Total Probability, we have

$\displaystyle\mathbb{E}_{\lambda}[I_{j}]$
$\displaystyle=\sum_{k=1}^{3}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{k}^{j}]\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{k}^{j}]=\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}^{j}]\operatorname{Pr}_{\lambda}[I_{j}(\omega)=1|\omega\in\Omega_{3}^{j}],$
$\displaystyle\mathbb{E}_{\lambda}[I^{v}_{j}]$
$\displaystyle=\sum_{k=1}^{3}\operatorname{Pr}_{\lambda}[\omega\in\Omega_{k}^{j}]\operatorname{Pr}_{\lambda}[I^{v}_{j}(\omega)=1|\omega\in\Omega_{k}^{j}]$
$\displaystyle=\operatorname{Pr}_{\lambda}[\omega\in\Omega_{3}^{j}]\operatorname{Pr}_{\lambda}[I^{v}_{j}(\omega)=1|\omega\in\Omega_{3}^{j}]+\operatorname{Pr}_{\lambda}[\omega\in\Omega_{2}^{j}]\operatorname{Pr}_{\lambda}[I^{v}_{j}(\omega)=1|\omega\in\Omega_{2}^{j}].$

If we fix distinct $i,k\in[n]\setminus\\{j\\}$, then conjugation by
appropriate elements implies
$\Pr_{\lambda}[\omega(i)=j|\omega\in\Omega_{2}^{j}]=\Pr_{\lambda}[\omega(i)=j|\omega\in\Omega_{3}^{j}]=\frac{1}{n-1}$
and
$\Pr_{\lambda}[\omega(i)=j\wedge\omega(j)=k|\omega\in\Omega_{3}^{j}]=\frac{1}{(n-1)(n-2)}$.

Now let $i,j,k$ be elements appearing in succession in a cycle of length at
least 3. A cyclic double ascent at $j$ occurs if and only if $i<j<k$, and
hence there are a total of $(j-1)(n-j)$ choices $\\{i,k\\}$ that result in a
cyclic double ascent at $j\neq 1,n$. A cyclic valley occurs if $i>j<k$, and
thus there are a total of $(n-j)(n-j-1)$ choices for $\\{i,k\\}$ that result
in a cyclic valley at $j\neq n$. However, a cyclic valley also occurs at $j$
when $(i,j)$ is a 2-cycle with $i>j$. There are $(n-j)$ choices for $i$ in
this case.

Combined with the preceding lemma, we see that

$\displaystyle\mathbb{E}_{\lambda}[I_{j}]$
$\displaystyle=\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)\cdot\frac{(j-1)(n-j)}{(n-1)(n-2)},$
$\displaystyle\mathbb{E}_{\lambda}[I^{v}_{j}]$
$\displaystyle=\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)\cdot\frac{(n-j-1)(n-j)}{(n-1)(n-2)}+\frac{2a_{2}}{n}\cdot\frac{n-j}{n-1}.$

Summing over all $j$ gives

$\displaystyle\mathbb{E}_{\lambda}[\operatorname{cdasc}]$
$\displaystyle=\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)\cdot\frac{1}{(n-1)(n-2)}\cdot\sum_{j=2}^{n-1}(j-1)(n-j)=\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)\cdot\frac{n}{6},$
$\displaystyle\mathbb{E}_{\lambda}[\operatorname{cval}]$
$\displaystyle=\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)\cdot\frac{1}{(n-1)(n-2)}\cdot\sum_{j=1}^{n-1}(n-j-1)(n-j)+\frac{2a_{2}}{n(n-1)}\cdot\sum_{j=1}^{n-1}(n-j)$
$\displaystyle=\left(1-\frac{a_{1}}{n}-\frac{2a_{2}}{n}\right)\cdot\frac{n}{3}+a_{2},$

using the facts that $\sum_{j=2}^{n-1}(j-1)(n-j)=\binom{n}{3}$ and
$\sum_{j=1}^{n-1}(n-j-1)(n-j)=2\binom{n}{3}.$ This finishes the proof. ∎

These results confirm the fact that
$\operatorname{exc}(\omega)=\operatorname{cval}(\omega)+\operatorname{cdasc}(\omega)$.

##  6 First moments on $S_{n}$ from conjugacy class

In this section, we consider connections between the first moments on
conjugacy classes with those on all of $S_{n}$. Observe that the expected
values of a statistic $X$ on individual conjugacy classes is related to the
expected value on the entire symmetric group by the formula

$\mathbb{E}_{S_{n}}[X]=\sum_{\lambda\vdash
n}z_{\lambda}^{-1}\mathbb{E}_{\lambda}[X],$ (6.1)

since the order of the conjugacy class indexed by $\lambda$ is
$n!/z_{\lambda}$.

In this section we analyse Equation (6.1) more carefully. The following
identities will be useful.

######  Lemma 6.1.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$. The following
identities hold:

  1. 1.

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}=1$,

  2. 2.

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}a_{1}=1$,

  3. 3.

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}a_{1}^{2}=2$, and

  4. 4.

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}a_{2}=1/2.$

###### Proof.

  1. 1.

This is the class equation for $S_{n}$ [DF91], a consequence of the fact that
$n!=\sum_{\lambda\vdash n}|C_{\lambda}|.$

  2. 2.

This is Burnside’s lemma for the symmetric group [DF91, Sta99].

  3. 3.

Here we consider $S_{n}$ acting on 2-subsets of $[n]$. There is only one
orbit, and a permutation fixes a 2-subset $\\{i,j\\}$ if and only if either
$i,j$ are both fixed points, or $i,j$ form a 2-cycle. Hence the number of
2-subsets fixed by a permutation of cycle type $\lambda$ with $a_{k}$ parts of
length $k$, is $\binom{a_{1}}{2}+a_{2}$, and Burnside’s lemma gives

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}\left(\binom{a_{1}}{2}+a_{2}\right)=1.$
(6.2)

Similarly, by applying Burnside’s lemma to the action of $S_{n}$ on the set
$[n]\times[n]$ of ordered pairs $(i,j)$, which has two orbits $\\{(i,i):1\leq
i\leq n\\}$ and $\\{(i,j):1\leq i,j\leq n,i\neq j\\}$, and counting fixed
points, we obtain

$\sum_{\lambda\vdash
n}z_{\lambda}^{-1}\left(a_{1}+2\binom{a_{1}}{2}\right)=2=\sum_{\lambda\vdash
n}z_{\lambda}^{-1}a_{1}^{2}.$ (6.3)

  4. 4.

Using (6.3) and the second identity also gives

$\sum_{\lambda\vdash n}2z_{\lambda}^{-1}\binom{a_{1}}{2}=1.$ (6.4)

The last identity now follows from (6.2) and (6.4).∎

It is now easy to compute the first moments of the preceding statistics over
the whole symmetric group; see Table 1 for an overview of our results, as well
as a comparison to the literature. Note that we are able to obtain the first
moment over the whole symmetric group without knowledge of the generating
function for the statistic. Recall the definitions of
$\alpha_{n}(X)=\sum_{1\leq i<j\leq n}\text{wt}(i,j)$ and
$\beta_{n}(X)=\sum_{1\leq i<j\leq n}(j-i-1)\text{wt}(i,j)$ for a weighted
inversion statistic $X=\sum_{1\leq i<j\leq n}\text{wt}(i,j)I_{i,j}$ from
Theorem 4.8.

######  Proposition 6.2.

Let $\lambda=(1^{a_{1}},2^{a_{2}},\ldots,n^{a_{n}})\vdash n$, and let
$X=\sum_{1\leq i<j\leq n}\text{wt}(i,j)I_{i,j}$ be a weighted inversion
statistic. Then

  1. 1.

$\mathbb{E}_{S_{n}}[X]=\frac{\alpha_{n}(X)}{2}$, and

  2. 2.

$\mathbb{E}_{\lambda}[X]=\mathbb{E}_{S_{n}}[X]+f^{X}_{n}(a_{1},a_{2}),$ where
$f^{X}_{n}$ is a polynomial of degree at most $2$ in $a_{1}$ and $a_{2}$ such
that

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}f^{X}_{n}(a_{1},a_{2})=0.$

###### Proof.

Note first that $\operatorname{Pr}_{S_{n}}[I_{i,j}=1]=1/2$ for $1\leq i<j\leq
n$. The decomposition $X=\sum_{1\leq i<j\leq n}\text{wt}(i,j)I_{i,j}$ implies

$\mathbb{E}_{S_{n}}[X]=\frac{1}{2}\sum_{1\leq i<j\leq n}\text{wt}(i,j).$

Although we can now conclude Part (2) as well, it is instructive to examine
the different contributions to our expression for $\mathbb{E}_{\lambda}[X]$
more carefully. Since $\beta_{n}(X)=\sum_{1\leq i<j\leq
n}(j-i-1)\text{wt}(i,j)$, from Theorem 4.8 we obtain

$\displaystyle\mathbb{E}_{\lambda}[X]$
$\displaystyle=\left(\frac{1}{2}+\frac{a_{2}}{n(n-1)}-\frac{a_{1}(a_{1}-1)}{2n(n-1)}\right)\alpha_{n}(X)+\left(\frac{n-na_{1}-a_{1}+a_{1}^{2}-2a_{2}}{n(n-1)(n-2)}\right)\beta_{n}(X)$
$\displaystyle=\frac{\alpha_{n}(X)}{2}+\frac{1}{n(n-1)}\left(a_{2}-\binom{a_{1}}{2}\right)\alpha_{n}(X)+\frac{1}{n(n-1)(n-2)}\left(n(1-a_{1})+2\binom{a_{1}}{2}-2a_{2}\right)\beta_{n}(X).$

The function $f_{n}(X)$ is given by

$f_{n}(X)=\frac{1}{n(n-1)}\left(a_{2}-\binom{a_{1}}{2}\right)\alpha_{n}(X)+\frac{1}{n(n-1)(n-2)}\left(n(1-a_{1})+2\binom{a_{1}}{2}-2a_{2}\right)\beta_{n}(X).$

Now Lemma 6.1 guarantees that the two sums

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}(1-a_{1}),\ \ \sum_{\lambda\vdash
n}z_{\lambda}^{-1}\left(a_{2}-\binom{a_{1}}{2}\right)$

vanish identically. Since $\alpha_{n}(X)$ and $\beta_{n}(X)$ are independent
of $\lambda$, we obtain

$\sum_{\lambda\vdash
n}z_{\lambda}^{-1}f_{n}(X)=0\quad\text{and}\quad\sum_{\lambda\vdash
n}z_{\lambda}^{-1}\mathbb{E}_{\lambda}[X]=\frac{\alpha_{n}(X)}{2},$

as claimed. ∎

Now let $Y$ be any of the cyclic permutation statistics considered in Section
5. Arguments analogous to the above give us the following.

######  Proposition 6.3.

For any of the cyclic statistics $Y$ from Section 5, the first moment on the
conjugacy class $C_{\lambda}$ for each
$\lambda=(1^{a_{1}},2^{a_{2}},\ldots)\vdash n$ is of the form

$\mathbb{E}_{\lambda}[Y]=\mathbb{E}_{S_{n}}[Y]+g_{n}(Y),$

where $g_{n}(Y)$ is some polynomial of degree at most $1$ in $a_{1}$ and
$a_{2}$ such that $\sum_{\lambda\vdash n}z_{\lambda}^{-1}g_{n}(Y)=0.$ We have

  1. 1.

$\mathbb{E}_{S_{n}}[\operatorname{exc}]=\frac{n-1}{2}$,
$\mathbb{E}_{S_{n}}[\operatorname{aexc}]=\frac{n+1}{2}$,

  2. 2.

$\mathbb{E}_{S_{n}}[\operatorname{cdasc}]=\frac{n-2}{6}=\mathbb{E}_{S_{n}}[\operatorname{cddes}]$,
and

  3. 3.

$\mathbb{E}_{S_{n}}[\operatorname{cval}]=\frac{2n-1}{6}=\mathbb{E}_{S_{n}}[\operatorname{cpk}]$.

###### Proof.

These follow as in Proposition 6.2, from Theorem 5.1 and Theorem 5.4, using
Lemma 6.1. ∎

We conclude this section by noting that we can now also compute the variance
of the statistic $\operatorname{exc}$, thanks to the following generating
function derived in [CJZ20].

Recall that $C_{\lambda}$ denotes the conjugacy class in $S_{n}$ indexed by
the partition $\lambda$.

######  Proposition 6.4.

[CJZ20, Corollary 7] Let $\lambda$ be a partition of $n$ with $a_{1}$ parts of
size 1. Then

$\sum_{w\in
C_{\lambda}}t^{\operatorname{exc}(w)}=\sum_{i=0}^{\lfloor{(n-a_{1})/2}\rfloor}\gamma_{i}t^{i}(1+t)^{n-a_{1}-2i},$

where $\gamma_{i}=2^{-n+a_{1}+2i}|\\{w\in
C_{\lambda}:\operatorname{cval}(w)=i\\}|$.

From this we can compute, essentially by differentiating twice to get the
generating function for $\operatorname{exc}^{2}$, the second moment over the
conjugacy class $C_{\lambda}$:

$\mathbb{E}_{\lambda}[\operatorname{exc}^{2}]=\frac{(n-a_{1})(n-a_{1}+1)}{4}-\frac{1}{2}\mathbb{E}_{\lambda}[\operatorname{cval}]=\frac{(n-a_{1})^{2}}{4}+\frac{n-a_{1}}{4}-\frac{n-a_{1}+a_{2}}{6},$

and therefore the variance

$\operatorname{Var}_{\lambda}[\operatorname{exc}]=\mathbb{E}_{\lambda}[\operatorname{exc}^{2}]-\frac{(n-a_{1})^{2}}{4}=\frac{n-a_{1}-2a_{2}}{12}.$

Hence we obtain, using Lemma 6.1, the second moment over all of $S_{n}$,

$\mathbb{E}_{S_{n}}[\operatorname{exc}^{2}]=\frac{(3n-2)(n+1)}{12},$

and the variance over all of $S_{n}$,

$\operatorname{Var}_{S_{n}}[\operatorname{exc}]=\frac{n-2}{12}.$

##  7 Permutation constraints and higher moments

In this section, we examine permutation statistics that track permutations
respecting a specified partial function. Somewhat surprisingly, this notion
captures the entire class of permutation statistics. This formulation allows
us to extend a technique of Fulman [Ful98, Theorem 3] to establish an
independence result for the $k$th moment ($k\geq 1$) across individual
conjugacy classes of arbitrary permutation statistics, provided each part of
the indexing permutation is sufficiently large. Fulman [Ful98, Corollary 5]
established the analogous result for $d(\omega)$ and $\operatorname{maj}$. In
the symmetric case, we also show that these higher moments are polynomials in
$n$.

We first start by defining the notion of a permutation constraint statistic.

######  Definition 7.1.

Suppose we have a set of pairs
$K:=\\{(i_{1},j_{1}),(i_{2},j_{2}),\dots,(i_{\ell},j_{\ell})\\}$ with each
$i_{t}\in[n],j_{t}\in[n]$. We call this a (permutation) constraint and say it
has size $m$ if $K$ contains $m$ pairs. Note that since $K$ is a set, repeated
pairs are not allowed. We say $\omega\in S_{n}$ satisfies $K$ if for each
$(i_{t},j_{t})\in K$, $\omega(i_{t})=j_{t}$. We say that $K$ is well-defined
if all the $i_{t}\in[n]$ are distinct and all the $j_{t}\in[n]$ are distinct;
note that some $i_{t}$ may be equal to some $j_{s}$. Define the support of a
constraint $K$ to be the set of all (distinct) $i_{t}$ and $j_{s}$.

Given a constraint $K$, construct the graph $G(K)$ on vertices $[n]$ by
drawing an edge between each pair $(i_{t},j_{t})$. We say that $K$ is _acyclic
of size $m$_ if $K$ is well-defined and $G(K)$ is acyclic with $m$ edges. Note
that the graph constructed from a set of acyclic constraints will be a set of
disconnected directed paths.

######  Example 7.2.

Consider the constraint $K=\\{(1,2),(2,3)\\}$ of size $2$. The permutation
$(1234)$ satisfies $K$, as $(1234)$ maps $1\mapsto 2$ (specified by $(1,2)\in
K$) and $2\mapsto 3$ (specified by $(2,3)\in K$). Intuitively, permutations
that satisfy $K$ contain $123$ as a subsequence within the same cycle.

######  Example 7.3.

Consider the acyclic constraint $K=\\{(1,2),(2,3),(3,4)\\}$ of size $3$. The
permutation $(1234)$ satisfies $K$. Now the graph arising from $K$ as in
Definition 7.1 is acyclic – in particular, observe that the constraint
$(4,1)\not\in K$. Nonetheless, $(1234)$ is a closed cycle. Thus, there may be
cycles in the support of a constraint $K$, even when $K$ is itself acyclic.

Permutation constraints induce statistics on $S_{n}$, which we formalize as
follows.

######  Definition 7.4.

Let $\mathcal{C}$ be a set of permutation constraints. The _size_ of
$\mathcal{C}$, denoted $\text{size}(\mathcal{C})$, is the maximum of the sizes
of the constraints in $\mathcal{C}$. Note that while the size of a single
constraint $K\in\mathcal{C}$ is simply its size as a set, this is not true for
a set of constraints $\mathcal{C}$.

######  Definition 7.5.

A weighted constraint statistic $X$ is any statistic which can be expressed in
the form $\sum_{K\in\mathcal{C}}\text{wt}(K)I_{K}$ where $\mathcal{C}$ is a
set of constraints, $I_{K}$ is the indicator function that a permutation
satisfies the constraint $K$, and weights
$\text{wt}(K)\in\mathbb{R}\setminus\\{0\\}$ for all $K$. In this case, we say
$X$ is _realizable_ over $\mathcal{C}$. If $X$ can be expressed in this form
with $\text{wt}(K)=1$ for all $K\in\mathcal{C}$, then $X$ is the unweighted
constraint statistic induced by $\mathcal{C}$.

Note that in general, the decomposition
$\sum_{K\in\mathcal{C}}\text{wt}(K)I_{K}$ is not unique. The _size_ of a
weighted constraint statistic $X$ is defined as

$\text{size}(X)=\min\left\\{\text{size}(\mathcal{C})\,\bigg{|}\,X=\sum_{K\in\mathcal{C}}\text{wt}(K)I_{K}\text{
for }\text{wt}(K)\in\mathbb{R}\setminus\\{0\\}\right\\}.$

######  Remark 7.6.

It turns out that the class of weighted constraint statistics actually
captures all permutation statistics. Fix $n\geq 1$. For a permutation
$\omega\in S_{n}$, consider its graph
$\mathcal{G}_{\omega}=\\{(i,\omega(i)):i\in[n]\\}$. The indicator for the
constraint induced by $\mathcal{G}_{\omega}$ is precisely the indicator
function for the constraint specified by the permutation $\omega$. The class
of weighted constraint statistics includes indicator functions for any single
permutation, as well as $\mathbb{R}$-linear combinations of them. This in turn
captures the algebra of functions from $S_{n}\to\mathbb{R}$.

In this section, we will establish independence results for higher moments of
permutation statistics on individual conjugacy classes, provided all parts of
the indexing partition are sufficiently large compared to the size of the
statistic. Thus, when investigating an individual permutation statistic $X$,
it is of interest to exhibit _small_ constraint sets that realize $X$.

######  Remark 7.7.

Any unweighted constraint statistic $X$ can also be considered as a weighted
constraint statistic. In general, the size of $X$ as an unweighted permutation
constraint statistic may be different than when viewing it as a weighted
constraint statistic, though we only consider the notion of size for weighted
constraint statistics.

The above definitions are a little abstract and very general, so we first give
a few familiar examples.

######  Example 7.8.

The number of fixed points is a constraint statistic of size $1$. To see this,
let $\mathcal{\mathcal{C}_{\text{fix}}}$ be the set of all constraints
$\\{\\{(i,i)\\}:i=1,\dots,n\\}$. Then we have

$\text{Fix}(\omega)=\sum_{K\in\mathcal{C}_{\text{fix}}}I_{K}(\omega).$

######  Example 7.9.

Let $\mathcal{C}_{i,j}$ be the set of all constraints $\\{\\{(i,a),(j,b)\\}$ :
$a>b\\}$. Then we may express $\operatorname{des},\operatorname{maj}$, and
$\operatorname{inv}$ in terms of these, meaning that these are weighted
constraint statistics of size at most $2$ (and indeed, $\operatorname{des}$
and $\operatorname{inv}$ are unweighted). In particular define the following:

  * •

$\mathcal{C}_{\text{inv}}=\cup_{1\leq i<j\leq n}\mathcal{C}_{i,j}$, and

  * •

$\mathcal{C}_{\text{des}}=\cup_{1\leq i\leq n-1}\mathcal{C}_{i,i+1}$.

Then setting $\text{wt}(\\{(i,a),(j,b)\\}):=i$, we obtain

$\operatorname{maj}(\omega)=\sum_{K\in\mathcal{C}_{\text{des}}}\text{wt}(K)I_{K}(\omega).$

Similar formulas exist for $\operatorname{des}$ and $\operatorname{inv}$. We
can also obtain more general statistics such as cyclic descents. For example,

$\mathcal{C}_{\operatorname{cdes}}=\mathcal{C}_{\operatorname{des}}\cup\mathcal{C}_{n,1}.$

Then in a similar manner to before we have that

$\operatorname{cdes}(\omega)=\sum_{K\in\mathcal{C}_{\operatorname{cdes}}}I_{K}(\omega).$

Note that these statistics actually have size equal to $2$. This fact follows
from our work on first moments, combined with Corollary 7.17 below.

We give another example of a weighted constraint statistic that is not a
weighted inversion statistic: excedance.

######  Example 7.10.

Recall that an excedance is defined as an $i\in[n]$ with $\omega(i)>i$. We can
define the corresponding set of constraints as follows:

$\mathcal{C}_{\operatorname{exc}}=\cup_{1\leq i<j\leq n}\\{\\{(i,j)\\}\\}.$

Then we have that

$\operatorname{exc}(\omega)=\sum_{K\in\mathcal{C}_{\operatorname{exc}}}I_{K}(\omega).$

######  Remark 7.11.

Note that weighted constraint statistics, even those that are realizable over
constraints of size $2$, are more general than weighted inversion statistics.
Furthermore, permutation statistics realizable over constraints of size $3$
already capture all 14 of the statistics from [BS21]. For instance, we will
see below that the number of inversions between excedances where the greater
excedance is _linked_ (denoted ile) is realizable over symmetric constraints
of size $3$.

######  Example 7.12.

The number of inversions between excedances where the greater excedance is
_linked_ is defined [BS21] by

$\text{ile}(\omega):=\\#\\{(i,j)\in[n]\times[n]:i<j<\omega(j)<\omega(i)\text{
and }\omega^{-1}(j)<j\\}.$

(Recall from Section 5.1 that the linked excedances of [BS21] coincide with
the cyclic double ascents of [CJZ20].)

We are therefore counting occurrences of $i<j$ with
$\omega^{-1}(j)<j<\omega(j)<\omega(i)$. This means we can define the following
set of all constraints:

$\mathcal{C}_{\text{ile}}:=\cup_{1\leq i<j\leq
n}\\{\\{(i,a),(j,b),(k,j)\\}:k<j<b<a\\}.$

In a similar manner to before this gives

$\text{ile}(\omega)=\sum_{K\in\mathcal{C}_{\text{ile}}}I_{K}(\omega).$

######  Example 7.13.

[FZ90] The _Denert_ statistic is defined by

$\begin{split}\mathrm{den}(\omega):=&\,\\#\\{1\leq i<j\leq
n:\omega(j)<\omega(i)\leq j\\}\\\ +&\,\\#\\{1\leq i<j\leq n:\omega(i)\leq
j<\omega(j)\\}\\\ +&\,\\#\\{1\leq i<j\leq
n:j<\omega(j)<\omega(i)\\}\end{split}$

The statistic $\mathrm{den}$ has the property that the joint distributions of
the pairs $(\operatorname{exc},\mathrm{den})$ and
$(\operatorname{des},\operatorname{maj})$ coincide. Such pairs are called
Euler-Mahonian in the literature [FZ90].

Observe that $\mathrm{den}$ may be realized as an unweighted constraint
statistic induced by a constraint set of size 2, since we have

$\mathrm{den}(\omega)=\sum_{K\in\mathcal{C}_{\mathrm{den}}}I_{K}(\omega)$

for the set of constraints

$\begin{split}\mathcal{C}_{\mathrm{den}}:=&\cup_{1\leq i<j\leq
n}\\{\\{(i,a),(j,b)\\}:b<a\leq j\\}\\\ \bigcup&\cup_{1\leq i<j\leq
n}\\{\\{(i,a),(j,b)\\}:a\leq j<b\\}\\\ \bigcup&\cup_{1\leq i<j\leq
n}\\{\\{(i,a),(j,b)\\}:j<b<a\\}.\end{split}$

We now give a relatively simple observation.

######  Proposition 7.14.

Let $K$ be a well-defined constraint of size $m$. Then we have:

$\operatorname{Pr}_{S_{n}}[\omega\text{ satisfies
}K]=\frac{1}{n(n-1)(n-2)\dots(n-m+1)}.$

###### Proof.

Let $K:=\\{(i_{1},j_{1}),(i_{2},j_{2}),\dots,(i_{m},j_{m})\\}$, and suppose
$\omega$ satisfies $K$. This means that we have $\omega(i_{t})=j_{t}$ for
$t=1,\dots,m$, which is possible since the constraint is well-defined. The
number of permutations which satisfy these $m$ values is just the number of
permutations on the remaining $n-m$ symbols, which is $(n-m)!$. Therefore the
probability of a random permutation satisfying $K$ is $(n-m)!/n!$ as required.
∎

We are interested in the behavior of certain constraint statistics on fixed
conjugacy classes. The key result of this section is the following, which says
that for $\lambda$ with all parts “large,” the probability of a permutation in
$C_{\lambda}$ satisfying a constraint is only dependent on whether the
constraint set is acyclic.

######  Lemma 7.15.

Let $\lambda$ have all parts of size at least $m+1$, and let $K$ be a
constraint of size $m$. If $K$ is acyclic then we have

$\displaystyle\operatorname{Pr}_{\lambda}[\omega\text{ satisfies
}K]=\frac{1}{(n-1)(n-2)\dots(n-m)}.$

If $K$ is not acyclic then we have

$\operatorname{Pr}_{\lambda}[\omega\text{ satisfies }K]=0.$

###### Proof.

We first note that if $K$ is not acyclic, then in order for $\omega$ to
satisfy $K$, $\omega$ must contain a cycle induced by constraints in $K$.
Since $K$ has size $m$, then this cycle is of length at most $m$. However we
assumed $\omega$ is of cycle type $\lambda$ with all cycles of length at least
$m+1$, so this is not possible.

Now suppose $K$ is acyclic. We fix $n$ and then prove this lemma by induction
on $m$. For $m=1$, we will show that

$\operatorname{Pr}_{\lambda}[\omega(i_{1})=j_{1}]=\frac{1}{n-1}.$

This follows from the fact that conjugating by $(j_{1}\,k)$ for any $k\neq
i_{1},j_{1}$ maps from the set of $\omega$ with $\omega(i_{1})=j_{1}$ to those
with $\omega(i_{1})=k$. Therefore this probability is the same for each
$j_{1}\neq i_{1}$, and is zero for $i_{1}=j_{1}$ since $\lambda$ is fixed
point free. Therefore the probability is $1/(n-1)$ as required.

Assume the statement is true for $m-1$. Let
$A=\\{(i_{1},j_{1}),\dots,(i_{m},j_{m})\\}$ be an acyclic constraint of size
$m$. Let $\lambda\vdash n$ have all parts of size at least $m+1$, and label
the cycles of any permutation in $C_{\lambda}$ by $c_{1},\dots,c_{t}$. By
Definition 7.4, we have

$\displaystyle\operatorname{Pr}_{\lambda}[\omega\text{ satisfies }A]$
$\displaystyle=\operatorname{Pr}_{\lambda}\left[\bigwedge_{\ell=1}^{m}\omega(i_{\ell})=j_{\ell}\right]$
$\displaystyle=\operatorname{Pr}_{\lambda}\left[\bigwedge_{\ell=1}^{m-1}\omega(i_{\ell})=j_{\ell}\biggr{|}\,\omega(i_{m})=j_{m}\right]\cdot\operatorname{Pr}_{\lambda}[\omega(i_{m})=j_{m}]$
$\displaystyle=\frac{1}{n-1}\sum_{h=1}^{t}\operatorname{Pr}_{\lambda}\left[\bigwedge_{\ell=1}^{m-1}\biggr{(}\omega(i_{\ell})=j_{\ell}\land
i_{m}\in c_{h}\biggr{)}\biggr{|}\,\omega(i_{m})=j_{m}\right]$
$\displaystyle=\frac{1}{n-1}\sum_{h=1}^{t}\operatorname{Pr}_{\lambda}\left[\bigwedge_{\ell=1}^{m-1}\omega(i_{\ell})=j_{\ell}\,\biggr{|}\,i_{m}\in
c_{h}\land\omega(i_{m})=j_{m}\right]\cdot\operatorname{Pr}_{\lambda}[i_{m}\in
c_{h}\mid\omega(i_{m})=j_{m}].$

Notice that $A^{\prime}:=\\{(i_{1},j_{1}),\dots,(i_{m-1},j_{m-1})\\}$ is an
acyclic constraint of size $m-1$. Let $\lambda^{\prime}(h)$ be the partition
obtained by reducing the size of the $h^{th}$ part of $\lambda$ by one. This
is a partition of an $(n-1)$-element set (though perhaps not $[n-1]$) with all
parts of size at least $m-1$. It is then fairly straightforward to see that

$\operatorname{Pr}_{\lambda}\left[\bigwedge_{\ell=1}^{m-1}\omega(i_{\ell})=j_{\ell}\,\biggr{|}\,i_{m}\in
c_{h}\land\omega(i_{m})=j_{m}\right]=\operatorname{Pr}_{\lambda^{\prime}(h)}[\omega\text{
satisfies }A^{\prime}]=\frac{1}{(n-2)(n-3)\dots(n-m)},$

where the last equality follows by the induction hypothesis. Note that the
first term is $n-2$, as the probability is in $S_{n-1}$. Putting this
altogether gives

$\displaystyle\operatorname{Pr}_{\lambda}[\omega\text{ satisfies }A]$
$\displaystyle=\frac{1}{n-1}\sum_{h=1}^{t}\frac{1}{(n-2)(n-3)\dots(n-m)}\frac{\lambda_{h}}{n}$
$\displaystyle=\frac{1}{(n-1)(n-2)\dots(n-m)}.$

This completes the inductive step and the proof. ∎

As a consequence, we obtain that for each $k$, the $k$th moment of these
statistics is independent of conjugacy class, as long as the cycles are
sufficiently long.

######  Theorem 7.16.

Let $X$ be a permutation statistic that is realizable over a constraint set of
size $m$, and fix $k\geq 1$. If $\lambda\vdash n$ has all parts of size at
least $mk+1$, then $\mathbb{E}_{\lambda}[X^{k}]$ is independent of $\lambda$.

###### Proof.

Express $X=\sum_{P\in\mathcal{C}}\text{wt}(P)I_{P}$, where
$\text{size}(\mathcal{C})=m$. We start by decomposing the variable $X^{k}$
into random indicator variables.

$\displaystyle\mathbb{E}_{\lambda}[X^{k}]$
$\displaystyle=\sum_{P_{1}\in\mathcal{C}}\sum_{P_{2}\in\mathcal{C}}\dots\sum_{P_{k}\in\mathcal{C}}\prod_{i=1}^{k}\text{wt}(P_{i})\cdot\mathbb{E}_{\lambda}[I_{P_{i}}]$
$\displaystyle=\sum_{P_{1}\in\mathcal{C}}\sum_{P_{2}\in\mathcal{C}}\dots\sum_{P_{k}\in\mathcal{C}}\left(\prod_{i=1}^{k}\text{wt}(P_{i})\right)\operatorname{Pr}_{\lambda}\left[\bigwedge_{i=1}^{k}\omega\text{
satisfies }P_{i}\right].$

We therefore continue by evaluating each of the individual probabilities in
the sum.

Fix some tuple $P_{1},P_{2},\dots,P_{k}$, and let $Y$ be the union of all of
these constraints excluding repeats. Write
$Y=\\{(i_{1},j_{1}),\dots,(i_{s},j_{s})\\}$, noting that all the pairs are
distinct. We split into three cases.

  * •

Case 1: Suppose first that $Y$ is not well defined. Then there must be some
repeated $i_{t}$ or $j_{t}$. Since we excluded repeats, there must be pairs of
the form $\\{(i_{t},a),(i_{t},b)\\}$ or $\\{(a,j_{t}),(b,j_{t})\\}$. However
$\omega(i_{t})$ and $\omega^{-1}(j_{t})$ can only take one value, so the
probability of $Y$ being satisfied is zero.

  * •

Case 2: Suppose instead that $Y$ is not acyclic. Then by Lemma 7.15, we have
that $\operatorname{Pr}_{\lambda}[w\text{ satisfies }Y]=0$.

  * •

Case 3: $Y$ is well defined, and no subsets of the values in
$\omega(i_{1})=j_{1},\omega(i_{2})=j_{2},\dots,\omega(i_{s})=j_{s}$ form a
cycle. Then this is a set of acyclic constraints of size at most $mk$. By the
previous proposition we therefore have that

$\operatorname{Pr}_{\lambda}[\omega\text{ satisfies
}Y]=\frac{1}{(n-1)(n-2)\dots(n-s)}.$

In particular, none of these probabilities depend on the choice of $\lambda$,
so the result follows. ∎

######  Corollary 7.17.

Let $X$ be a permutation statistic, and let $\lambda\vdash n$. Suppose that
$\mathbb{E}_{\lambda}[X]$ depends on the number of parts of $\lambda$ of size
$m$. Then any constraint set realizing $X$ must have size at least $m$.

######  Remark 7.18.

Let $\mathcal{C}$ be a constraint set of size $m$. Clearly, if we can express
$X=\sum_{P\in\mathcal{C}}I_{P}$, then any minimum-sized constraint set
realizing $X$ has size at most $m$.

The above corollary shows that calculating the first moment of $X$ even just
on specific conjugacy classes allows us to obtain a lower bound on the size of
$X$. This approach allows us to explicitly calculate the size for many
statistics.

Once we have determined the size of $X$, we can then apply Theorem 7.16, so we
see that information on the higher moments of $X$ can be obtained from the
first moment, further highlighting the importance of the latter.

######  Remark 7.19.

It will be useful later to write the expectation $\mathbb{E}_{\lambda}[X^{k}]$
from Theorem 7.16 more explicitly in the unweighted case, so we do this.

Let $\mathcal{A}$ be the set of all the acyclic constraints from amongst the
tuples $P_{1},\dots,P_{k}$ in the sum. Let $\mathcal{A}_{t}$ be the set of all
the acyclic constraints in $\mathcal{A}$ of size $t$. Using the three previous
cases, we may write the required expectation as

$\displaystyle\mathbb{E}_{\lambda}[X^{k}]$
$\displaystyle=\sum_{P\in\mathcal{A}}\operatorname{Pr}_{\lambda}[\omega\text{
satisfies }P]$
$\displaystyle=\sum_{t}\frac{|\mathcal{A}_{t}|}{(n-1)(n-2)\dots(n-t)}.$

This number is independent of the choice of $\lambda$ as long as it has parts
of size at least $mk+1$. Observe that taking
$X(\omega)=\operatorname{maj}(\omega)$ or
$X(\omega)=d(\omega)=1+\operatorname{des}(\omega)$ yields [Ful98, Theorem 2].

We continue by showing that when a statistic is _symmetric_ , these moments
are polynomial in $n$. We now define this precisely.

######  Definition 7.20.

Let $a_{1},\ldots,a_{n_{0}}\in[n]$. A function
$f:\\{a_{1},\ldots,a_{n_{0}}\\}\rightarrow[n]$ is _order-preserving_ when
$a_{i}<a_{j}$ if and only if $f(a_{i})<f(a_{j})$ for all $i,j\in[n_{0}]$. Note
that any such function must be injective.

######  Definition 7.21.

Let $\mathcal{C}$ be a set of permutation constraints, and let $X$ be the
unweighted constraint statistic induced by $\mathcal{C}$. Take some
$P=\\{(i_{1},j_{1})\dots(i_{\ell},j_{\ell})\\}\in\mathcal{C}$. Let the
distinct symbols amongst the $i_{1},\dots,i_{\ell},j_{1},\dots,j_{\ell}$ be
$1\leq a_{1}<a_{2}<\dots<a_{n_{0}}\leq n$. If
$f(P):=\\{(f(i_{1}),f(j_{1}))\dots(f(i_{\ell}),f(j_{\ell}))\\}\in\mathcal{C}$
for all such choices of $P\in\mathcal{C}$ and order-preserving
$f:\\{a_{1},\ldots,a_{n_{0}}\\}\rightarrow[n]$, then we say that $X$ is
_symmetric_.

We start by examining how this definition relates to some familiar statistics.

  * •

Inversions are symmetric: take any
$P=\\{(a,b),(c,d)\\}\in\mathcal{C}_{\text{inv}}$ and any order preserving
injection $f:\\{a,b,c,d\\}\rightarrow[n]$. Then we must have $a<c,b>d$, so
$f(a)<f(c),f(b)>f(d)$. Therefore
$f(P)=\\{(f(a),f(b)),(f(c),f(d))\\}\in\mathcal{C}_{\text{inv}}$.

  * •

Descents cannot be realized as symmetric constraint statistics using
constraints of size $2$. Let $\mathcal{C}_{i,j}$ be as defined in Example 7.9.
For example, take
$P=\\{(1,5),(2,4)\\}\,{\in\mathcal{C}_{1,2}}\subseteq\mathcal{C}_{\text{des}}$.
Let $1<3<4<5$, with $f(1)=1,f(2)=3,f(4)=4,f(5)=5$. Then
$f(P)=\\{(1,5),(3,4)\\}\,{\in\mathcal{C}_{1,3}}\not\subseteq\mathcal{C}_{\text{des}}$.
We may iterate on this argument, replacing $(1,5),(2,4)$ with arbitrary values
respecting the same relative ordering. It is not clear whether descents can be
realized using a symmetric constraint set of larger size.

  * •

The number of inversions between excedances, as defined in [BS21], is
symmetric. This is because the constraints for this statistic are exactly the
$(a,b),(c,d)$ with $a<c<d<b$, so the images of these elements under an order-
preserving $f$ will give another valid constraint.

Given a symmetric permutation constraint statistic on $S_{n_{0}}$, there is
also a natural way of extending this statistic to any $S_{n}$.

######  Definition 7.22.

Let $X$ be a symmetric permutation constraint statistic on $S_{n_{0}}$ induced
by some $\mathcal{C}$ supported on $[n_{0}]$. Then for any $S_{n}$, we can
define a symmetric permutation constraint statistic $X_{n}$ on $S_{n}$ by
starting with the set of constraints $\mathcal{C}$ for $X$ and constructing
the following set of constraints $\mathcal{C}_{n}$ for $X_{n}$.

  * •

If $n\leq n_{0}$, then let $\mathcal{C}_{n}$ contain all $P\in\mathcal{C}$
with support contained in $[n]$.

  * •

If $n>n_{0}$, then let $\mathcal{C}_{n}$ contain all $P\in\mathcal{C}$, as
well as all $f(P)$ for all order-preserving functions
$f:[n_{0}]\rightarrow[n]$. Note that we exclude repeated constraints in
$\mathcal{C}_{n}$.

Then by construction each $X_{n}$ is symmetric. We call $(X_{n})$ a _symmetric
extension of $X$_.

######  Example 7.23.

While the previous definition seems technical, there are several natural
examples.

  * •

Consider the constraint $K=\\{(1,2)\\}$, and define the statistic $X$ on
$S_{2}$ by $X=I_{K}$. Then the $(X_{n})$ are the excedance statistics.

  * •

Fix $\omega\in S_{m}$. Let $\mathcal{C}$ be the constraints of size $m$ in
$S_{2m}$ that induce the permutation pattern statistic for $\omega$ in
$S_{2m}$. Then each statistic in $(X_{n})$ is the number of appearances of the
permutation pattern $\omega$ for a given element in $S_{n}$. Note that
choosing $\omega=(12)\in S_{2}$ results in the usual inversion statistics on
$S_{n}$.

######  Remark 7.24.

The preceding examples show that symmetric permutation constraint statistics
are more general than permutation pattern statistics, as excedances cannot be
expressed as a permutation pattern. See Remark 1.7 for more discussion, as
well as a comparison of our work with that of Gaetz and Pierson [GP22].

######  Remark 7.25.

In general, it is necessary to consider symmetric extensions starting from
some sufficiently large $n_{0}$. Observe that both $\\{(1,2)\\}$ and
$\\{(1,2),(2,1)\\}$ induce $\operatorname{inv}$ on $S_{2}$. However, the
symmetric extension of $\\{(1,2)\\}$ yields the excedance statistic, while the
symmetric extension of $\\{(1,2),(2,1)\\}$ realizes transpositions. In the
preceding example, we see that the symmetric extension starting with the
inversion statistic on $S_{4}$ results in the inversion statistics on all
$S_{n}$.

With this definition in hand, we now show that when all parts of a partition
are sufficiently large, the moments of any statistic constructed in this
manner are given by a single polynomial dependent only on $n$.

######  Theorem 7.26.

Fix $k,m\geq 1$. Let $(\lambda_{n})$ be a sequence of partitions, where
$\lambda_{n}\vdash n$ and all parts of $\lambda_{n}$ have size at least
$mk+1$. Let $(X_{n})$ be a symmetric extension of a symmetric permutation
statistic $X=X_{n_{0}}$ induced by a constraint set of size $m$. There exists
a polynomial $p_{X}(n)$ depending only on $X$ such that
$p_{X}(n)=\mathbb{E}_{\lambda_{n}}[X_{n}^{k}]$.

###### Proof.

As in Theorem 7.16, it suffices to consider
$\mathcal{A}_{n}=\bigcup_{i}P_{n,i}$, where the union runs over all well-
defined acyclic $k-$tuples of constraints in $X_{n}$. Let
$\mathcal{A}_{n,t}\subseteq\mathcal{A}_{n}$ be the constraints of size $t$.
Note that each constraint $P\in\mathcal{A}_{n}$ is a tuple of constraint, and
multiple constraints may involve the same elements. Recall that the support of
a constraint
$P=\\{(i_{1},j_{1}),\dots,(i_{\ell},j_{\ell})\\}\in\mathcal{A}_{n}$ is the set
of distinct elements among the $i_{1},\dots,i_{\ell},j_{1},\dots,j_{\ell}$.
Define $\mathcal{A}_{n,t,s}\subseteq\mathcal{A}_{n,t}$ be the constraints of
size $t$ with support on $s$ elements, where acyclicity of elements in
$\mathcal{A}_{n,t}$ implies $t+1\leq s\leq 2t$. Then we have from Remark 7.19
that

$\begin{split}\mathbb{E}_{\lambda_{n}}[X_{n}^{k}]&=\sum_{t=1}^{mk}\frac{|\mathcal{A}_{n,t}|}{(n-1)(n-2)\dots(n-t)}\\\
&=\sum_{t=1}^{mk}\left(\frac{1}{(n-1)(n-2)\dots(n-t)}\sum_{s=t+1}^{2t}|\mathcal{A}_{n,t,s}|\right).\end{split}$
(7.1)

Now let $\mathcal{A}_{n,t,s}^{\prime}\subseteq\mathcal{A}_{n,t,s}$ be the
constraints that are supported on $[s]$. Observe that when $n<s$,
$\mathcal{A}_{n,t,s}^{\prime}=\emptyset$, and since $X_{n}$ is formed as the
symmetric extension of $X_{n_{0}}$, this $\mathcal{A}_{n,t,s}^{\prime}$ is
independent of $n$ for $n\geq s$, so we call this common set
$\mathcal{A}_{t,s}$. Furthermore, since $X_{n}$ is symmetric, for $n\geq s$,
we can express

$\mathcal{A}_{n,t,s}=\bigcup_{f}\bigcup_{P\in\mathcal{A}_{t,s}}f(P),$

where the first union is over all order-preserving $f$. Now as each $P$ uses
all elements of $[s]$ and each $f$ is determined by its image in $[n]$, we
have that $f_{1}(P_{1})=f_{2}(P_{2})$ can only occur if $f_{1}=f_{2}$ and
$P_{1}=P_{2}$. Then letting $a_{t,s}=|\mathcal{A}_{t,s}|$, we have that for
$n\geq s$,

$|\mathcal{A}_{n,t,s}|={n\choose s}a_{t,s},$

as there are ${n\choose s}$ order-preserving functions $f:[s]\to[n]$. Letting
$I_{s}(n)$ be the indicator function for $n\geq s$, we see that (7.1) can be
rewritten as

$\begin{split}\mathbb{E}_{\lambda_{n}}[X_{n}^{k}]&=\sum_{t=1}^{mk}\left(\frac{1}{(n-1)(n-2)\dots(n-t)}\sum_{s=t+1}^{2t}{n\choose
s}a_{t,s}I_{s}(n)\right)\\\ &=\sum_{t=1}^{mk}\sum_{s=t+1}^{2t}{n\choose
s}\frac{a_{t,s}I_{s}(n)}{(n-1)(n-2)\dots(n-t)}.\end{split}$ (7.2)

Observe that $s\geq t+1$, and when $n\geq s$, we have that

$\begin{split}\binom{n}{s}\cdot\frac{1}{(n-1)(n-2)\dots(n-t)}&=\frac{1}{s!}\cdot\frac{n(n-1)(n-2)\dots(n-s+1)}{(n-1)(n-2)\dots(n-t)}\\\
&=\frac{1}{s!}\cdot n(n-t-1)\ldots(n-s+1)\end{split}$

is a polynomial in $n$ of degree $s-t$. Furthermore, $\lambda_{n}$ has all
parts of size at least $mk+1>t$, so $n\geq mk+1>t$. When values of $n$ with
$t<n<s$ are substituted, the above polynomial vanishes. Hence, we can rewrite
(7.2) and omit the $I_{s}$ indicator function to obtain

$\begin{split}\mathbb{E}_{\lambda_{n}}[X_{n}^{k}]&=\sum_{t=1}^{mk}\sum_{s=t+1}^{2t}\frac{a_{t,s}}{s!}\cdot
n(n-t-1)\ldots(n-s+1).\end{split}$ (7.3)

We conclude that (7.2) is a polynomial in $n$ of degree

$\max_{P\in\mathcal{A}_{2mk}}(|\operatorname{supp}(P)|-\text{size}(P))\leq
mk.\qed$

######  Remark 7.27.

The proof of the preceding result gives a method for finding $p_{X}(n)$, which
we illustrate with an example. Consider the mean of the inversion statistic on
conjugacy classes $\lambda_{n}$ with cycle lengths of at least $3$, so that
$m=2$ and $k=1$ in (7.3). In the summation of (7.2), the only nonzero values
involve $t=2$, which implies $s\in\\{3,4\\}$. Of the constraints in
$\operatorname{inv}$ using only values in the sets $[3]$ and $[4]$, we see
that the acyclic ones that use all values are

$\mathcal{A}_{2,3}=\left\\{\\{(1,3),(2,1)\\},\\{(1,2),(3,1)\\},\\{(1,3),(3,2)\\},\\{(2,3),(3,1)\\}\right\\},$
$\mathcal{A}_{2,4}=\left\\{\\{(1,4),(2,3)\\},\\{(1,4),(3,2)\\},\\{(1,3),(4,2)\\},\\{(2,4),(3,1)\\},\\{(2,3),(4,1)\\},\\{(3,2),(4,1)\\}\right\\}.$

Then (7.3) becomes

$\mathbb{E}_{\lambda_{n}}[\operatorname{inv}]=\frac{4}{3!}\cdot
n+\frac{6}{4!}\cdot n(n-3)=\frac{3n^{2}-n}{12},$

which agrees with our Corollary 4.10. For higher moments, explicit description
of acyclic constraints in terms of $k$-tuples becomes significantly more
complex, and this method becomes computationally very difficult.

In the case of certain statistics such as inversions, we can determine much
more about the structure of this polynomial.

######  Proposition 7.28.

Let $\lambda$ be a partition of $n$ with all parts of size at least $2k+1$.
Then $\mathbb{E}_{\lambda}[\mathrm{inv}^{k}]$ is a polynomial in $n$ of degree
$2k$ with leading coefficient $2^{-2k}$.

###### Proof.

The polynomiality follows from Theorem 7.26. From the proof of this Theorem we
also have that

$\displaystyle\mathbb{E}_{\lambda}[\text{inv}^{k}]=\sum_{t=1}^{2k}\sum_{s=t+1}^{2t}\frac{a_{t,s}}{s!}\cdot
n(n-t-1)\ldots(n-s+1).$ (7.4)

Recall that $a_{t,s}$ is the number $k$-tuples $\\{(a,b),(c,d)\\}$ with
$a<c,b>d$ that consist of $t$ distinct pairs and use exactly the elements in
$[s]$. The degree of this polynomial corresponds to when $s-t\leq 2k$ is
maximal. Note that $s-t=2k$ can occur only when $s=4k$ and $t=2k$, so it
suffices to show that $a_{2k,4k}$ is nonzero. Hence, we consider $2k$ distinct
pairs using all elements in $[4k]$.

There are $\binom{4k}{4,4,\dots,4}$ ways to partition $[4k]$ into $k$ sets of
four symbols. For each set of four symbols $\\{a,b,c,d\\}$ suppose that
$a<b<c<d$. Then there will be $6$ ways to put this set into two pairs which
relate to an inversion constraint, which are

$\\{(a,c),(d,b)\\},\,\\{(a,d),(b,c)\\},\,\\{(a,d),(c,b)\\},\,\\{(b,c),(d,a)\\},\,\\{(c,b),(d,a)\\},\,\\{(b,d),(c,a)\\}.$

Therefore in total we have
$a_{2k,4k}=\binom{4k}{4,4,\dots,4}6^{k}=(4k)!/4^{k}$. Substituting this back
into (7.4) gives a leading coefficient of $1/4^{k}$ for the $x^{2k}$ term as
required. ∎

As an application, we can use polynomial interpolation on $2k+1$ values of $n$
to explicitly compute $\mathbb{E}_{\lambda}[\operatorname{inv}^{k}]$ when all
parts of $\lambda$ have size at least $2k+1$. The case of the second moment of
$\operatorname{inv}$ is given below.

######  Corollary 7.29.

Let $\lambda$ be a partition of $n$ with all parts of size at least $5$. Then

$\mathbb{E}_{\lambda}[\operatorname{inv}^{2}]=\frac{1}{16}n^{4}-\frac{1}{72}n^{3}-\frac{1}{80}n^{2}-\frac{49}{360}n,$

and consequently,

$\operatorname{Var}_{\lambda}[\operatorname{inv}]=\frac{1}{36}n^{3}-\frac{7}{360}n^{2}-\frac{49}{360}n.$

###### Proof.

We consider the conjugacy class $C_{(n)}$ corresponding to full cycles in
$S_{n}$. Using code, we find the following values:

$\displaystyle\mathbb{E}_{(5)}[\operatorname{inv}^{2}]=109/3,$
$\displaystyle\mathbb{E}_{(6)}[\operatorname{inv}^{2}]=1151/15,$
$\displaystyle\mathbb{E}_{(7)}[\operatorname{inv}^{2}]=2156/15,$
$\displaystyle\mathbb{E}_{(8)}[\operatorname{inv}^{2}]=247,$
$\displaystyle\mathbb{E}_{(9)}[\operatorname{inv}^{2}]=3977/10,$

The result for $\mathbb{E}_{\lambda}[\operatorname{inv}^{2}]$ follows by
polynomial interpolation, and
$\operatorname{Var}_{\lambda}[\operatorname{inv}]=\mathbb{E}_{\lambda}[\operatorname{inv}^{2}]-(\mathbb{E}_{\lambda}[\operatorname{inv}])^{2}$
then follows by direct calculation. ∎

######  Remark 7.30.

We compare Corollary 7.29 with Feller’s corresponding result for the full
$S_{n}$ [Fel68, p. 257, equations (6.1)-(6.3)]:

$\mathbb{E}_{S_{n}}[\operatorname{inv}]=\frac{1}{4}n(n-1),$

$\mathbb{E}_{S_{n}}[\operatorname{inv}^{2}]=\frac{1}{16}n^{4}-\frac{7}{72}n^{3}+\frac{5}{48}n^{2}-\frac{5}{72}n,$

$\operatorname{Var}_{S_{n}}[\operatorname{inv}]=\frac{1}{72}(2n^{3}+3n^{2}-5n).$

We note that leading terms coincide.

##  8 Conclusion

In this paper, we investigated the distributions of various permutation
statistics on individual conjugacy classes. We first introduced general
notions of permutation statistics, including (i) weighted inversion
statistics, which generalized inversions, major index, descents, and baj, and
(ii) permutation constraints. We utilized the notion of permutation
constraints to reason about arbitrary permutation statistics. Precisely, we
showed that the higher moments are independent of the conjugacy class indexed
by the partition $\lambda\vdash n$, provided all parts of $\lambda$ are
sufficiently large. For permutation statistics realizable over symmetric
constraints, we were further able to establish polynomiality for the higher
moments on individual conjugacy classes indexed by $\lambda\vdash n$, again
provided that all parts of $\lambda$ are sufficiently large. Our work leaves
open several questions.

In Proposition 6.2, we showed that for any conjugacy class $\lambda$ and a
weighted inversion statistic $X$, $\mathbb{E}_{\lambda}[X]$ can be written as
$\mathbb{E}_{S_{n}}[X]$ plus some error term $f_{n}^{X}(a_{1},a_{2})$, which
is a degree $2$ polynomial depending only on $X$ and $a_{i}$ ($i=1,2$), the
number of cycles of size $i$ in $\lambda$. As our independence results in
Section 7 require that all parts of $\lambda$ be sufficiently large, we
suspect that Proposition 6.2 can be extended in the following manner.

######  Problem 8.1.

Show that
$\mathbb{E}_{\lambda}[X^{k}]=\mathbb{E}_{S_{n}}[X^{k}]+f_{n}^{X^{k}}(a_{1},\ldots,a_{2k})$,
where $a_{i}$ is the number of cycles of length $i$ in $\lambda$, and
$f_{n}^{X^{k}}$ is a polynomial of degree at most $2k$, (necessarily)
satisfying the condition

$\sum_{\lambda\vdash n}z_{\lambda}^{-1}f_{n}^{X^{k}}(a_{1},\ldots,a_{2k})=0.$

Our technique in establishing Proposition 6.2 required detailed case analysis.
Moving to even the second moment, the number of cases grows substantially. It
would be of interest to find a tractable technique that easily extends to
higher moments.

As we have not only an independence result, but also polynomiality on the
higher moments of permutation statistics realizable over symmetric constraint
sets, it seems plausible that such statistics admit a nice asymptotic
distribution. In particular, a central limit theorem for descents on
individual conjugacy classes is known [Ful98, Kim19, KL20]. We thus ask the
following.

######  Problem 8.2.

Fix $k,m\geq 1$. Let $(X_{n})$ be a symmetric extension of a symmetric
permutation statistic of size $m$. Let $\lambda_{n}$ be a partition of $n$,
with each part of size at least $mk+1$. Establish a central limit theorem for
$(X_{n})$ on $\lambda_{n}$.

While we have established that a number of statistics such as
$\operatorname{inv}$, $\operatorname{exc}$, $\operatorname{aexc}$,
$\text{cdasc},$ and cddes are symmetric, we have been unable to show that any
of the statistics in this paper are not symmetric. In particular, we do not
have tractable conditions to show that a permutation statistic is not
symmetric. Thus, we ask the following.

######  Problem 8.3.

Provide a characterization of when a permutation statistic is realizable over
a symmetric constraint set.

In light of Theorem 7.26 and the fact that the first moment of
$\operatorname{cdes}$ is a rational function on any individual conjugacy class
(Theorem 4.14), we have that the family $(\operatorname{cdes}_{n})$ cannot be
realized as the symmetric extension of any permutation statistic $X$. We
conjecture that no individual $\operatorname{cdes}_{m}$ is itself symmetric.
However, it is not clear how to establish this. Furthermore, we conjecture
that $\operatorname{des},\operatorname{maj},\operatorname{baj},$ and
$\operatorname{baj}-\operatorname{inv}$ are not realizable over any symmetric
permutation constraints or as the symmetric extensions of any permutation
statistic.

Since our work in this paper establishes results for the Coxeter group of type
$A$, it is natural to ask the following.

######  Problem 8.4.

Extend the results of this paper to other Coxeter groups.

It is likely that the calculations would need to be updated to the setting of
the given family of Coxeter groups being considered, but that the techniques
in this paper might still apply. Ideally, one might hope for a general
technique that can handle all Coxeter groups without redoing the calculations
for each such family.

Given a statistic $X$ on the symmetric group $S_{n}$, the first moments
$\mathbb{E}_{\lambda}[X]$ are class functions, and may thus be interpreted as
the character of a possibly virtual representation of $S_{n}$. Equation (6.1),
which gives the first moment of $X$ on all of $S_{n}$, is then precisely the
multiplicity of the trivial module in some (virtual) representation of
$S_{n}$. Thus one could ask if there is a representation-theoretic
interpretation of our results, beyond the connection with character
polynomials as in [GP22].

######  Problem 8.5.

Investigate representation-theoretic interpretations of these results.

## References

  * [BD92] Dave Bayer and Persi Diaconis.  Trailing the dovetail shuffle to its lair.  The Annals of Applied Probability, 2, 05 1992.  doi:10.1214/aoap/1177005705.
  * [BKS20] Sara C. Billey, Matjaž Konvalinka, and Joshua P. Swanson.  Asymptotic normality of the major index on standard tableaux.  Adv. in Appl. Math., 113:101972, 36, 2020.  doi:10.1016/j.aam.2019.101972.
  * [Bre93] Francesco Brenti.  Permutation enumeration, symmetric functions, and unimodality.  Pacific J. Math., 157(1):1–28, 1993.  URL: http://projecteuclid.org/euclid.pjm/1102634861.
  * [BS21] Natasha Blitvić and Einar Steingrímsson.  Permutations, moments, measures.  Transactions of the American Mathematical Society, 374(08):5473–5508, 2021.
  * [Cel98] Paola Cellini.  Cyclic Eulerian elements.  European J. Combin., 19(5):545–552, 1998.  doi:10.1006/eujc.1998.0218.
  * [CJZ20] M. Crossan Cooper, William S. Jones, and Yan Zhuang.  On the joint distribution of cyclic valleys and excedances over conjugacy classes of ${S}_{n}$.  Adv. in Appl. Math., 115:101999, 15, 2020.  doi:10.1016/j.aam.2020.101999.
  * [DF91] David S. Dummit and Richard M. Foote.  Abstract Algebra.  Prentice Hall, Inc., Englewood Cliffs, NJ, 1991.
  * [DG19] Persi Diaconis and Ron Graham.  12\. The Magic of Charles Sanders Peirce, pages 161–203.  Princeton University Press, Princeton, 2019.  doi:10.1515/9780691194417-014.
  * [DMP95] Persi Diaconis, Michael McGrath, and Jim Pitman.  Riffle shuffles, cycles, and descents.  Combinatorica, 15(1):11–29, mar 1995.  doi:10.1007/BF01294457.
  * [DP86] Persi Diaconis and JW Pitman.  Permutations, record values and random measures.  Unpublished lecture notes, Statistics Department, University of California, Berkeley, 1986.
  * [Fel68] William Feller.  An Introduction to Probability Theory and Its Applications, volume 1.  Wiley, January 1968.  URL: http://www.amazon.ca/exec/obidos/redirect?tag=citeulike04-20{&}path=ASIN/0471257087.
  * [Foa68] Dominique Foata.  On the Netto inversion number of a sequence.  Proc. Amer. Math. Soc., 19:236–240, 1968.  doi:10.2307/2036179.
  * [Foa77] Dominique Foata.  Distributions eulériennes et mahoniennes sur le groupe des permutations.  In Martin Aigner, editor, Higher Combinatorics, pages 27–49, Dordrecht, 1977. Springer Netherlands.  doi:10.1007/978-94-010-1220-1_2.
  * [FS70] Dominique Foata and Marcel Paul Schützenberger.  Théorie Géométrique des Polynômes Eulériens.  Springer Berlin, Heidelberg, 1970.  doi:10.1007/BFb0060799.
  * [Ful98] Jason Fulman.  The distribution of descents in fixed conjugacy classes of the symmetric groups.  J. Combin. Theory Ser. A, 84(2):171–180, 1998.  doi:10.1006/jcta.1998.2893.
  * [FZ90] Dominique Foata and Doron Zeilberger.  Denert’s permutation statistic is indeed Euler-Mahonian.  Stud. Appl. Math., 83(1):31–59, 1990.  doi:10.1002/sapm199083131.
  * [GP22] Christian Gaetz and Laura Pierson.  Positivity of permutation pattern character polynomials, 2022.  doi:10.48550/ARXIV.2204.10633.
  * [GR93] Ira M. Gessel and Christophe Reutenauer.  Counting permutations with given cycle structure and descent set.  Journal of Combinatorial Theory, Series A, 64(2):189–215, 1993\.  doi:10.1016/0097-3165(93)90095-P.
  * [GR20] Christian Gaetz and Christopher Ryba.  Stable characters from permutation patterns.  Selecta Mathematica, 27:1–13, 2020.  doi:https://doi.org/10.1007/s00029-021-00692-9.
  * [Kim19] Gene B. Kim.  Distribution of descents in matchings.  Annals of Combinatorics, 23:73–87, 2019.  doi:10.1007/s00026-019-00414-1.
  * [KL20] Gene B. Kim and Sangchul Lee.  Central limit theorem for descents in conjugacy classes of ${S}_{n}$.  Journal of Combinatorial Theory, Series A, 169:105123, 2020.  doi:10.1016/j.jcta.2019.105123.
  * [Knu98] Donald E. Knuth.  The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching.  Addison Wesley Longman Publishing Co., Inc., USA, 1998.
  * [Mac15] P. MacMahon.  Combinatory analysis.  Cambridge University Press, 1915.
  * [Mac16] P. A. MacMahon.  Two Applications of General Theorems in Combinatory Analysis: (1) To the Theory of Inversions of Permutations; (2) To the Ascertainment of the Numbers of Terms in the Development of a Determinant which has Amongst its Elements an Arbitrary Number of Zeros.  Proc. London Math. Soc. (2), 15:314–321, 1916.  doi:10.1112/plms/s2-15.1.314.
  * [Mac04] Percy A. MacMahon.  Combinatory analysis. Vol. I, II (bound in one volume).  Dover Phoenix Editions. Dover Publications, Inc., Mineola, NY, 2004.  Reprint of ıt An introduction to combinatory analysis (1920) and ıt Combinatory analysis. Vol. I, II (1915, 1916).
  * [Rio14] John Riordan.  An Introduction to Combinatorial Analysis.  Princeton University Press, Princeton, 2014.  doi:doi:10.1515/9781400854332.
  * [Rod39] M. Olinde Rodrigues.  Note sur les inversions, ou dérangements produits dans les permutations.  Journal De Mathématiques Pures et Appliquées, 1839.
  * [Sta97] Richard P. Stanley.  Enumerative Combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1997.  With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.  doi:10.1017/CBO9780511805967.
  * [Sta99] Richard P. Stanley.  Enumerative Combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.  With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.  doi:10.1017/CBO9780511609589.
  * [SW98] John R. Stembridge and Debra J. Waugh.  A Weyl group generating function that ought to be better known.  Indag. Math. (N.S.), 9(3):451–457, 1998.  doi:10.1016/S0019-3577(98)80012-8.
  * [Zab03] Mike Zabrocki.  A bijective proof of an unusual symmetric group generating function, 2003\.  doi:10.48550/ARXIV.MATH/0310301.