\magnification=\magstep1
\input amstex
%\input kratt

 \catcode`\@=11 \newif\iftab@\tab@false \newif\ifvtab@\vtab@false
\def\tab{\bgroup\tab@true\vtab@false\vst@bfalse\Strich@false%
   \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}
   \edef\l@{\the\leftskip}\ialign\bgroup\hskip\l@##\hfil&&##\hfil\cr}
\def\endtab{\cr\egroup\egroup}
\def\vtab{\vtop\bgroup\vst@bfalse\vtab@true\tab@true\Strich@false%
   \bgroup\def\\{\cr}\ialign\bgroup&##\hfil\cr}
\def\endvtab{\cr\egroup\egroup\egroup}
\def\stab{\D@cke0.5pt\null 
 \bgroup\tab@true\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@
 \edef\l@{\the\leftskip}\ialign
 \bgroup\hskip\l@##\hfil&&##\hfil\crcr}
\def\endstab{\crcr\egroup
 \egroup}
\newif\ifvst@b\vst@bfalse
\def\vstab{\D@cke0.5pt\null
 \vtop\bgroup\tab@true\vtab@false\vst@btrue\Strich@true\bgroup\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\bgroup}
\def\endvstab{\crcr\egroup\egroup
 \egroup\tab@false\Strich@false}

\newdimen\htstrut@
\htstrut@8.5\p@
\newdimen\htStrut@
\htStrut@12\p@
\newdimen\dpstrut@
\dpstrut@3.5\p@
\newdimen\dpStrut@
\dpStrut@3.5\p@
\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@
  \divide\dimen@ by2
  \advance\htstrut@\dimen@
  \advance\htStrut@\dimen@
  \advance\dpstrut@\dimen@
  \advance\dpStrut@\dimen@}
\def\Let@@{\relax\iffalse{\fi%
    \def\\{\global\hline@@false%
     \ifhline@\global\hline@false\global\hline@@true\fi\cr}%
    \iffalse}\fi}
\def\matrix{\null\,\vcenter\bgroup
 \tab@false\vtab@false\vst@bfalse\Strich@false\Let@@\vspace@
 \normalbaselines\openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr
 \Mathstrut@\crcr\noalign{\kern-\baselineskip}}
\def\endmatrix{\crcr\Mathstrut@\crcr\noalign{\kern-\baselineskip}\egroup
 \egroup\,}
\def\smatrix{\D@cke0.5pt\null\,
 \vcenter\bgroup\tab@false\vtab@false\vst@bfalse\Strich@true\Let@@\vspace@
 \normalbaselines\offinterlineskip
  \openup\spreadmlines@\ialign
 \bgroup\hfil$\m@th##$\hfil&&\quad\hfil$\m@th##$\hfil\crcr}
\def\endsmatrix{\crcr\egroup
 \egroup\,\Strich@false}
\newdimen\D@cke
\def\Dicke#1{\global\D@cke#1}
\newtoks\tabs@\tabs@{&}
\newif\ifStrich@\Strich@false
\newif\iff@rst

\def\Stricherr@{\iftab@\ifvtab@\errmessage{\noexpand\s not allowed
     here. Use \noexpand\vstab!}%
  \else\errmessage{\noexpand\s not allowed here. Use \noexpand\stab!}%
  \fi\else\errmessage{\noexpand\s not allowed
     here. Use \noexpand\smatrix!}\fi}
\def\format{\ifvst@b\else\crcr\fi\egroup\iffalse{\fi\ifnum`}=0 \fi\format@}
\def\format@#1\\{\def\preamble@{#1}%
 \def\Str@chfehlt##1{\ifx##1\s\Stricherr@\fi\ifx##1\\\let\Next\relax%
   \else\let\Next\Str@chfehlt\fi\Next}%
 \def\c{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\r{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi}%
 \def\l{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi\iftab@\else$\m@th\fi\the\hashtoks@\iftab@\else$\fi\hfil}%
 \def\s{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@%
          \fi\the\tabs@\ }%
 \def\sa{\ifStrich@\vrule width\D@cke\the\hashtoks@%
            \the\tabs@\ %
            \fi}%
 \def\se{\ifStrich@\ \the\tabs@\vrule width\D@cke\the\hashtoks@\fi}%
 \def\cd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \def\rd{\hfil\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$}%
 \def\ld{\noexpand\ifhline@@\hbox{\vrule height\htStrut@%
   depth\dpstrut@ width\z@}\noexpand\fi%
   \ifStrich@\hbox{\vrule height\htstrut@ depth\dpstrut@ width\z@}%
   \fi$\dsize\m@th\the\hashtoks@$\hfil}%
 \ifStrich@\else\Str@chfehlt#1\\\fi%
 \setbox\z@\hbox{\xdef\Preamble@{\preamble@}}\ifnum`{=0 \fi\iffalse}\fi
 \ialign\bgroup\span\Preamble@\crcr}
\newif\ifhline@\hline@false
\newif\ifhline@@\hline@@false
\def\hlinefor#1{\multispan@{\strip@#1 }\leaders\hrule height\D@cke\hfill%
    \global\hline@true\ignorespaces}
\def\htextfor#1 #2{\multispan@{\strip@#1 }\hfil\hbox{#2}\hfill%
    \global\hline@true\ignorespaces}
\catcode`\@=13



\NoBlackBoxes

\TagsAsMath
\documentstyle{amsppt}


\headline=               
{\ifnum\pageno=1\hfil
 \else\vbox{\line {\tenit 
Carlitz compositions
 \hfil\tenrm\number\pageno}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13

\define\cc{\overline{c}}
\define\C{\overline{C}}
\define\r{\overline{\rho}}
\define\eps{\varepsilon}

%\NoBlackBoxes
\TagsOnRight
\topmatter

\title 
On Carlitz compositions
\endtitle
\author Arnold Knopfmacher and Helmut Prodinger \endauthor
\affil 
Department of 
Computational and Applied Mathematics\\
University of Witwatersrand, Johannesburg, South Africa\\
Department of Algebra and Discrete Mathematics\\ 
Technical University of Vienna, Austria
\endaffil
\address
\phantom{shit}\newline
Arnold Knopfmacher\newline
Department of 
Computational and Applied Mathematics\newline
University of Witwatersrand (Wits) 2050\newline
 Johannesburg\newline
 South Africa\newline
email: {\tt arnoldk\@gauss.cam.wits.ac.za}\newline
www: {\tt http://sunsite.wits.ac.za/wits/science/number\_theory/arnold.htm}
\newline
\phantom{shit}\newline
Helmut Prodinger\newline
Department of Algebra and Discrete Mathematics \newline
 TU Vienna\newline
 Wiedner Hauptstrasse 8-10\newline A-1040 Vienna\newline Austria\newline
email: {\tt Helmut.Prodinger\@tuwien.ac.at}\newline
www: {\tt http://info.tuwien.ac.at/theoinf/proding.htm}
\endaddress 
\abstract
This paper deals with Carlitz compositions of natural numbers
(adjacent parts have to be different). The following parameters
are analyzed: Number of parts, number of equal adjacent parts
in ordinary compositions, largest part, Carlitz compositions with
zeros allowed (correcting an erroneous formula from Carlitz).
It is also briefly demonstrated that  so--called 1--compositions
of a natural number can be treated in a similar style.
\endabstract

\def\heute{\ifcase\month\or January\or February\or March\or April\or May
\or June\or July\or August\or September\or October
\or November\or December\fi
\space\number\day, \number\year}


\endtopmatter

%\centerline{--- \heute\ ---}
\centerline{--- October 14, 1997\ ---}
\document



\head 1. Introduction \endhead

A restricted composition of a natural number $n$ in the sense
of Carlitz \cite{4}, which we shall call a {\it Carlitz composition,}
is defined to be a composition 
$$
n=a_1+a_2+\dots +a_k \quad\text{such that}\quad a_i\neq a_{i+1}\
\text{for } i=1,\dots,k-1.
$$
We refer to $n$ as the {\it size\/} 
and to $k$ as the {\it number of parts\/} of the composition.

Observe that there are $2^{n-1}$ unrestricted compositions of the integer
$n$ with generating function $1/(1-z/(1-z))$. 

Let $c(n)$ denote the number of Carlitz compositions
of $n$.
In \cite{4}, Carlitz found the generating function
$$
C(z):=\sum_{n\ge0}c(n)z^n.
$$
Since we are going to compute several related parameters we
find it useful to rederive his result in a streamlined way, 
using a method that has appeared for example
 in \cite{6} under the nickname
``adding a new slice.'' We proceed from a Carlitz composition
with $k$ parts to one with $k+1$ parts by allowing $a_{k+1}$ to
be any number and then subtracting the forbidden case $a_{k+1}=a_k$.
In terms of generating functions this reads as follows. Let
$f_k(z,u)$ be the generating function of those Carlitz compositions
with $k$ parts where the coefficient of $z^nu^j$ refers to 
size $n$ and last part $a_k=j$. Then 
$$
f_{k+1}(z,u)=f_k(z,1)\frac{zu}{1-zu}-f_k(z,zu)+\delta_{k,0}
\quad \text{for } k\ge0, \ \ f_0(z,u)=1.\tag{*}
 $$
The first term means that we forget the labelling of the last part
($u:=1$) and add any term, together with a labelling by $u$,
and the second one means that we subtract the forbidden term, which
is a repetition of the previous last part. Introducing
$F(z,u):=\sum_{k\ge1}f_k(z,u)$ and summing on $k\ge0$, we get
$$
F(z,u)=F(z,1)\frac{zu}{1-zu}+\frac{zu}{1-zu}-F(z,zu).
$$
This functional equation can now be {\it iterated\/} and gives
$$
F(z,1)=\sigma(z)+ F(z,1)\,\sigma(z),
$$
with
$$
\sigma(z)=\sum_{j\ge1}\frac{z^j(-1)^{j-1}}{1-z^j}.
$$
Since $C(z)=1+F(z,1)$, we find the formula of Carlitz,
$$
C(z)=\frac{1}{1-\sigma(z)}.
$$
Here are the first few values:
$$
1+z+{z}^{2}+3{z}^{3}+4{z}^{4}+7{z}^{5}+14{z}^{6}+23{z}^{7}+
39{z}^{8}+71{z}^{9}+124{z}^{10}+\dots;
$$
it is sequence $A003242$ in \cite{14}.
 
In his paper, Carlitz noted only that the radius of convergence
of $C(z)$ is at least $\frac12$.
Now we can go further than that and notice that there is a
dominant pole $\rho$, which is the unique real solution 
in the interval $[0,1]$
of the
equation $\sigma(z)=1$. Numerically we find $\rho=0.571349\dots$
The other poles are further away, which can proved by Rouch\'e's
theorem very much as in \cite{6,9,11,12,13}. 

Consequently, in a neighbourhood of $z=\rho$, 
$$
C(z)\sim\frac{A}{1-z/\rho}, \quad\text{with}\quad
A=\frac{1}{\rho\sigma'(\rho)}=0.456387\dots
$$
Therefore, 
$$
c(n)\sim A\rho^{-n}=0.456387\cdot(1.750243)^n.
$$






\head 2. The number of parts \endhead

Now we are interested to know how many parts a (random)
Carlitz composition of size $n$ has (on the average).

We will use another variable, $w$, to label the number 
of parts. The functional recursion ($*$) is of course 
our starting point. Introducing
$G(z,u,w):=\sum_{k\ge1}w^kf_k(z,u)$, we find by 
multiplying ($*$) by $w^{k+1}$ and summing over $k\ge0$,
$$
G(z,u,w)=wG(z,1,w)\frac{zu}{1-zu}+w\frac{zu}{1-zu}-wG(z,zu,w).
$$
Iterating this as before we find
$$
G(z,1,w)=\frac{\tau(z,w)}{1-\tau(z,w)},
$$
with
$$
\tau(z,w)=\sum_{j\ge1}\frac{z^jw^j(-1)^{j-1}}{1-z^j}.
$$

\vbox{
$$
\scriptstyle{
\smatrix \format \sa \c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\se\\
\omit&n\backslash k&&
1&\omit&2&\omit&3&\omit&4&\omit&5&\omit&6&\omit&
7&\omit&8&\omit
\\
\hlinefor{19}\\
\omit&1&&1&\\
\omit&\omit&\hlinefor{3}\\
\omit&2&&1&\\
\omit&\omit&\hlinefor{5}\\
\omit&3&&1&&2&\\
\omit&\omit&\hlinefor{7}\\
\omit&4&&1&&2&&1&\\
\omit&\omit&\hlinefor{7}\\
\omit&5&&1&&4&&2&\\
\omit&\omit&\hlinefor{9}\\
\omit&6&&1&&4&&7&&2&\\
\omit&\omit&\hlinefor{11}\\
\omit&7&&1&&6&&9&&6&&1&\\
\omit&\omit&\hlinefor{11}\\
\omit&8&&1&&6&&15&&14&&3&\\
\omit&\omit&\hlinefor{13}\\
\omit&9&&1&&8&&21&&24&&15&&2&\\
\omit&\omit&\hlinefor{15}\\
\omit&10&&1&&8&&28&&46&&30&&10&&1&\\
\omit&\omit&\hlinefor{15}\\
\omit&11&&1&&10&&35&&66&&68&&30&&4&\\
\omit&\omit&\hlinefor{17}\\
\omit&12&&1&&10&&46&&100&&119&&76&&24&&2&\\
\omit&\omit&\hlinefor{17}
\endsmatrix}$$
\centerline{{\smc Table 1.} Carlitz compositions  by size and number of parts}
}
\bigskip

To compute the average value, we need the function
$$
\overline{G}(z):=\frac{\partial}{\partial w}G(z,1,w)\Big\vert_{w=1},
$$
for which we easily find
$$
\overline{G}(z)=\frac{\mu(z)}{(1-\sigma(z))^2}
\quad\text{with}\quad
\mu(z)=\sum_{j\ge1}\frac{jz^j(-1)^{j-1}}{1-z^j}.
$$
Consequently, 
$$
\overline{G}(z)\sim \frac{B}{(1-z\rho)^2},
\quad\text{with}\quad
B=\mu(\rho)A^2= 0.159996.
$$
Therefore
$$
[z^n]\overline{G}(z)\sim B\,n\,\rho^{-n},
$$
and thus the average number of parts in a Carlitz
composition of size $n$ is asymptotic to
$$
\frac{B\,n\,\rho^{-n}}{A\,\rho^{-n}}=  0.350571\cdot n.
$$
By contrast, an unrestricted composition of $n$ has $\frac{n+1}{2}$
parts on average.

\head 3. Counting adjacent equal parts \endhead

In this section 
we consider all compositions of $n$ and
count the number of adjacent equal parts.
The original Carlitz case is then equivalent to compositions 
where this count gives zero.

Again our starting point will be recursion ($*$); we will use 
a variable $v$ to count the number of adjacent equal parts.
($v=0$ means the Carlitz case.)

We have by the same reasoning as before
$$
f_{k+1}(z,u,v)=f_k(z,1,v)\frac{zu}{1-zu}-(1-v)f_k(z,zu,v)+
(1-v)\delta_{k,0}
\quad \text{for } k\ge0, 
 $$
and $f_0(z,u,v)=1$.
Defining $F(z,u,v):=\sum_{k\ge1}f_k(z,u,v)$ and summing  we
get
$$
F(z,u,v)=F(z,1,v)\frac{zu}{1-zu}+\frac{zu}{1-zu}
-(1-v)F(z,zu,v).
$$
Iterating as before we find for the generating function of
interest $1+F(z,1,v)$ that
$$
1+F(z,1,v)=\frac{1}{1-\sigma(z,v)}
\quad\text{with}\quad
\sigma(z,v)
=\sum_{j\ge1}\frac{z^j(v-1)^{j-1}}{1-z^j}.
$$
Observe that $v:=0$ gives the generating function of 
the Carlitz compositions and $v:=1$
gives the generating function $\frac{1-z}{1-2z}$
of all compositions, as it should.

If we are thus interested in the generating function of
compositions with exactly $m$  adjacent equal parts, then
we must extract the coefficient of $v^m$, which we might
do by Taylor's formula as
$$
[v^m]\frac{1}{1-\sigma(z,v)}=\frac{1}{m!}\frac{\partial^m}
{\partial v^m}	\frac{1}{1-\sigma(z,v)}\bigg\vert_{v=0}.
$$
For instance, we get for $m=1$
$$
\frac{\sigma'(z,0)}{(1-\sigma(z))^2},
$$
the derivative being w.r.t. $v$. For general $m$
we get something of the form
$$
\frac{p_m(z)}{(1-\sigma(z))^{m+1}},
$$
with a function $p_m(z)$ that is built up from derivatives of
the function $\sigma(z,v)$. Consequently, for fixed $m$ and
$n\to\infty$ the number of compositions with exactly $m$
equal adjacent parts has the following asymptotic behaviour
$$
C_m\,n^{m}\, \rho^{-n}
$$
with explicitly computable constants $C_m$.
The first few are
$$\align
C_0 &= 0.4563,\\
C_1 &= 0.0482,\\
C_2 &= 0.0025.
\endalign
$$


\medskip

Also,  we can determine the average number of equal adjacent parts
by differentiation w.r.t. $v$, followed by
setting $v=1$,
which yields 
$$
\frac{(1-z)^2}{(1-2z)^2}\frac{z^2}{1-z^2}=\frac{z^2(1-z)}{(1+z)(1-2z)^2}.
$$
For $n\ge1$ the coefficient of $z^n$ therein is
$$
\frac{1}{12}(n+1)2^n-\frac{1}{18}2^n+\frac29(-1)^n,
$$
which gives (upon division by $2^{n-1}$) our average as
$$
\frac{3n+1}{18}+O(2^{-n}).
$$

\vbox{
$$
\scriptstyle{
\smatrix \format \sa \c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\se\\
\omit&n\backslash k&&0&\omit&
1&\omit&2&\omit&3&\omit&4&\omit&5&\omit&6&\omit&
7&\omit&8&\omit&9&\omit&10&\omit&11&\omit
\\
\hlinefor{27}\\
\omit&1&&1&\\
\omit&\omit&\hlinefor{5}\\
\omit&2&&1&&1&\\
\omit&\omit&\hlinefor{7}\\
\omit&3&&3&&0&&1&\\
\omit&\omit&\hlinefor{8}\\
\omit&4&&4&&3&&0&&1&\\
\omit&\omit&\hlinefor{11}\\
\omit&5&&7&&6&&2&&0&&1&\\
\omit&\omit&\hlinefor{13}\\
\omit&6&&14&&7&&8&&2&&0&&1&\\
\omit&\omit&\hlinefor{15}\\
\omit&7&&23&&20&&10&&8&&2&&0&&1&\\
\omit&\omit&\hlinefor{17}\\
\omit&8&&39&&42&&22&&13&&9&&2&&0&&1&\\
\omit&\omit&\hlinefor{19}\\
\omit&9&&71&&72&&58&&28&&14&&10&&2&&0&&1&\\
\omit&\omit&\hlinefor{21}\\
\omit&10&&124&&141&&112&&72&&33&&16&&11&&2&&0&&1&\\
\omit&\omit&\hlinefor{23}\\
\omit&11&&214&&280&&219&&150&&92&&36&&18&&12&&2&&0&&1&\\
\omit&\omit&\hlinefor{25}\\
\omit&12&&378&&516&&466&&311&&189&&112&&40&&20&&13&&2&&0&&1&\\
\omit&\omit&\hlinefor{25}
\endsmatrix}$$
\centerline{{\smc Table 2.} Compositions $C(n,k)$ by size and
number of adjacent equal parts}
}

\bigskip

{\smc Remark.} We notice formul\ae{} such as
$$\align
C(n,n-1)&=1,\quad n\ge 1,\\
C(n,n-2)&=0,\quad n\ge 3,\\
C(n,n-3)&=2,\quad n\ge 5,\\
C(n,n-4)&=n+1,\quad n\ge 7,\\
C(n,n-5)&=2n-4,\quad n\ge 9,\\
C(n,n-6)&=4n-8,\quad n\ge 11,\\
C(n,n-7)&=\frac{n^2+15n-102}{2},\quad n\ge13 ,\dots
\endalign
$$

They are all easy to prove by considering
$$
\frac{1}{1-\sigma(zv,v^{-1})}
$$
and looking for the coefficient of a fixed power of $v$.






\head 4. The largest part in Carlitz compositions \endhead

For ordinary partitions, the statistic ``largest part of a composition''
has obtained a lot of attention, \cite{5,10}.
Now we want to sketch the analogous analysis for the case of
Carlitz compositions.

Let us first consider the generating function(s) where all parts
are less than or equal to $h$. Then essentially the  same idea
as in ($*$) works, except that  we only use a factor
$$
(zu)+\dots+(zu)^h=\frac{zu(1-(zu)^h)}{1-zu}
$$
instead of the full geometric series.
This results finally in 
$$
1+F_h(z,1)=\frac{1}{1-\sigma_h(z)},
$$
with
$$
\sigma_h(z)=
\sum_{j\ge1}\frac{\big(z^j-z^{j(h+1)}\big)(-1)^{j-1}}{1-z^j}.
$$
The dominant pole $\rho_h$ is now the (positive real) solution of
the equation $\sigma_h(z)=1$. It is clear that $\rho_h$ tends
to $\rho$, but we have to determine how fast. We will use
the ``bootstrapping method'' from \cite{11}.

Now, around $z=\rho$ we have the approximate equation
$$
1\approx\sigma(z)-\rho^{h+1}.
$$
Using Taylor's theorem and setting $\rho_h=\rho(1+\eps_h)$, we
arrive at
$$
0\approx\rho\eps_h\sigma'(\rho)-\rho^{h+1},
$$
or
$$
\eps_h\approx\frac{1}{\sigma'(\rho)}\rho^h.
$$
Therefore the number of Carlitz compositions with largest part
$\le h$ is approximated by
$$
\frac{1}{\rho_h\sigma'(\rho_h)}\rho_h^{-n}\approx
\frac{1}{\rho\sigma'(\rho)}\rho^{-n}(1+\eps_h)^{-n}.
$$
Consequently the probability that a
Carlitz composition has largest part
$\le h$ is approximated by

$$
(1+\eps_h)^{-n}\approx \Big(1-\frac{1}{\sigma'(\rho)}\rho^h\Big)^n.
$$
For the probability that the largest part is $>h$ we have then
approximately
$$
1-\Big(1-\frac{1}{\sigma'(\rho)}\rho^h\Big)^n,
$$
and to get the desired average value $E_n$
we must sum this up over $h\ge0$.
The next step is 
to use the exponential approximation $(1-a)^n\approx e^{-an}$;
$$
E_n\approx\sum_{h\ge0}\Big(
1-e^{-n\rho^h/\sigma'(\rho)}
\Big).
$$
But this quantity is quite well studied 
\cite{5} (we might even 
set $N:=n/\sigma'(\rho)$ for the moment to make it look 
closer to already existing formul\ae).

The answer is
$$
E_n\sim \log_{1/\rho}N-\frac{\gamma}{\log\rho}+\frac12+
\delta(\log_{1/\rho}N),
$$
with a certain periodic function $\delta(x)$ that has period
1, mean 0, and small amplitude.

Rewriting this we find
$$
E_n\sim \log_{1/\rho}n-
\log_{1/\rho}{\sigma'(\rho)}-
\frac{\gamma}{\log\rho}+\frac12+
\overline{\delta}(\log_{1/\rho}n),
$$
where $\overline{\delta}(x)=\delta(x-\log_{1/\rho}{\sigma'(\rho)})$, 
which has the same properties as $\delta(x)$.
The numerical constant is 
$-
\log_{1/\rho}{\sigma'(\rho)}-\frac{\gamma}{\log\rho}+\frac12
=- 0.870252$.

\medskip

It might be of interest
for the reader to learn that Xavier Gourdon studied
{\it largest components in combinatorial structures\/}
in great generality \cite{8}. From this treatment it
seems that almost the distributions in our paper
are {\it asymptotically Gaussian}, although we have not
performed a rigorous analysis. 
The distribution of the largest part (section 4) 
follows a {\it double exponential law}. 
This holds under very general conditions, e.~g.
for {\it unrestricted compositions}, compare
\cite{8; p. 190ff}.
The paper
\cite{3} should also be mentioned in this context.

































\head 5. Carlitz Compositions with zeros \endhead


For ordinary compositions it is meaningless to allow the $a_i$'s
to be zero, since then there would be infinitely many compositions
for each $n$.
However, in the context of Carlitz compositions, it {\it makes\/}
sense, since one can have at most $n+1$ zeros, so the number
$\cc(n)$ of Carlitz compositions with zeros allowed 
is meaningful.

In \cite{4} Carlitz gave an erroneous formula for the generating function
$$
\C(z)=\sum_{n\ge0}\cc(n)z^n
$$
viz.
$$
\C(z)=\frac{1}{1-\overline{\sigma}(z)}
\quad\text{with}\quad
\overline{\sigma}(z)=(1-z)\sum_{j\ge1}
\frac{z^{2j-1}}{(1-z^{2j-1})(1-z^{2j})}.
$$
A simple rearrangement shows that $C(z)=\C(z)$, 
so this cannot be correct. Here is a brief explanation
of the flaw in the derivation.

Carlitz gives {\it mutatis mutandis}
$$
f_{k+1}(z,u)=f_k(z,1)\frac{1}{1-zu}-f_k(z,zu)+\delta_{k,0}
\quad \text{for } k\ge0, \ \ f_0(z,u)=1
 $$
and

$$
F(z,u)=F(z,1)\frac{1}{1-zu}+\frac{1}{1-zu}-F(z,zu),
$$
as in section 1, which is still correct, but then he iterates
that, which is prohibited, because of a problem with the
{\it constant term.}

Here is a corrected version: We dissect the set of 
compositions into those with last part $\ge1$ (counted
by $g_k(z,u)$) and those with last part $=0$
(counted by $h_k(z)$). Clearly, $h_k(z)=g_{k-1}(z,1)$.

Then the usable recursion is (for $k\ge1$)
$$
g_{k+1}(z,u)=g_k(z,1)\frac{zu}{1-zu}+h_k(z)\frac{zu}{1-zu}
-g_k(z,zu).
$$
Denoting $G(z,u)=\sum_{k\ge1}g_k(z,u)$ and summing up we get
$$
G(z,u)=2\frac{zu}{1-zu}+2G(z,1)\frac{zu}{1-zu}-G(z,zu).
$$
This version {\it is\/} now amenable to iteration, and consequently
we get (with the function $\sigma(z)$ from the introduction)
$$
G(z,1)=\frac{2\sigma(z)}{1-2\sigma(z)}.
$$
Therefore
$$
\C(z)=1+2G(z,1)=\frac{1+2\sigma(z)}{1-2\sigma(z)}.
$$
Again, there is a dominant singularity $\r$, which is the solution
in the interval $[0,1]$ of the equation $\sigma(z)=\frac12$.

Numerically we find $\r=0.386960$. This is also in contrast
to Carlitz's comment that is should be close to $\frac12$.

Thus

$$
\cc(n)\sim \frac{1+2\sigma(\r)}{2\r\sigma'(\r)}\r^{-n}=
 1.337604
\cdot( 2.584243)^n.
$$


A Carlitz composition with zeros allowed can have at most $2n+1$
parts. It is therefore of interest to compare the asymptotic formula
for $\cc(n)$ with the total number of compositions (zeros allowed)
having at most 
$2n+1$ parts. This number is given by
$$
\sum_{k=1}^{2n+1}\binom{n+k-1}{n}=\binom{3n+1}{n+1}
\sim \frac{3\sqrt3}{2\sqrt{\pi n}}\Big(\frac{27}{4}\Big)^n.
$$
Note that $\frac{27}4=6.75$.


\head 6. 1--compositions \endhead

If we impose the conditions $a_2\le a_1+1$,
$a_3\le a_2+1$, etc. on an ordinary composition,
we encounter a different family
of restricted compositions  which are termed ``1--composition''
in \cite{2,15}.

We want to demonstrate that the technique of adding a new slice
applies also very well in this context. 

Again, we are using the generating functions $f_k(z,u)$ for
1--compositions enumerated by size and last part. Assume that the last
part is $j$, which is coded by $u^j$. Then the next part can be any
number between 1 and $j+1$. In other words, we must replace $u^j$
by 
$$
(zu)+(zu)^2+\dots+(zu)^{j+1}=\frac{zu(1-(zu)^{j+1})}{1-zu}.
$$
In terms of generating functions this substitution translates into
$$
f_{k+1}(z,u)=\frac{zu}{1-zu}f_k(z,1)-
\frac{z^2u^2}{1-zu}f_k(z,zu)
$$
for $k\ge1$ and $f_1(z,u)=\frac{zu}{1-zu}$. With
$F(z,u)=\sum_{k\ge1}f_k(z,u)$ this means
$$
F(z,u)=\frac{zu}{1-zu}F(z,1)-
\frac{z^2u^2}{1-zu}F(z,zu)+
\frac{zu}{1-zu},
$$
and upon iteration
$$
1+F(z,1)=\frac{1}{1-\sigma(z)},
$$
with
$$
\sigma(z)=\sum_{j\ge1}\frac{(-1)^{j-1}z^{j^2}}
{(1-z)(1-z^2)\dots(1-z^j)}.
$$
There is again a dominant pole at $\rho=0.576148$,
and $\rho\sigma'(\rho)=1.089257$, so the number of
1--compositions of $n$ is asymptotic to
$$
\frac{1}{\rho\sigma'(\rho)}\rho^{-n}=0.918056
\cdot( 1.735662)^n.
$$

Now we can also count how many times the condition
$a_i\le a_{i+1}+1$ is {\it not\/} satisfied. If we use an
auxiliary variable $v$ as we did before, it means that we have
to replace $u^j$ by
$$
\frac{zu(1-(zu)^{j+1})}{1-zu}
+\frac{(zu)^{j+2}v}{1-zu}
=\frac{zu(1-(1-v)(zu)^{j+1})}{1-zu}.
$$
The appropriate changes are then as follows:
$$
F(z,u,v)=\frac{zu}{1-zu}F(z,1,v)-
\frac{z^2u^2(1-v)}{1-zu}F(z,zu,v)+
\frac{zu}{1-zu},
$$
and 
$$
1+F(z,1,v)=\frac{1}{1-\sigma(z,v)},
$$
with
$$
\sigma(z,v)=\sum_{j\ge1}\frac{(v-1)^{j-1}z^{j^2}}
{(1-z)(1-z^2)\dots(1-z^j)}.
$$
Differentiating $1+F(z,1,v)$ w.r.t. $v$ and setting $v=1$
gives
$$
\frac{z^4}{(1+z)(1-2z)^2}.
$$
Reading off the coefficient of $z^n$ and dividing by
$2^{n-1}$ we get the average as
$$
\frac{3n-8}{36}+O(2^{-n}).
$$

\vbox{ 
$$
\scriptstyle{
\smatrix \format \sa \c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\s\c\se\\
\omit&n\backslash k&&0&\omit&
1&\omit&2&\omit&3&\omit
\\
\hlinefor{11}\\
\omit&1&&1&\\
\omit&\omit&\hlinefor{3}\\
\omit&2&&2&\\
\omit&\omit&\hlinefor{3}\\
\omit&3&&4&\\
\omit&\omit&\hlinefor{5}\\
\omit&4&&7&&1&\\
\omit&\omit&\hlinefor{5}\\
\omit&5&&13&&3&\\
\omit&\omit&\hlinefor{5}\\
\omit&6&&23&&9&\\
\omit&\omit&\hlinefor{5}\\
\omit&7&&41&&23&\\
\omit&\omit&\hlinefor{7}\\
\omit&8&&72&&55&&1&\\
\omit&\omit&\hlinefor{7}\\
\omit&9&&127&&123&&6&\\
\omit&\omit&\hlinefor{7}\\
\omit&10&&222&&267&&23&\\
\omit&\omit&\hlinefor{7}\\
\omit&11&&388&&561&&75&\\
\omit&\omit&\hlinefor{9}\\
\omit&12&&677&&1150&&220&&1&\\
\omit&\omit&\hlinefor{9}
\endsmatrix}$$
\centerline{{\smc Table 3.} Compositions  by size and
number of adjacent parts $a,b$ with $b>a+1$}
}

\bigskip

If we consider ``0--compositions'' ($a_1\le a_2\le\dots$), which
actually means {\it partitions}, and perform the same analysis, we
find the functional equation
$$
F(z,u)=\frac{zu}{1-zu}F(z,1)-
\frac{zu}{1-zu}F(z,zu)+
\frac{zu}{1-zu},
$$
and upon iteration
$$
1+F(z,1)=\frac{1}{1-\sigma(z)},
$$
with
$$
\sigma(z)=\sum_{j\ge1}\frac{(-1)^{j-1}z^\binom{j+1}{2}}
{(1-z)(1-z^2)\dots(1-z^j)}.
$$
Since 
$$
1+F(z,1)=\prod_{k\ge1}\frac{1}{1-z^k},
$$
we find in this way one of {\it Euler's partition identities},
\cite{1}.

This time, there is no dominant pole, since the equation
$\sigma(z)=1$ has no solution inside the unit circle,
and the asymptotics are  harder.
The interested reader can find the asymptotics
(originally by Hardy, Ramanujan, and Rademacher), in the
book \cite{1}. Here, one can also find information about 
the famous Rogers--Ramanujan identities which are
close in spirit to ``1--compositions.''
A further paper where such generating functions appear, is
\cite{13}; however, we don't intend to be encyclopedic.



















\head 7. Concluding Remarks \endhead

It should be clear by now that several related quantities
can also be treated along the lines of this paper.
We mention in particular Carlitz composition with zeros
where one can also investigate the parameters that we
considered for ordinary Carlitz compositions. In all instances, 
variances could be computed. 2--compositions etc. could also be done.

A harder problem that we don't know how to do at the moment is the
number of different part sizes in Carlitz compositions
(for ordinary compositions see \cite{10,12}).

Also, it seems that the rows of all 
the tables given in this paper are unimodal
(apart from the last entry 
of each row in Table 2).
These observations would still require  proof.

\medskip

The referee has kindly informed us about a different
approach using {\it Smirnov words}; see
\cite{7; p. 69}. This approach would give some
(but not all) of our generating functions, and it
is worthwhile to sketch it here.

Think about the parts $1,2,\dots$ of a composition
as words and use letters $x_1,x_2,\dots$\!. 
Then Smirnov words are those with adjacent letters
being different. By replacing each letter 
$x_i$ by a sequence $x_i/(1-x_i)$ of this letter, all
words are obtained. But this is a trivial set
(or the generating function is very simple, depending
on how things are phrased). With an obvious notation
we get
$$
S\Big(\frac{x_1}{1-x_1},\frac{x_2}{1-x_2},\dots\Big)
=\frac{1}{1-\sum_{i\ge1}x_i}\,.
$$
Since
$$
\frac{x}{1-x}=y \quad\longleftrightarrow\quad
\frac{y}{1+y}=x,
$$
the above relation can be {\it inverted\/}:
$$
S(y_1,y_2,\dots)=\frac{1}{1-\sum_{i\ge1}\frac{x_i}{1+x_i}}\,.
$$
Now for compositions, we should replace each $y_i$ by $z^i$, which
gives the following alternative representation of the generating
function $C(z)$;
$$
C(z)=\frac{1}{1-\sum_{i\ge1}\frac{z^i}{1+z^i}}\,.
$$ 
It is not hard to see that the two version coincide; one has to show
that
$$
\sum_{i\ge1}\frac{z^i}{1+z^i}=\sum_{j\ge1}\frac{z^j(-1)^{j-1}}{1-z^j}.
$$ 
For that, one expands the geometric series and interchanges the order
of the summations.


  
 (For the other generating functions we would also get versions without
the alternating sign $(-1)^i$.) 










\bigskip
{\smc Acknowledgment.} This research was done while the second
author visited 
the Centre for Applicable Analysis and Number Theory, at
the University of Witwatersrand, Johannesburg. He is thankful
for the hospitality he encountered there.

We would also like to thank the referee for lots of additional
information and appreciative remarks.




















\Refs


\ref\no1\by G.~E.~Andrews
\book The Theory of Partitions
\publ Addison--Wesley
\yr 1976
\endref


\ref\no2\by G.~E.~Andrews
\paper The hard-hexagon model and Rogers--Ramanujan type
identities
\jour Proc. Natl. Acad. Sci. USA
\yr 1981
\pages 5290--5292
\vol78
\endref




\ref \no 3 \by 
E.~Bender \paper
Central and local limit theorems applied to asymptotic enumeration
\jour J. Comb. Theory, Ser. A
\pages 91--111\yr1973\vol15
\endref


\ref \no 4 \by 
L. Carlitz \paper Restricted Compositions
\jour The Fibonacci Quarterly
\pages 254--264\yr1976\vol14
\endref


\ref\no5\by
P.~Flajolet, X.~Gourdon, and P.~Dumas
\paper
Mellin transform and asymptotics: Harmonic sums
\jour Theoretical Computer Science
\vol144	\yr1995
\pages3--58 
\endref

\ref\no6\by
P.~Flajolet and H.~Prodinger
\paper
Level Number Sequences for Trees
\jour Discrete Mathematics
\vol65	\yr1987	
\pages 149--156 
\endref


\ref\no7\by I.~Goulden and D.~Jackson
\book Combinatorial Enumeration
\publ John Wiley
\yr 1983
\endref


\ref\no8\by X.~Gourdon
\book Combinatoire, Algorithmique et G\'eom\'etrie des Polyn\^omes
\publ Th\`ese, \'Ecole polytechnique
\yr 1996
\endref






\ref\no9\by H.~K.~Hwang and Y.~N.~Yeh
\paper Measures of Distinctness for Random
Partitions and Compositions of an Integer
\jour Advances in Applied Mathematics
\vol19\yr1997\pages378--414
\endref


\ref\no10\by A.~Knopfmacher and M.~E.~Mays
\paper Compositions with $m$ distinct parts
\jour Ars Combinatoria, to appear
\endref


\ref\no11\by D.~E.~Knuth
\paper The Average Time for Carry Propagation
\jour Indagationes Mathematic\ae{}
\vol40\yr1978\pages 238--242
\endref

\ref\no12\by A.~M.~Odlyzko and L.~B.~Richmond
\paper On the Compositions of an Integer
\jour Lecture Notes in Mathematics
\vol 829\yr 1979\pages199--209
\endref


\ref\no13\by A.~M.~Odlyzko and H.~Wilf
\paper $n$ Coins in a Fountain
\jour American Mathematical Monthly
\vol40\yr1978\pages 238--242
\endref

\ref\no14\by N.~Sloane and S.~Plouffe
\book The Encyclopedia of Integer Sequences
\publ Academic Press
\yr1995
\endref


\ref\no15\by G.~X.~Viennot
\paper Bijections for the Rogers--Ramanujan reciprocal
\jour J. Indian Math. Soc., New Series
\vol 52\yr 1987\pages171--183
\endref

\endRefs


\enddocument


