<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\vskip .2 in

\begin{center}
\vskip 1cm{\LARGE\bf
A Note on a Permutation Statistic \\
}
\vskip 1cm
\large
Tam\'as Lengyel\\
Occidental College\\
1600 Campus Road \\
Los Angeles, CA 90041 \\
USA\\
\href{mailto:lengyel@oxy.edu}{\tt lengyel@oxy.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
We study the length of the initial up-down
 alternating segment of a permutation of $[n]$ selected uniformly at random. It turns out that as $n$ tends to infinity, the expected value and the standard deviation of this statistic converge to small constants.
\end{abstract}


\section{Introduction}\label{sec:1}
Analyzing properties of permutation statistics is a popular subject in combinatorics, cf.\ B\'ona \cite{Bona}.
There has been much recent work on determining and statistically analyzing the length of the longest increasing and alternating subsequences of random permutations, cf.\ Stanley \cite{Stanley}.  A permutation $a_1 a_2 \cdots a_n$ of $[n]$ is up-down
alternating if $a_1&lt;a_2&gt;a_3&lt;a_4&gt;\cdots a_n$. Let $A_n$ denote the number of
up-down alternating permutations of $[n]=$ $\{1,2,\dots,n\}$. Andr\'{e} studied these numbers and established their relations to Euler and tangent numbers, 
cf.\ Comtet  \cite[pp.\ 258--259]{Comtet}. It is well known
that
$2A_{n+1}=\sum_{k=0}^n {n\choose k} A_k A_{n-k}$ for $n\ge 1$ with $A_0=A_1=1$. The first few terms of this sequence are
\[
1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, \ldots,
\]
cf.\ \seqnum{A000111} in the {\it On-Line Encyclopedia of Integer Sequences}.
For their exponential generating function we have the remarkable exponential generating function identity
\begin{equation}
\label{eq:egf}
A(x)=\sum_{k=0}^\infty \frac{A_k}{k!}x^k=\sec(x)+\tan(x),\end{equation} cf.\ Comtet \cite{Comtet}.
The convergence radius easily follows as well as
\begin{equation}
\label{eq:sim}
A_n/n!\sim 2\left(\frac{2}{\pi}\right)^{n+1}
\end{equation}
as $n\to\infty$, cf.\ Borwein et al.~\cite{BBD}.

We are interested in the \emph{initial} up-down alternating segments of the permutations.
Let $X_n$ denote the length of the initial up-down
alternating sequence of a permutation of $[n]$ selected uniformly at random, i.e., we set $X_n=n$ for an up-down alternating permutation, and otherwise, $X_n=2k$ or $X_n=2k+1$ if $a_1&lt;a_2&gt;a_3&lt;\cdots &gt;a_{2k-1}&lt;a_{2k}&lt;a_{2k+1}$  or $a_1&lt;a_2&gt;a_3&lt;\cdots &lt;a_{2k}&gt;a_{2k+1}&gt;a_{2k+2}$, respectively.
Clearly, $1\le X_n\le n$ and $X_n=n$ exactly if the permutation is up-down alternating.
The random variable $X_n$  has some surprising properties.
We will see in Theorems~\ref{th:exp} and \ref{th:stdev} that the expected value and standard deviation of $X_n$ depends only very slightly on $n$
and the limits of these moments are small constants. Theorem~\ref{th:approx} shows that for a large $n$ the probability $P(X_n=k)$ decreases exponentially as $k$ grows while Corollary~\ref{cor:cor} confirms that $P(X_n=k)$ becomes constant for $n&gt;k$.





\section{Main results}
\begin{theorem}
\label{th:exp} For $1\le k\le n-1$ we have that
\begin{equation}
\label{eq:exact}
P(X_n= k)=P(X_n\ge k)-P(X_n\ge k+1)=\frac{A_k}{k!}-\frac{A_{k+1}}{(k+1)!},
\end{equation}
\[EX_n=\sum_{k=1}^n \frac{A_k}{k!},\]
and $\lim_{n\to\infty} EX_n=\sec(1)+\tan(1)-1
\approx 2.40822$.
\end{theorem}





\begin{proof}
We use the fact that for any positive integer valued random variable $X_n$
\begin{equation}
\label{eq:greater}
EX_n=\sum_{k=1}^\infty P(X_n\ge k).
\end{equation}
We observe that $P(X_n=n)=A_n/n!$. On the other hand, determining $P(X_n=k)$ for other values of $k$ seems complicated, however, as it turns out, calculating $P(X_n\ge k)$ for $1\le k\le n-1$ is fairly simple:
\begin{equation}
\label{eq:diff}
P(X_n\ge k)=\frac{{n\choose k}A_k (n-k)!}{n!}=\frac{A_k}{k!},
\end{equation}
since we can pick $k$ elements for the initial segment in ${n\choose k}$ ways and place them in
up-down alternating order in $A_k$ ways, while the other $n-k$ elements can be put in arbitrary order.
Identity \eqref{eq:diff} also holds for $k=n$.
Now \eqref{eq:diff} and \eqref{eq:greater} imply identities \eqref{eq:exact} and
\[EX_n=\sum_{k=1}^n \frac{A_k}{k!}.\]
The limit follows by the exponential generating function \eqref{eq:egf}.\end{proof}

Theorem~\ref{th:exp} implies the somewhat surprising

\begin{corollary}
\label{cor:cor}
The probability $P(X_n=k)$ does not depend on $n$ as long as $n&gt;k$.
\end{corollary}


The following theorem is straightforward.

\begin{theorem}
\label{th:stdev} We set $B(x)=(A(x)-1)/x$. For the standard deviation of $X_n$ we have
\[\sigma(X_n)=\left(\sum_{k=1}^{n-1} k^2\left(\frac{A_k}{k!}-\frac{A_{k+1}}{(k+1)!}\right)+n^2\frac{A_n}{n!}-(EX_n)^2\right)^{1/2},\]
and
\begin{align*}
\lim_{n\to\infty} \sigma(X_n) &amp;= \left((A"(x)+A'(x))-(B"(x)+B'(x))\mid_{x=1}-(EX_n)^2\right)^{1/2}\\
&amp;\approx 2.09958.
\end{align*}
\end{theorem}

The next theorem quantifies $P(X_n=k)$ for any $k\ge 4$ and sufficiently large $n$.\begin{theorem}
\label{th:approx} For a large
$n$ and $k&lt;n$, the probability $P(X_n = k)$ decreases exponentially as $k$ grows. More precisely,
for $k\ge 4$ and a large enough $n$, we have that
\[P(X_n=k)\approx 2\left(\frac{2}{\pi}\right)^{k+1}\left(1-\frac{2}{\pi}\right).\]
\end{theorem}
\begin{proof}
By the asymptotic result \eqref{eq:sim}, the exact distribution \eqref{eq:exact} and some numerical calculation show that the absolute difference between $P(X_n=k)$ and its approximated value is less than $10^{-3}$ for $k\ge 4$.
\end{proof}

\begin{thebibliography}{9}

\bibitem{Bona} {M.~B\'ona},
    \textit{Combinatorics of Permutations}, Chapman \&amp;
Hall/CRC, 2004.

\bibitem{BBD} {J.~M.~Borwein,  P.~B.~Borwein, and K.~Dilcher},
    {Pi, Euler Numbers, and Asymptotic Expansions}, \textit{Amer. Math. Monthly }  \textbf{96}
    (1989), 681--687.

\bibitem{Comtet} {L.~Comtet},
\textit{Advanced Combinatorics}, {D. Reidel Publishing Co.},
1974.

\bibitem{Stanley} {R.~Stanley},
    \textit{Enumerative Combinatorics}, Vol.~2, Cambridge University Press,
    1999.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15, 60C05.

\noindent \emph{Keywords: }
alternating permutation, generating function, combinatorial probability.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000111}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 28 2019;
revised versions received August 16 2019; August 19 2019.
Published in {\it Journal of Integer Sequences}, August 19 2019.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

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