\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

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

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
Circular Permutations Avoiding Runs of $i,i+1,i+2$ or $i,i-1,i-2$\\
}
\vskip 1cm
\large
Wayne M. Dym\'a\v cek and Isaac Lambert\\
Department of Mathematics\\
Washington and Lee University\\
Lexington, Virginia 24450 \\
USA\\
\href{mailto:dymacekw@wlu.edu}{\tt dymacekw@wlu.edu}\\
\end{center}

\vskip .2 in

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




%%%%%%%%%%%%%%%%%%%%%% Macros %%%%%%%%%%%%%%%%%%

\newcommand{\Cp}[1]{\ensuremath{\mathcal{C}^*(#1)}}

\newcommand{\SP}[1]{\ensuremath{\mathcal{S}^*(#1)}}

\newcommand{\Cpm}[1]{\ensuremath{\overline{\mathcal{C}^*}(#1)}}

\newcommand{\Spm}[1]{\ensuremath{\overline{\mathcal{S}^*}(#1)}}

\newcommand{\B}[3]{\ensuremath{\mathcal{B}_{{#1}\dots{#2}}^{#3}}}

\newcommand{\Bp}[3]{\ensuremath{\mathcal{B}_{{#1}\dots{#2}}^{*{#3}}}}

\newcommand{\Cpx}[2]{\ensuremath{\mathcal{C}^*(#1,#2)}}

\newcommand{\Spmx}[2]{\ensuremath{\overline{\mathcal{S}^*}(#1,#2)}}

\newcommand{\cp}[1]{\ensuremath{{c}^*(#1)}}

\newcommand{\sP}[1]{\ensuremath{{s}^*(#1)}}

\newcommand{\cpm}[1]{\ensuremath{\overline{{c}^*}(#1)}}

\newcommand{\spm}[1]{\ensuremath{\overline{{s}^*}(#1)}}

\newcommand{\bp}[3]{\ensuremath{{b}_{{#1}\dots{#2}}^{*{#3}}}}

\newcommand{\cpx}[2]{\ensuremath{{c}^*(#1,#2)}}

\newcommand{\spmx}[2]{\ensuremath{\overline{{s}^*}(#1,#2)}}

\begin{abstract}
In this paper we examine permutations that avoid
increasing or decreasing runs and extend known results to the circular
and modular cases,
allowing us to calculate sequence \seqnum{A078628} in Sloane's
{\it On-Line Encyclopedia of Integer Sequences}.
\end{abstract}


\section{Introduction}

The main purpose of this paper is to answer the following question: In how many ways can $n$ cards, numbered 0
to $n-1$, be placed in a circle so that no three consecutive cards are labeled consecutively? For example, if
$n=8$, then both of the following permutations have consecutively labeled cards in positions 3, 4, and 5 (we
use 0-origin): $(5,1,0,2,3,4,6,7)$ and $(5,1,0,4,3,2,6,7)$. If we consider $(n-1,0,1)$ and $(n-2,n-1,0)$ as
consecutively labeled cards, then this sequence of numbers is sequence A078628 in Sloane's Encyclopedia
\cite{Sloane} which previously had only thirteen terms calculated. We actually consider four sequences and we
begin with the following definition.

\begin{definition}A permutation $\pi=(a_0,a_1,\dots,a_{n-1})$ has a run if there is an $i$ such that either
$a_{i+1}= a_i + 1$ and $a_{i+2}= a_i + 2$ or $a_{i+1}= a_i - 1$ and $a_{i+2}= a_i - 2$. If the equalities are
replaced by congruences modulo $n$, then the runs are  modular runs. The set of $n$-long permutations 
without runs is denoted by $\SP{n}$ and the set without modular runs is denoted by $\Spm{n}$. 
\end{definition}

As is customary, we denote the size of $\SP{n}$ by $\sP{n}$ and likewise for the other sets in this paper. A
{\it circular permutation\/} $\pi=(a_0,\dots,a_{n-1})$ is a permutation in which the indices are from the ring
of integers modulo $n$ and so there are $(n-1)!$ circular permutations on $n$ objects. We let $\Cp{n}$ be the
set of $n$-long circular permutations that have no runs and $\Cpm{n}$ be the set of circular permutations
without a modular run. Note that $\cpm{n}$ is the sequence  A078628 mentioned above and that for $n=8$, neither
$(0,1,5,4,6,2,3,7) = (7,0,1,5,4,6,2,3)$ nor $(0,7,5,4,6,2,3,1) = (1,0,7,5,4,6,2,3)$ are in $\Cpm{n}$
since both have modular runs $(7,0,1)$ and $(1,0,7)$ respectively, but $(1,0,6,4,5,7,2,3)$ is in $\Cpm{n}$.
   
In the following, we often need to create a regular permutation from a circular one. This process we call {\it
flattening.\/} If $\pi= (a_0,\dots,a_{n-1})$ is a circular permutation, then $\pi^{f_a}$ is $\pi$ flattened at
$a$ if $i$ is the index for which $a_i= a$ and $\pi^{f_a} = (a_i, a_{i+1},\dots,a_{n-1},a_0, \dots, a_{i-1})$.
If we flatten at 0, then we denote this by $\pi^f$. Changing a regular permutation into a circular one is
straightforward. If $\pi=(a_0,\dots,a_{n-1})$ is a regular permutation, then $\pi$ {\it circularized\/} is the
circular permutation $\pi^c=(a_0,\dots,a_{n-1})$.

Note that if $\pi$ has no runs, then $\pi^{f_a}$ has no runs but it is possible to flatten a circular
permutation in the middle of a run so that the run is not preserved  in the flattened permutation. Also, a
regular permutation $\pi$ may not have a run but $\pi^c$ might. For example,
$\pi=(3,5,0,6,4,1,2)$ does not have a run but $\pi^c = (3,5,0,6,4,1,2) = (1,2,3,5,0,6,4) $ has the run
$(1,2,3)$.

One other useful operation we call {\it prepending}.  Given a straight permutation $\pi=(a_1,\dots,a_n)$ of
length $n$, prepending $a_0$ gives us a straight permutation $(a_0,a_1,\dots,a_n)$ of length $n+1$.  We must
take care when prepending $a_0$ to $\pi$ that we actually get a permutation.  Likewise {\it appending} adds a
digit to the end of a straight permutation.
 
If $\pi=(a_0,\dots,a_{n-1})$ is a permutation (straight or circular), then $-\pi=(n-1-a_0,\dots,n-1-a_{n-1})$
is also a permutation. Again,   $\pi$ has no runs if and only if $-\pi$ has no runs. 

The context for this paper is the study of arithmetic progressions in permutations. There are at least two ways
of defining an arithmetic progression in a permutation $\pi= (a_0,a_1,\dots,a_{n-1})$. We follow Hegarty
\cite{Hegarty} in defining a progression of rise $r$ and distance $d$ in $\pi$ as a sequence $(a_i,
a_{i+d},a_{i+2 d})$ where $r= a_{i+d}- a_i = a_{i+2 d}-a_{i+d}$. Note that a run is a progression with
distance $d=1$ and rise $r=\pm 1$.

Riordan \cite{Riordan} computed the number of permutations with $x$ progressions of rise $r=1$ and $d=1$ and
called them 3-sequences. He noted that  these were generalizations of a topic Whitworth considered, see
\cite[pp.~103--107]{Whitworth}. Charalambides \cite[pp.~176--184]{Charalambides} further generalized
Whitworth's sequences. Jackson and Read \cite{JackRead} called progressions  of distance 1
and rise $\pm 1$ increasing runs if $r=1$  and  decreasing runs if $r=-1$ and they gave  generating
functions  for the number of permutations without progressions with $d=1$ and $r=\pm 1$ of length
$\ell$. Jackson and Reilly \cite{JackRei} derived a generating function for the number of permutations with
exactly $x$ increasing runs of length $\ell$  and showed that the computation of the number of such
permutations  is $O(n^3)$.  Myers \cite{Myers} called a progression of rise 1 and distance 1 a block and counted
the number of permutations that contains $m$ blocks. He also considered rigid patterns and noticed that
difficulties occur if patterns can be interweaved.

The definition of an arithmetic progression in the permutation $\pi$ that we are {\em not} using is a sequence
$(a_i, a_{j},a_{k})$ with $0\le i < j < k<n$ where $a_{j}-a_i =a_k-a_j$. Progressions of this type were
studied by several authors,  \cite{Davis, Entringer,Sharma} (see also \cite{Lyndon,Odda,Simmons,Thomas}).


 
\section{The Main Results}

In Table~\ref{r=+-1} we list values for the sequences, $ \sP{n}$, $\spm{n}$, $\cp{n}$, and $\cpm{n}$. Jackson
and Read \cite{JackRead} computed the first column  and  Abramson and Moser \cite{Abramson} gave a formula for
it (see Theorem~\ref{Sp(n)}).  We will relate the other three columns of Table~\ref{r=+-1} to the
first column giving a fairly easy way to compute each of these columns. Since there three summations in
Theorem~\ref{Sp(n)} and the only multiplications are computing factorials and binomial coefficients, $\sP{n}$
can be computed with at most $O(n^4)$ operations. Also, as we will show, the other columns can be computed from
the first by $O(n)$ additions and so all these sequences can be computed in polynomial time. We believe that
$\cpm{n}$, $n\ge 13$, is computed here for the first time and the first fifty values of $\cpm{n}$ are listed at
the end of the paper. We first compute $\cp{n}$.

\begin{theorem}(Abramson, Moser, Jackson, Read) For $n\ge 3$,  \[ \sP{n}=\left (\sum_{k=1}^{n-2}(-1)^k
\sum_{i=0}^{k-1} {k-1
\choose i} (n-k-i-1)! \sum_{j=0}^i {i \choose j} {n-i-k-1 \choose j+1} 2^{j+1}
 \right ) + n!.\] \label{Sp(n)} \end{theorem}


\begin{table}[h]\centering
\begin{tabular}{|c||r|r||r|r|}\hline
$n$ & $ \sP{n}$ & \vphantom{${\overline{\SP{n}}}$}$\spm{n}$ & $\cp{n}$ & $\cpm{n}$\\ \hline
$3$ & $4$ & $0$ & $0$ & $0$\\ \hline
$4$ & $18$ & $16$ & $4$ & $4$\\ \hline
$5$ & $92$ & $80$ & $16$ & $12$\\ \hline
$6$ & $570$ & $516$ & $86$ & $76$\\ \hline
$7$ & $4082$ & $3794$ & $542$ & $494$\\ \hline
$8$ & $33292$ & $31456$ & $3932$ & $3662$\\ \hline
$9$ & $304490$ & $290970$ & $32330$ & $30574$\\ \hline
$10$ & $3086890$ & $2974380$ & $297438$ & $284398$\\ \hline
$11$ & $34357812$ & $33311520$ & $3028320$ & $2918924$\\ \hline
$12$ & $416526730$ & $405773448$ & $33814454$ & $32791604$\\ \hline
$13$ & $5463479106$ & $5342413414$ & $410954878$ & $400400062$\\ \hline
$14$ & $77094352076$ & $75612301688$ & $5400878692$ & $5281683678$\\ \hline
\end{tabular}
\caption{Values of $\sP{n}$, $\spm{n}$, $\cp{n}$, and $\cpm{n}$}
\label{r=+-1}
\end{table}

\begin{theorem} For $n \ge 4$ and if $\sP 1 = 0$ and $\sP{2} = 1$, then \[\cp{n} = \sP{n-1} -
2\sum_{i=1}^{\lfloor (n-2)/3\rfloor}\Big(\sP{n-3 i} - \sP{n-1-3 i}\Big). \]
\label{C=S-2S+2S}
\end{theorem}

\begin{proof}  Let $\pi$ be in $\Cp{n}$.  If we flatten $\pi$ at $n-1$, we get a permutation
$\pi^{f_{n-1}}=(n-1,a_0,\dots,a_{n-2})$. Note that $(a_0,\dots,a_{n-2})$ is in $\SP{n-1}$, but not all
permutations in $\SP{n-1}$ can have an $n-1$ prepended and then circularized to be in $\Cp{n}$.
In fact, these are precisely the permutations for which either $a_0=n-2$ and $a_1=n-3$ or $a_{n-3}=n-3$ and
$a_{n-2}=n-2$. In the first case, $\pi$ had the run $(n-1,n-2,n-3)$ and in the second case, $\pi$ had the
run $(n-3,n-2,n-1)$. Thus we need to exclude those permutations in $\SP{n-1}$ of the form
$(n-2,n-3,a_2,\dots,a_{n-2})$ or $(a_0,\dots,a_{n-4},n-3,n-2)$.

Since there are no runs in either $(a_2,\dots,a_{n-2})$ or $(a_0,\dots,a_{n-4})$, there are at most
$2\sP{n-3}$ permutations of the type we need to exclude and so $\cp{n}\ge \sP{n-1}-2 \sP{n-3}$. The
reason this inequality is not an equality is that if $a_2=n-4$ or $a_{n-4}=n-4$ in a permutation in $\SP{n-3}$,
then neither $(n-2,n-3,n-4,a_3\dots,a_{n-2})$ nor $(a_0,\dots,a_{n-5},n-4,n-3,n-2)$ would be in $\SP{n-1}$.
Since both $(a_3,\dots,a_{n-2})$ and $(a_0,\dots,a_{n-5})$ must be in $\SP{n-4}$, we have $\cp{n}\le
\sP{n-1}-2  \sP{n-3} +2 \sP{n-4}$.

As in the first exclusion, $(a_0,\dots,a_{n-7},n-6,n-5,n-4)$ and $(n-4,n-5,n-6,a_5,\dots,a_{n-2})$ are not
in $\SP{n-3}$ but $(a_0,\dots,a_{n-7},n-6,n-5)$ and $(n-5,n-6,a_5,\dots,a_{n-2})$ are in
$\SP{n-4}$. Hence we need to subtract the number of permutations of the form $(a_0,\dots,a_{n-7})$ and
$(a_5,\dots,a_{n-2})$  that are in $\SP{n-6}$. At this point, $\cp{n}\ge \sP{n-1}-2 \sP{n-3} +2
\sP{n-4} - 2\sP{n-6}$.

Continue in this manner. If $n\equiv 1~(\bmod~3)$, then in the last step we add $2\sP{3}$ getting the formula
in the statement of the theorem. If $n\equiv 0~(\bmod~3)$, then on the last step we must add back permutations
of length $n=3$ which begin or end with the value of $2$ which have no runs.  The only permutations with this
property are $(2,0,1)$ and $(1,0,2)$ and so the formula works with $\sP{2}=1$. If $n\equiv 2~(\bmod~3)$, then
on the last step we must avoid a permutation of length $n=4$ which begins with $(3,2)$ or ends with $(2,3)$ and
has no runs. The only permutations with this property are $(3,2,0,1)$ and $(1,0,2,3)$. So again $\sP{2}=1$
satisfies the equation.

\end{proof}

Let $\Bp{a}{b}{n}$ be the set of straight permutations that do not
have a run and which start with the sequence $a$ and end with the sequence $b$. For example, the permutation
$(0,5,1,6,4,2,3,7,8)$ is in $\Bp{0}{7,8}{9}$. While we include values for
$\bp{0}{2,1}{n}$ in Table~\ref{Bp}, we only use this sequence in the proofs of the following lemmas. We show
that $\cpm{n}$ can be computed using $\cp{n}$ and these $\bp{a}{b}{n}$'s. Since $\cp{n}$ can be computed from
$\sP{n}$, sequence A078628  can now be easily computed.

\begin{table}[h]\centering
\begin{tabular}{|c||r|r|r|r|}\hline
$n$ & $\bp{0,1}{n-2,n-1}{n}$ & $\bp{0}{n-2,n-1}{n}$ & $\bp{0}{n-1}{n}$ & $\bp{0}{2,1}{n} $\\ \hline
$5$ & $0$ & $1$ & $4$ & $1$\\ \hline
$6$ & $1$ & $3$ & $16$ & $3$\\ \hline
$7$ & $2$ & $13$ & $86$ & $14$\\ \hline
$8$ & $11$ & $73$ & $543$ & $75$\\ \hline
$9$ & $62$ & $470$ & $3934$ & $481$\\ \hline
\end{tabular}
\caption{Straight permutations which begin and end with certain sequences}
\label{Bp}
\end{table}

\begin{theorem}For $n \ge 3$, $\cpm{n} = \cp{n} - 2\Big(\bp{0,1}{n-1}{n} + \bp{0}{n-2,n-1}{n} -
\bp{0,1}{n-2,n-1}{n}\Big)$.
\label{barCp=Cp-stuff}
\end{theorem}

\begin{proof}The permutations in $\Cp{n}$ that are not in $\Cpm{n}$ are the ones containing the
sequence $(n-1,0,1) $ and its reverse $(1,0,n-1)$ or the sequence $(n-2,n-1,0)$ and its reverse $(0,n-1,n-2)$.
Since the number of permutations with one of these sequences is the same as the number with the sequence's
reverse, we focus on the sequences $(n-1,0,1) $ and $(n-2,n-1,0)$.

Flattening a permutation containing one of these sequences  at $0$, we need to subtract from $\cp{n}$, the
following: $\bp{0,1}{n-1}{n} +\bp{0}{n-2,n-1}{n}$. Since the permutations in
$\Bp{0,1}{n-2,n-1}{n}$ are  in both $\Bp{0,1}{n-1}{n}$ and  $\Bp{0}{n-2,n-1}{n}$, we need to add
$\bp{0,1}{n-2,n-1}{n}$ to get $\cpm{n} = \cp{n} - 2\Big(\bp{0,1}{n-1}{n} + \bp{0}{n-2,n-1}{n} \Big) + 2
\bp{0,1}{n-2,n-1}{n}$.
\end{proof}


The following two lemmas are  used only for tidying-up results that we will need later.

\begin{lemma} For $n \ge 3$, $\bp{0}{2,1}{n}=\bp{0}{n-2,n-1}{n} + \bp{0,1}{n-3,n-2}{n-1}$.
\label{B021}
\end{lemma}

\begin{proof} Let $\pi=(0,a_1,\dots,a_{n-3},2,1)$ be in $\Bp{0}{2,1}{n}$ and so $a_{n-3} \ne 3$. If $a_1
\ne n-1$ or $a_2\ne n-2$, then multiplying $\pi$ by $-1$ gives $-\pi = (0,-a_1, \dots, -a_{n-3}, -2, -1) =
(0,-a_1, \dots, -a_{n-3}, n-2, n-1)$.  Since $a_{n-3} \ne 3$, $-\pi$ is in  $\Bp{0}{n-2,n-1}{n}$.

If $a_1=n-1$ and $a_2=n-2$, then $-\pi= (0,1,2,-a_3,\dots, -a_{n-3}, n-2, n-1)$. Note that if $-a_3=3$, then
$(n-1,n-2,n-3) $ would have been a run in $\pi$. Removing $0$ from $-\pi$ and subtracting 1 from each entry
gives a permutation  in $\Bp{0,1}{n-3,n-2}{n-1}$. Therefore, $\bp{0}{2,1}{n}=\bp{0}{n-2,n-1}{n} +
\bp{0,1}{n-3,n-2}{n-1}$.

\end{proof}


\begin{lemma} For $n \ge 3$, $\bp{0,1}{n-1,n}{n+1} =  \bp{0,1}{n-1}{n} -  \bp{0,1}{n-2,n-1}{n}$.
\label{Bp01n-1n2}
\end{lemma}

\begin{proof}If $\pi=(0,1,a_2,\dots,a_{n-2}, n-1)$ is in $\Bp{0,1}{n-1}{n}$, then 
$a_{n-2} = n-2$ if and only if $\pi$ is in $\Bp{0,1}{n-2,n-1}{n}$. On the other hand, $a_{n-2} \ne n-2$ if and
only if appending $n$ to $\pi$ gives a permutation in $\Bp{0,1}{n-1,n}{n+1}$. Therefore, $\bp{0,1}{n-1}{n}
=  \bp{0,1}{n-2,n-1}{n} +  \bp{0,1}{n-1,n}{n+1}$.
\end{proof}


The next four results enable us to compute recursively any entry in Table~\ref{Bp} and hence by
Corollary~\ref{barCp=Cp-same} to compute $\cpm{n}$. 

%Using Corollary~\ref{Bp0n}, Lemmas~\ref{Bp0n-1n} and~\ref{Bp01n-1n}, values for $\Cp{n}$, and
%any given line of Table~\ref{Bp}, we can compute the next line of the table.


\begin{lemma} For $n \ge 3$, $\bp{0}{n}{n+1} =  \cp{n} +  \bp{0}{2,1}{n}  - \bp{0}{n-2,n-1}{n}$.
\label{Cpn}
\end{lemma}
\begin{proof}Let $\pi = (0,a_1,\dots, a_{n-1}, n)$ be in $\Bp{0}{n}{n+1}$. If $a_{n-2}\ne 2$ or
$a_{n-1} \ne 1$, then dropping the $n$ from $\pi$ and circularizing $(0, a_1,\dots, a_{n-1})$ gives a
permutation in $\Cp{n}$. If $a_{n-2}=2$ and $a_{n-1}=1$, then removing $n$ gives a permutation in $\Bp{0}{2,1}{n}$.

If, however, $\pi=(0, b_1, \dots, b_{n-3}, n-2, n-1)$ is a circular permutation in $\Cp{n}$, then
appending an $n$ to $\pi^f$ does not give a permutation in $\Bp{0}{n}{n+1}$. The number of such
permutations is $\bp{0}{n-2,n-1}{n}$ which must be subtracted from $\cp{n}  + \bp{0}{2,1}{n}$ to obtain
$\bp{0}{n}{n+1}$.
\end{proof}

Using Lemma~\ref{B021} gives us the following corollary to Lemma~\ref{Cpn}.

\begin{corollary}For $n \ge 3$, $\bp{0}{n}{n+1} =  \cp{n} +  \bp{0,1}{n-3,n-2}{n-1} $.
\label{Bp0n}
\end{corollary}


\begin{lemma} For $n \ge 3$, $\bp{0}{n-1,n}{n+1} = \bp{0}{n-1}{n} - \bp{0}{n-2,n-1}{n}$.
\label{Bp0n-1n}
\end{lemma}


\begin{proof} The proof of this lemma is very similar to the proof of Lemma~\ref{Bp01n-1n2} and is 
omitted.

\end{proof}

\begin{lemma} For $n\ge 3$, $\bp{0,1}{n-1,n}{n+1} = \bp{0}{n-2,n-1}{n} - \bp{0,1}{n-2,n-1}{n}$.
\label{Bp01n-1n}
\end{lemma}

\begin{proof}Let $\pi=(0,1,a_2,\dots,a_{n-3},n-1,n)$ be  in $\B{0,1}{n-1,n}{n+1}$. Note that $a_2 \ne
2$.  Hence deleting 0 from $\pi$ and subtracting 1 from each of the remaining entries gives the permutation
$(0,a_2-1,\dots, a_{n-3}-1,n-2,n-1)$ which is in $\B{0}{n-2,n-1}{n}$. But a permutation in
$\B{0}{n-2,n-1}{n}$ could have a $1$ in the second position in which case  the permutation is in
$\B{0,1}{n-2,n-1}{n}$.

\end{proof}

Theorem~\ref{C=S-2S+2S} allows  us to compute $\cp{n}$ for any $n$. Next suppose that we have two rows, say
$m-1$ and $m$, of known values in Table~\ref{Bp}. By Corollary~\ref{Bp0n}, we can compute row~$m+1$ of Column~3
in Table~\ref{Bp} and by Lemma~\ref{Bp0n-1n} we can compute row~$m+1$ of Column~2. Finally, by
Lemma~\ref{Bp01n-1n}, we can compute row~$m+1$ of Column~1. Therefore we can compute recursively
$\bp{0,1}{n-2,n-1}{n}$, $\bp{0}{n-2,n-1}{n}$, and $\bp{0}{n-1}{n}$ for $n>6$.

Using Theorem~\ref{barCp=Cp-stuff}  and  Lemma~\ref{Bp01n-1n2} and then Lemma~\ref{Bp01n-1n}, we can rewrite
$\cpm{n}$ in terms of just $\cp{n}$ and  $\bp{0,1}{n-2,n-1}{n}$.

\begin{corollary} For $n \ge 3$, $\cpm{n} = \cp{n} -2\bp{0,1}{n-2,n-1}{n} - 4 \bp{0,1}{n-1,n}{n+1}$.
\label{barCp=Cp-same}
\end{corollary}

For completeness, we now sketch the proof of the connection between the second and third columns of
Table~\ref{r=+-1}. If $\pi = (a_0,\dots,a_{n-1})$, then for $j$ an integer we define $\pi + j$ to be the
permutation $(a_0+j,\dots,a_{n-1}+j)$ where all additions are modulo $n$. Note that $\pi$ and $\pi+j$ have the
same number of modular runs.

\begin{theorem} For $n\ge 3$ and for $x>0$, $n \cdot \cpx{n}{x} =\spmx{n}{x}$ where $\Spmx{n}{x}$ is the set
of permutations with exactly $x$  modular runs and $ \Cpx{n}{x}$ is the set of circular permutations with
exactly $x$ runs.
\label{nCp(n,x)=S(n,x)}
\end{theorem}

\begin{proof}First consider a permutation $\pi=(0,a_1,\dots,a_{n-1})$ in $\Cp{n,x}$. The basic goal of
this proof is to flatten $\pi$ at $0$ to get $\pi^{f}$ and create a set of $n$  straight permutations
$\Pi=\{\pi^f,\pi^f+1,\dots,\pi^f+(n-1)\}$, each of which will have the same number of modular runs as
$\pi$ has runs. But since flattening may remove a run from the original permutation, there are  four cases.

{\bf Case 1: } Either $a_1\ne n-1$ or $a_2\ne n-2$ and either $a_{n-2}\ne 2$ or $a_{n-1}\ne 1$. In this case we
simply need to flatten the permutation at $0$ and create the set $\Pi$ as above.

{\bf Case 2: }  $a_1 = n-1$ and $a_2 = n-2$ and  $a_{n-2}= 2$ and $a_{n-1}= 1$. In this case we flatten the
permutation at $0$ and create the set $\Pi$ as above. Note that $(2,1,0)$ is a run in the
circular permutation and $(0,n-1,n-2)$ is a modular run in the straight permutation $\pi^f$. Hence
$\pi$ and $\pi^f$ have the same number of runs.

{\bf Case 3: }  $a_1 = n-1$ and $a_2 = n-2$ and either $a_{n-2}\ne 2$ or $a_{n-1}\ne 1$. In this case we
consider $\gamma= \left[ -\pi' \right]^{f}$, where $-\pi'$ is $-\pi$ reversed.   Hence
$\gamma=(0,-a_{n-1},\dots,-a_3,2,1)$ and has the same number of modular runs as $\pi$ has runs.
We use $\gamma$ to create the set of $n$ modular permutations that corresponds to $\pi$.

{\bf Case 4: } Either $a_1\ne n-1$ or $a_2\ne n-2$ and $a_{n-2}= 2$ and $a_{n-1}= 1$. We again
consider $\gamma= \left[ -\pi' \right]^{f}$, where again $-\pi'$ is $-\pi$ reversed.   Hence
$\gamma=(0,{n-1},n-2,-a_{n-3},\dots,-a_3)$ and has the same number of modular runs as $\pi$ has runs.

It is not difficult to show that the $n$  permutations produced by each of these cases are unique. If
$\pi=(a_0,a_1,\dots,a_{n-1})$ is in $\Spm{n,x}$, then $\pi-a_0$ will fit one of the four cases above.
Circularize $\pi-a_0$ and it will be the permutation that gives rise to the set of $n$ straight permutations
$\{ \pi+j: 0\le j < n\}$.
\end{proof}

\begin{corollary} For $n \ge 3$, $n \cdot \cp{n} = \spm{n}$.  
\label{nCp=S} 
\end{corollary}

\begin{proof} By the above theorem,  $n \cdot \cp{n} = n \cdot [(n-1)! - \sum_{x>0}\cpx{n}{x}] = n! -
\sum_{x>0}\spmx{n}{x} = \spm{n}$, as desired.
\end{proof}


\section{Probability}

It is not surprising that the probability that a permutation of length $n$ does not have  runs is close to 1.
In this section we verify this by showing that the probability that our deck of cards from the introduction has
no runs is essentially~1.

Since there are two ways to choose a modular run (increasing or decreasing), $n-2$ ways to choose the starting
position of the run, $n$ ways to choose the starting value of the run, and $(n-3)!$ ways to place the remaining
$n-3$ numbers in the permutation, there are at most $2(n-2)n(n-3)!$ permutations that have a modular run. Hence
$\spm{n} \ge n!- 2(n-2)n(n-3)!$ and so 
$$
\frac{\spm{n}}{n!} \ge 1 - \frac{2}{n-1}.
$$
Hence we have the following:

\begin{theorem} The probability that a permutation of length $n$ does not have a modular run approaches 1 as $n$
approaches infinity.
\label{big barS=1}
\end{theorem}

Since  $\sP{n} > \spm{n}$, we also have

\begin{corollary} The probability that a permutation of length $n$ does not have a run approaches 1 as $n$
approaches infinity.
\label{big S=1}
\end{corollary}

For circular permutations, position does not matter so there are at most $2 n(n-3)!$ circular permutations that
contain a modular progression. Hence 
$$
\frac{\cpm{n}}{(n-1)!} \ge 1- \frac{2 n}{(n-1)(n-2)}.
$$

Again, since $\cp{n}\ge \cpm{n}$, we have 

\begin{theorem} The probability that a circular permutation of length $n$ does not have a modular run approaches
1 as $n$ approaches infinity and the probability that a circular permutation of length $n$ does not have a  run
approaches 1 as $n$ approaches infinity. 
\label{big barC=1}
\end{theorem}

\section{Sequences}

This paper deals with sequences \seqnum{A002629}, \seqnum{A078628}, \seqnum{A095816}, \seqnum{A165963},  and \seqnum{A165964}. The first
fifty terms of sequence \seqnum{A078628} are as follows:

\medskip

$\cpm{1} = 0$

$\cpm{2} = 0$
                                   
$\cpm{3} = 0$
                                   
$\cpm{4} = 4$

$\cpm{5} = 12$
                                   
$\cpm{6} = 76$

$\cpm{7} = 494$
                                  
$\cpm{8} = 3662$
                                  
$\cpm{9} = 30574$
                                 
$\cpm{10} = 284398$
                                 
$\cpm{11} = 2918924$
                                
$\cpm{12} = 32791604$
                               
$\cpm{13} = 400400062$
                               
$\cpm{14} = 5281683678$
                              
$\cpm{15} = 74866857910$
                             
$\cpm{16} = 1135063409918$
                             
$\cpm{17} = 18330526475060$
                            
$\cpm{18} = 314169905117860$

$\cpm{19} = 5695984717957246$
                            
$\cpm{20} = 108921059813769710$
                           
$\cpm{21} = 2190998123920252622$
                          
$\cpm{22} = 46250325111346491694$
                          
$\cpm{23} = 1022301429750398188716$

$\cpm{24} = 23613740754886647958180$

$\cpm{25} = 568950024006846904093598$

$\cpm{26} = 14274866445575578119743438$

$\cpm{27} = 372374376152806360290989110$

$\cpm{28} = 10084828164172773195319256062$

$\cpm{29} = 283174462307289209810184927092$

$\cpm{30} = 8233653220849232427790328045876$

$\cpm{31} = 247614562274689810303882719509278$

$\cpm{32} = 7693604324191919134660311677872254$

$\cpm{33} = 246722167225395915065853140640911086$

$\cpm{34} = 8158170043027413464766703084133765486$

$\cpm{35} = 277900813774915739274082551738004741004$

$\cpm{36} = 9743794575197519961922090241025348596308$

$\cpm{37} = 351363839903830230918432098902818922192894$

$\cpm{38} = 13021021361761744809803587469208204799416830$
     
$\cpm{39} = 495539146920588230240234245219779841743108086$
     
$\cpm{40} = 19353425998749866625987965362312555548402003838$
     
$\cpm{41} = 775178453748407731849560920571080474371157593332$
     
$\cpm{42} = 31822940480660363909632901120497416610409109814276$
     
$\cpm{43} = 1338188780079916734821715054077664877231344980041022$
     
$\cpm{44} = 57608766415416937793463862738387567270274014040964686$
     
$\cpm{45} = 2537585460353397962654355343635847873682378459704820302$
     
$\cpm{46} = 114311753947370344920005481482946829653263862575017508398$
     
$\cpm{47} = 5263639446015081410706509916195602027644548310012924070828$
     
$\cpm{48} = 247629532177056272405843061340997818641369089724829503112772$
     
$\cpm{49} = 11897189001344425293916047304884946295425321612277069481144286$
     
$\cpm{50} = 583477983942047048226466538472338140101669906331645943031808878$

\section{Acknowledgments}

The first author  was supported by one of Washington and Lee
University's Lenfest Summer Grants. Parts of this paper are from Isaac
Lambert's honors thesis. We appreciated the suggestions of a referee.

\begin{thebibliography}{99}

\bibitem{Abramson}M. Abramson and  W. O. J. Moser, Permutations without rising or falling
$\omega$-sequences, \emph{Ann.~Math.~Statist.} \textbf{38}  (1967), 1245--1254.

\bibitem{Charalambides}C. A. Charalambides, \emph{Enumerative Combinatorics}, CRC Press, 2002.

\bibitem{Davis}J. A. Davis, R. C. Entringer, R. L. Graham, and G. J. Simmons, On permutations containing
no long arithmetic progressions,  \emph{Acta Arith.}  \textbf{34}  (1977/78), 81--90.

\bibitem{Entringer} R. C. Entringer  and D. E. Jackson, Elementary Problem 2440, \emph{Amer.\ Math.\ Monthly}
\textbf{80} (1973), 1058.

\bibitem{Hegarty}P. Hegarty, Permutations avoiding arithmetic patterns, \emph{Electron.~J. Combin.} \textbf{11}
(2004), \#R39.

\bibitem{JackRead}D. M. Jackson and R. C. Read, A note of permutations without runs of given length,
\emph{ Aequationes Math.} \textbf{17} (1978), 336--343.

\bibitem{JackRei}D. M. Jackson and  J. W. Reilly, Permutations with a prescribed number of p-runs, \emph{Ars
Combinatoria} \textbf{1} (1976), 297--305.

\bibitem{Lyndon}R. C. Lyndon, Solution to Elementary Problem 2440, \emph{Amer.\ Math.\ Monthly} \textbf{82}
(1975), 74--75.

\bibitem{Myers}A. N. Myers, Counting permutations by their rigid patterns, \emph{ J. Combin.\ Theory Ser.~A}
\textbf{99} (2002), 345--357.

\bibitem{Odda}T. Odda, Solution to Elementary Problem 2440, \emph{Amer.\ Math.\ Monthly} \textbf{82} (1975), 74.

\bibitem{Riordan}J. Riordan, Permutations without 3-sequences,  \emph{ Bull.~Amer.~Math.~Soc.} \textbf{51}
(1945), 745--748.

\bibitem{Sharma}A. Sharma, Enumerating permutations that avoid three term arithmetic progressions,
\emph{Electron.~J. Combin.} \textbf{16}, (2009) \#R63.

\bibitem{Simmons}G. J. Simmons, Comment on Elementary Problem 2440,  \emph{Amer.\ Math.\ Monthly} \textbf{82}
(1975), 76--77.

\bibitem{Sloane} N. J. A. Sloane,
The On-Line Encyclopedia of Integer Sequences, available electronically
at \href{http://oeis.org}{\tt http://oeis.org}.

\bibitem{Thomas}H. E. Thomas Jr., Solution to Elementary Problem 2440, \emph{Amer.\ Math.\ Monthly} \textbf{82}
(1975), 75--76.

\bibitem{Whitworth}W. A. Whitworth, \emph{Choice and Chance}, Hafner, 1965.


\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } permutation, circular permutation, run,
arithmetic progression.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A002629},
\seqnum{A078628},
\seqnum{A095816},
\seqnum{A165963}, and
\seqnum{A165964}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  January 15 2010;
revised version received  July 14 2010; January 19 2011.
Published in {\it Journal of Integer Sequences},
February 8 2011.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


.