\documentclass[a4paper,reqno,11pt]{amsart}
\usepackage{amsfonts,amsmath,amssymb}
\textheight193mm
\textwidth122mm
\pagestyle{empty}
\usepackage{latexsym}
%\usepackage{emlines2}
\def\eps{\varepsilon}
\def\al{\alpha}
\def\1{\bar{1}}
\def\NN{\mathbb{N}}
\def\EE{\bold{E}}
\def\qf#1#2{(#1;q)_{#2}}
\def\bb#1{[\![#1]\!]}
\def\[{[\! [}
\def\]{]\! ]}
\def\lk{[\! [}
\def\rk{]\! ]}
\def\llk{[\! [\![}
\def\rrk{]\! ]\!]}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\ZZ{\mathbb{Z}}
\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}[theorem]{Proposition}%[section]
\newtheorem{lemma}[theorem]{Lemma}%[section]
\newtheorem{cor}[theorem]{Corollary}
\renewcommand{\thecor}{}
\newtheorem{ncor}[theorem]{Corollary}
\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\newcommand\U{{\mathcal{U}}}
\newcommand\E{{\bold{E}}}
\newcommand\V{{\bold{V}}}
\newcommand\T{{\mathcal{T}}}
\renewcommand\P{{\mathbb{P}}}
\renewcommand\a{{\bold{a}}}
\newcommand\p{{\bold{p}}}
\newcommand\mcirc{{\bigcirc}}
\newcommand\C{{\mathcal C}}
\newcommand\bl{\operatorname{L}}
\newcommand{\floor}[2]{\genfrac{\lfloor}{\rfloor}{}{}{#1}{#2}}
\newcommand{\ceil}[2]{\genfrac{\lceil}{\rceil}{}{}{#1}{#2}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\setcounter{topnumber}{5}
\renewcommand{\topfraction}{1.0}
\renewcommand{\textfraction}{.0}
%\renewcommand{\baselinestretch}{1.8}
\begin{document}
\title[Words, Permutations, and Representations of Numbers]
{Words, Permutations, and Representations of Numbers}
\author[H.~Prodinger]
{Helmut Prodinger}
\address{The John Knopfmacher
Centre for Applicable Analysis and Number Theory\\School of
Mathematics\\ University of the Witwatersrand\\ P.O. Wits\\ 2050
Johannesburg\\ South Africa.}
\email{helmut@gauss.cam.wits.ac.za\vskip0pt {\it WWW--address{\rm:
}}\texttt{http://www.wits.ac.za/helmut/index.htm}}
\date{}
\begin{abstract} In this survey paper we consider words, where
the letters are interpreted to be
numbers or digits. In the first part, natural numbers
are weighted with probabilities (from the geometric distribution).
Several properties and parameters of sets of such words are
analyzed probabilistically; the case of permutations is a limiting
case. In the second part, the representation of Gaussian integers
to the base $-2+i$ is considered, as well as redundant representations
to the base $q$, where the digits can be
arbitrary integers.
\end{abstract}
\maketitle
\thispagestyle{empty}
\begin{center}{{\sf Dedicated to Werner Kuich on the occasion
of his sixtieth birthday}}
\end{center}
\section{Introduction}
In this survey paper, we consider words $w=a_1a_2\dots a_n$, where
the letters $a_i$ are taken from the set $\ZZ$
or a finite subset thereof. In the first part, we assume that
the letters are obtained from the geometric distribution, i.\;e.
$\P\{a=k\}=pq^{k-1}$ with $p+q=1$. In this way, a probability
(weight) is attached to each word $w$, namely $(p/q)^nq^{a_1+\dots+a_n}$
(we assume that the letters are independent from each other). Of course,
a probability is then also attached to each set
$L\cap \NN^n$, where $L$ is an arbitrary language.
Most of the time, we will consider probability generating functions
$\sum_{n\ge0}\P\{L\cap \NN^n\}z^n$.
A typical example is the set of all {\it up--down\/} words
$L=\{a_1a_2\dots a_n\mid n\ge0,\, a_1\le a_2\ge a_3\le\dots\}$. The probability
of $L\cap\NN^n$ is then the probability that a random word of length $n$
is an up--down word. The interest in the geometric distribution comes
from computer science applications, namely a data structure
called {\it skip lists} \cite{KiPr94}, and {\it permutation counting}.
A permutation $\sigma_1 \sigma_2\dots \sigma_n $ does not enjoy
the independence property of letters in a word; a letter $\sigma_i$
can only occur if it was not already used in
$\sigma_1 \sigma_2\dots \sigma_{i-1} $.
This is often cumbersome to model. However, with the present approach,
we can (often) consider the limit $q\to1$. Then, the probability that
a letter appears more than once, goes to 0, and each relative
ordering of the letters is equiprobable. Hence parameters of
permutations which only depend on the ``order statistics''
will carry over. For example, the parameter ``position of the
largest element'' translates accordingly,
but not ``value of the largest element.''
We report about some recent results in the sequel.
\smallskip
The second part of this survey deals with the alphabet
$\{0,1,\dots,q-1\}$ and similar ones;
we think of the letters as digits,
and consider the words as representations of numbers.
For example, a word $a_n\dots a_1a_0$ represents the number
$\sum_{i=0}^na_iq^i$ in the $q$--ary representation.
The $k$th digit of the $q$--ary representation
of $n$ is given by
\begin{equation*}
a_k=\fl{\frac{n}{q^k}}-q\fl{\frac{n}{q^{k+1}}}.
\end{equation*}
We will deal with more exotic number systems:
On the one hand, with the basis $-2+i$ (with the complex
unit $i=\sqrt{-1}\,$), see \cite{GrKiPr98}, and on the other
hand with redundant representations
to the base $q$,
where the digits are allowed to be integers
(the alphabet is then $\ZZ$),
see \cite{prodinger162, HePr01}.
\section{Words, geometric probabilities, and permutations}
\subsection{Monotone words} One of the simplest examples deals
with the probability that a word is monotone, i.\;e.
$a_1< a_2<\dots$ (or $a_1\le a_2\le\dots$).
This establishes a nice
combinatorial interpretation of
{\it Euler's partition identities\/}
(see \cite{Prodinger93b}).
The identities in question are
$$
\prod_{n\ge0}\big(1+tq^n\big)=\sum_{n\ge0}\frac{t^nq^{\binom n2}}{\qf qn}
\quad\text{and}\quad
\prod_{n\ge0}\frac 1{1-tq^n}=\sum_{n\ge0}\frac{t^n}{\qf qn},
$$
where $\qf xn:=(1-x)(1-qx)\dots(1-q^{n-1}x)$.
Now the language of monotone words is
$\mathcal{ M}_{<}=\big(\varepsilon+1\big)\big(\varepsilon+ 2\big)\dots$
resp. $
\mathcal{M}_{\le}=1^\ast\cdot2^\ast\dots$,
so that the associated generating functions are given as
$$
M_{<}(z)=\prod_{k\ge0} \big(1+pq^{k}z\big)=
\sum_{n\ge0}\frac{p^nz^nq^{\binom n2}}{\qf qn}
$$
and
$$
M_{\le}(z)=\prod_{k\ge0}\frac{1}{1-pq^{k}z}=
\sum_{n\ge0}\frac{p^nz^n}{\qf qn}.
$$
Therefore the probability that a word of length $n$
is strictly monotone, is
${p^nq^{\binom n2}}/{\qf qn}$
and that it is weakly monotone is
${p^n}/{\qf qn}$. Both quantities tend for $q\to1$
to $1/n!$, which confirms to the fact that just one
permutation of $n$ elements is monotone.
\subsection{Alternating words} Let us now consider
up--down words or down--up words; for permutations, this
does not make a difference, but for words it does
(see \cite{Prodinger00b} for details).
Naturally, one can combine the weak and strict forms for the
inequalities. Also, one must distinguish the case of odd
resp. even lengths of words. The case of odd lengths is more
interesting. Let $f^{\le>}(z)$ be the generating functions
where the coefficient of $z^{2n+1}$ is
the probability that a word
$a_1\dots a_{2n+1}$ satisfies $a_1\le a_2>a_3\le\dots$, etc.
The results can all be expressed with the following
``$q$--tangent function"
$$
\tan_q^{[A,B,C,D]}(z):=
\sum_{n\ge0}\dfrac{(-1)^nz^{2n+1}}{[2n+1]_q!}
q^{An^2+Bn}
\bigg/
\sum_{n\ge0}\dfrac{(-1)^nz^{2n}}{[2n]_q!}
q^{Cn^2+Dn};
$$
here we used the notation of $q$--factorials:
$[n]_q!=\qf qn/(1-q)^n$, which converges for
$q\to1$ to $n!$.
\begin{gather*}
f^{\ge\le}(z)=
\tan_q^{[1,1,1,-1]}(z),\qquad
f^{<>}(z)=\tan_q^{[1,1,1,0]}(z),\\
f^{><}(z)=
\tan_q^{[1,0,1,0]}(z),\qquad
f^{\le\ge}(z)=
\tan_q^{[1,0,1,-1]}(z),\\
f^{\ge<}(z)=f^{\le>}(z)=f^{>\le}(z)
=f^{<\ge}(z)=
\tan_q^{[0,0,0,0]}(z).
\end{gather*}
Generating functions for patterns like $(\le\le\ge)^*$
lead to {\it Olivier functions}, see \cite{Carlitz73};
$q$--versions of that are currently worked out together
with A.~Tsifhumulo.
\subsection{The $\boldsymbol{q}$--path length of a binary search tree}
The path length $\rho(t)$ of a binary search tree
$t$ is the defined to be the sum over all distances from the
root to any node in the tree (measured in terms of
nodes, not edges) and satisfies the recursion
$\rho(t)=\rho(t_L)+\rho(t_R)+|t_L|+|t_R|$ where $t_L$ and
$t_R$ are the left resp. right subtree of the root.
($|t| $ denotes the size of the tree $t$, i.\;e. the number
of nodes.)
Our aim is to rewrite the definition of the path length in
terms of permutations.
For a permutation $\pi=\pi_1\dots\pi_n$ we define
$\rho(\pi)$ by
\begin{equation*}\rho(\pi)=\big|\{(j,k)\mid 1\le j