%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{8}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{mathtools,latexsym,enumerate,tikz}

\newcommand{\since}[1]{\tag*{\scriptsize{(#1)}}}
\newcommand{\smallfrac}[2]{\textstyle\frac{#1}{#2}\displaystyle}
\newcommand{\Perm}{S}
\newcommand{\Cyc}{C}
\newcommand{\alphacyc}{\alpha^{\text{cyc}}}
\newcommand{\betacyc}{\beta^{\text{cyc}}}
\DeclareMathOperator{\Ecyc}{E^{\text{cyc}}}
\DeclareMathOperator{\mob}{M\ddot{o}b}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\type}{type}
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\ev}{ev}
\DeclareMathOperator{\co}{co}
\newcommand{\PP}{\mathbb{P}}
\DeclareMathOperator{\Alt}{Alt}
\DeclareMathOperator{\alt}{alt}
\newcommand{\gam}{\gamma}
\newcommand{\ee}{\chi}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\card}[1]{{\lvert #1 \rvert}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem*{question}{Question}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}

\everymath{\displaystyle}


%% define your title in the usual way
\title{The number of cycles with a given descent set}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sergi Elizalde\thanks{\href{mailto:sergi.elizalde@dartmouth.edu}{sergi.elizalde@dartmouth.edu}. Partially supported by Simons Foundation grant \#280575.}\addressmark{1} \and Justin M. Troyka\thanks{\href{mailto:jmtroyka@math.dartmouth.edu}{jmtroyka@math.dartmouth.edu}}\addressmark{1}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Dartmouth College, Hanover, NH}

%% put the date of submission here
\received{2017 November 7}

%% leave this blank until submitting a revised version
\revised{2018 March 23}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Using a result of Gessel and Reutenauer, we find a simple formula for the number of cyclic permutations with a given descent set, by expressing it in terms of ordinary descent numbers (i.e., those counting all permutations with a given descent set). We then use this formula to show that, for almost all sets $I \subseteq [n-1]$, the fraction of size-$n$ permutations with descent set $I$ which are $n$-cycles is asymptotically $1/n$. As a special case, we recover a result of Stanley for alternating cycles. We also use our formula to count $n$-cycles with no two consecutive descents.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{permutation, cycle, descent set, enumeration, asymptotic}

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

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{08-Elizalde-Troyka.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

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

\section{Introduction} \label{Introduction}

Two of the most common ways to represent a permutation are its one-line notation, which views the permutation as a word,
and its expression as a product of disjoint cycles, which depicts the algebraic nature of the permutation.
Many known properties of permutations concern one of these two perspectives.
For example, by considering the one-line notation of a permutation, one can study descent sets, pattern avoidance, longest increasing subsequences, etc.
On the other hand, by viewing a permutation as a product of cycles, one can study its number of fixed points, its number of cycles, whether it is an involution, etc.

However, the interplay between these two depictions of permutations is far from being understood. 
We are particularly interested in how the cycle structure of a permutation (with a focus on permutations that consist of one cycle) and its decent set relate.
The first major breakthrough in this area is the seminal paper of Gessel and Reutenauer~\cite{GR}, which expresses the number of permutations with a given cycle structure and descent set as an inner product of symmetric functions. %Their proof uses a bijection involving multisets of necklaces.
For the special case of cyclic permutations (sometimes called {\em
cycles} or {\em $n$-cycles}), an unexpected property of the distribution
of descent sets was later given in~\cite{Elizalde}, showing that descent
sets of $n$-cycles, when restricted to the first $n-1$ entries, have the
same distribution as descent sets of permutations of length $n-1$. Around
the same time, using results from~\cite{GR}, Stanley gave a formula for
the number of cycles which are alternating~\cite{StanleySurvey}. He used
it to show that, on a random permutation, the events ``being a cycle''
and ``being alternating'' are independent, in a precise sense that will be discussed later.

After introducing some notation and background in Section~\ref{NotationSection}, we present our main theorem in Section~\ref{MainTheoremSection}. 
It gives four equivalent formulas relating the enumeration of cyclic permutations with a given descent set and the enumeration of all permutations with a given descent set, the latter being a well-understood problem. In Section~\ref{sec:consequences} we discuss some consequences of our main theorem, including the result from~\cite{Elizalde} mentioned above, and Stanley's formula counting alternating cycles, as well as some extensions of it. In Section~\ref{AsymptoticSection} we study the asymptotic implications of our main theorem, generalizing Stanley's observation about the independence of being cyclic and being alternating, and conjecturing that it can be even further generalized.

The last section of the paper relates to pattern avoidance. The first significant result about the interaction of pattern avoidance and cycle structure of permutations is due to Robertson, Saracino and Zeilberger~\cite{RSZ},  who showed that the number of fixed points has the same distribution on permutations avoiding two different patterns of length~3. 
At the conference Permutation Patterns 2010, Stanley proposed the problem of enumerating cyclic permutations that avoid a given pattern of length $3$. While this problem remains unsolved, cyclic permutations avoiding some specific sets of patterns 
have been enumerated by Archer and Elizalde~\cite{ArcEli}, and permutations with restrictions that involve both their one-line notation and their cycle structure are counted in~\cite{Elicont} using continued fractions. 

In Section~\ref{sec:monotone} we consider a related problem, namely that of counting cycles that avoid a monotone {\em consecutive} pattern.  
%In Section~\ref{sec:monotone} we consider the problem of counting cycles that avoid a monotone consecutive pattern.  
Avoiding a monotone consecutive pattern of length $k$ is equivalent to not having $k-1$ consecutive ascents (or descents).
In general, consecutive patterns differ from classical patterns by adding the requirement that the entries in an occurrence of the pattern have to be adjacent; see~\cite{Eli_survey} for a survey of the literature in the subject. We use symmetric functions, along with our main theorem, to give an explicit formula counting permutations avoiding the consecutive pattern $\underline{123}$ or $\underline{321}$.

The proofs that have been omitted in this extended abstract due to space constraints can be found in the full version of the paper~\cite{EliTro}.

\section{Notation and definitions} \label{NotationSection}

Let $n\ge1$, and let $\Perm_n$ denote the symmetric group on $[n]=\{1,2,\dots,n\}$. For a permutation  $\pi \in \Perm_n$, let $\type(\pi)$ denote the cycle type of $\pi$, that is, the partition of $n$ whose parts are the lengths of the cycles of $\pi$.
Let $D(\pi) \subseteq [n-1]$ denote the descent set of $\pi$, that is,
\[ D(\pi) = \{i \colon \pi(i) > \pi(i+1)\}. \]
Let $\Cyc_n$ denote the set of permutations in $\Perm_n$ whose cycle type is $(n)$. We call the elements of $\Cyc_n$ {\em cyclic permutations}, {\em $n$-cycles}, or simply {\em cycles}.
\begin{defn} For $I \subseteq [n-1]$, let
\[ \begin{matrix}
\alpha_n(I) = \#\{\pi \in \Perm_n \colon D(\pi) \subseteq I\}; \quad & \alphacyc_n(I) = \#\{\pi \in \Cyc_n \colon D(\pi) \subseteq I\}; \\
\beta_n(I) = \#\{\pi \in \Perm_n \colon D(\pi) = I\}; \quad & \betacyc_n(I) = \#\{\pi \in \Cyc_n \colon D(\pi) = I\}.
\end{matrix}\]
\end{defn}
The numbers $\alpha_n(I)$ and $\beta_n(I)$ are well-understood and easy
to compute; see \cite[Section 1.4 \& Example 2.2.4]{Stanley1}.

We use $\mob$ to denote the M\"obius function from number theory. For $I$ a set of integers and $n\ge1$, define $(I,n) = \text{gcd}(I \cup \{n\})$; and for integer $d \ge 1$, define $I/d = \{i/d \colon \text{$i \in I$ and $d\mid i$}\}$.

Given a subset $I \subseteq [n-1]$, let $\co(I)$ denote the associated composition of $n$; that is, if $I = \{i_1 < i_2 < \cdots < i_{k-1}\}$, then $\co(I) = (i_1, i_2 - i_1, i_3 - i_2, \ldots, i_{k-1} - i_{k-2}, n - i_{k-1})$. If $\mu = (\mu_1, \ldots, \mu_k)$ is a composition and $d \mid \mu_j$ for each $j$, then define $\mu/d = (\mu_1/d, \ldots, \mu_k/d)$.

\begin{defn} \label{lyndon} Let $w$ be a (finite) non-empty word on alphabet $\{1, 2, \ldots\}$. We say $w$ is a \textit{primitive word} if $w$ is not equal to any of its non-trivial cyclic shifts: that is, if $w = uv$ with $u$ and $v$ non-empty then $w \not= vu$. We say $w$ is a \textit{Lyndon word} if $w$ is strictly less than all of its non-trivial cyclic shifts in the lexicographic order: that is, if $w = uv$ with $u$ and $v$ non-empty, then $w < vu$ in the lexicographic order.
\end{defn}

Note that every Lyndon word is primitive, and every primitive word has
exactly one cyclic shift that is a Lyndon word. It is well-known (see
\cite[Theorem 5.1.5]{L} or \cite[Exercise 7.89.d]{Stanley2}) that every word has a unique factorization into a weakly decreasing (in the lexicographic order) sequence of Lyndon words: that is, for every word $w$ there is a unique sequence of Lyndon words $u_1 \ge u_2 \ge \cdots \ge u_k$ such that $w = u_1u_2\dots u_k$.

\begin{defn} \label{type} Given a word $w$ whose factorization into Lyndon words is $w = u_1u_2\dots u_k$, the \textit{type} of $w$, denoted $\type(w)$, is the partition whose parts are equal to the lengths of the Lyndon words $u_1, u_2, \ldots, u_k$, arranged in order of weakly decreasing length. The \textit{evaluation} of $w$ is the weak composition $\ev(w) = (\mu_1, \mu_2,\ldots)$ such that $\mu_j$ is the number of $j$'s in $w$. The \textit{period} of $w$, denoted $\per(w)$, is the length of the shortest word $v$ such that $w = v^r$ for some $r$.
\end{defn}

Let $x^\mu$ denote the monomial $x_1^{\mu_1}x_2^{\mu_2}\cdots$. Given a partition $\lambda$, let $L_\lambda$ denote the symmetric function
\begin{equation}\label{eq:Ldef} L_\lambda = \sum_{\type(w) = \lambda} x^{\ev(w)}, \end{equation}
where the sum is over all words $w$ with type $\lambda$. We will write
$L_n$ instead of $L_{(n)}$. It is well-known (see for instance
\cite[Equation (2.2)]{GR}, \cite[Exercise 7.89.a]{Stanley2} or \cite[Theorem 7.2]{Reutenauer}) that
\[ L_n = \frac{1}{n} \sum_{\text{$d \mid n$}} \mob(d)\,p_d^{n/d}, \]
where $p_d = x_1^d + x_2^d + \cdots$, the power-sum symmetric function.

Given a partition $\lambda$ and a weak composition $\mu = (\mu_1, \mu_2, \ldots)$, let $a_{\lambda,\mu}$ denote the number of words of type $\lambda$ and evaluation $\mu$. We will write $a_{n,\mu}$ instead of $a_{(n),\mu}$. By definition,
\begin{equation}\label{eq:L} 
L_\lambda = \sum_\mu a_{\lambda,\mu} x^\mu,
\end{equation}
where the sum is over all weak compositions $\mu$. 

Recall that the multinomial coefficient $\binom{n}{\mu}$ denotes the total number of length-$n$ words with evaluation $\mu$. The following result is well-known.

\begin{lem}[{\cite[Proposition 1.4.1]{Stanley1}}] \label{lem:multi}
$$\alpha_n(I) = \binom{n}{\mu}.$$
\end{lem}

The proof of our main theorem, in Section \ref{MainTheoremSection}, uses the following important result of Gessel and Reutenauer \cite{GR}.

\begin{thm}[{\cite[Corollary 2.2]{GR}}] \label{GRcor}
Let $\mu = \co(I)$. The number of $\pi \in \Perm_n$ with $\type(\pi) = \lambda$ and $D(\pi) \subseteq I$ is equal to $a_{\lambda,\mu}$.
%, which is also the coefficient of $x^\mu$ in $L_\lambda$.
In particular, $\alphacyc_n(I) = a_{n,\mu}$, the number of Lyndon words with evaluation $\co(I)$.
%, which is also the coefficient of $x^\mu$ in $L_n$.
\end{thm}

By Equation~\eqref{eq:L}, $a_{n,\mu}$ is the coefficient of $x^\mu$ in $L_n$.
Note that Gessel and Reutenauer \cite{GR} state their results not in terms of words and Lyndon words, but in terms of primitive necklaces and multisets of primitive necklaces.


\section{The main theorem} \label{MainTheoremSection}

Our main result is a relation between the number of permutations with a given descent set and the number of cycles with a given descent set, expressed in four equivalent identities.

\begin{thm} \label{maintheorem}
Let $I \subseteq [n-1]$, and recall the notation $(I,n) = \gcd(I \cup \{n\})$ and $I/d = \{i/d \colon \text{$i \in I$ and $d \mid i$}\}$. We have
\begin{itemize}
\item[(a)] $\alpha_n(I) = \sum_{\text{$d\mid(I,n)$}} \frac{n}{d}\, \alphacyc_{n/d}(I/d)$;
\item[(b)] $\alphacyc_n(I) = \frac{1}{n}\sum_{\text{$d\mid(I,n)$}} \mob(d)\,\alpha_{n/d}(I/d)$;
\item[(c)] $\betacyc_n(I) = \frac{1}{n} \sum_{\text{$d\mid n$}} \mob(d)\,(-1)^{|I|-|I/d|}\beta_{n/d}(I/d)$;
\item[(d)] $\beta_n(I) = \sum_{\text{$d\mid n$}} (-1)^{|I|-|I/d|}\,\frac{n}{d}\,\betacyc_{n/d}(I/d)$.
\end{itemize}
\end{thm}

We show in~\cite{EliTro} that these four formulas are equivalent, by way of M\"obius Inversion and the Principle of Inclusion--Exclusion. We present independent proofs of (a) and (b).

\begin{proof}[Proof of Theorem \ref{maintheorem}(a).] Let $\mu = \co(I)$, and recall from Lemma~\ref{lem:multi} that $\alpha_n(I)$ equals the number of length-$n$ words with evaluation $\mu$.

Let $m = (I,n)$, and note that $m = \gcd(\mu_1,\mu_2,\ldots)$. In particular, if there is a word $w$ with $\ev(w) = \mu$ and $\per(w) = n/d$, then we must have $d \mid m$. We have
\begin{align*}
\alpha_n(I) = \binom{n}{\mu} &= \sum_{\text{$d \mid m$}} \#\{\text{words $w$ with $|w| = n$ and $\ev(w) = \mu$ and $\per(w) = n/d$}\} \\
&= \sum_{\text{$d \mid m$}} \#\{\text{primitive words $u$ with $|u| = n/d$ and $\ev(u) = \mu/d$}\} \\
&= \sum_{\text{$d \mid m$}} \frac{n}{d} \cdot \#\{\text{Lyndon words $u$ with $|u| = n/d$ and $\ev(u) = \mu/d$}\} \\
&= \sum_{\text{$d \mid m$}} \frac{n}{d}\, a_{n/d,\mu/d}.
\end{align*}
We have $\co(I/d) = \mu/d$, so by Theorem \ref{GRcor}, $a_{n/d,\mu/d} = \alphacyc_{n/d}(I/d)$, from where the result follows.\end{proof}

Our direct proof of (b) uses the machinery of symmetric functions introduced in Section \ref{NotationSection}.

\begin{proof}[Proof of Theorem \ref{maintheorem}(b).] Let $\mu = \co(I)$. For a symmetric function $f$, let $[x^\mu] f$ denote the coefficient of $x^\mu$ in $f$. By Theorem \ref{GRcor},
\[ \alphacyc_n(I) = [x^\mu]L_n = \frac{1}{n}\sum_{\text{$d \mid n$}} \mob(d)\, [x^\mu]p_d^{n/d}. \]
Let $m = (I,n) = \gcd(\mu_1,\mu_2,\ldots)$. Since $p_d^{n/d} = {\left(x_1^d + x_2^d + \cdots\right)}^{n/d}$, the expression $p_d^{n/d}$ is a series in $x_1^d, x_2^d, \ldots$, so $[x^\mu]p_d^{n/d}$ is zero if $m$ is not divisible by $d$. On the other hand, if $m$ is divisible by $d$, then we can make the substitution $z_i = x_i^d$, and we obtain
\[ [x^\mu]p_d^{n/d} = [z^{\mu/d}]{\left(z_1 + z_2 + \cdots\right)}^{n/d} = \binom{n/d}{\mu/d}. \]
Therefore,
\[ \alphacyc_n(I) = \frac{1}{n}\sum_{\text{$d\mid m$}} \mob(d)\,\binom{n/d}{\mu/d}. \]
We have $\co(I/d) = \mu/d$, and so $\binom{n/d}{\mu/d} = \alpha_{n/d}(I/d)$.
\end{proof}


\section{Consequences of the main theorem}\label{sec:consequences}

In this section we study some special cases of Theorem~\ref{maintheorem}, and use them to recover a few results in the literature.

%\subsection{Simple special cases}

\begin{cor} \label{cor1} Let $I \subseteq [n-1]$.
\begin{itemize}
\item[(a)] If $(I,n) = 1$, then $\alpha_n(I) = n\,\alphacyc_n(I)$. 
\item[(b)] If $\gcd(i,n) = 1$ for all $i \in I$, then $\beta_n(I) = n\,\betacyc_n(I) + (-1)^{|I|}$.
\end{itemize}
\end{cor}

Corollary \ref{cor1}(b) shows that, when $I$ meets the given condition, $\betacyc_n(I)$ is very close to $\smallfrac1n \beta_n(I)$. In Section \ref{sec:special}, we will see that a similar phenomenon holds for almost all sets $I$.

As a special case of Theorem \ref{maintheorem}(c), we recover the
following result of Elizalde \cite{Elizalde} relating descents sets on
$\Cyc_n$ and $\Perm_{n-1}$. Two proofs are presented in~\cite{Elizalde}:
one is bijective, and the other uses Theorem~\ref{GRcor} and inclusion--exclusion.

\begin{cor}[{\cite[Corollary 4.1]{Elizalde}}] \label{CorSergi} 
For $I \subseteq [n-2]$,
\[ \#\{\pi \in \Cyc_n \colon D(\pi) \cap [n-2] = I\} = \beta_{n-1}(I). \]
Equivalently, $\betacyc_n(I) + \betacyc_n(I \cup \{n-1\}) = \beta_{n-1}(I)$.
\end{cor}

For $I \subseteq [n-1]$, let $\overline{I} = [n-1] \smallsetminus I$
denote its complement. It follows from \cite[Theorem 4.1]{GR} that $\betacyc_n(\overline{I}) = \betacyc_n(I)$ when $n \not\equiv 2\bmod 4$. The following proposition is a full description of the case where $n \equiv 2\bmod 4$. Recall that $I/2 = \{i/2 \colon \text{$i \in I$ and $i$ is even}\}$. Note that, for $n \equiv 2\bmod 4$, exactly one of $I$ or $\overline{I}$ has an odd number of odd elements.

\begin{prop} \label{complement} If $n \equiv 2\bmod 4$ and $I \subseteq [n-1]$ has an odd number of odd elements, then $\betacyc_n(I) - \betacyc_n(\overline{I}) = \betacyc_{n/2}(I/2)$.
\end{prop}

\begin{cor} \label{complementcor} Let $n \equiv 2\bmod 4$, and $I \subseteq [n-1]$. We have
\begin{enumerate}[(a)]
\item $\betacyc_n(I) \ge \betacyc_n(\overline{I})$ if $I$ has an odd number of odd elements;
\item $\betacyc_n(I) = \betacyc_n(\overline{I})$ if and only if one of $I$ and $\overline{I}$ has no even elements.
\end{enumerate}
\end{cor}


\subsection{Cycles with descent set $\{k, 2k, 3k, \ldots\}$} \label{sec:Stanley}

In this section we recover a result of Stanley as a special case of our main theorem. We also derive a generalized version of Stanley's result.

Let $E_n$ denote the $n$th Euler number, \textit{i.e.}\ $E_n = \beta_n(2\mathbb{Z} \cap [n-1])$, the number of alternating (up--down) permutations in $\Perm_n$.

\begin{cor}[{\cite[Theorem 5.3]{StanleyAlt}}]\label{alternating} The number of alternating cycles in $\Cyc_n$ is
$$\betacyc_n(2\mathbb{Z} \cap [n-1])=\begin{cases}
\frac{1}{n}\sum_{\text{$d \mid n$}} \mob(d)\,(-1)^{(d-1)/2}\,E_{n/d}, & \text{if $n$ is odd;}\\
\frac{1}{n}\sum_{\substack{\text{$d \mid n$}\\\text{$d$ odd}}} \mob(d)\,E_{n/d}, & \text{if $n$ is even but not a power of 2;}\\
\frac{1}{n}\left(E_n - 1\right), & \text{if $n \ge 2$ is a power of $2$.}
\end{cases}$$
\end{cor}

The analogous result for down--up permutations, \textit{i.e.}\ those with
descent set $[n-1] \cap \{1, 3, 5, \ldots\}$, can be proved similarly.
This result also appears in \cite[Theorem 5.3]{StanleyAlt}.

We can extend Corollary~\ref{alternating} from alternating permutations to permutations with descent set $\{k, 2k, 3k, \ldots\}$ for any $k$. Let $E_n^{(k)}$ denote the generalized Euler numbers, \textit{i.e.}\ $E_n^{(k)} = \beta_n(k\mathbb{Z} \cap [n-1])$, which is the number of permutations with descent set $k\mathbb{Z} \cap [n-1]$.

\begin{thm} \label{generalized}
The number of cycles with descent set $k\mathbb{Z} \cap [n-1]$ is given by
\[ \betacyc_n(k\mathbb{Z} \cap [n-1]) = \frac{1}{n}\sum_{\text{$d \mid n$}} \mob(d) \, (-1)^{\left\lfloor\frac{n-1}{k}\right\rfloor - \left\lfloor\frac{n-d}{\lcm(k,d)}\right\rfloor} \, E_{n/d}^{\left(\frac{k}{\gcd(k,d)}\right)}. \]
\end{thm}

It is worth considering the special case where $k$ is an odd prime.

\begin{cor} \label{gencor2}
Let $p$ be an odd prime. Then
$$\betacyc_n(p\mathbb{Z} \cap [n-1]) = \begin{cases}
\frac{1}{n}\sum_{\text{$d \mid n$}} \mob(d)\, (-1)^{\left\lfloor\frac{n-1}{p}\right\rfloor - \left\lfloor\frac{n-d}{pd}\right\rfloor}\, E_{n/d}^{(p)}, & \text{if $p \nmid n$;}\\
\frac{1}{n}\sum_{\text{$d \mid m$}} \mob(d)\,(-1)^{\frac{n(d-1)}{d}}\,E_{n/d}^{(p)}, & {\text{if $n = m p^a$ with $a\ge1$,}\atop\text{$p\nmid m$ and $m > 2$;}}\\
\frac{1}{n}\left(E_n^{(p)} + E_{n/2}^{(p)} - 2\right), & \text{if $n = 2p^a$ with $a\ge1$;} \medskip \\
\frac{1}{n}\left(E_n^{(p)} - 1\right), & \text{if $n = p^a$ with $a\ge1$.}
\end{cases}$$
\end{cor}

\section{Asymptotic results} \label{AsymptoticSection}

In this section we use the notation $f(n)\sim g(n)$ to mean $\lim_{n\to\infty} g(n)/f(n)=1$, and $f(n)\gg g(n)$ to mean $\lim_{n\to\infty} g(n)/f(n)=0$.

\subsection{Questions about asymptotic independence}\label{sec:independence}

In \cite[Section 5]{StanleySurvey}, Stanley describes the following consequence of his result expressed in Corollary \ref{alternating} above:
\begin{quote}``\ldots as $n \to \infty$, a fraction $1/n$ of the
alternating permutations are $n$-cycles. Compare this with the simple
fact that (exactly) $1/n$ of the permutations $w \in \Perm_n$ are
$n$-cycles. We can say that the properties of being an alternating
permutation and an $n$-cycle are `asymptotically independent.' What other
classes of permutations are asymptotically independent from the
alternating permutations?''\end{quote}

Considering that alternating permutations are those with descent set $2\ZZ\cap[n-1]$, here we ask the following related question.
\begin{question} For what other sets $I \subseteq [n-1]$ are the properties of having descent set $I$ and being an $n$-cycle asymptotically independent?
\end{question} 

To make this asymptotic question precise, one has to define the sets $I \subseteq [n-1]$ for arbitrary values of $n$. We conjecture that, in fact, as long as each $I$ is a non-empty proper subset of $[n-1]$, we asymptotically have $\frac{\betacyc_n(I)}{\beta_n(I)} \sim \frac{1}{n}$, and so the two above properties are independent in a very strong sense:

\begin{conj} \label{Conjecture} $$\lim_{n\to\infty}\max_{\varnothing \subsetneqq I \subsetneqq [n-1]} \left| \frac{n\, \betacyc_n(I)}{\beta_n(I)} - 1\right| = 0.$$
\end{conj}

We first use our main theorem to prove that an analogous relationship between $\alphacyc_n(I)$ and $\alpha_n(I)$ holds.

\begin{thm} \label{AlphaTheorem} $$\lim_{n\to\infty}\max_{\varnothing \subsetneqq I \subseteq [n-1]} \left| \frac{n\, \alphacyc_n(I)}{\alpha_n(I)} - 1\right| = 0.$$
\end{thm}

\begin{proof}
Let $I$ be a non-empty subset of $[n-1]$, let $\mu = \co(I)$, and let $m = \text{gcd}(I \cup \{n\})$. By Theorem~\ref{maintheorem}(b), 
\begin{align*}
\left| \frac{n\, \alphacyc_n(I)}{\alpha_n(I)} - 1\right| = \left| \sum_{\text{$d \mid m$}} \frac{\mob(d)\,\alpha_{n/d}(I/d)}{\alpha_n(I)} - 1\right| 
%= \left| \sum_{\substack{\text{$d \mid m$}\\d\not=1}} \frac{\mob(d)\,\alpha_{n/d}(I/d)}{\alpha_n(I)}\right| 
\le \sum_{\substack{\text{$d \mid m$}\\d\not=1}} \frac{\alpha_{n/d}(I/d)}{\alpha_n(I)} = \sum_{\substack{\text{$d \mid m$}\\d\not=1}} \frac{\binom{n/d}{\mu/d}}{ \binom{n}{\mu}}.
\end{align*}
Among the $\binom{n}{\mu}$ words with evaluation $\mu$, $\binom{n/d}{\mu/d}^d$ is the number of those of the form $w_1 \dots w_d$ where each $w_i$ is a word with evaluation $\mu/d$. Thus, $\binom{n/d}{\mu/d} \le \binom{n}{\mu}^{1/d}$, and
$$\left| \frac{n\, \alphacyc_n(I)}{\alpha_n(I)} - 1\right| \le \sum_{\substack{\text{$d \mid m$}\\d\not=1}} \binom{n}{\mu}^{1/d-1} \le \sum_{\substack{\text{$d \mid m$}\\d\not=1}} \binom{n}{\mu}^{-1/2} \le d(n)\,\binom{n}{\mu}^{-1/2}\le d(n)\,n^{-1/2},
$$
where $d(n)$ denotes the number of divisors of $n$.
The proof is completed by the fact that $\lim_{n\to\infty} d(n)\,n^{-1/2}
= 0$, which is shown in~\cite[Section 13.10]{Apostol}.
\end{proof}

In Section~\ref{sec:special} we state two theorems that are special cases of Conjecture~\ref{Conjecture}. 
Just as it follows immediately from Corollary \ref{alternating} that the fraction of alternating permutations that are cycles asymptotically approaches $1/n$, it will follow (not immediately) from Theorem \ref{maintheorem}(c) that, among permutations with almost any given descent set, the fraction of those that are cycles asymptotically approaches $1/n$.

\subsection{Asymptotic independence in special cases} \label{sec:special}

We first prove Conjecture~\ref{Conjecture} in the case where the descent set is periodic. Let $\PP$ denote the set of positive integers. For $\ell \ge 1$, say $I \subseteq \PP$ is \emph{$\ell$-periodic} if, for each $i \in \PP$, we have $i \in I$ if and only if $i+\ell \in I$.

\begin{thm} \label{thm:periodic2} Fix $k \ge 2$, and define
\[ \mathcal{I}_n = \{ I \cap [n-1]  \colon \varnothing\subsetneqq I \subsetneqq \PP \text{ and $I$ is $\ell$-periodic for some $\ell$ with $1 \le \ell \le k$}\}. \]
Then $\lim_{n\to\infty} \max_{I \in \mathcal{I}_n} \left|\frac{n\,\betacyc_n(I)}{\beta_n(I)} - 1\right| = 0$.
\end{thm}

Our main tool in proving this is a result of Bender, Helton and Richmond
\cite[Theorems 1 \& 2]{BHR} which describes the asymptotic growth of $\beta_n(I \cap [n-1])$ when $I$ is periodic.

Since the set $I=2\ZZ$ is 2-periodic, Theorem~\ref{thm:periodic2} applies in particular to alternating permutations, and so it generalizes the observation of Stanley quoted in Section~\ref{sec:independence}.

We conclude this section with another special case of Conjecture~\ref{Conjecture}.

\begin{defn} \label{alternation} The \emph{alternation set} of $I \subseteq [n-1]$ is 
$$\Alt(I)=\{i\in[n-2]\colon|I\cap\{i,i+1\}|=1\},$$ 
that is, the set of $i \in [n-2]$ such that exactly one of $i$ and $i+1$ is in $I$. The \emph{alternation number} of $I$ is $\alt(I) = \card{\Alt(I)}$.
\end{defn}

Note that a given subset of $[n-2]$ is equal to $\Alt(I)$ for exactly two sets $I \subseteq [n-1]$, which are complements of each other. Note also that, for $\Alt(I)$ to be well-defined, we need to specify $n$. The value of $n$ will always be clear from context.

\begin{thm} \label{TheBigOne}
Let $\varepsilon > 0$. For each $n$, define
\[ \mathcal{I}_n = \{I \subseteq [n-1] \colon \alt(I) > n/2 - n^{1-\varepsilon}\}. \]
Then $\lim_{n\to\infty} \max_{I \in \mathcal{I}_n} \left|\frac{n\,\betacyc_n(I)}{\beta_n(I)} - 1\right| = 0$.
\end{thm}

Observe that, for a uniformly random subset of $[n-1]$, the expected alternation number is $n/2-1$. While $n/2 - n^{1-\varepsilon}$ is less than this expected value (assuming $0 < \varepsilon < 1$), it is asymptotically the same. Thus the sets in $\mathcal{I}_n$ can be thought of as sets whose alternation number is at least average or a little bit less than average. The proof of the theorem builds on the work of Ehrenborg and Mahajan~\cite{EM}.

Theorem~\ref{TheBigOne} shows that, for subsets $I \subseteq [n-1]$ with $\alt(I)>n/2 - n^{1-\varepsilon}$, the properties of having descent set $I$ and being an $n$-cycle are asymptotically independent. Since $2\ZZ\cap[n-1]$ has alternation number $n-2$, this result applies to alternating permutations, thus generalizing the observation of Stanley quoted in Section~\ref{sec:independence}.

Taking $\varepsilon \in \left(0, \smallfrac12\right)$ in Theorem~\ref{TheBigOne}, we can derive the following result, which shows that $\frac{\betacyc_n(I)}{\beta_n(I)} \sim \frac{1}{n}$ for almost all $I \subseteq [n-1]$ in a precise sense.

\begin{cor} \label{AlmostAll} For each $n$, there is a collection $\mathcal{I}_n$ of subsets of $[n-1]$ such that $\left|\mathcal{I}_n\right|\sim 2^{n-1}$ and $\lim_{n\to\infty} \max_{I \in \mathcal{I}_n} \left|\frac{n\,\betacyc_n(I)}{\beta_n(I)} - 1\right| = 0$.
\end{cor}

\section{Cycles avoiding $\underline{123}$ or $\underline{321}$} \label{sec:monotone}

We say a permutation \emph{avoids the consecutive pattern} $\underline{123}$ (resp.\ $\underline{321}$) if it does not have two consecutive ascents (resp.\ descents). 
Consecutive patterns in permutations were introduced in~\cite{EliNoy}; see also the recent survey~\cite{Eli_survey}. In this section we give formulas counting cycles that avoid $\underline{123}$ and cycles that avoid $\underline{321}$. The analogous problem for classical patterns, that is, without the adjacency requirement, was proposed by Stanley in 2010 and remains open; see~\cite{ArcEli,Elicont} for partial progress in this direction.

Let $\gam_n$ denote the number of permutations in $\Perm_n$ avoiding
$\underline{123}$, and let $\gam_n^*$ denote the number of permutations
in $\Perm_n$ avoiding $\underline{321}$ that begin and end with an
ascent. A generating function for $\gam_n$ was previously given in
\cite{EliNoy}, and similar methods can easily be applied to $\gamma^*$.
In addition, formulas for $\gam_n$ and $\gam_n^*$ can be obtained using
\cite[Section 5.2, Examples 3 \& 4]{GesselThesis}.

We use Theorem \ref{maintheorem} to find formulas for the number of cycles avoiding $\underline{123}$ or avoiding $\underline{321}$, in terms of the numbers $\gam_n$ and $\gam_n^*$.

\begin{thm} \label{avoid123} Define
\[ \theta(n) = \begin{cases}
1 & \text{if $n = 3^a$ with $a \ge 1$}; \\
-2 & \text{if $n = 2 \cdot 3^a$ with $a \ge 1$}; \\
0 & \text{else}.
\end{cases} \]
Then the number of $n$-cycles that avoid $\underline{123}$ is
\[ \frac{1}{n} \left[ \theta(n) + \sum_{\mathclap{\substack{\text{$d \mid n$}\\ \text{$d \equiv 1\bmod 3$}}}} \mob(d)\, \gam_{n/d} + \sum_{\mathclap{\substack{\text{$d \mid n$}\\ \text{$d \equiv 2\bmod 3$}}}} \mob(d)\, (-1)^{n/d}\, \gam_{n/d}^*\right]. \]
\end{thm}

By symmetry, $\gamma_n$ also equals the number of permutations in $\Perm_n$ avoiding $\underline{321}$, and $\gamma_n^*$ also equals the number of permutations in $\Perm_n$ avoiding $\underline{123}$ that begin and end with a descent. We now give an analogous formula for the number of $n$-cycles that avoid $\underline{321}$. 
By the remarks preceding Proposition \ref{complement}, this is equal to the number of $n$-cycles that avoid $\underline{123}$ if $n \not\equiv 2\bmod 4$.

\begin{thm} \label{avoid321} Define
\[ \widetilde{\theta}(n) = \begin{cases}
1 & \text{if $n = 3^a$ with $a \ge 1$}; \\
0 & \text{else}.
\end{cases} \]
Then the number of $n$-cycles that avoid $\underline{321}$ is
\[ \frac{1}{n} \left[ \widetilde{\theta}(n) \,+\, \sum_{\mathclap{\substack{\text{$d \mid n$}\\ \text{$d \equiv 1\bmod 3$}}}} \mob(d)\,(-1)^{(d-1)n/d}\, \gam_{n/d} \,+\, (-1)^n \sum_{\mathclap{\substack{\text{$d \mid n$}\\ \text{$d \equiv 2\bmod 3$}}}} \mob(d)\, \gam_{n/d}^*\right]. \]
\end{thm}

In proving Theorems \ref{avoid123} and \ref{avoid321}, we rely on the
machinery of symmetric functions provided by Gessel and Reutenauer
\cite{GR}, as well as symmetric-function identities from Gessel's PhD
thesis \cite[Section 2, Examples 3 \& 4]{GesselThesis}.

Unfortunately, our proof techniques for Theorems \ref{avoid123} and \ref{avoid321} do not easily generalize to the case of permutations avoiding  $\underline{1\dots k}$ or $\underline{k\dots 1}$ for $k \ge 4$. 


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
