\documentclass[11pt,reqno]{amsart}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amscd}

%TCIDATA{TCIstyle=article/art1.lat,amsart,amsart}

%TCIDATA{Created=Wed May 02 16:01:06 2001}
%TCIDATA{LastRevised=Wed May 09 17:54:34 2001}
%TCIDATA{Language=American English}

\parskip=0.15cm
\parindent=0cm
%\pagestyle{empty}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{9in}
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\def\j{\bold{j}}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\al{\alpha}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q
}
\newcommand{\gausss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_
{q^2}}
\newcommand{\gaussss}[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_
{#3}}
\def\qff#1#2{(#1;q^2)_{#2}}
\newcommand{\qf}[2]{(#1;q)_{#2}}
\newcommand{\C}{\mathbb{C}}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\allowdisplaybreaks


\begin{document}
\title[On $q$--Olivier functions]
{On $\boldsymbol{ q}$--Olivier functions}
\author[H. Prodinger]{Helmut Prodinger}
\address[H. P.]{The John Knopfmacher Centre for Applicable Analysis and
Number Theory\\
University of the Witwatersrand\\
Private Bag 3\\
WITS 2050, South Africa}
\email{helmut@cam.wits.ac.za}
\urladdr{http://www.wits.ac.za/helmut/index.htm}
\author[T. A. Tshifhumulo]{Tuwani A. Tshifhumulo}
\address[T. A. T]{The John Knopfmacher Centre for Applicable Analysis and
Number Theory\\
University of the Witwatersrand\\
Private Bag 3\\
WITS 2050, South Africa}
\email{tat@univen.ac.za}
\keywords{}
\subjclass{}
\date{\today}

\begin{abstract}
We consider words $w_1\dots w_n$ with letters $w_i\in\{1,2,3,\dots\}$
satisfying an up--up--down pattern like $a_1\le a_2\le a_3\ge a_4\le
a_5\le
a_6\ge\dots\,$. Attaching the (geometric) probability $pq^{i-1}$ to the
letter $i$ (with $p=1-q$), every word gets a probability by assuming
indepence of letters. We are interested in the probability that a random
word of length $n$ satisfies the up--up--down condition. It turns out
that
one has to consider the 3 residue classes $\pmod 3$ separately; then one
can
compute the associated probability generating function. They turn out to
be $%
q$--analogues of so called Olivier functions.
\end{abstract}

\maketitle

\section{Introduction}

We consider words $w_{1}\dots w_{n}$ with letters $w_{i}\in
\{1,2,3,\dots \}$
satisfying an up--up--down pattern like $a_{1}\le a_{2}\le a_{3}\ge
a_{4}\le
a_{5}\le a_{6}\ge \dots \,$. Attaching the (geometric) probability
$pq^{i-1}$
to the letter $i$ (with $p=1-q$), every word gets a probability by
assuming
independence of letters. We are interested in the probability that a
random
word of length $n$ satisfies the up--up--down condition. It turns out
that
one has to consider the 3 residue classes $\pmod 3$ separately; then one
can
compute the associated probability generating function.

This extends previous research of the first author about up-down
patterns,
leading to $q$--tangent and $q$--secant numbers, see \cite{HP}. There
are
several variations possible, since ``up'' might mean $\le $ or $<$ and
similar for ``down.'' Also, one can consider down--down--up patterns.

As it was discussed already in \cite{ HP}, the limit $q\to 1$ yields
the
model of permutations (in one line notation). Thus we get the generating
functions of permutations satisfying the up--up--down condition as
corollaries. These results are due to Carlitz \cite{CG}. The
generating
functions he obtained are known as Olivier functions \cite{CSG, CSE}: 
\begin{equation*}
\Phi_{k,t}(z):=\sum_{n\ge0}\frac{z^{kn+t}}{(kn+t)!}.
\end{equation*}
In this way we get various different $q$--Olivier functions.

We arrange these functions in a table and prove only one significant
instance, the other ones being similar. More details can be found in the
forthcoming thesis of the second author \cite{TA}.

Extensions to patterns like $(\le\dots\le\ge)^*$ and $(\le\le>>)^*$
are also discussed.

We need the following notations:
$(x;q)_{n}:=(1-x)(1-qx)\dots(1-q^{n-1}x)$
and $[n]_q!=(q;q)_{n}/p^n$, which in the limit $q\to1$ are the ordinary
factorials.

\section{Results}

We first consider $n\equiv 1\bmod3$. The probability generating function
is
given by 
\begin{equation*}
\sum_{n\ge0}(-1)^n\frac{z^{3n+1}q^{An^2+Bn}}{[3n+1]_q!}\Bigg/ %
\sum_{n\ge0}(-1)^n\frac{z^{3n}q^{Cn^2+Dn}}{[3n]_q!},
\end{equation*}
with the parameters $A,B,C,D$ given in the following table.

\begin{center}
\renewcommand{\arraystretch}{1.5} 
\begin{tabular}{||c||r|r|r|r||}
\hline
& A & B & C & D \\ \hline
$(\le \le \ge )^{*}$ & $\frac{3}{2}$ & $-\frac{1}{2}$ & $\frac{3}{2}$ &
$-%
\frac{3}{2}$ \\ \hline
$(\le \le >)^{*}$ & $0$ & $0$ & $0$ & $0$ \\ \hline
$(\le <\ge )^{*}$ & $3$ & $0$ & $3$ & $-2$ \\ \hline
$(\le <>)^{*}$ & $\frac 32$ & $\frac 12$ & $\frac32$ & $-\frac12$ \\ \hline
$(<\le \ge )^{*}$ & $3$ & $1$ & $3$ & $-1$ \\ \hline
$(<\le >)^{*}$ & $\frac{3}{2}$ & $\frac{3}{2}$ & $\frac{3}{2}$ &
$\frac{1}{2}
$ \\ \hline
$(<<\ge )^{*}$ & $\frac{9}{2}$ & $\frac{3}{2}$ & $\frac{9}{2}$ &
$-\frac{3}{2%
}$ \\ \hline
$(<<>)^{*}$ & $3$ & $2$ & $3$ & $0$ \\ \hline
\end{tabular}
\qquad \renewcommand{\arraystretch}{1.5} 
\begin{tabular}{||c||r|r|r|r||}
\hline
& A & B & C & D \\ \hline
$(\ge \ge \le )^{*}$ & $\frac{3}{2}$ & $\frac{3}{2}$ & $\frac{3}{2}$ &
$-%
\frac{3}{2}$ \\ \hline
$(\ge \ge <)^{*}$ & $0$ & $0$ & $0$ & $0$ \\ \hline
$(\ge >\le )^{*}$ & $3$ & $2$ & $3$ & $-1$ \\ \hline
$(\ge ><)^{*}$ & $\frac{3}{2}$ & $\frac{1}{2}$ & $\frac{3}{2}$ &
$\frac{1}{2}
$ \\ \hline
$(>\ge \le )^{*}$ & $3$ & $1$ & $3$ &
$-2$ \\ \hline
$(>\ge <)^{*}$ & $\frac{3}{2}$ & $-\frac{1}{2}$ & $\frac{3}{2}$ &
$-\frac{1}{%
2}$ \\ \hline
$(>>\leq )^{*}$ & $\frac{9}{2}$ & $\frac{3}{2}$ & $\frac{9}{2}$ &
$-\frac{3}{%
2}$ \\ \hline
$(>><)^{*}$ & $3$ & $0$ & $3$ & $0$ \\ \hline
\end{tabular}
\end{center}

Now we consider $n\equiv 2\bmod3$. The probability generating function
is
given by 
\begin{equation*}
\sum_{n\ge 0}(-1)^{n}\frac{z^{3n+2}q^{An^{2}+Bn+E}}{[3n+2]_{q}!}\Bigg/ %
\sum_{n\ge 0}(-1)^{n}\frac{z^{3n}q^{Cn^{2}+Dn}}{[3n]_{q}!},
\end{equation*}
with the parameters $A,B,C,D,E$ given in the following table.

\begin{center}
\renewcommand{\arraystretch}{1.5} 
\begin{tabular}{||c||r|r|r|r|r||}
\hline
& A & B & C & D & E \\ \hline
$(\le \le \ge )^{*}\le $ & $\frac{3}{2}$ & $\frac{1}{2}$ & $\frac{3}{2}$
& $-%
\frac{3}{2}$ & $0$ \\ \hline
$(\le \le >)^{*}\le $ & $0$ & $0$ & $0$ & $0$ & $0$ \\ \hline
$(\le <\ge )^{*}\le $ & $3$ & $2$ & $3$ & $-2$ & $0$ \\ \hline
$(\le <>)^{*}\le $ & $\frac{3}{2}$ & $\frac{3}{2}$ & $\frac{3}{2}$ &
$-\frac{%
1}{2}$ & $0$ \\ \hline
$(<\le \ge )^{*}<$ & $3$ & $3$ & $3$ & $-1$ & $1$ \\ \hline
$(<\le >)^{*}<$ & $\frac{3}{2}$ & $\frac{5}{2}$ & $\frac{3}{2}$ &
$\frac{1}{2%
}$ & $1$ \\ \hline
$(<<\ge )^{*}<$ & $\frac{9}{2}$ & $\frac{9}{2}$ & $\frac{9}{2}$ &
$-\frac{3}{%
2}$ & $1$ \\ \hline
$(<<>)^{*}<$ & $3$ & $4$ & $3$ & $0$ & $1$ \\ \hline
\end{tabular}
\qquad \renewcommand{\arraystretch}{1.5} 
\begin{tabular}{||c||r|r|r|r|r||}
\hline
& A & B & C & D & E \\ \hline
$(\ge \ge \le )^{*}\ge $ & $\frac{3}{2}$ & $\frac{3}{2}$ & $\frac{3}{2}$
& $-%
\frac{3}{2}$ & $0$ \\ \hline
$(\ge \ge <)^{*}\ge $ & $0$ & $0$ & $0$ & $0$ & 0 \\ \hline
$(\ge >\le )^{*}\ge $ & $3$ & $2$ & $3$ & $-1$ & $0$ \\ \hline
$(\ge ><)^{*}\ge $ & $\frac{3}{2}$ & $\frac{1}{2}$ & $\frac{3}{2}$ &
$\frac{1%
}{2}$ & $0$ \\ \hline
$(>\ge \le )^{*}>$ & $3$ & $4$ & $3$ & $-2$ & $1$ \\ \hline
$(>\ge <)^{*}>$ & $\frac{3}{2}$ & $\frac{5}{2}$ & $\frac{3}{2}$ &
$-\frac{1}{%
2}$ & $1$ \\ \hline
$(>>\leq )^{*}>$ & $\frac{9}{2}$ & $\frac{9}{2}$ & $\frac{9}{2}$ &
$-\frac{3%
}{2}$ & $1$ \\ \hline
$(>><)^{*}>$ & $3$ & $3$ & $3$ &$0$ & $1$ \\ \hline
\end{tabular}
\end{center}

Finally, we consider $n\equiv 0\bmod3$. The probability generating
function
is given by 
\begin{equation*}
1\Bigg/ \sum_{n\ge0}(-1)^n\frac{z^{3n}q^{Cn^2+Dn}}{[3n]_q!},
\end{equation*}
with the parameters $C,D$ given in the following table.

\begin{center}
\renewcommand{\arraystretch}{1.5} 
\begin{tabular}{||c||r|r||}
\hline
& C & D \\ \hline
$(\le \le \ge )^\ast\le\le$ & $\frac32$ & $-\frac32$ \\ \hline
$(\le \le >)^\ast\le\le$ & $0$ & $0$ \\ \hline
$(\le <\ge)^\ast\le<$ & $3$ & $-2$ \\ \hline
$(\le <>)^\ast\le<$ & $\frac32$ & $-\frac12$ \\ \hline
$(< \le \ge)^\ast<\le$ & $3$ & $-1$ \\ \hline
$(< \le >)^\ast<\le $ & $\frac32$ & $\frac12$ \\ \hline
$(<< \ge)^\ast< <$ & $\frac92$ & $-\frac32$ \\ \hline
$(<<>)^\ast<<$ & $3$ & $0$ \\ \hline
\end{tabular}
\qquad \renewcommand{\arraystretch}{1.5} 
\begin{tabular}{||c||r|r||}
\hline
& C & D \\ \hline
$(\ge \ge \le)^\ast\ge\ge$ & $\frac32$ & $-\frac32$ \\ \hline
$(\ge \ge <)^\ast\ge\ge$ & $0$ & $0$ \\ \hline
$(\ge >\le)^\ast\ge>$ & $3$ & $-1$ \\ \hline
$(\ge ><)^\ast\ge>$ & $\frac32$ & $\frac12$ \\ \hline
$(> \ge \le)^\ast>\ge$ & $3$ & $-2$ \\ \hline
$(> \ge <)^\ast>\ge$ & $\frac32$ & $-\frac12$ \\ \hline
$(>> \ge)^\ast>>$ & $\frac92$ & $-\frac32$ \\ \hline
$(>><)^\ast>>$ & $3$ & $0$ \\ \hline
\end{tabular}
\end{center}

As an illustration, we prove the instance of $(\le \le \ge )^{*}$, i.\;e.
we
consider words of length $1,4,7,\dots \,$. Denote by $a_{n}(u)$ the
following probability generating function: the coefficient of $u^{i}$ in
$%
a_{n}(u)$ is the probability that a word of length $3n-2$ has the
desired
shape and ends with $i$. The initial value is immediate:
\begin{equation*}
a_{1}(u)=\frac{pu}{1-qu}.
\end{equation*}
To get a recursion, we compute what can become of the variable $u^i$:
\begin{align}\label{subst}\begin{split}
u^i&\longrightarrow \sum_{i\le j\le k\ge l } pq^{j-1}pq^{k-1}pq^{l-1}u^l\\
&=\frac{p^3uq^{2i}}{q^2(1-q)(1-q^2)(1-qu)}-
\frac{up^3u^iq^{3i}}{q^2(1-qu)(1-q^2u)(1-q^3u)}.
\end{split}\end{align}
The multiple sum was computed with Maple.
This gives us the following recursion which involves substitutions as well:



\begin{equation*}
a_{n+1}(u)=\frac{p^{3}u}{q^{2}(q;q)_{2}(1-qu)}a_{n}(q^{2})-\frac{p^{3}u}
{%
q^{2}(qu;q)_{3}}a_{n}(q^{3}u).
\end{equation*}
We translate that into a generating function: Set 
\begin{equation*}
f(u)=\sum_{n\ge 1}a_{n}(u)z^{3n-2},
\end{equation*}
then 
\begin{equation*}
f(u)=z\frac{pu}{1-qu}+\frac{z^{3}p^{3}u}{q^{2}(q;q)_{2}(1-qu)}f(q^{2})-
\frac{%
z^{3}p^{3}u}{q^{2}(qu;q)_{3}}f(q^{3}u).
\end{equation*}
The nature of that functional equation makes it necessary to compute
first $f(q^{2})$, something that can be achieved by iteration: 
\begin{align*}
f(q^{2})& =z\frac{pq^{2}}{1-q^{3}}+\frac{z^{3}p^{3}q^{2}}{%
q^{2}(q;q)_{2}(1-q^{3})}f(q^{2}) \\
& -\frac{z^{3}p^{3}q^{2}}{q^{2}(q^{3};q)_{3}}\bigg[
z\frac{pq^5}{1-q^{6}}+%
\frac{z^{3}p^{3}q^{5}}{q^{2}(q;q)_{2}(1-q^{6})}f(q^{2}) \\
& -\frac{z^{3}p^{3}q^{5}}{q^{2}(q^{6};q)_{3}}\bigg[
z\frac{pq^8}{1-q^{9}}+%
\frac{z^{3}p^{3}q^{8}}{q^{2}(q;q)_{2}(1-q^{9})}f(q^{2}) \\
& -\frac{z^{3}p^{3}q^{8}}{q^{2}(q^{9};q)_{3}}\bigg[\dots ,
\end{align*}
or 
\begin{align*}
f(q^{2})& \bigg[1-\frac{z^{3}p^{3}}{(q;q)_{3}}
+\frac{z^{6}p^{6}q^{3}}{%
(q;q)_{6}}-\frac{z^{9}p^{9}q^{0+3+6}}{(q;q)_{9}}+\dots \bigg] \\
&
=\frac{zpq^{2}}{(q^{3};q)_{1}}-\frac{z^{4}p^{4}q^{5}}{(q^{3};q)_{4}}
+\frac{%
z^{7}p^{7}q^{11}}{(q^{3};q)_{7}}-\frac{z^{10}p^{10}q^{2+(0+3+6+9)}}{%
(q^{3};q)_{10}}+\dots ,
\end{align*}
which gives us the explicit form 
\begin{equation*}
f(q^{2})=\sum_{n\ge
0}(-1)^{n}\frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2}n^{2}+%
\frac{3}{2}n+2}}{(q^{3};q)_{3n+1}}\Bigg/ \sum_{n\ge 0}(-1)^{n}\frac{%
z^{3n}p^{3n}q^{\frac{3}{2}n^{2}-\frac{3}{2}n}}{(q;q)_{3n}}.
\end{equation*}
Now that this quantity is known, we can compute $f(u)$, again by
iteration:

\begin{align*}
f(u)&=z\frac{pu}{1-qu}+ \frac{z^3p^3u}{q^2(q;q)_{2}(1-qu)}f(q^2) \\
&-\frac{z^3p^3u}{q^2(qu;q)_{3}}\bigg[ z\frac{puq^3}{1-q^4u}+
\frac{z^3p^3q^3u%
}{q^2(q;q)_{2}(1-q^4u)}f(q^2) \\
&-\frac{z^3p^3q^3u}{q^2(q^4u;q)_{3}}\bigg[ z\frac{puq^6}{1-q^7u}+
\frac{%
z^3p^3q^6u}{q^2(q;q)_{2}(1-q^7u)}f(q^2) \\
&-\frac{z^3p^3q^6u}{q^2(q^7;q)_{3}}\bigg[\dots,
\end{align*}
or 
\begin{equation*}
f(u)=\sum_{n\ge0}(-1)^n\frac{z^{3n+1}p^{3n+1}u^{n+1}q^{\frac{3}{2}n^2
-\frac12n}}{(qu;q)_{3n+1}}-f(q^2) \sum_{n\ge1}(-1)^n\frac{z^{3n}p^{3n}
u^nq^{%
\frac{3}{2}n^2-\frac72n}} {(q;q)_{2}(qu;q)_{3n-2}}.
\end{equation*}
Of course, we are especially interested in $u=1$: 
\begin{align*}
f(1)&=\sum_{n\ge0}(-1)^n\frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2}n^2
-\frac12n}}{(q;q)_{3n+1}} \\
&-\sum_{n\ge0}(-1)^n\frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2}n^2+
\frac{3}{2}n+2}%
}{(q;q)_{3n+3}} \sum_{n\ge1}(-1)^n\frac{z^{3n}p^{3n}q^{\frac{3}{2}%
n^2-\frac72n}} {(q;q)_{3n-2}}\Bigg/
\sum_{n\ge0}(-1)^n\frac{z^{3n}p^{3n}q^{%
\frac{3}{2}n^2- \frac{3}{2}n}}{(q;q)_{3n}}.
\end{align*}
We will write everything over a common denominator and thus have to
compute 
\begin{multline*}
\sum_{n\ge0}(-1)^n\frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2}n^2
-\frac12n}}{%
(q;q)_{3n+1}} \sum_{n\ge0}(-1)^n\frac{z^{3n}p^{3n}q^{\frac{3}{2}n^2-
\frac{3%
}{2}n}}{(q;q)_{3n}} \\
+\sum_{n\ge0}(-1)^{n+1}\frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2}n^2+
\frac{3}{2}%
n+2}}{(q;q)_{3n+3}} \sum_{n\ge1}(-1)^n\frac{z^{3n}p^{3n}q^{\frac{3}{2}%
n^2-\frac72n}} {(q;q)_{3n-2}}.
\end{multline*}
The coefficient of $(pz)^{3n+1}$ in the first sum is 
\begin{align*}
&(-1)^n\sum_{k=0}^n\frac{q^{\frac{3}{2}k^2
-\frac12k}}{(q;q)_{3k+1}}\frac{
q^{\frac{3}{2}(n-k)^2-\frac{3}{2}(n-k)}}{(q;q)_{3n-3k}} =(-1)^nq^{%
\frac32n(n-1)}\sum_{k=0}^n\frac{q^ {k(3k+1)-3kn}}
{(q;q)_{3k+1}(q;q)_{3n-3k}}%
;
\end{align*}
the coefficient of $(pz)^{3n+1}$ in the second sum is

\begin{align*}
(-1)^{n+1}q^{\frac32n(n-1)}\sum_{k=0}^{n}\frac{ q^{3k^2-k(3n-1)}} {%
(q;q)_{3k+1}(q;q)_{3n-3k}} +(-1)^{n}\frac{q^{\frac32 n^2-\frac12n} }{%
(q;q)_{3n+1}};
\end{align*}
so the combination of both is simply 
\begin{align*}
(-1)^{n}\frac{q^{\frac32 n^2-\frac12n} }{(q;q)_{3n+1}}.
\end{align*}
This proves that 
\begin{equation*}
f(1)=\sum_{n\ge0}(-1)^n\frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2}n^2-
\frac{1}{2}n}%
}{(q;q)_{3n+1}}\Bigg/
\sum_{n\ge0}(-1)^n\frac{z^{3n}p^{3n}q^{\frac{3}{2}n^2- 
\frac{3}{2}n}}{(q;q)_{3n}},
\end{equation*}
as claimed.

\section{A generalization}

We briefly report on the more
general pattern up\dots up--down, with
$k-1$
up steps always followed by a down step (except possibly at the right
border). Details of these computations are
to be found in \cite{TA}. There are four cases to
be considered:

First, we consider $n\equiv 0\bmod k$. 
For the pattern $(\leq \leq \dots \leq \geq)^{*} $,
 the probability generating function is
\begin{equation*}
1\Bigg/ \sum_{n\ge
0}(-1)^{n}\frac{z^{kn}q^{\frac{k}{2}n^{2}-\frac{k}{2}n}}{%
[kn]_{q}!}.
\end{equation*}
For the pattern $(\leq \leq \dots \leq >)^{*}$, the probability generating
function is
\begin{equation*}
1\Bigg/ \sum_{n\ge 0}(-1)^{n}\frac{z^{kn}}{[kn]_{q}!}.
\end{equation*}
For the pattern $(<<\dots <\geq)^{*} $, the probability generating
function is
\begin{equation*}
1\Bigg/ \sum_{n\ge
0}(-1)^{n}\frac{z^{kn}q^{\frac{k^{2}}{2}n^{2}-\frac{k}{2}%
n}}{[kn]_{q}!}.
\end{equation*}
Finally, for the pattern $(<<\dots <>)^{*}$, the
probability generating function is given by
\begin{equation*}
1\Bigg/ \sum_{n\ge 0}(-1)^{n}\frac{z^{kn}q^{\frac{k\left( k-1\right)
}{2}%
n^{2}}}{[kn]_{q}!}.
\end{equation*}

Next, we consider $n\equiv t\bmod k$, where $t=1,2,\dots ,k-1$.
That means that we consider $t-1$ extra up steps at the right
border.  
For the pattern $(\leq \leq \dots \leq \geq)^{*}\le^{t-1} $, the probability generating
function is
\begin{equation*}
\sum_{n\geq 0}\left( -1\right) ^{n}\frac{z^{kn+t}q^{\frac{k}{2}
n^{2}+\left( t-\frac{k}{2}\right) n}}{\left[ kn+t\right] _{q}!}\Bigg/ %
\sum_{n\ge
0}(-1)^{n}\frac{z^{kn}q^{\frac{k}{2}n^{2}-\frac{k}{2}n}}{[kn]_{q}!%
}.
\end{equation*}
For the pattern $(\leq \leq \dots \leq >)^{*}\le^{t-1}$, the probability generating
function is
\begin{equation*}
\sum_{n\geq 0}\left( -1\right) ^{n}\frac{z^{kn+t}}{\left[
nk+t\right] _{q}!}\Bigg/ \sum_{n\ge 0}(-1)^{n}\frac{z^{kn}}{[kn]_{q}!}.
\end{equation*}
For the pattern $(<<\dots <\geq)^{*}<^{t-1} $, the probability generating
function is
\begin{equation*}
\sum_{n\geq 0}\left( -1\right) ^{n}\frac{z^{kn+t}
q^{\frac{k^2}2n^2+(t-\frac12)kn+\frac{t(t-1)}2}
}{\left[
kn+t\right] _{q}!}\Bigg/ \sum_{n\ge
0}(-1)^{n}\frac{z^{kn}q^{\frac{k^{2}}{2}%
n^{2}-\frac{k}{2}n}}{[kn]_{q}!}.
\end{equation*}
Finally, for the pattern 
$(<<\dots <>)^{*}<^{t-1}$, the probability generating function is given by
\begin{equation*}
\sum_{n\geq 0}\left( -1\right) ^{n}\frac{z^{kn+t}q^{\frac{k\left(
k-1\right) }{2}n^{2}+\left( k-1\right) tn+\frac{t(t-1)}{2}}}{\left[
nk+t\right]
_{q}!}\Bigg/ \sum_{n\ge 0}(-1)^{n}\frac{z^{kn}q^{\frac{k\left(
k-1\right) }{2%
}n^{2}}}{[kn]_{q}!}.
\end{equation*}

We sketch again the instance $(\le\le\dots\le\ge)^{*}$:
Maple computes in analogy to (\ref{subst})
\begin{align*}
u^i&\longrightarrow \sum_{i\le j\le k\le l\ge h } pq^{j-1}pq^{k-1}pq^{l-1}
pq^{h-1}u^h\\
&=\frac{p^4uq^{3i}}{q^3(q;q)_3(1-qu)}-
\frac{up^4u^iq^{4i}}{q^3(qu;q)_4},
\end{align*}
as well as the next instance (a five fold sum)
\begin{align*}
u^i\longrightarrow \frac{p^5uq^{4i}}{q^4(q;q)_4(1-qu)}-
\frac{up^5u^iq^{5i}}{q^4(qu;q)_5},
\end{align*}
from which it is easy to guess the general substitution formula and
to prove it by induction. 
This leads to the recursion
\begin{equation*}
a_{n+1}(u)=\frac{p^{k}u}{q^{k-1}(q;q)_{k-1}(1-qu)}a_{n}(q^{k-1})-
\frac{p^{k}u}{q^{k-1}(qu;q)_{k}}a_{n}(q^{k}u).
\end{equation*}
The rest of the proof is then as in the 
previous section.







\section{Other patterns}

The method we use is suitable to deal with other patterns as well. As an
example, we consider words (and permutations in the limit) of length
$\equiv
1\bmod4$ satisfying the pattern $(\le \le >>)^{*}$. A relatively
straight forward computation leads to

\begin{align*}
a_1(u)=\frac{pu}{1-qu},
\end{align*}
and for $n\ge1$ 
\begin{align*}
a_{n+1}(u)=\frac{p^3u}{q(q;q)_{2}(1- q^2u)}a_n(q^2) -\frac{p^4u}{%
q^3(q;q)_{3}(1-qu)}a_n(q^3)+ \frac{p^4}{q^4(qu;q)_{4}}a_n(q^4u).
\end{align*}
We translate that into a generating function, 
\begin{equation*}
f(u)=\sum_{n\ge1}z^{4n-3}a_{n}(u).
\end{equation*}
With this notation we get the functional equation 
\begin{align}\label{fu:eq}
f(u)=\frac{zpu}{1-qu} +\frac{z^4p^3u}{q(q;q)_{2}(1-q^2u)}f(q^2) -\frac{%
z^4p^4u}{q^3(q;q)_{3}(1-qu)}f(q^3)+ \frac{z^4p^4}{q^4(qu;q)_{4}}f(q^4u).
\end{align}
We must compute $f(q^2)$ and $f(q^3)$:

\begin{align*}
f(q^{2})&
=\frac{zpq^{2}}{1-q^{3}}+\frac{z^{4}p^{3}q^{2}}{q(q;q)_{2}(1-q^{4})%
}f(q^{2})-\frac{z^{4}p^{4}q^{2}}{q^{3}(q;q)_{3}(1-q^{3})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{3};q)_{4}}\bigg[
\frac{zpq^{6}}{1-q^{7}}+\frac{%
z^{4}p^{3}q^{6}}{q(q;q)_{2}(1-q^{8})}f(q^{2})-\frac{z^{4}p^{4}q^{6}}{%
q^{3}(q;q)_{3}(1-q^{7})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{7};q)_{4}}\bigg[
\frac{zpq^{10}}{1-q^{11}}+%
\frac{z^{4}p^{3}q^{10}}{q(q;q)_{2}(1-q^{12})}f(q^{2})-\frac{z^{4}p^{4}q^
{10}%
}{q^{3}(q;q)_{3}(1-q^{11})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{11};q)_{4}}\bigg[+\dots
\end{align*}

{}{}{}So defining the auxiliary quantities 
\begin{align*}
\alpha & =q^{2}\sum_{n\ge 0}\frac{z^{4n+1}p^{4n+1}}{(q^{3};q)_{4n+1}},
\\
\beta & =1-\frac{q}{p}\sum_{n\ge
1}\frac{z^{4n}p^{4n}}{(q;q)_{4n-2}(1-q^{4n})%
}, \\
\gamma & =-\frac{1}{q(q;q)_{3}}\sum_{n\ge 1}\frac{z^{4n}p^{4n}}{%
(q^{3};q)_{4n-3}}, \\
&
\end{align*}
we get 
\begin{equation*}
f(q^{2})\beta =\alpha +\gamma f(q^{3}).
\end{equation*}
Similarly, 
\begin{align*}
f(q^{3})&
=\frac{zpq^{3}}{1-q^{4}}+\frac{z^{4}p^{3}q^{3}}{q(q;q)_{2}(1-q^{5})%
}f(q^{2})-\frac{z^{4}p^{4}q^{3}}{q^{3}(q;q)_{3}(1-q^{4})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{4};q)_{4}}\bigg[
\frac{zpq^{7}}{1-q^{8}}+\frac{%
z^{4}p^{3}q^{7}}{q(q;q)_{2}(1-q^{9})}f(q^{2})-\frac{z^{4}p^{4}q^{7}}{%
q^{3}(q;q)_{3}(1-q^{8})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{8};q)_{4}}\bigg[
\frac{zpq^{11}}{1-q^{12}}+%
\frac{z^{4}p^{3}q^{11}}{q(q;q)_{2}(1-q^{13})}f(q^{2})-\frac{z^{4}p^{4}q^
{11}%
}{q^{3}(q;q)_{3}(1-q^{12})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{12};q)_{4}}\bigg[ \dots ,
\end{align*}
or, with 
\begin{align*}
\delta & =q^{3}\sum_{n\ge 0}\frac{z^{4n+1}p^{4n+1}}{(q^{4};q)_{4n+1}},
\\
\rho & =\frac{q^{2}}{p(q;q)_{2}}\sum_{n\ge 1}\frac{z^{4n}p^{4n}}{%
(q^{4};q)_{4n-4}(1-q^{4n+1})}, \\
\sigma & =\sum_{n\ge 0}\frac{z^{4n}p^{4n}}{(q;q)_{4n}}, \\
&
\end{align*}
we get 
\begin{equation*}
f(q^{3})\sigma =\delta +\rho f(q^{2}).
\end{equation*}
Solving the system we find 
\begin{align*}
f(q^{2})& =\frac{\alpha \sigma +\gamma \delta }{\beta \sigma -\gamma
\rho },
\\
f(q^{3})& =\frac{\alpha \rho +\beta \delta }{\ \beta \sigma -\gamma \rho
}.
\end{align*}
Now we can compute $f(1)$: 
\begin{align*}
f(1)&
=\frac{zp}{1-q}+\frac{z^{4}p^{3}}{q(q;q)_{2}(1-q^{2})}f(q^{2})-\frac{%
z^{4}p^{4}}{q^{3}(q;q)_{3}(1-q)}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q;q)_{4}}\bigg[
\frac{zpq^{4}}{1-q^{5}}+\frac{%
z^{4}p^{3}q^{4}}{q(q;q)_{2}(1-q^{6})}f(q^{2})-\frac{z^{4}p^{4}q^{4}}{%
q^{3}(q;q)_{3}(1-q^{5})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{5};q)_{4}}\bigg[
\frac{zpq^{8}}{1-q^{9}}+\frac{%
z^{4}p^{3}q^{8}}{q(q;q)_{2}(1-q^{10})}f(q^{2})-\frac{z^{4}p^{4}q^{8}}{%
q^{3}(q;q)_{3}(1-q^{9})}f(q^{3}) \\
& +\frac{z^{4}p^{4}}{q^{4}(q^{9};q)_{4}}\bigg[\dots ,
\end{align*}
or, with 
\begin{align*}
\lambda & =\sum_{n\ge 0}\frac{z^{4n+1}p^{4n+1}}{(q;q)_{4n+1}}, \\
\mu & =\frac{1}{pq(q;q)_{2}}\sum_{n\ge 0}\frac{z^{4n+4}p^{4n+4}}{%
(q;q)_{4n}(1-q^{4n+2})}, \\
\nu & =\frac{1}{q^{3}(q;q)_{3}}\sum_{n\ge
1}\frac{z^{4n}p^{4n}}{(q;q)_{4n-3}}%
,
\end{align*}
\begin{equation*}
f(1)=\lambda +\mu f(q^{2})-\nu f(q^{3}).
\end{equation*}
We are not aiming to simplify this expression in the general case.
However,
we move straight to the limit $q\to 1$, to study permutations. 
At this stage it seems necessary to make the variable $z$ (and residue class
$\pmod4$) explicit: We write $H_1(z):=f(1)$.
Then

\begin{equation*}
H_1(z)=\lambda +\mu \frac{\alpha \sigma +\gamma \delta }{\beta \sigma
-\gamma
\rho }-\nu \frac{\alpha \rho +\beta \delta }{\beta \sigma -\gamma \rho
},
\end{equation*}
with 
\begin{align*}
\alpha & =2\sum_{n\ge 0}\frac{z^{4n+1}}{(4n+3)!}, \\
\beta & =1-\sum_{n\ge 1}\frac{z^{4n}}{(4n-2)!(4n)}, \\
\gamma & =-\frac{1}{3}\sum_{n\ge 1}\frac{z^{4n}}{(4n-1)!}, \\
\delta & =6\sum_{n\ge 0}\frac{z^{4n+1}}{(4n+4)!}, \\
\rho & =3\sum_{n\ge 1}\frac{z^{4n}}{(4n-1)!(4n+1)}, \\
\sigma & =\sum_{n\ge 0}\frac{z^{4n}}{(4n)!}, \\
\lambda & =\sum_{n\ge 0}\frac{z^{4n+1}}{(4n+1)!}, \\
\mu & =\frac{1}{2}\sum_{n\ge 0}\frac{z^{4n+4}}{(4n)!(4n+2)}, \\
\nu & =\frac{1}{6}\sum_{n\ge 1}\frac{z^{4n}}{(4n-3)!}.
\end{align*}
%\newpage

%\vspace*{\fill}

All these series can be expressed by exponential functions as follows: 
\begin{align*}
\alpha & =\frac{1}{2z^{2}}\left[ e^{z}+ie^{iz}-e^{-z}-ie^{-iz}\right] ,
\\
\beta & =\frac{1}{4}\left[ e^{z}+e^{iz}+e^{-z}+e^{-iz}\right]
-\frac{z}{4}%
\left[ e^{z}+ie^{iz}-e^{-z}-ie^{-iz}\right] , \\
\gamma & =-\frac{z}{12}\left[ e^{z}+ie^{iz}-e^{-z}-ie^{-iz}\right] , \\
\delta & =-\frac{6}{z^{3}}+\frac{3}{2z^{3}}\left[
e^{z}+e^{iz}+e^{-z}+e^{-iz}\right] , \\
\rho & =\frac{3}{4}\left[ e^{z}+e^{iz}+e^{-z}+e^{-iz}\right]
-\frac{3}{4z}%
\left[ e^{z}-ie^{iz}-e^{-z}+ie^{-iz}\right] , \\
\sigma & =\frac{1}{4}\left[ e^{z}+e^{iz}+e^{-z}+e^{-iz}\right] , \\
\lambda & =\frac{1}{4}\left[ e^{z}-ie^{iz}-e^{-z}+ie^{-iz}\right] , \\
\mu & =\frac{z^{3}}{8}\left[ e^{z}-ie^{iz}-e^{-z}+ie^{-iz}\right]
-\frac{%
z^{2}}{8}\left[ e^{z}-e^{iz}+e^{-z}-e^{-iz}\right] , \\
\nu & =\frac{z^{3}}{24}\left[ e^{z}-ie^{iz}-e^{-z}+ie^{-iz}\right] .
\end{align*}
Finally, this allows to express the generating function of interest as


\begin{equation*}
H_1(z)=(1+i){\frac{-i{e^{(1+i)z}}-{e^{(-1+i)z}}+i{e^{(-1-i)z}}+{e^{(1-i)z}
}}{{%
e^{(1+i)z}}+{e^{(-1+i)z}}+4+{e^{(-1-i)z}}+{e^{(1-i)z}}}}.
\end{equation*}
Here is the list of the first coefficients (normalized by factorials, to
make them the number of permutations satisfying the pattern
$(\le\le>>)^{n}$,
for $n=0,1,2,\dots $): 
\begin{align*}
& 1,6,1456,2020656,9336345856,108480272749056,2664103110372192256, \\
& 122840808510269863827456,9758611490955498257378246656, \\
&
1251231616578606273788469919481856,2459961197430582881322307594975770050
56,%
\dots\;.
\end{align*}
This sequence is not in Sloane's encyclopedia
 \cite{Sl_internet, Sl_book}.

Now we sketch briefly what happens for the other residue classes $\pmod4$.
They can all be obtained from $f(u)$ by appropriate substitutions.



For an extra up step $\leq $, we must compute $H_2(z):=\frac{z}{q}f( q) $. Starting from
the functional equation (\ref{fu:eq})
we  obtain 
\[
\frac{1}{q}f( q) =\sum_{n\geq 0}\frac{p^{4n+1}z^{4n+1}}{%
( q^{2};q) _{4n+1}}+\frac{f( q^{2}) }{pq(
q;q) _{2}}\sum_{n\geq 1}\frac{p^{4n}z^{4n}}{(
q^{2};q) _{4n-4}( 1-q^{4n-1}) }-\frac{f( q^{3}) 
}{q^{3}( q;q) _{3}}\sum_{n\geq 1}\frac{p^{4n}z^{4n}}{%
( q^{2};q) _{4n-3}}. 
\]
If we let 
\begin{align*}
\lambda_{1} &=\sum_{n\geq 0}\frac{p^{4n+1}z^{4n+1}}{(
q^{2};q) _{4n+1}}, \\
\varrho &=\frac{1}{pq( q^{2};q) }\sum_{n\geq 1}\frac{%
p^{4n}z^{4n}}{( q;q) _{4n-3}( 1-q^{4n-1}) }, \\
\omega &=\frac{1}{q^{3}( q;q) _{3}}\sum_{n\geq 1}\frac{%
p^{4n}z^{4n}}{( q^{2};q) _{4n-3}},
\end{align*}
we obtain 
\[
\frac{1}{q}f( q) =\lambda_{1} +\frac{\sigma \alpha +\gamma \delta }{%
\beta \alpha -\gamma \rho }\varrho -\frac{\rho \alpha +\beta \delta }{\beta
\alpha -\gamma \rho }\omega .
\]
Again, we concentrate on the limit $q\rightarrow 1$, to study permutations. So
\[
H_{2}( z) =z\Big( \lambda_{1} +\frac{\sigma \alpha +\gamma \delta 
}{\beta \alpha -\gamma \rho }\varrho -\frac{\rho \alpha +\beta \delta }{%
\beta \alpha -\gamma \rho }\omega \Big) 
\]
where 
\begin{align*}
\lambda_{1} &=\sum_{n\geq 0}\frac{z^{4n+1}}{( 4n+1) !}, \\
\varrho &=\frac{1}{2}\sum_{n\geq 1}\frac{z^{4n}}{( 4n-3)
!( 4n-1) }, \\
\omega &=\frac{1}{6}\sum_{n\geq 1}\frac{z^{4n}}{( 4n-2) !%
}.
\end{align*}
The three series $\omega$, $\varrho $ and $\lambda_{1} $ can be expressed by
exponential functions as follows: 
\begin{align*}
\lambda_{1} &=\frac{1}{4}[ e^{z}-ie^{iz}-e^{-z}+ie^{-iz}] , \\
\varrho &=\ \frac{z^{2}}{8}[ e^{z}-e^{iz}+e^{-z}-e^{-iz}) -\frac{%
z}{8}( e^{z}+ie^{iz}-e^{-z}-ie^{-iz}] ,\\
\omega &=\frac{z^{2}}{24}[ e^{z}-e^{iz}+e^{-z}-e^{-iz}].
\end{align*}
This allows us to express the generating function of interest as follows: 
\begin{equation*}
H_{2}( z) =-i\frac{ e^{(1+i)z}-e^{(1-i)z}-e^{(-1+i)z}+e^{(-1-i)z}}{
e^{(1+i)z}+e^{(1-i)z}+4+e^{(-1+i)z}+e^{(-1-i)z}}.
\end{equation*}
The first few values are $
1,26,10576,20551376,122087570176,1733786041150976 $, corresponding to $n=2,6,10,14,18$.



For two extra up steps $\leq \leq $, we must
compute $H_3(z):=\frac{z^2}{q( 1+q) }f(q^{2}) $.
In the limit $q\rightarrow 1,$ this becomes 
\begin{equation*}
H_{3}( z) =2\frac{e^{z}-e^{-z}+ie^{iz}-ie^{-iz}}{%
e^{(1+i)z}+e^{(1-i)z}+4+e^{(-1+i)z}+e^{(-1-i)z}}.
\end{equation*}
The first few values are $%
1,71,45541,120686411,908138776681$, corresponding to $n=3,7,11,15,19$.

Finally, for 3 extra steps $\leq \leq >$ we compute 
\[H_0(z):=
1+\frac{z^{3}}{q^{2}( 1+q) }f( q^{2}) -\frac{z^{3}}{%
q^{3}( 1+q) ( 1+q+q^{2}) }f( q^{3}) .
\]
In the limit $q\rightarrow 1$, this becomes 
\begin{equation*}
H_{0}( z) =2\frac{e^{z}+e^{-z}+e^{iz}+e^{-iz}}{%
e^{(1+i)z}+e^{(1-i)z}+4+e^{(-1+i)z}+e^{(-1-i)z}}.
\end{equation*}


The first few values are $1,3,413,397023,1402815833$, corresponding to $%
n=0,4,8,12,16$.

{\bf Remark}. Alternative expressions are as follows:
If we define (following Carlitz)
\begin{equation*}
\phi_i(z)=\sum_{n\ge0}\frac{z^{4n+i}}{(4n+i)!},\qquad\text{for $i=0,1,2,3$},
\end{equation*}
(these are the functions $\Phi_{4,i}(z)$ from the Introduction)
and $N:=\phi_0(z)^2-\phi_1(z)\phi_3(z)$, then
\begin{align*}
H_1(z)&=\frac{\phi_1(z)\phi_0(z)-\phi_2(z)\phi_3(z)}{N},\\
H_2(z)&=\frac{\phi_2(z)\phi_0(z)-\phi_3^2(z)}{N}=
\frac{\phi_1^2(z)-\phi_3^2(z)}{2N},\\
H_3(z)&=\frac{\phi_3(z)}{N},\\
H_0(z)&=\frac{\phi_0(z)}{N}.
\end{align*}
Carlitz and Scoville in \cite{CSE, CSG} have such results.
However, 
in \cite[p.~47]{CSE} we see a result that is difficult to
interpret; there is a drawing of an up-up-down-down
permutation of a length $\equiv 1 \bmod 4$, but its length is
denoted by $4n-1$; as a generating function the authors give
\begin{equation*}
\frac{\phi_1(z)\phi_2(z)-\phi_0(z)\phi_3(z)}{N}=
2\frac{z^3}{3!}+132\frac{z^7}{7!}+\dots,
\end{equation*}
but there is only one permutation of length 3 satisfying
that pattern.

The equivalence of the two forms for $H_2(z)$ follow from the
relation $\phi_1^2(z)+\phi_3^2(z)=2\phi_0(z)\phi_2(z)$, 
given by \cite[(3.12)]{CSG}.

















\begin{thebibliography}{9}
\bibitem{CG}  L. Carlitz, Generating Functions for a Special Class of
Permutations. Proc. Amer. Math. Soc. $47$  $(1975) $, 251--256.
\bibitem{CSE}L. Carlitz and R. Scoville, Enumeration of Rises and Falls by Position. 
Discrete Math. ${5}$ $(1973)$, 45--59.
\bibitem{CSG}L. Carlitz and R. Scoville, Generating Functions for Certain
Types of Permutations. J. Comb. Theory (A) {18} (1975), 262--275.
\bibitem{HP}  H. Prodinger, Combinatorics of Geometrically Distributed
Random Variables: New $q$--Tangent and $q$--Secant Numbers. Internat. J.
Math. and Math. Sci.  $24$ $(2000) $, 825--838.
\bibitem{Sl_internet}  N.\;J.\;A. Sloane,
The On--line Encyclopedia of Integer Sequences, 2001,
published electronically,
 \textsf{ http://www.research.att.com/$\sim$njas/sequences/}.
\bibitem{Sl_book}  N.\;J.\;A. Sloane and S. Plouffe,
The On--line Encyclopedia of Integer Sequences, 1995,
Academic Press.

\bibitem{TA} T.\;A. Tshifhumulo, Combinatorics of Geometrically Distributed Random
Variables: Words and Permutations Avoiding 
and Satisfying Contiguous Patterns. PhD Thesis (2002).
\end{thebibliography}

\end{document}

