\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<k\le n,\
\pi_j={\scriptstyle{\min\{\pi_j,\dots,\pi_k\}}} \ \text{\normalsize{or} }\
\pi_k={\scriptstyle{\min\{\pi_j,\dots,\pi_k\}}
}\}\big|.
\end{equation*}
Then $\rho(\square)=0$ and, if $\pi=\sigma1\tau$, then
$\rho(\pi)=\rho(\sigma)+\rho(\tau)+|\sigma|+|\tau|$,
as pairs with the left coordinate in $\sigma$  and the
right coordinate in $\tau$ are definitely not counted. 
(The correspondence from permutations to trees is as follows:
the smallest number forms the root, everything to the left (right)
of it (recursively) the left (right) subtree.)
This definition gives the path length of the binary search tree
associated to the permutation $\pi=\pi_1\dots\pi_n$,
provided we interpret $\pi_i$ as the arrival position of
key $i$.
But this definition of $\pi$ can be taken as it is, where
$\pi_1\dots\pi_n$ now denotes a {\it word\/} over the alphabet
$\{1,2,\dots\}$. We compute the expectation 
of the parameter $\rho$, for random words
of length $n$, and define for this purpose
random variables

\begin{equation*}
L_{jk}=\begin{cases}1 & \text{if}\ \pi_j=\min\{\pi_j,\dots,\pi_k\}
 \\ 0 &\text{ otherwise},\end{cases},\ \;
R_{jk}=\begin{cases}1 & \text{if}\ \pi_k=\min\{\pi_j,\dots,\pi_k\}
 \\ 0 &\text{ otherwise},\end{cases},
\end{equation*}
$B_{jk}=L_{jk}\cdot R_{jk}$, $N_{jk}=(1-L_{jk})\cdot (1-R_{jk})$.
(The letters $L,R,B,N$ are chosen to indicate
{\it left, right, both, not}.)
Then the parameter $\rho$ may be described as
\begin{equation*}   
\rho=\sum_{1\le j< k\le n}\Big[L_{jk}+R_{jk}-B_{jk}\Big].
\end{equation*}
 From this one can compute the expected value ($q$--analogue
of the path length in a binary search tree of size $n$):
\begin{align*}
\E_n=(1-q^2)\sum_{1\le i\le n}\frac{n+1-i}{1-q^{i}}-n(1+q),
\end{align*}
which is in  the limit $q\to1$: $\ \E_n=2(n+1)H_n-4n$,
as is of course well known. (The notations $H_n=\sum_{1\le k\le n}\frac1k$
 refer to harmonic
numbers, see e.~g. \cite{GrKnPa94}.)
The variance can also be computed, but this is much harder. 

A similar but simpler parameter appears in \cite{Prodinger01b},
namely the number of inversions (for words):

\begin{align*}
\E_n&=\frac{n(n-1)}{2}\frac{q}{1+q},\\
\V_n&=\frac{n(n-1)}{6}\frac{q}{(1+q)^2(1+q+q^2)}
\Big(2(1-q+q^2)n
-q^2+7q-1\Big).
\end{align*}
The same paper has also a parameter $a$ of  Knuth,
which is important in the analysis of 
{\em permutation in situ}:
\begin{equation*}
a=\big|\big\{(i,j)\mid 1\le i<j\le n,\ x_i=\min\{
x_i,x_{i+1},\dots,x_j
\}\big\}\big|.
\end{equation*}
Its expectated value can be computed as follows:
\begin{align*}
\EE_n&=\Big(\frac pq\Big)^{n}
\sum_{i_1,\dots,i_n\ge1}
q^{i_1+\dots+i_n}
\sum_{1\le j<k\le n}
\bb{i_j=\min \{i_j,\dots,i_k\}}\\
&=\sum_{1\le j<k\le n}
\Big(\frac pq\Big)^{k+1-j}
\sum_{i_j=\min\{i_j,\dots,i_k\}}q^{i_j+\dots+i_k}\\
&=\sum_{1\le j<k\le n}
\Big(\frac pq\Big)^{k+1-j}
\sum_{i\ge1}q^{i(k+1-j)}\frac{1}{p^{k-j}}\\
&=p\sum_{1\le j<k\le n}
\Big(\frac 1q\Big)^{k+1-j}
\sum_{i\ge1}q^{i(k+1-j)}\\
&=p\sum_{1\le j<k\le n}
\frac{1}{1-q^{k+1-j}}\\
&=p\sum_{2\le h\le n}(n+1-h)
\frac{1}{1-q^{h}}.
\end{align*}
(We used the Iverson convention: $\bb C=1$ if the condition
$C$ is true, and $\bb C=0$ otherwise.)








\subsection{Lengths of ascending runs}







Knuth in \cite{Knuth98} has considered the average length
$L_k$ of the $k$th ascending run in random  permutations
of $n$ elements
(for simplicity, mostly the instance $n\to \infty$ was discussed).
We study the concept of
ascending runs in our usual setting (see \cite{Prodinger00c,LoPr01}),
i.\;e., we consider infinite words, with letters $1,2,\cdots$,
and they appear with probabilities $p,pq,pq^2,\cdots$.
If we decompose a word into ascending runs
\begin{equation*}
a_1<\dots< a_r \ge b_1<\dots< b_s \ge c_1<\dots< c_t\ge\cdots,
\end{equation*}
then $r$ is the length of the first, $s$ of the second, $t$ of
the third run, and so on. 
We are interested in the averages of these parameters.
The generating function
\begin{equation*}
\prod_{i\ge1}(1+pq^{i-1}z)=\qf{-pz}\infty
\end{equation*}
plays a r\^ole here, where
$(a;q)_\infty=(1-a)(1-aq)(1-aq^2)\cdots$:


\begin{equation*}
\Lambda_m(z)=\sum_{n\ge0}[{\scriptstyle{\text{Probability
that a word of length $n$ has (exactly) $m$ ascending runs}}}]z^n,
\end{equation*}
then $\Lambda_0(z)=1$ and $\Lambda_1(z)=(-pz;q)_\infty-1$
and we have the recurrence 							

\begin{align*}
\Lambda_m(z)=\big(\qf{-pz}\infty\big)^m-\sum_{k=1}^m\frac1{k!}D^k\big(z^k
\Lambda_{m-k}(z)\big)
\end{align*}
($D$ means differentiation w.\;r.\;t. $z$.)
In the limiting case $q\to1$ we can specify these quantities
explicitly:
\begin{align*}
\Lambda_m(z):=e^{mz}-\sum_{k=1}^m\frac1{k!}D^k\big(z^k
\Lambda_{m-k}(z)\big),\qquad
\Lambda_0(z):=1,
\end{align*}
and for $m\ge1$ (e.\;g. via induction)
\begin{equation*}
\Lambda_m(z)=\sum_{j=0}^me^{jz}
\frac{z^{m-j-1}(-1)^{m-j}j^{m-j-1}\big(j(z-1)+m\big)}{(m-j)!}.
\end{equation*}
Knuth has shown that the average length of the $m$th run
is given by

\begin{equation*}
L_m=\Lambda_m(1)=
m\sum_{j=0}^m\frac{(-1)^{m-j}j^{m-j-1}}{(m-j)!}e^j,
\end{equation*}
and that $L_m\to2$.
In the general case, we are able to prove that
 $L_m\to1+q$. 
To do that we 
study the double generating function
 $$R(w,z)=\sum_{m\geq 0}\Lambda_m(z) w^m
=\frac{1-w}{1-w\prod_{n\geq 0}(1+pz(1-w)q^n)}.$$
In the limit $q\to1$ we get $R(w,z)=(1-w)/(1-we^{z(1-w)})$,
which is the generating function for Eulerian numbers
$A(n,k)$. Note that $A(n,k)$ is the number of permutations
of $n$ elements with exactly $k$ runs. (Sometimes, as
in \cite{GrKnPa94}, the focus is on the number of descents, 
which is one less than the number of runs.)
Hence $R(w,z)$  provides $q$--Eulerian
numbers which differ from those investigated by Carlitz
\cite{Carlitz75}.

\subsection{Left--to--right maxima}

As is easy to guess by the name, this parameter counts how often we
meet a number that is larger than all the elements to the left. 
The results for random permutations are: The harmonic number $H_n$ for the
expectation and $H_n-H_n^{(2)}$ for the variance;
here, $H_n^{(2)}=1+\frac14+\dots+\frac{1}{n^2}$ denotes the $n$th
harmonic number of second order.

For recent research on that in the context of random words, 
see \cite{Prodinger96c, KnPr01, Prodinger01d}.
We will set up a
certain ``language'' $\mathcal{ L}$
and translate it to enumerating generating functions.
We decompose all sequences $x_1x_2\dots$ in a canonical way as follows:
We combine each left--to--right maximum 
$ k$ with the following (smaller or equal) elements.
Such a part is described by
$\mathcal {A}_k:=k \{1, \dots , {k}\}^*$.
Such a group may be present or not. This observation gives the desired
``language,'' where $\varepsilon$ denotes the ``empty word:''
$$
\mathcal {L}:=\big(\mathcal {A}_1+\varepsilon\big)
\cdot\big(\mathcal {A}_2+\varepsilon\big)\cdot
\big(\mathcal {A}_3+\varepsilon\big)\dots. 
$$
Now we want to mark each letter by a ``$z$'' and each left--to--right 
maximum
by a ``$u$''. The probability $pq^{k-1}$ for a letter $ k$ should
of course not being forgotten. The set
$\{ 1, \dots , {k}\}$ maps into $z(1-q^k)$ and its star
$\{1, \dots , {k}\}^*$ into $1\big/\big(1-z(1-q^k)\big)$.
So we obtain the generating function $F(z,u)$ as an infinite product:
$$
F(z,u)=\prod_{k\ge1}\left(1+\frac{zupq^{k-1}}{1-z(1-q^k)}\right).
$$
To be explicit, the coefficient of $z^nu^k$ in $F(z,u)$
is the probability that
$n$ random variables have $k$ left--to--right maxima.
Let $f(z)=\frac{\partial F(z,y)}{\partial y}\big|_{y=1}$. It is the 
generating function for the expected values $\EE_n$.
We obtain
$$
f(z)=\frac{pz}{1-z}\sum_{k\ge 0}\frac{q^k}{1-z(1-q^k)},
$$
which is also, by partial fraction decomposition,
$$
f(z)=p\sum_{k\ge 0}\left[\frac{1}{1-z}-\frac1{1-z(1-q^k)}\right].
$$
 From this the coefficients $\E_n$ are easy to get:
$$
\EE_n=
[z^n]f(z)=p\sum_{k\ge 0}\left[1-\big(1-q^k\big)^n\right].
$$
The asymptotic evaluation of this is well known:
The average number $\E_n$ of left--to--right maxima
in the context of $n$ independently distributed geometric random variables
has the asymptotic expansion
$$
\EE_n=
p\left[\log_Qn+\frac{\gamma}{L}+\frac 12-\delta\left(\log_Qn\right)\right]
+\mathcal{O}\big(\frac 1n\big)
$$
with a (small) periodic function $\delta(x)$. (Here and later we
will use the handy abbreviations $Q=1/q$ and $L=\log Q$.)

Now we turn to
the average {\em value \/} and {\em position\/} 
of the $r$th 
left--to--right maximum, for fixed $r$ and $n\to\infty$,
something that was studied by Wilf in the instance of
permutations \cite{Wilf95}.
Summarizing our results, we obtain the 
asymptotic
formul{\ae}
$\frac rp$ and 
$\frac{1}{(r-1)!}\big(\frac pq\log_Qn\big)^{r-1}$.
The generating function  related to the {\em value\/}
of interest is
\begin{equation*}
\text{{\sf Value}}(z,u):=
\frac{1}{1-z}
\prod_{i=1}^{h-1}\left\{
1+\frac{pq^{i-1}zu}{1-(1-q^i)z}\right\}
zpq^{h-1},
\end{equation*}
which originates from the (unique) decomposition of a string
as $a_1w_1\dots\allowbreak a_{r-1}w_{r-1}a_r w$ where
$a_1,\dots, a_r$ are the left--to--right maxima, 
the $w_i$ are the strings between them, and $w$ can be anything.
Note that if $a_k=l$, then this corresponds to a term
$pq^{l-1}zu$.
Any letter in $w_k$ can come with the probability
$1-q^k$,
 and thus $w_k$ corresponds to $\sum_{j\ge0}(1-q^k)^jz^j=1/\big(
1-(1-q^k)z\big)$. A particular value $i$ does not necessarily occur
as a left--to--right maximum; that is reflected by the 
$1+\dots$ in the product. However, when we look for the
coefficient of $u^{r-1}$, we have seen $r-1$
 left--to--right maxima, and the $r$th has value $h$. 
What comes after that is irrelevant and covered by the
factor $1/(1-z)$.
We find it useful to use the abbreviation
$\bb{i}:=1-(1-q^i)z$.
The coefficients of $z^nu^{r-1}$ in $\text{{\sf Value}}(z,u)$, call them 
$\pi ^{(r)}_{n,h}$, are not probabilities, because there exist words of length
$n$ with fewer than $r$     left--to--right maxima,    but 
the quantities
${\pi ^{(r)}_{n,h}}\big/{\pi ^{(r)}_{n}} $
are, 
 where $\pi ^{(r)}_{n}$ is the probability that a string of
length $n$ {\em has\/} 
$r$
left--to--right maxima. We compute
$\pi ^{(r)}_{n}$ from $\text{{\sf Value}}(z,u)$ by
summing over all values $h$;
\begin{equation*}
\pi ^{(r)}_{n}:=[z^nu^{r-1}]\frac{1}{1-z}
\sum_{h\ge1}\prod_{i=1}^{h-1}\left\{
1+\frac{pq^{i-1}zu}{\bb i}\right\}
zpq^{h-1}
=\sum_{h\ge1}\pi ^{(r)}_{n,h}.
\end{equation*}
			 Now we turn to the {\em position.}
Set
\begin{equation*}
\sigma ^{(r)}_{n,j}:=[z^nu^{r-1}v^j]\frac{1}{1-z}\sum_{h\ge1}
\prod_{k=1}^{h-1}\left\{
1+\frac{pq^{k-1}zvu}{1-(1-q^k)zv}\right\}
zvpq^{h-1},
\end{equation*}
then
${\sigma^{(r)}_{n,j}}\big/{\pi ^{(r)}_{n}}$
is the probability that a random string of length $n$ has
the $r$th left--to--right maximum in position $j$. 
It is  the same decomposition as before, however, we are
not interested in the value $h$, so we sum over it. 
On the other hand, we label the position with the variable $v$, 
so we must make sure that every $z$ that does not appear in 
the factor $1/(1-z)$ must be multiplied by a $v$.
 Computationally, we find it easier to work with the parameter
``position~$-r$''.  This leads us to the generating
function
\begin{equation*}
\text{{\sf Position}}(z,u,v):=
\frac{1}{1-z}\sum_{h\ge1}
\prod_{k=1}^{h-1}\left\{
1+\frac{pq^{k-1}zu}{1-(1-q^k)zv}\right\}
zpq^{h-1}.
\end{equation*}
There is no space to develop this further;
for a full account see \cite{KnPr01}.

Now we consider the instance of {\it large\/} left--to--right maxima
(see \cite{Prodinger01d}).
We say that the last left--to--right maximum is the
instance $r=1$, the previous left--to--right maximum
is the instance $r=2$, and so on.   

The largest element in a random permutation of $n$ elements
(which is $n$) is expected to be in the middle.
The second largest is then expected to be in the middle
of the first half, and so on. In general, the average
position should be about ${n}/2^r$. 
The following expression for  
the average value of the $r$th left--to--right
maximum from the right is obtained
as before; just observe that we assume that it
is $h$, and that $r-1$ more left--to--right
maxima follow to the right, whereas  to the left
everything is smaller than $h$:


\begin{align*}
 &\E^{(r)}_{n}
=(-1)^r
\Big(\frac{p}{q}\Big)^{r}
\sum_{k=r}^{n}\binom{n}{k}(-1)^k\times\\&
\times[w^k]
\sum_{1\le h< i_1< \dots <i_{r-1} }\frac{hwq^{h}}{(1-wq^{h-1})(1-wq^{h})}
\frac{q^{i_{1}}w\dots q^{i_{r-1}}w}{
(1-q^{i_{1}}w)\dots(1-q^{i_{r-1}}w)}.\\
\end{align*}
A lengthy study leads to
\begin{equation*}   
\E^{(r)}_n=\log_Qn+\sigma_r+\delta_r(\log_Qn)+o(1),
\end{equation*}
where $\delta_r(x)$ is a small periodic function of\/
$\log_Qn$; the constant $\sigma_r$  is given by
\begin{align*}   
\sigma_r&=\frac{\gamma}{L}+\frac{1}{2}-
p^{r-1}
\sum_{j\ge1}\frac{q^{(j-1)(r-1)}}{(1-q^j)^r}
-{p}
\sum_{j\ge1}
\frac{q^{j}}{(1-q^j)^2}\\&
+p^{r-1}
\sum_{j\ge1}
\frac{q^{j(r-1)}}{(1-q^j)^2(1-q^{j+1})^{r-2}}.
\end{align*}
Turning to the average position of the $r$th left--to--right
maximum from the right we find

\begin{align*}
&\E^{(r)}_n
=(-1)^{r-1}\Big(\frac pq\Big)^r\sum_{k=r+1}^n\binom nk(-1)^k
\times\\&
\times
[w^k]\sum_{1\le h<i_1<\dots <i_{r-1}}
\frac{wq^{h}w(1-q^{h-1})}{(1-wq^{h-1})^2(1-wq^h)}
\frac{wq^{i_{1}}}{1-wq^{i_1}}\dots
\frac{wq^{i_{r-1}}}{1-wq^{i_{r-1}}}
\end{align*}
and
\begin{equation*}   
\E^{(r)}_n=(-1)^r\Big(\frac pq\Big)^{r-1}\psi_r(1)\,n+
\varpi_r(\log_Qn)+o(n),
\end{equation*}
with some complicated constants
and periodic functions.
In the limit $q\to1$ (permutations), this simplifies to
 \begin{equation*}   
\E^{(r)}_n=\frac n{2^r}+o(n).
\end{equation*}

\subsection{Skip lists}

We start from the interpretation of a skip list $\rho$ of size $n$
as a word $\rho=a_1\dots a_{n}$, $n\ge0$,  
 $a_i\in\{1,2,3,\dots\}$.
The (horizontal) path length $X_{n}$ 
is a random variable defined on the  set of words of length $n$.
For an individual word, the path length $b(\rho)$ is
defined as the sum of
all numbers of (weak) right--to--left maxima in the subwords
(prefixes) $a_1,\dots,a_i$. 

For example, consider $21413$. The 
right--to--left maxima when considering  prefixes are
2, 2---1, 4, 4---1, 4---3, given a total of $1+2+1+2+2=8$.

In order to obtain an expression for the 
corresponding probability generating
function  it is convenient to start from the 
following combinatorial decomposition:
        
Let $m$ be the maximal element occuring in $\rho$. Then we can write
$\rho$ in a unique way as
$$
\rho=\sigma m\tau,\quad\text{where}\quad 
\sigma\in\{1,\dots,m-1\}^*,\  \tau\in\{1,\dots,m\}^*
$$
(fixing the leftmost occurence of the maximum $m$). From this decomposition
it follows that
\begin{equation}\label{2.2}
b(\rho)=b(\sigma m\tau)=b(\sigma)+b(\tau)+|\tau|+1,\quad b(\varepsilon)
=0,
\end{equation}
since the contribution of the leftmost maximum 
is 1 plus the number of the succeding elements. 
We introduce the bivariate generating functions $P^{=m}(z,u)$, where
the coefficient of $z^nu^j$ is the probability that a skip list 
$\rho$ with
$n$ elements has maximum element
$m$ and  path length $j$. The generating functions
$P^{\le m}(z,u)$ and $P^{<m}(z,u)$ are defined analogously. Then relation
(\ref{2.2}) translates into the functional equation
\begin{equation}\label{2.3}
P^{=m}(z,u)=pq^{m-1}zuP^{<m}(z,u)P^{\le m}(zu,u),
\quad P^{=0}(z,u)=1.
\end{equation}
Although no simple closed formula for the solution of (\ref{2.3})
is available, it allows to extract sufficient information on the moments
of the path length. 
If we set $F^*(z)=\frac{\partial P^*}{\partial u}(z,1)$, where $*$ stands
for $=m$, $\le m$ or $<m$, the generating function $F(z)=\sum_{n\ge0}
\EE(X_{n})z^n$ of the
{\it expectations} is obtained as
$$
F(z)=\lim_{m\to\infty}F^{\le m}(z).
$$
Performing some algebra one derives
$$
F^{\le m}(z)=\frac pq \frac z{\[m\]^2}\sum_{i=1}^m\frac{q^{i}}{\[i\]}.
$$
Now we let $m$ tend to infinity and obtain
$$
F(z)=\frac pq\frac 
z{(1-z)^2}\sum_{i\ge1}\frac{q^i}{\[i\]}.
$$
The generating function $H(z)$ of the second factorial moments can be
obtained in the same way, although the computations are much more 
involved, see \cite{KiPr94}.
 It is, however, 
 not too complicated to  find the coefficients in
  $F(z)$:
\begin{alignat*}{1}
\EE(X_{n})&=[z^{n}]F(z)=\frac pq\sum_{i\ge1}\left[
-Q^i+n+1+ Q^i\left(1-q^i\right)^{n+1}
\right]\\
&\phantom{ =[z^{n-1}]F(z) }\;=\frac pq
\sum_{k=2}^{n+1}\binom{n+1}k(-1)^k\frac{1}{Q^{k-1}-1}\\
&=(Q-1)n\Big(\log_Qn+\frac{\gamma-1}{L}-\frac12+\frac 1L
\delta_1(\log_Qn)\Big)+O(\log n)
\end{alignat*}
where $\gamma$ is Euler's constant and
$
\delta_1(x)=\sum_{k\ne0}\Gamma(-1-\frac{2k\pi i}{L})e^{2k\pi ix}
$
is a continuous periodic function of period 1
and mean zero. 






\section{Representations of numbers}


\subsection{Complex bases}



There are representations of numbers that are perhaps
not very well known, see e.\;g. \cite{GrKiPr98}. For
easier readability, we describe only a special case. 
Every Gaussian integer $z\in\ZZ[i] $ (of the form
$z=x+iy$, with $x,y\in\ZZ$) can be uniquely written as
\begin{equation*}
\sum_{k=0}^n\eps_k(-2+i)^k,\quad\text{with}\quad
\eps_k\in\{0,1,2,3,4\}.
\end{equation*}
The minimal polynomial of $-2+i$ is $x^2+4x+5$.
As a consequence, $145=0$, and there is the carry
rule $5=1310$. So if one wants to add $2041$ and
$4432$, one takes $6473$, uses the carry rule to get
$19523$ and the reduction rule to get $5023$, and
eventually $1310023$. Or, one applies the reduction
rule earlier, to get $5023$ from $6473$.

The digits can be computed as follows: Define 
\begin{equation*}
s_{k+1}=-4\fl{\frac{s_k}{5}}-\fl{\frac{s_{k-1}}{5}},
\ k\ge0,\ \ s_{-1}=-5y, \ s_0=x+2y,
\end{equation*}
then the $k$th digit is given by $s_k\bmod5$.

Addition of 1 (or any fixed number) can be described by
a {\em transducer}; digits are read from right to left,
and eventually one of the two states marked by $\bullet$
are reached, where the convention is that all digits not
read so far are simply copied.  The states represent the
possible carries. 


\begin{figure}[h]
%\input london.pic
\hskip0.8cm
\unitlength 0.7mm
\linethickness{0.4pt}
\begin{picture}(138.27,93.00)
\put(38.00,8.00){\circle{6.00}}
\put(107.00,8.00){\circle{6.00}}
\put(107.00,77.00){\circle{6.00}}
\put(38.00,77.00){\circle{6.00}}
\put(73.00,56.00){\circle{6.00}}
\put(73.00,29.00){\circle{6.00}}
\put(41.00,77.00){\vector(1,0){62.67}}
\put(107.33,74.33){\vector(0,-1){63.67}}
\put(104.00,8.00){\vector(-1,0){62.67}}
\put(38.00,10.67){\vector(0,1){63.33}}
\put(105.00,75.00){\vector(-3,-2){28.33}}
\put(70.33,55.33){\vector(-3,2){30.00}}
\put(39.67,10.33){\vector(2,1){31.67}}
\put(75.33,27.67){\vector(3,-2){29.00}}
\put(70.67,31.00){\vector(0,1){22.67}}
\put(75.00,54.33){\vector(0,-1){22.67}}
\put(110.33,8.00){\vector(1,0){21.00}}
%\put(131.33,8.00){\vector(0,0){0.00}}
\put(35.00,77.00){\vector(-1,0){21.33}}
\put(9.33,77.00){\circle*{5.20}}
\put(135.67,8.00){\circle*{5.20}}
\put(38.33,92.33){\vector(0,-1){10.00}}
\put(22.00,93.00){\makebox(0,0)[cc]{$0|1$}}
\put(22.00,87.00){\makebox(0,0)[cc]{$1|2$}}
\put(22.00,80.67){\makebox(0,0)[cc]{$2|3$}}
\put(22.00,72.00){\makebox(0,0)[cc]{$3|4$}}
\put(71.00,82.33){\makebox(0,0)[cc]{$4|0$}}
\put(26.67,41.67){\makebox(0,0)[cc]{$0|4$}}
\put(118.00,42.33){\makebox(0,0)[cc]{$4|0$}}
\put(70.67,2.00){\makebox(0,0)[cc]{$0|4$}}
\put(82.33,47.00){\makebox(0,0)[cc]{$2|0$}}
\put(82.33,42.33){\makebox(0,0)[cc]{$3|1$}}
\put(82.33,37.33){\makebox(0,0)[cc]{$4|2$}}
\put(63.67,47.00){\makebox(0,0)[cc]{$0|2$}}
\put(63.67,42.33){\makebox(0,0)[cc]{$1|3$}}
\put(63.67,37.33){\makebox(0,0)[cc]{$2|4$}}
\put(47.00,64.67){\makebox(0,0)[cc]{$0|3$}}
\put(52.67,59.33){\makebox(0,0)[cc]{$1|4$}}
\put(98.67,65.00){\makebox(0,0)[cc]{$0|1$}}
\put(93.00,59.67){\makebox(0,0)[cc]{$1|2$}}
\put(90.33,72.00){\makebox(0,0)[cc]{$2|3$}}
\put(82.67,65.67){\makebox(0,0)[cc]{$3|4$}}
\put(45.33,18.67){\makebox(0,0)[cc]{$1|0$}}
\put(56.67,23.00){\makebox(0,0)[cc]{$2|1$}}
\put(53.67,13.00){\makebox(0,0)[cc]{$3|2$}}
\put(63.67,18.33){\makebox(0,0)[cc]{$4|3$}}
\put(88.00,24.67){\makebox(0,0)[cc]{$3|0$}}
\put(96.00,19.00){\makebox(0,0)[cc]{$4|1$}}
\put(121.67,2.67){\makebox(0,0)[cc]{$4|3$}}
\put(121.67,12.00){\makebox(0,0)[cc]{$3|2$}}
\put(121.67,18.00){\makebox(0,0)[cc]{$2|1$}}
\put(121.67,24.00){\makebox(0,0)[cc]{$1|0$}}
\end{picture}
\end{figure}


The paper \cite{GrKiPr98} deals also with the sum--of--digits
function (defined in an obvious way), and {\it fundamental regions}.
Each complex number has a representation in this system, of the form
$\sum_{k=-\infty}^n\eps_k(-2+i)^k$, which is in general unique;
only ``a few'' numbers have 2 or even 3  representations. (This is
akin to the base  10 representation, where $1=0.9999\dots\,$.)

\subsection{Redundant representations}

The paper \cite{prodinger162} is based on the Paul system, which
is to the base 2, with digits in $\{-1,0,1\}$, and no two adjacent
nonzero digits. This leads to unique representations, see
\cite{m_paul}. However, it was later found out that this
system was rediscovered many times. Probably the first appearance
is in \cite{Reitwiesner60}.
 Let us write $\1=-1$ for convenience. It was found out that
the $k$-th digit is given by

\begin{equation*}
a_k(n)=1\Longleftrightarrow
\left\lfloor\frac{n}
{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{4}{6} \right\rfloor=1
\end{equation*}
and

\begin{equation*}
a_k(n)=\1\Longleftrightarrow
\left\lfloor\frac{n}
{2^{k+2}}+\frac{2}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{1}{6} \right\rfloor=1.
\end{equation*}
If the expressions on the right hand sides are not 1, they must be 0.
Consequently we have the formula
\begin{equation*}
n=\sum_{k\ge0}\left(
\left\lfloor\frac{n}{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{4}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+2}}+\frac{2}{6} \right\rfloor+
\left\lfloor\frac{n}
{2^{k+2}}+\frac{1}{6} \right\rfloor
\right)2^k.
\end{equation*}
The key formula (see \cite[1.2.4, Ex.~38]{Knuth68})
to manipulate such floor functions is


\begin{equation}\label{keyformula}
\lfloor x\rfloor+\lfloor x+\tfrac1q\rfloor+\dots+
\lfloor x+\tfrac{q-1}{q}\rfloor=\lfloor qx\rfloor,
\end{equation}
where $q$ is an integer $\ge1$ and $x$ a real number.
We can now consider the
binary representation of $\lambda n$, for a natural number
$\lambda$: The $k$th digit is given by
\begin{equation*}
a_k(\lambda n)=\sum_{i=0}^{2\lambda-1}
\left\lfloor\frac{n}{2^{k+1}}+\frac{i}{2\lambda} \right\rfloor
(-1)^{i-1};
\end{equation*}
this follows from 
\begin{equation*}
\lambda n=\sum_{k\ge0}2^k\left(
\left\lfloor\frac{\lambda n}{2^{k}} \right\rfloor
-2\left\lfloor\frac{\lambda n}{2^{k+1}} \right\rfloor
\right)
\end{equation*}
and the formula (\ref{keyformula}).
From this it follows that the representation investigated
by Reitwiesner, Paul and others is simply obtained as follows:
One computes the ordinary representations of $3n/2$ and of
$n/2$ and takes the bitwise difference!
For example, $25=(11001)_2$, and $\frac32\cdot 25=37.5=(100101.1)_2$,
$\frac12\cdot 25=12.5=(1100.1)_2$, and the bitwise difference is
$10\1001$, which is the representation of $25$.
Clearly, the result is a representation of $n$  in
base 2 using digits $-1,0,1$. An obvious generalization is
to consider $n=(\al+1)n-\al n$ and take the bitwise differences
of the two representations.
We  analyzed only the case that $\al$ is either an integer
or an integer divided by a power of 2 (a dyadic rational number).
Here is one example:

\begin{align*}
a_k&(4n)-a_k(3n)=\\
&=\left\lfloor\frac{n}{2^{k+1}}+\frac{7}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{5}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{6}{8} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{4}{6} \right\rfloor\\
&
+\left\lfloor\frac{n}{2^{k+1}}+\frac{5}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{4}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{3}{6} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{3}{8} \right\rfloor\\
&
+\left\lfloor\frac{n}{2^{k+1}}+\frac{2}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{2}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{6} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{8} \right\rfloor.
\end{align*}
We discuss now a few syntactical properties.
In \cite{m_paul} the rewriting rules
$$
1\1\longrightarrow01 \qquad\1 1\longrightarrow0\1 \qquad
011\longrightarrow10\1 \qquad
0\1\1\longrightarrow\1 01
$$
are presented, that can be (repeatedly) applied in any order to
transform the standard binary representation of $n\in\mathbb N$
into the ``$3n/2-n/2$'' representation. We say ``repeatedly'' because of
a problem with carries; the following example explains what happens:

$$
01111
\longrightarrow
10\1 11
\longrightarrow
100\1 1
\longrightarrow
1000\1.
$$

A more ``algorithmic'' version is by the following {\it transducer.}
It reads the  binary representation of $n$ from right to left
(leading zeros must be added if needed). 
Of course, the output is also produced from right to left. 
The basic idea is to transform
$01^k$
into $10^{k-1}\1$ for $k\ge2$.
 However, if the next group (to the left) starts
immediately with $1$, then we can't output the leading 1; it is then
a carry, belonging to the next group.
To make sure that the transduction ends in the starting state
(as it should), we
can add two leading zeros (see Figure~1).


\begin{figure}[h]\label{paul1a}
\hskip1.4cm
%\input paul1aa.pic
\unitlength 0.6mm
\linethickness{0.7pt}
\begin{picture}(122.67,65.33)
\put(55.00,44.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(96.00,44.00){\circle{6.00}}
\put(96.00,10.00){\circle{6.00}}
\put(67.67,57.33){\makebox(0,0)[cc]{$0|0$}}
\put(78.33,49.67){\makebox(0,0)[cc]{$0|01$}}
\put(37.00,29.67){\makebox(0,0)[cc]{$1|\eps$}}
\put(68.33,36.67){\makebox(0,0)[cc]{$0|01$}}
\put(79.33,23.00){\makebox(0,0)[cc]{$1|\eps$}}
\put(75.00,3.00){\makebox(0,0)[cc]{$1|0\1$}}
\put(102.67,32.33){\makebox(0,0)[cc]{$0|\eps$}}
\put(122.67,18.00){\makebox(0,0)[cc]{$1|0$}}
\put(40.33,44.33){\makebox(0,0)[cc]{$\longrightarrow$}}
\put(92.67,44.00){\vector(-1,0){34.67}}
\put(95.33,41.00){\vector(-4,-3){37.67}}
\put(96.00,12.67){\vector(0,1){28.00}}
\put(58.33,9.67){\vector(1,0){34.33}}
\bezier{120}(99.00,8.67)(117.33,3.67)(118.33,14.67)
%\bezvec{152}(118.33,14.33)(115.00,28.33)(97.33,13.00)
\put(97.33,13.00){\vector(-1,-1){0.2}}
\bezier{152}(118.33,14.33)(115.00,28.33)(97.33,13.00)
%\end
\bezier{120}(56.33,46.67)(67.33,62.67)(57.00,63.67)
%\bezvec{132}(57.67,63.67)(45.00,65.33)(53.67,47.00)
\put(53.67,47.00){\vector(1,-3){0.2}}
\bezier{132}(57.67,63.67)(45.00,65.33)(53.67,47.00)
%\end
\put(57.00,12.67){\vector(0,1){28.67}}
\put(53.00,41.67){\vector(0,-1){28.67}}
\end{picture}


\caption{The binary $\to$ ``$3n/2-n/2$'' transformer}
\end{figure}

When dealing with number systems, it is usually very instructive
to see how the number $1$ can be added. This can normally be done
by an automaton. 
The word is processed from right to left. If no continuation is
defined, the rest of the word is left unchanged. Again, possibly
leading zeros are needed to lead to one of the accepting states
to the right. The output is also recorded from right to left, usually
replacing only a suffix of the word (representation of a number),
when reaching one of the two states to the right.

\begin{figure}[h]\hskip2cm\label{addone}
\hskip0.5cm
\unitlength 0.6mm
\linethickness{0.7pt}
\begin{picture}(140.67,57.00)
\put(116.67,54.00){\circle{6.00}}
\put(34.67,16.00){\circle{6.00}}
\put(77.67,17.00){\circle{6.00}}
\put(137.67,17.00){\circle{6.00}}
\put(32.67,40.00){\makebox(0,0)[cc]{$1|\eps$}}
\put(80.33,35.67){\makebox(0,0)[cc]{$0|\eps$}}
\put(55.67,29.00){\makebox(0,0)[cc]{$0|0$}}
\put(55.33,2.33){\makebox(0,0)[cc]{$1|\1$}}
\put(102.00,47.67){\makebox(0,0)[cc]{$\1|0$}}
\put(122.00,21.67){\makebox(0,0)[cc]{$0|01$}}
\put(122.00,10.67){\makebox(0,0)[cc]{$\1|0\1$}}
\put(56.67,54.00){\circle{6.00}}
\put(42.00,53.67){\makebox(0,0)[cc]{$\longrightarrow$}}
\put(59.67,54.00){\vector(1,0){54.00}}
\put(53.67,53.00){\vector(-1,-2){17.17}}
\put(59.33,53.33){\vector(1,-2){16.33}}
\put(80.67,16.67){\vector(1,0){54.00}}
%\bezvec{192}(37.67,16.67)(56.00,32.67)(74.67,17.67)
\put(74.67,17.67){\vector(4,-3){0.2}}
\bezier{192}(37.67,16.67)(56.00,32.67)(74.67,17.67)
%\end
%\bezvec{200}(75.00,15.67)(58.67,-1.33)(37.67,14.67)
\put(37.67,14.67){\vector(-3,2){0.2}}
\bezier{200}(75.00,15.67)(58.67,-1.33)(37.67,14.67)
%\end
\end{picture}


%\input paul3aa.pic
\caption{Adding 1 in the ``$3n/2-n/2$'' representation}
\end{figure}



Now let us consider a few properties of the system induced by
writing $n=5n/4-n/4$:
First, we describe the syntactically correct words. If
$B=1+\1+ 11(\11)^*(\eps+\1)+ \1\1(1\1)^*(\eps+1)$,
then the possible representations are given by
$\eps+(B000^*)^*B0^*$.
It is also possible to give a complete set
of rewriting rules, but, again, an automaton (transducer)
is more instructive:
Input are natural numbers, written in ordinary binary notation.
The computation ends in the starting state.


\begin{figure}[h]
\hskip1.5cm
%\input paul2aa.pic
\unitlength 0.60mm
\linethickness{0.7pt}
\begin{picture}(157.67,71.33)
\put(77.00,44.00){\circle{6.00}}
\put(132.00,45.00){\circle{6.00}}
\put(53.00,14.00){\circle{6.00}}
\put(107.00,14.00){\circle{6.00}}
%links 1
%rechts 1. Teil
\put(31.00,60.33){\makebox(0,0)[cc]{$0|0$}}
\put(121.00,60.33){\makebox(0,0)[cc]{$1|0$}}
\put(56.67,50.67){\makebox(0,0)[cc]{$1|\eps$}}
\put(93.67,50.67){\makebox(0,0)[cc]{$0|\eps$}}
\put(28.00,26.00){\makebox(0,0)[cc]{$0|001$}}
\put(60.67,31.67){\makebox(0,0)[cc]{$0|\eps$}}
\put(100.33,31.67){\makebox(0,0)[cc]{$1|\eps$}}
\put(129.00,26.00){\makebox(0,0)[cc]{$1|00\1$}}
\put(77.67,25.33){\makebox(0,0)[cc]{$0|1$}}
\put(77.67,2.33){\makebox(0,0)[cc]{$1|\1$}}
\put(126.33,33.33){\line(0,0){0.00}}
\put(25.00,45.00){\circle{6.00}}
\put(20.00,37.00){\makebox(0,0)[cc]{$\nearrow$}}
\put(129.00,44.33){\vector(-1,0){48.00}}
\put(28.00,44.67){\vector(1,0){45.67}}
\put(109.67,14.33){\vector(3,4){21.00}}
\put(51.00,16.33){\vector(-1,1){25.67}}
\put(75.00,42.00){\vector(-3,-4){19.25}}
\put(79.33,42.00){\vector(1,-1){26.00}}
\bezier{160}(22.00,44.00)(-1.33,50.33)(10.00,61.67)
%\bezvec{160}(9.33,61.33)(22.33,71.33)(25.00,47.67)
\put(25.00,47.67){\vector(0,-1){0.2}}
\bezier{160}(9.33,61.33)(22.33,71.33)(25.00,47.67)
%\end
\bezier{160}(131.33,47.67)(128.67,70.00)(143.33,61.33)
%\bezvec{164}(143.00,61.67)(157.67,52.33)(135.33,45.33)
\put(135.33,45.33){\vector(-3,-1){0.2}}
\bezier{164}(143.00,61.67)(157.67,52.33)(135.33,45.33)
%\end
%\bezvec{220}(104.00,15.00)(77.67,28.33)(55.67,15.00)
\put(55.67,15.00){\vector(-2,-1){0.2}}
\bezier{220}(104.00,15.00)(77.67,28.33)(55.67,15.00)
%\end
%\bezvec{212}(56.00,12.67)(77.33,1.00)(104.00,11.67)
\put(104.00,11.67){\vector(3,1){0.2}}
\bezier{212}(56.00,12.67)(77.33,1.00)(104.00,11.67)
%\end
\end{picture}
\caption{The binary $\to$ ``$1=5/4-1/4$'' transformer}
\end{figure}

\subsection{Minimal representations}
Motivated by algorithms on elliptic curves, in \cite{HePr01}
representations of an integer $n$ 
in base $q\ge 2$
with arbitrary digits are again studied;
set
\begin{equation*}
  R_q(n):=\Big\{\eps=(\eps_0,\dots,\eps_l)
\,\Bigm\vert\, l\in\NN,\, \eps_i\in\ZZ,\,
  n=\sum_{i=0}^l \eps_iq^i\Big\}.
\end{equation*}
We define the \emph{cost of a representation} $\eps\in R_q(n)$ as
\begin{equation*}
  c(\eps)=c(\eps_0,\dots,\eps_l):=l+1+\sum_{i=0}^l |{\eps_i}|
\end{equation*}
and look for representations of $n$ with minimum cost.
The modified cost
function, which we will call \emph{relaxed costs,} namely
\begin{equation*}
  c'(\eps)=c'(\eps_0,\dots,\eps_l):=\sum_{i=0}^l |{\eps_i}|
\end{equation*}
is more natural and easier to study.

We note that in general there is no unique minimal representation:
Both $(-1,2)\in R_3(5)$ and $(2,1)\in R_3(5)$ are representations of $5$ in
base $3$ with cost $c(-1,2)=c(2,1)=5$.
We will describe a
special minimal representation (``reduced representation''),
which is unique. In \cite{HePr01}
there is a full set of
conversion rules between the two 
minimal representations relative to the two types 
of costs. Although they have a language theoretic
flavour, they cannot be included here.

In \cite{HePr01} we are able to derive
 an explicit formula for the digits of the reduced representation 
in the case of
odd and even $q$, respectively. These formul\ae{} are very useful
 for the
computation of the frequencies of digits and the expected costs of the
representations.
  Let $q\ge 3$ be odd and $n$ be a positive integer. Let
  $$\eps_r:=b_q^{(r)}(2n)-b_q^{(r)}(n), \qquad r\ge 0,$$
  where $b_q^{(r)}(n)$ is   
  the $r$-th digit of the ``usual'' $q$-adic expansion of $n$, i.\;e. 
  $$b_q^{(r)}(n)=\fl{\frac{n}{q^r}}-q\fl{\frac{n}{q^{r+1}}},$$ 
  and $l:=\max\{r\ge 0\mid \eps_r\neq 0\}$.
  Then $\eps=(\eps_0,\dots,\eps_l)$
  is the relaxed reduced minimal representation.
The formula for  $q\ge 2$  even is more complicated:
  For $r\ge 0$ define
  \begin{equation*}
  \begin{aligned}
    \eps_r:=\sum_{i=0}^{q/2-1}\Biggl(
    \sum_{j=0}^{q/2-1} &\fl {\frac{n}{q^{r+2}}+ \frac{1+\frac
        q2+(q+1)(iq+j)}{q^2(q+1)}}\\
    -(q-1)&\fl{\frac{n}{q^{r+2}}+\frac{\frac{q}2+(q+1)(iq+q/2)}{q^2(q+1)}}\\
    +\sum_{j=q/2+1}^{q-1} &\fl{\frac{n}{q^{r+2}}+\frac{\frac{q}2+(q+1)(iq+j)}{q^2(q+1)}}\Biggr)\\
    +\sum_{i=q/2}^{q-1}\Biggl(
    \sum_{j=0}^{q/2-2} &\fl {\frac{n}{q^{r+2}}+ \frac{1+\frac
        q2+(q+1)(iq+j)}{q^2(q+1)}}\\
    -(q-1)&\fl{\frac{n}{q^{r+2}}+\frac{1+\frac{q}2+(q+1)(iq+q/2-1)}{q^2(q+1)}}\\
    +\sum_{j=q/2}^{q-1} &\fl{\frac{n}{q^{r+2}}+\frac{\frac{q}2+(q+1)(iq+j)}{q^2(q+1)}}\Biggr).
  \end{aligned}
  \end{equation*}
  Let $l:=\max\{r\ge 0\mid \eps_r\neq 0\}$. 
  Then $\eps=(\eps_0,\dots,\eps_l)\in R_q(n)$
  is the relaxed reduced minimal representation.
We make that explicit for $q=2$:
  \begin{equation*}
    \eps_r=\fl{\frac{n}{2^{r+2}}+\frac56}-
    \fl{\frac{n}{2^{r+2}}+\frac46}-
    \fl{\frac{n}{2^{r+2}}+\frac26}+
    \fl{\frac{n}{2^{r+2}}+\frac16},
  \end{equation*}
so we see that it is the representation studied by Reitwiesner
and others.

It is also possible to formulate a simple algorithm to create
the representation of an integer $m$: Consider $a\equiv m\bmod q$,
and take a representative in the interval $-q/2\le a\le q/2$.
In case, a decision has to be made whether to take $a=-q/2$
or $a=q	/2$. It is based on the fractional part of $m/q^2$:
if $\{m/q^2\}<1/2$ then take $a=q/2$. Continue with $m\leftarrow 
(m-a)/q$. This rule makes the system balanced.

We are also interested  to count how often a given digit $i$ occurs in 
the relaxed
reduced expansion
among the numbers $1$, $\dots$, $n$; call that
$\#_i(n)$. 
In the case $q$ odd, 
the reduced representation is actually the $(q,d)$ representation,
with $d=-\frac{q-1}{2}$, and digits $d,d+1,\dots,d+q-1$.
(For example, $32\101$ with base 4 represents 
$3\,4^4+2\,4^3-4^2+1=881$.)
Digit counting in this representation is well known, see
\cite{KiPr84}. Every digit occurs with the same frequency 
$\frac{1}{q}$, and
\begin{equation*}
\#_i(n)=\frac{1}{q}n\log_qn+\mathcal{O}(n).
\end{equation*}
Actually, more is known about the error term. It can
be made fully explicit and is basically given by $n$ times
a periodic function in $\log_qn$.
 From that we get the average value of $c'(\eps)$. It is
\begin{equation*}   
\left(\frac{q}{4}-\frac{1}{4q}\right)\log_qn+\mathcal{O}(1).
\end{equation*}     
In the instance $q$ even, things are a bit more complicated; digit
$0$ occurs with frequency $\frac{q+2}{q(q+1)}$, digits $\pm1,\dots, \pm \frac
q2-1$ with frequency $\frac{1}{q}$, digits $\pm\frac{q}{2}$ each with frequency
$\frac{1}{2(q+1)}$.  So we see that digit $0$ appears a bit more often than the
other digits, and the digits $\pm\frac{q}{2}$ (combined) appear a bit less
often than the other digits. 
This leads to
\begin{align*}
\#_0(n)&=\frac{q+2}{q(q+1)}n\log_qn+\mathcal{O}(n),\\
\#_i(n)&=\frac{1}{q}n\log_qn+\mathcal{O}(n),
&&\text{for $i= \pm1,\dots, \pm \frac q2-1$},\\
\#_i(n)&=\frac{1}{2(q+1)}n\log_qn+\mathcal{O}(n),
&&\text{for $i=\pm \frac q2$}.\\
\end{align*}
Summing this, (multiplied by $|i|$), 
over all possible digits $i$, we get the
average value of $\sum|\eps_i|$:

\begin{equation*}   
\left(\frac{q}{4}-\frac{1}{2(q+1)}\right)\log_qn+\mathcal{O}(1).
\end{equation*}     





\subsection{Representations in the sense of Morain and Olivos}
The representation of $n$ in base 2, with digits $-1,0,1$, where
no two adjacent nonzero digits are adjacent, has the lowest number
of nonzero digits (roughly speaking, the
probability that a random digit is different
from zero, is $\frac13$). As we have seen, it can be obtained by
repeated applications of replacement rules. 
Morain and Olivos in \cite{MoOl90}, see also \cite{Thuswaldner99},
consider the simpler version, where all occurrences $1^a$
($a\ge2$, and the block is rendered by zeros) are simultaneously
 replaced by $10^{a-1}\1$. For example, $11011$ is transformed
into $10\110\1$. This Morain/Olivos representation of natural
numbers does not take care of carries (but they also consider
them, in a second algorithm). However, it is also possible to 
give explicit formul{\ae} for the digits:
\begin{equation*}
a_0(n)=\fl{\frac{n}{4}+\frac{3}{4}}-
\fl{\frac{n}{4}+\frac{2}{4}}-
\fl{\frac{n}{4}+\frac{1}{4}}+
\fl{\frac{n}{4}+\frac{0}{4}},
\end{equation*}



\begin{equation*}
a_1(n)=\fl{\frac{n}{8}+\frac{6}{8}}-
\fl{\frac{n}{8}+\frac{5}{8}}-
\fl{\frac{n}{8}+\frac{2}{8}}+
\fl{\frac{n}{8}+\frac{1}{8}},
\end{equation*}
and for $k\ge2$




\begin{align*}
a_k(n)&=\fl{\frac{n}{2^{k+2}}+\frac{13}{16}}
-\fl{\frac{n}{2^{k+2}}+\frac{10}{16}}\\&
+\fl{\frac{n}{2^{k+2}}+\frac{5}{16}}
-2\fl{\frac{n}{2^{k+2}}+\frac{4}{16}}
+\fl{\frac{n}{2^{k+2}}+\frac{2}{16}}.
\end{align*}
A rigorous proof of that is probably unpleasant but
doable as in \cite{HePr01}.

From this it follows that the number of nonzero
digits $\sigma(n) $ in the Morain/Olivos
representation is given by
\begin{align*}
&\sigma(n)=\fl{\frac{n}{4}+\frac{3}{4}}-
\fl{\frac{n}{4}+\frac{2}{4}}+
\fl{\frac{n}{4}+\frac{1}{4}}-
\fl{\frac{n}{4}+\frac{0}{4}}\\
&+\fl{\frac{n}{8}+\frac{6}{8}}-
\fl{\frac{n}{8}+\frac{5}{8}}+
\fl{\frac{n}{8}+\frac{2}{8}}-
\fl{\frac{n}{8}+\frac{1}{8}}\\
&+\sum_{k\ge2}\Bigg\{
\fl{\frac{n}{2^{k+2}}+\frac{13}{16}}
-\fl{\frac{n}{2^{k+2}}+\frac{10}{16}}
+\fl{\frac{n}{2^{k+2}}+\frac{5}{16}}
-\fl{\frac{n}{2^{k+2}}+\frac{2}{16}}
\Bigg\},
\end{align*}
and therefore
\begin{align*}
&\sum_{n<N}\sigma(n)=\fl{\frac{N}{2}}+
\fl{\frac{N+1}{4}}\\
&+\sum_{n<N}\sum_{k=2}^{l+2}\Bigg\{
\fl{\frac{n}{2^{k+2}}+\frac{13}{16}}
-\fl{\frac{n}{2^{k+2}}+\frac{10}{16}}
+\fl{\frac{n}{2^{k+2}}+\frac{5}{16}}
-\fl{\frac{n}{2^{k+2}}+\frac{2}{16}}
\Bigg\},
\end{align*}
with $l=\log_2N$. Now we use Delange's
approach \cite{Delange75} to develop
that further (this leads to a more elementary
computation than Thuswaldner's in \cite{Thuswaldner99}). 
Define
\begin{equation*}   
g(x)=\int_0^x
\Bigg\{
\fl{t+\frac{13}{16}}
-\fl{t+\frac{10}{16}}
+\fl{t+\frac{5}{16}}
-\fl{t+\frac{2}{16}}
-\frac{3}{8}\Bigg\}dt,
\end{equation*}
then
\begin{align*}
\sum_{n<N}\sigma(n)&=\frac{3N}{4}+\mathcal{O}(1)+\frac{3}{8}(\fl l+1)
+\sum_{k=2}^{\fl{l}+2}
2^{k+2}g\Big(
\frac{N}{2^{k+2}}\Big)\\
&=\frac{3N}{4}+\mathcal{O}(1)+\frac{3}{8}\log_2N+
\frac{3}{8}(1-\{\log_2N\})\\
&+N2^{2-\{\log_2N\}}\sum_{r\ge0}
2^{-r}g(2^{\{\log_2N\}-2+r}).
\end{align*}
Defining
\begin{equation*}   
H(x)=\frac{3}{4}+
\frac{3}{8}(1-\{x\})+2^{2-\{x\}}\sum_{r\ge0}
2^{-r}g(2^{\{x\}-2+r}),
\end{equation*}
which is periodic with period 1, we find that
the average of $\sigma(n)$ is given by
\begin{equation*}   
\frac{1}{N}\sum_{n<N}\sigma(n)=\frac{3}{8}\log_2N+
H(\log_2N)+\mathcal{O}\Big(\frac{1}{N}\Big).
\end{equation*} 
One can compute the Fourier coefficients of $H(x)$,
which we omit because of lack of space. The formula should
be compared with the $\sim\frac{1}{3}\log_2N+
F(\log_2N)$  formula in the Reitwiesner instance. 
So the more sophisticated algorithm brings the constant
down from $\frac{3}{8}$ to $\frac{1}{3}$.




\bibliographystyle{plain}
%\bibliography{C:/texfiles2001/pro_bib}

\begin{thebibliography}{10}

\bibitem{Carlitz73}
L.~Carlitz.
\newblock Permutations with prescribed pattern.
\newblock {\em Math. Nachr.}, 58:31--53, 1973.

\bibitem{Carlitz75}
L.~Carlitz.
\newblock A combinatorial property of $q$--{E}ulerian numbers.
\newblock {\em American Mathematical Monthly}, 82:51--54, 1975.

\bibitem{Delange75}
H.~Delange.
\newblock Sur la fonction sommatoire de la fonction somme des chiffres.
\newblock {\em Enseignement Math\'ematique}, 21:31--47, 1975.

\bibitem{GrKiPr98}
P.~Grabner, P.~Kirschenhofer, and H.~{P}rodinger.
\newblock The sum--of--digits function for complex bases.
\newblock {\em J. London Math. Soc.}, 57:20--40, 1998.

\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics (Second Edition)}.
\newblock Addison Wesley, 1994.

\bibitem{m_paul}
U.~G{\"u}ntzer and M.~Paul.
\newblock Jump interpolation search trees and symmetric binary numbers.
\newblock {\em Information Processing Letters}, 26:193--204, 1987/88.

\bibitem{HePr01}
C.~Heuberger and H.~Prodinger.
\newblock On minimal expansions in redundant number systems: Algorithms and
  quantitative analysis.
\newblock {\em Computing}, 2001.

\bibitem{KiPr84}
P.~Kirschenhofer and H.~{Prodinger}.
\newblock Subblock occurrences in positional number systems and {G}ray code
  representation.
\newblock {\em Journal of Information and Optimization Sciences}, 5:29--42,
  1984.

\bibitem{KiPr94}
P.~Kirschenhofer and H.~{P}rodinger.
\newblock The path length of random skip lists.
\newblock {\em Acta Informatica}, 31:775--792, 1994.

\bibitem{KnPr01}
A.~Knopfmacher and H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables: Value
  and position of the $r$th left-to-right maximum.
\newblock {\em Discrete Mathematics}, 226:255--267, 2001.

\bibitem{Knuth68}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 1: Fundamental
  Algorithms.
\newblock Addison-Wesley, 1968.
\newblock Third edition, 1997.

\bibitem{Knuth98}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
  Searching.
\newblock Addison-Wesley, 1973.
\newblock Second edition, 1998.

\bibitem{LoPr01}
G.~Louchard and H.~Prodinger.
\newblock Ascending runs of sequences of geometrically distributed random
  variables: a probabilistic analysis.
\newblock {\em submitted}, 2001.

\bibitem{MoOl90}
F.~Morain and J.~Olivos.
\newblock Speeding up the computations on an elliptic curve using
  addition-subtraction chains.
\newblock {\em RAIRO Inform. Th\'eor. Appl.}, 24(6):531--543, 1990.

\bibitem{Prodinger93b}
H.~Prodinger.
\newblock Combinatorial problems of geometrically distributed random variables
  and applications in computer science.
\newblock In V.~Strehl and R.~K{\"o}nig, editors, {\em Publications de l'IRMA
  (Stra\ss bourg) ($=$S\'eminaire Lotharingien de Combinatoire)}, volume~30,
  pages 87--95, 1993.

\bibitem{Prodinger96c}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables:
  Left-to-right maxima.
\newblock {\em Discrete Mathematics}, 153:253--270, 1996.

\bibitem{Prodinger01b}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables:
  {I}nversions and a parameter of {K}nuth.
\newblock {\em Annals of Combinatorics, to appear}, 2001.

\bibitem{Prodinger00c}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables:
  {L}engths of ascending runs.
\newblock {\em LATIN2000, Lecture Notes in Computer Science 1776}, pages
  473--482, 2000.

\bibitem{Prodinger00b}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables: New
  $q$--tangent and $q$--secant numbers.
\newblock {\em International Journal of Mathematical Sciences}, 24:825--838,
  2000.

\bibitem{prodinger162}
H.~Prodinger.
\newblock On binary representations of integers with digits $-1$, $0$, $1$.
\newblock {\em Integers}, pages A8, 14 pp. (electronic), 2000.

\bibitem{Prodinger01d}
H.~Prodinger.
\newblock Combinatorics of geometrically distributed random variables: Value
  and position of large left-to-right maxima,
\newblock {\em submitted}, 2000.

\bibitem{Reitwiesner60}
G.~Reitwiesner.
\newblock Binary arithmetic.
\newblock {\em Vol.~1 of Advances in Computers, Academic Press}, pages
  231--308, 1960.

\bibitem{Thuswaldner99}
J.~Thuswaldner.
\newblock Summatory functions of digital sums occurring in {Cryptography}.
\newblock {\em Periodica Math. Hungarica}, 38:111--130, 1999.

\bibitem{Wilf95}
H.~Wilf.
\newblock On the outstanding elements of permutations, 1995,\\
\newblock {\em {\tt http://www.cis.upenn.edu/$\sim$wilf}}.

\end{thebibliography}


\end{document}



