\documentclass[12pt,reqno]{article}

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

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Generalizations of Carlitz Compositions
}
\vskip 1cm
\large
Sylvie Corteel\footnote{Supported in part by the NSF grant INT-0230800.} \\
LRI \\
CNRS Universit\'e Paris-Sud\\ 
91405 Orsay \\
France\\
\href{mailto:Sylvie.Corteel@lri.fr}{\tt Sylvie.Corteel@lri.fr}\\
\ \\
Pawe{\l} Hitczenko\footnote{Supported in part by the NSF grant INT-0230800 
and  by the NSA under Grant H98230-05-1-0016.} \\ 
LRI \\
CNRS  Universit\'e Paris-Sud \\
91405 Orsay \\
France \\
and \\
Department of Mathematics \\ 
Drexel University\\ 
Philadelphia, PA 19104 \\
USA  
\\
\href{mailto:phitczenko@math.drexel.edu}{\tt phitczenko@math.drexel.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
We consider a class of generating functions that appear in the context
of Carlitz compositions. In order to combinatorially interpret them, we
introduce a combinatorial structures that we name generalized
compositions and $p$-Carlitz compositions of integers.
We explain their connection  to Carlitz compositions, the relation to
other combinatorial structures, and  we describe their basic
properties.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}


\def\k{\kappa}
\def\D{{\Delta}}
\def\Bin{\textrm{Bin}}
\def\E{\textsf{E}}
\def\Pr{\textsf{Pr}}


\section{Introduction}

The following function $\sigma(z)$ defined by 
\begin{equation}\sigma(z)=\sum_{j=1}^\infty(-1)^{j-1}\frac{z^j}{1-z^j}.\label{sigma}\end{equation}
 has been introduced by Carlitz in \cite{carlitz}. It is related to the generating function of all compositions of $n$ whose any two consecutive parts are different (such compositions have been subsequently called Carlitz compositions, and studied, e.g., in
\cite{kpcarlitz,gh, lpcarlitz, khey3}; see also \seqnum{A003242} in \cite{s}).  
Specifically, if $C(z)$ is the generating function of Carlitz compositions 
then 
\begin{equation}C(z)=\frac1{1-\sigma(z)}.\label{basicrel}\end{equation}
If $\sigma(z)$ had all coefficients non--negative the same would be true of $C(z)$. However, $\sigma(z)$ does not have that property. Yet, it is a generating function of a natural sequence. Namely,
 by expanding $1/(1-z^j)$ into geometric series and rearranging the terms in (\ref{sigma}), we see that  
$$\sigma(z)=\sum_{j=1}^\infty(-1)^{j-1}z^j\sum_{k=0}^\infty z^{jk}=\sum_{j,k\ge1}(-1)^{j-1}z^{jk}=\sum_{n\ge1}z^n\sum_{j\ge1,\ j|n}(-1)^{j-1},$$
and so 
$\sigma(z)$ is the generating function of a sequence $\phi(n):=
\sum\limits_{j\ge1,\ j|n}(-1)^{j-1}$, which 
 is just the number of odd divisors of $n$ minus  the number of even divisors of $n$. Equivalently,  $\phi(n)$ may be 
defined 
as the  number of divisors of $n$ minus twice the number of even 
divisors of $n$.
 It is then natural to further define 
 for a positive integer $p$,  $\sigma_p(z)$ to be the generating function of a sequence \lq\lq the number of all divisors of $n$ minus $p$ times the number of  divisors of 
$n$ that are divisible by $p$\rq\rq. That is,  
let 
$d_q(m)$ be the number of divisors of $m$ that are multiples of $q$ and let
$$
\phi_p(j):=d_1(j)-pd_p(j)=d_1(j)-pd_1(j/p).$$
We then define
$$\sigma_p(z):=\sum_{j=1}^\infty\phi_p(j)z^j,$$
and set
\begin{equation}C_p(z):=\frac1{1-\sigma_p(z)},\label{cp}\end{equation}
(Thus, (\ref{basicrel}) is the special case of (\ref{cp}) corresponding to
 $p=2$ .)      

There does not seem to be  a priori reason for $C_p(z)$ to  have non--negative coefficients. But this is the case as we now show. 
\begin{lemma}\label{poslem}
 $C_p(z)$ defined by (\ref{cp}) has non-negative, increasing, integer coefficients for every integer $p\ge2$.
\label{lemcp}
\end{lemma}
\begin{proof}
Let $C_p(z)=\sum_{n\ge0}c_p(n)z^n$ and set $\D_p(n):=-\phi_p(n)$, $n\ge1$,  with $\D_p(0)=1$.  Set
$$\Psi_q(x)=\sum_{m\le x}\phi_q(m)=D_1(x)-qD_q(x).$$
Then,  (\ref{cp})  can be written as
$$
\Big(\sum_{n\ge0}c_p(n)z^n
\Big)\cdot
\Big(\sum_{n\ge0}\D_p(n)z^n
\Big)=1,$$
which leads to an infinite system of linear equations
$$\sum_{k=0}^mc_p(k)\D_p(m-k)=0,\quad m=1,2,\dots.$$
Adding up the first $m$ of them gives
$$c_p(0)\sum_{j=1}^m\D_p(j)+\sum_{\ell=1}^mc_p(\ell)\sum_{j=0}^{m-\ell}\D_p(j)=0,
$$
which, after extracting the last term and using $\D_p(0)=1$ gives
\begin{eqnarray*}c_p(m)&=&-c_p(0)\sum_{j=1}^m\D_p(j)-\sum_{\ell=1}^{m-1}c_p(\ell)\sum_{j=0}^{m-\ell}\D_p(j)\\&
=&c_p(0)\Psi_p(m)+\sum_{\ell=1}^{m-1}c_p(\ell)(-1+\Psi_p(m-\ell)).\end{eqnarray*}
Since this is to hold for all $m\ge1$, by an inductive argument it is enough to know that all the  $\Psi_p(n)$'s are positive.  In order  to show that let $I(d,m)=1$ if $d$ divides $m$, zero otherwise. Then
\begin{eqnarray*}
D_{1}(n)&=&
\sum\limits_{m\le n}\sum\limits_{d=1}^{n}I(d,m)
=\sum\limits_{d=1}^{n}\sum\limits_{m\leq n}I(d,m)
\\&=&\sum\limits_{d=
1}^{n}\Big\lfloor \frac nd\Big\rfloor .
\end{eqnarray*}
Similarly,
$$
pD_{p}(n)=p\sum\limits_{m\leq n}\sum\limits_{d=
1}^{n}I(dp,m)=\sum\limits_{d= 1}^{n}p\Big\lfloor \frac n{pd}\Big\rfloor.
$$
Since $
\lfloor {n/d}\rfloor \ge p\lfloor {n/pd}\rfloor
$
(just consider $n=mpd+\ell$ with $0\le\ell<pd$),
each term in the sum 
$$
\sum\limits_{d=1}^{n}
\Big(\Big\lfloor \frac nd\Big\rfloor -p\Big\lfloor \frac n{pd}\Big\rfloor\Big)
$$
is nonnegative and for $d=n$ the term is 1. Thus the whole sum is strictly positive.\end{proof}

In order to give a combinatorial proof of this result, we define two new combinatorial
objects: the generalized compositions and the $p$-Carlitz compositions.  In Section 2,
we define these objects and compute their generating functions. We show that the coefficient
of $z^n$ in $C_p(z)$ is equal to the number of $p$-Carlitz compositions of $n$.
Generalized compositions appear in \cite{s} as \seqnum{A129921},
while $p$-Carlitz compositions (or more precisely, $3$-Carlitz compositions)
are given as \seqnum{A129922}. 
In Section 3,
we use simple asymptotic techniques to compute the asymptotic behavior of
the number of generalized compositions of $n$ and $p$-Carlitz compositions of $n$. In Section 4,
we present some concluding remarks and further properties that 
can be deduced from known results.

\section{Generalized and $p$-Carlitz compositions}

We first recall some a few classical definitions for compositions. 
A composition of the integer $n$ is an ordered sequence
of positive integers $(a_1,a_2,\ldots)$ such that
$\sum_i a_i=n$. A composition of $n$ can also be seen as
a word $b_1^{i_1}b_2^{i_2}\ldots b_k^{i_k}$ with $\sum_j b_j i_j=n$, $b_j>0$, $i_j>0$
and $b_j\neq b_{j+1}$ for any $j$.

\begin{definition}
A  generalized composition of $n$ is a generalized word 
$b_1^{i_1}b_2^{i_2}\ldots b_k^{i_k}$ with $\sum_j b_j i_j=n$, $b_j>0$, $i_j>0$
for any $j$. The number of parts of the generalized 
composition is $\sum_{j}i_j$ and the length is $k$.
\end{definition}

\noindent {\bf Remark.} Generalized compositions are compositions where the condition  $b_j\neq b_{j+1}$
was taken off.
Generalized compositions can be seen as weighted compositions
where each part is weighted by its number of divisors
or weighted compositions where a part that is repeated exactly $i$
times is weighted by $2^{i-1}$.

\vspace{.3cm}

There are 7 generalized compositions of 3:
$3^1$, $1^12^1$, $2^11^1$, $1^3$, $1^21^1$, $1^11^2$ and $1^11^11^1$.

Let $g(n,\ell,k)$ the number of generalized compositions of $n$ with
$\ell$ parts and length $k$. 
Let $$
G(z,x,y)=\sum_{n,\ell,k}g(n,k,\ell)z^nx^\ell y^k.
$$
\begin{proposition}
We have
\begin{equation}\label{G:func} 
G(z,x,y)=\frac{1}{1-\sum_n \frac{xyz^n}{1-xz^n}}.
\end{equation}
\label{genegf}
\end{proposition}
\begin{proof}
This is straightforward using basic decomposition.
Each $b^{i}$ gives a contribution
$yx^{i}z^{bi}$ to the generating function. As $b$ and $i$ can have any non--negative values
the generating function of the generalized composition
of length one is $G_1(z,x,y)=\sum_{b\ge 0}\sum_{i\ge 0} 
yx^{i}z^{bi}=y\sum_{b}\frac{xz^b}{1-xz^b}$.
As a generalized composition is an ordered sequence of generalized compositions
of length 1, we get that
$$
G(x,y,z)=\frac{1}{1-G_1(z,x,y)}.$$
This completes the proof.
\end{proof}

Now we would like to link those generalized compositions 
to Carlitz compositions. 
 A Carlitz composition is a composition where any two 
consecutive entries must be different. Therefore a Carlitz
composition is a word $b_1^{i_1}b_2^{i_2}\ldots $ with $i_j=1$
and $b_j\neq b_{j+1}$ for all $j$.

Let $c(n)$ the number of Carlitz compositions of $n$.
A classical result is the following:
\begin{proposition}\cite{carlitz}
The generating function of Carlitz compositions
$C(z)$ is
$$
\frac{1}{1-\sum_n \frac{z^n}{1+z^n}}.
$$
\end{proposition}
\begin{proof}
There are numerous proofs for this result. We give a new one that links
Carlitz compositions to generalized compositions. When we compare
the previous generating function to the one presented in Proposition
\ref{genegf}, we straight away get that $C(z)=G(z,-1,-1)$. This implies 
that there exists a signed bijection between Carlitz compositions and
generalized compositions weighted by $-1$ to the number of parts plus the length. 
Equivalently, as Carlitz compositions are generalized compositions, there
exists a sign reversing involution $\phi$ on generalized compositions when the
sign is $1$ if the number of parts plus the length is even and $-1$ otherwise and
where the fixed points are indeed
the Carlitz compositions. We note that the sign of the Carlitz compositions
is always one as their number of parts is equal to their length.

This sign reversing involution is straightforward to define. Given a generalized
composition $B=b_1^{i_1}b_2^{i_2}\ldots b_k^{i_k}$, let $j$ be the first index
such that $i_j>1$ or $i_j=1$ and $b_j=b_{j+1}$. 
\begin{itemize} 
\item If no such index exists
then $B$ is a Carlitz composition and $\phi(B)=B$. 
\item If $i_j>1$ then $\phi(B)=
b_1^{i_1}b_2^{i_2}\ldots b_{j-1}^{i_{j-1}}b_j b_j^{i_j-1}b_{j+1}^{i_{j+1}}\ldots b_k^{i_k}$.
\item If $i_j=1$ then $\phi(B)=
b_1^{i_1}b_2^{i_2}\ldots b_{j-1}^{i_{j-1}}b_{j+1}^{i_{j+1}+1}b_{j+2}^{i_{j+2}}\ldots b_k^{i_k}$.
\end{itemize}
The number of parts  does not change 
but the parity of the length is always changed if $B$ is not a fixed point. Therefore the sign
of $\phi(B)$ is minus the sign of $B$. It is straightforward to check that $\phi$
is an involution.
For example, if $B=5^14^14^21^2$, then $\phi(B)=5^14^31^2$.
\end{proof}

Now we will generalize the previous idea 
to give
a combinatorial characterization of Lemma \ref{lemcp}.
\begin{definition}\label{def:p-cc}
A $p$-Carlitz composition is a generalized composition
$b_1^{i_1}b_2^{i_2}\ldots b_k^{i_k}$ such that $i_j<p$ for any $j$
and if $b_j=b_{j+1}$ then $i_j+i_{j+1}\neq p$.
\end{definition}
Note that Carlitz compositions are exactly 
$2$-Carlitz compositions.

Let $c_p(n)$ be the number of $p$-Carlitz compositions of $n$.
We will indeed prove the following
\begin{proposition}\label{prop:gfp-cc}
The generating function of $p$-Carlitz  compositions $\sum_n c_p(n)z^n$
is equal to
$$
C_p(z)=\frac{1}{1-\sum_n \left(\frac{z^n}{1-z^n}-p\frac{z^{np}}{1-z^{np}}\right)}.
$$
\end{proposition}
\begin{proof}
We will generalize the ideas developed for Carlitz compositions.
A $p$-generalized composition is two--rowed array 
$\left(\begin{array}{l}B\\A\end{array}\right)=\left(\begin{array}{ccc}
b_1^{i_1}&\ldots &b_k^{i_k}\\a_1&\ldots &a_k\end{array}\right)$,  where the first row is a
generalized composition and the second row a sequence of non--negative integers such
that $a_j=0$ if $i_j$ is not a multiple of $p$ and $0<a_j<p$ otherwise.

Note that if $\left(\begin{array}{l}B\\A\end{array}\right)$ is a $p$-generalized compositions and $B$ is 
a $p$-Carlitz composition then $A=(0,\ldots ,0)$.

Let $g^{(p)}(n,\ell,k,j)$ be the number of $p$-generalized compositions of $n$ with
$\ell$ parts and length $k$ and $j$ positive entries in $A$. Let $$G^{(p)}(z,x,y,w):=\sum_{n,\ell,k,j}g^{(p)}(n,k,\ell,j)z^nx^\ell y^kw^j.$$
Then
\begin{equation}\label{Gp:func}G^{(p)}(z,x,y,w)=
\frac{1}{1-\sum_n \left(\frac{yxz^n}{1-xz^n}-\frac{yx^pz^{np}}{1-x^pz^{np}}+
(p-1)\frac{ywx^pz^{np}}{1-x^pz^{np}}\right)}.
\end{equation}
The arguments are the same as in the proof of Proposition \ref{genegf}.
Each $b^{i}$ gives a contribution
$yx^{i}z^{bi}$ to the generating function if $i$ is not a multiple of $p$
and $wyx^iz^{bi}$ otherwise.
 Therefore we need to prove that $C_p(z)=G_p(z,1,1,-1)$.
To do that 
we define a sign reversing involution $\xi$ on the set of $p$-generalized compositions, where
the fixed points are the $p$-Carlitz compositions and 
the sign of a $p$-generalized
composition $(B,A)$ is 1 if the sequence $A$ has an even number of
positive entries and $-1$ otherwise.

Given a $p$-generalized
composition $\left(\begin{array}{l}B\\A\end{array}\right)=\left(\begin{array}{ccc}
b_1^{i_1}&\ldots &b_k^{i_k}\\a_1&\ldots &a_k\end{array}\right)$, let $j$ be the first index
such that:
\begin{itemize}
\item $i_j\ge p$ or
\item $i_j<p$ and $b_j=b_{j+1}$ and $i_{j+1}$ is a multiple of $p$ or
\item $i_j<p$ and $b_j=b_{j+1}$ and $i_j+i_{j+1}$ is a multiple of $p$
\end{itemize}
If no such index exists then $B$ is a $p$-Carlitz composition 
and $\xi\left(\begin{array}{l}B\\A\end{array}\right)=\left(\begin{array}{l}B\\A\end{array}\right)$.

The involution is defined as:
\begin{itemize}
\item If $i_j\ge p$ then 
\begin{itemize}
\item if $i_j$ is a multiple of $p$ then
$$\xi\left(\begin{array}{l}B\\A\end{array}\right)=
\left(\begin{array}{cccccccc}b_1^{i_1}&\ldots& b_{j-1}^{i^{j-1}}&b_j^{a_j}&b_j^{i_j-a_j}&b_{j+1}&\ldots &b_k\\
a_1&\ldots& a_{j-1}&0&0&a_{j+1}&\ldots &a_k\end{array}\right),$$ 
\item otherwise  
$$\xi(B,A)=\left(\begin{array}{cccccccc}b_1^{i_1}&\ldots& b_{j-1}^{i_{j-1}}&b_j^{t}&b_j^{i_j-t}&b_{j+1}&\ldots &b_k\\
a_1&\ldots &a_{j-1}&0&p-t&a_{j+1}&\ldots &a_k\end{array}\right),$$
with  $t=i_j-p\left\lfloor i_j/p\right\rfloor$.
\end{itemize}
\item If $i_j<p$ and $b_j=b_{j+1}$ and $i_{j+1}$ is a multiple of $p$ then
\begin{itemize}
\item if $i_j+a_{j+1}=p$ then
$$\xi\left(\begin{array}{l}B\\A\end{array}\right)=\left(\begin{array}{cccccccc}
b_1^{i_1}&\ldots &b_{j-1}^{i_{j-1}}&b_j^{i_j+i_{j+1}}&b_{j+2}^{i_{k+2}}&\ldots& b_k\\
a_1&\ldots &a_{j-1}&0&a_{j+2}&\ldots &a_k\end{array}\right),$$ 
\item otherwise
$$\xi\left(\begin{array}{l}B\\A\end{array}\right)=
\left(\begin{array}{cccccccc}b_1^{i_1}&\ldots& b_{j}^{i_{j}}&b_{j+1}^{a_{j+1}}&b_{j+1}^{i_{j+1}-a_{j+1}}&b_{j+2}^{i_{k+2}}&\ldots &b_k^{i_k}\\
a_1&\ldots &a_{j}&0&0&a_{j+2}&\ldots &a_k\end{array}\right).$$
\end{itemize}
\item If $i_j<p$ and $b_j=b_{j+1}$ and $i_j+i_{j+1}$ is a multiple of $p$ then
$$\xi\left(\begin{array}{l}B\\A\end{array}\right)=\left(\begin{array}{ccccccc}
b_1^{i_1}&\ldots &b_{j-1}^{i^{j-1}}&b_j^{i_j+i_{j+1}}&b_{j+2}&\ldots& b_k^{i_k}\\
a_1&\ldots &a_{j-1}&i_j&a_{j+2}&\ldots &a_k\end{array}\right).$$  
\end{itemize}
It is straightforward to prove that $\xi$ is a sign reversing involution.
One can carefully check that the involution $\xi$ for $p=2$ and $\phi$ are identical. 
\end{proof}

\section{The number of generalized and $p$-Carlitz compositions}
We let $G(z)=G(z,1,1)$ be the generating function of generalized compositions. 

\begin{proposition} 
The function $G(z)$
has a dominant singularity which is a real root $\rho$ of
$$\sigma(z):=\sum_{n\ge1}\frac{z^n}{1-z^n}=1.$$ This root is approximately $\rho=0.406148005001\ldots$. Hence, it follows that the number of generalized compositions of $n$ is, asymptotically,
$$\frac1{\rho\sigma'(\rho)}\rho^{-n}=\frac1{\rho\sigma'(\rho)}\left(\frac1\rho\right)^n\sim(0.481225\dots)(2.462156\dots)^n.$$
\end{proposition}
\begin{proof} This follows from general principles since all the coefficients (except the zeroth) in the power series of $\sigma(z)$ are strictly positive (see, e.g.,  \cite{bc} for a discussion) but can be also proved directly: the function $\sigma(z)$ treated as a  function of a real variable is strictly increasing on the interval $(0,1)$. Since $\sigma(0)=0$ and $\lim_{z\to 1-}\sigma(z)=\infty$, it must have a unique real root $\rho$ on the interval $(0,1)$. It is also the unique root in the disk $|z|\le\rho$ since
$$|\sigma(z)|\le\sum_{n\ge1}\frac{|z|^n}{|1-z^n|}\le\sum_{n\ge1}\frac{|z|^n}{1-|z|^n}\le1$$
and for $|z|<\rho$  the last inequality is strict while for $z=\rho e^{i\theta}$, unless $\theta=2k\pi$,  $|1-z|>1-|z|$ and the middle inequality is strict. Hence, by Cauchy integral formula and residue calculation
$$g(n)=\frac1{2\pi i}\oint_{|z|=r}\frac{dz}{(1-\sigma(z))z^{n+1}}=\frac1{\sigma'(\rho)\rho^{n+1}}+O\left((\rho+\varepsilon)^{-n}\right),$$
for a suitably chosen $\varepsilon>0$.\end{proof}

\begin{proposition}
Let $p\ge2$.
The generating function of $p$-Carlitz compositions 
has a dominant singularity which is the unique real root $\rho_p$ of 
$$\sigma_p(z)=1,$$   
where
$$\sigma_p(z):= \sigma(z)-p\sigma(z^p)=\sum_{n\ge 1}
\Big(\frac{z^n}{1-z^n}-p\frac{z^{pn}}{1-z^{pn}}
\Big).$$   
Thus, the number of $p$-Carlitz compositions of $n$ is, asymptotically,
$$c_p(n)\sim
\frac1{\rho_p\sigma_p'(\rho_p)}\left(\frac1{\rho_p}\right)^n.$$
\end{proposition}
\begin{proof} Each of the functions $C_p(z)$ has a singularity at  $\rho_p$ which is a real solution of $\sigma_p(z)=1$ for $0<z<1$. This follows from the positivity of the coefficients of $G_{p}(z)$ established in Lemma~\ref{poslem} (or by monotonicity of $\sigma_p(z)$ on the positive half--line). To show its uniqueness requires a bit more work since the coefficients of $\sigma_p(z)$ are not generally non-negative.
We intend to apply Rouch\'e's theorem to show that $\rho_p$ is the unique root of $\sigma_p(z)=1$ in a disk $|z|\le r$, for some $0<r<1$. To this end, we first observe that the roots $\rho_p$ monotonically decrease to $\rho$ as $p\ge2$ increases.  For this, it is enough to show that $\sigma_p(z)\le\sigma_{p+1}(z)$, i.e. that $p\sigma(z^p)\ge (p+1)\sigma(z^{p+1})$ for which it is enough that for $n\ge1$
$$p\frac{z^{np}}{1-z^{np}}\ge  (p+1)\frac{z^{n(p+1)}}{1-z^{n(p+1)}}.$$
This last statement is equivalent to
$f_p(z^n)\le p$ for $0<z<1$, where $f_p(y)=y(p+1-y^p)$, which is true since $f_p(1)=p$ and $f_p$ is increasing on $(0,1)$. 

In order to simplify calculations we will assume that $p\ge3$  (the case $p=2$ corresponds to Carlitz compositions and has been handled, by the same argument).
Putting together the terms of $\sum z^n/(1-z^n)$ in groups of $p$, rewrite $\sigma_p(z)$ as
$$\sum_{n\ge1}
\Big(\sum_{k=1}^p\frac{z^{(n-1)p+k}}{1-z^{(n-1)p+k}}-p\frac{z^{np}}{1-z^{np}}
\Big)=
\sum_{n\ge1}
\sum_{k=1}^{p-1}\left\{\frac{z^{(n-1)p+k}}{1-z^{(n-1)p+k}}-\frac{z^{np}}{1-z^{np}}\right\}.
$$
The absolute value of the term in curly brackets is
\begin{eqnarray*}
&&\Big|\sum_{k=1}^{p-1}
\Big(\frac{z^{(n-1)p+k}}{1-z^{(n-1)p+k}}-\frac{z^{np}}{1-z^{np}}
\Big)
\Big|\le\sum_{k=1}^{p-1}
\Big|\frac{z^{(n-1)p+k}-z^{np}}{(1-z^{(n-1)p+k})(1-z^{np})}
\Big|\\&&\quad
\le\frac{|z|^{(n-1)p}}{(1-|z|^{np})(1-|z|^{(n-1)p+1})}\sum_{k=1}^{p-1}|z|^k(1+|z|^{p-k})\\&&\quad
\le\frac{|z|^{(n-1)p}}{(1-|z|^{np})(1-|z|^{(n-1)p+1})}
\Big(\frac{|z|}{1-|z|}+(p-1)|z|^p
\Big)\\&&\quad
\le2\frac{|z|^{(n-1)p+1}}{(1-|z|)(1-|z|^{np})(1-|z|^{(n-1)p+1})}
\end{eqnarray*}
Hence, the sum over $n>n_0$ is bounded by
\begin{eqnarray*}
|h_p(z)|&\le&\frac{2|z|}{(1-|z|)(1-|z|^{(n_0+1)p})(1-|z|^{n_0p+1})}\sum_{n>n_0}|z|^{(n-1)p}\\
&=&\frac{2|z|^{n_0p+1}}{(1-|z|)(1-|z|^{p})(1-|z|^{(n_0+1)p})(1-|z|^{n_0p+1})}
\\
&\le&\frac{2|z|^{3n_0+1}}{(1-|z|)(1-|z|^{3})(1-|z|^{3(n_0+1)})(1-|z|^{3n_0+1})}
\end{eqnarray*} 
where in the last step we used the fact that $p\ge3$. In particular, choosing $n_0=2$, for $|z|=0.55$, the above expression is bounded by $0.083$. The rest of $\sigma_p(z)$ is 
\begin{eqnarray*}
&&
\sum_{k=1}^{2p}\frac{z^{k}}{1-z^{k}}-p
\Big(\frac{z^{p}}{1-z^{p}}
+\frac{z^{2p}}{1-z^{2p}}
\Big)\\&&\quad
=\sum_{k=1}^{6}\frac{z^{k}}{1-z^{k}}+\sum_{k\ge7}\frac{z^{k}}{1-z^{k}}
-p
\Big(\frac{z^{p}}{1-z^{p}}
+\frac{z^{2p}}{1-z^{2p}}
\Big).
\end{eqnarray*}
For $|z|=0.55$ 
we have
$$
\Big|\sum_{k\ge7}\frac{z^k}{1-z^k}
\Big|\le\frac{|z|^7}{(1-|z|)(1-|z|^7)}\le0.035,$$
and whenever $p\ge 3$  
$$p
\Big|\frac{z^p}{1-z^p}+\frac{z^{2p}}{1-z^{2p}}
\Big|\le p
\Big(\frac{|z|^p}{1-|z|^p}+\frac{|z|^{2p}}{1-|z|^{2p}}
\Big)\le0.65$$
Also, on the circle $|z|=0.55$,
$$\Big|\sum_{k=1}^6\frac{z^k}{1-z^k}-1
\Big|\ge 0.98> 0.083+0.65+0.035.$$ Hence, by Rouch\'e's theorem the equations $\sigma_p(z)=1$ and $\sum_{k=1}^6z^k/(1-z^k)=1$ have the same number of roots in the disc $|z|\le0.55$. Since the latter equation has the unique root in that disk, we conclude that $\rho_p$ is the dominant singularity of $G_p(z)$. Hence, by Cauchy, we get
\begin{eqnarray*}g_{p}(n)&=&\frac1{2\pi i}\oint_{|z|=r}\frac{dz}{(1-\sigma_p(z))z^{n+1}}=
\frac1{\sigma'_p(\rho_p)\rho_p^{n+1}}+O\left((\rho_p+\varepsilon)^{-n}\right).
\end{eqnarray*}
This completes the proof.\end{proof}

The approximate values of $1/\rho_p$ and the coefficients for the first few 
values of $p$ are given in Table~\ref{tab:asymp}. 

\begin{table}[htbp]
\begin{center}
\begin{tabular}{r|c|c}
$p$   & $1/(\rho_p\sigma'_p(\rho_p))$ & $1/\rho_p$   \\ \hline
2 & 0.4563501674  & 1.750226659
\\ \hline
3 & 0.5328099814  & 2.124758487
\\ \hline
4 & 0.5325715914  & 2.303902594
\\ \hline
5 & 0.5176390138  & 2.388474776
\\ \hline
6 & 0.5039489021  & 2.428059753
\\ \hline
7 & 0.4944459900  & 2.446480250
\\ \hline
8 & 0.4885607176  & 2.455002608
\\ \hline
9 & 0.4851499671  & 2.458917927
\\ \hline
10 & 0.4832639100  & 2.460702209
\\
\end{tabular}
\end{center}
\caption{Approximate values of the coefficients and the bases\label{tab:asymp}}
\end{table}
As $p$ increases to infinity the condition in Definition~\ref{def:p-cc} becomes less restrictive and thus  $p$-Carlitz compositions increasingly resemble  of generalized compositions. This can be also see from the form of the generating function in Proposition~\ref{prop:gfp-cc}. 

\section{Further remarks}

\noindent{\bf Remark 1.} As far as we know generalized compositions (or $p$-Carlitz compositions) have not appeared in a natural way before and may deserve further study. However, functions of the form (\ref{G:func}) and (\ref{Gp:func}) and limiting distributions of random variables represented by them are well understood thanks to work of Bender \cite{b}. Bender's work has been generalized by Hwang \cite{hwang} and is now referred to as a quasi-power theorem. We follow a presentation
by Flajolet and Sedgewick in their forthcoming book  
 \cite{fs} (see Sections~IX.5-6) and we refer there for more detailed discussion.  For example, 
the generating functions of the number of parts, $M_n$, and the length, $L_n$, are, respectively,
\begin{equation}\label{gfparts:alt}
G(z,u,1)=\frac1{1-\sum_{j=1}^\infty\frac{z^ju}{1-z^ju}},
\end{equation} 
and
\begin{equation}\label{gfparenth:alt}
G(z,1,u)=
\frac1{1-u\sum_{j=1}^\infty\frac{z^j}{1-z^j}}.
\end{equation} 
According to a  version of Bender's theorem  given by Flajolet and Sedgewick \cite[Theorem IX.8, Section IX.6]{fs}
  $M_n$ and $L_n$  are both asymptotically normal with means and variances linear in $n$, that is for a real number $t$
$$\Pr
\Big(\frac{M_n-\mu_mn}{\sigma_m\sqrt{n}}\le t
\Big)\longrightarrow\Phi(t)\quad\mbox{and}\quad\Pr
\Big(\frac{L_n-\mu_\ell n}{\sigma_\ell\sqrt{n}}\le t
\Big)\longrightarrow\Phi(t),$$
where $\Phi(t)=\frac1{\sqrt{2\pi}}\int_{\infty}^te^{-s^2/2}ds$ is the distribution function of the standard normal random variable. The values of  $\mu$'s,
may be obtained by evaluating  the derivative of $\rho/\rho(u)$ at $u=1$
(which gives $-\rho'(1)/\rho$)
where $\rho(u)$ is the solution of $H(\rho(u),u)=0$, $\rho(1)=\rho$,
and $H(z,u)$
is the denominator on the right--hand side of (\ref{gfparts:alt}) and (\ref{gfparenth:alt}), respectively. 
 By implicit differentiation $\rho'(1)=-H_u(\rho,1)/H_z(\rho,1)$ which gives
$$\mu_m=\frac{\sum_{j=1}^\infty\rho^j/(1-\rho^j)^2}{\rho\sum_{j=1}^\infty j\rho^{j-1}/(1-\rho^j)^2}\sim0.728026753148681\dots
$$
and 
$$\mu_\ell=\frac{1}{\sum_{j=1}^\infty j\rho^j/(1-\rho^j)^2}\sim0.6610001082360630\ldots
$$
Similarly, the coefficient in front of the variance is 
$$\Big(\Big(\frac\rho{\rho(u)}
\Big)^{''}+
\Big(\frac\rho{\rho(u)}
\Big)^{'}-
\Big(\Big(\frac\rho{\rho(u)}
\Big)^{'}
\Big)^2
\Big)_{\big|{u=1}}=
\Big(\frac{\rho'(1)}\rho\Big)^2-\frac{\rho'(1)}\rho-\frac{\rho''(1)}\rho.$$
The value of $\rho''(1)$ is obtained from the second differentiation of $H(\rho(u),u)=0$ and leads to
$$\sigma_m^2\sim2.93020675623619\ldots\quad\sigma_\ell^2\sim0.183409175142911\ldots$$
Similar arguments work for joint distributions and $p$-Carlitz compositions.

\noindent{\bf Remark 2.}
Alternatively,  generalized compositions  may be studied by observing that they are weighted compositions; each part that is repeated $i$ times in a row is weighted by $2^{i-1}$. Hence, the (classical) composition is weighted by $2^{M_n-R_n}$, where $M_n$ is the number of parts and $R_n$ is the number of runs. By a run we mean a succession (of a maximal length) of equal parts; for example the composition $(1,2,2,4,1,1,1,3)$ of 15 has 5 runs of lengths 1, 2, 1, 3, and 1. For  compositions these quantities have been studied in the past. In particular, the  exact distribution of $M_n$ is known to be $1+\Bin(n-1)$, where $\Bin(m)$ denotes a binomial random variable with parameters $m$ and $p=1/2$. We  need some information about the  joint distribution of $M_n$ and $R_n$. Write 
\begin{equation}\label{runs}R_n=1+\sum_{j=2}^{M_n}I_{\k_j\ne\k_{j-1}}.\end{equation} 
The quantity, 
$W_n:=M_n-R_n=\sum_{j=2}^nI_{\k_j=\k_{j-1}},$ 
under the name the number of levels, has been studied by various authors. In particular, 
Heubach and Mansour \cite{hm} showed  
that the trivariate generating 
function of the number of compositions of $n$ with $k$ parts and $\ell$ levels is 
$$A(z,u,w):=\sum_{n,k,\ell}a(n,k,\ell)x^nu^kw^\ell=\frac1{1-\sum_{j=1}^\infty\frac{z^ju}{1-z^ju(w-1)}
}.$$
Since generalized compositions are   
compositions weighted by $2^{W_n}$, it follows, for example, that the bivariate generating function of generalized compositions of $n$ with $k$ parts is 
$A(z,u,2)$. This agrees with (\ref{gfparts:alt}) as it should. 

Likewise, if we were interested in the length
 $L_n$ of a generalized composition  then  all we need is to notice  that given the values of $M_n$ and $R_n$ the length is distributed like $R_n+\Bin(M_n-R_n)$. Thus for a given $n$ its probability generating function is
$$\E u^{L_n}2^{W_n}=\E\E_{M_n,R_n} u^{R_n+\Bin(M_n-R_n)}2^{W_n}=\E u^{R_n}2^{W_n}\E_{M_n,R_n}u^{\Bin(W_n)},$$
where $\E$ is the integration over the space of ordinary compositions of $n$ and $\E_{M_n,R_n}$ is the conditional expectation given $M_n$ and $R_n$. Since 
$\E_{M_n,R_n}u^{\Bin(W_n)}=\left(\frac{u+1}2\right)^{W_n}$ we see that  
$$\E u^{L_n}2^{W_n}=\E u^{R_n}2^{W_n}
\Big(\frac{u+1}2
\Big)^{W_n}=
\E u^{M_n-L_n}(u+1)^{W_n}=\E u^{M_n}(1+u^{-1})^{W_n}.$$
But that just means that the bivariate generating function of generalized compositions of $n$ whose length is $k$  is given by
$A(z,u,1+u^{-1})$. Again,  this agrees with (\ref{gfparenth:alt}).


\section{Acknowledgment}
 Part of the research of the second author  was carried out while 
he was visiting the Algorithms and Complexity Group at the LRI, Universit\'e Paris-Sud in 2006-2007 academic year. He would like to express his thanks to Sylvie Corteel, Dominique Gouyou-Beauchamps and other members of the group for their support and hospitality.


\begin{thebibliography}{10}

\bibitem{b}
E.~A. Bender,
\newblock Central and local limit theorems applied to asymptotic enumeration,
\newblock {\em J. Combinatorial Theory Ser. A} {\bf 15} (1973), 91--111.

\bibitem{bc}
E.~A. Bender and E.~R. Canfield,
\newblock Locally restricted compositions, I. Restricted adjacent
  differences,
\newblock {\em Electron. J. Combin.} {\bf 12} (2005), Paper R57.  Available at \href{http://www.combinatorics.org/Volume_12/Abstracts/v12i1r57.html}{\tt http://www.combinatorics.org/Volume\_12/Abstracts/v12i1r57.html}.

\bibitem{carlitz}
L.~Carlitz,
\newblock Restricted compositions,
\newblock {\em Fibonacci Quart.} {\bf 14} (1976), 254--264.

\bibitem{fs}
P.~Flajolet and R.~Sedgewick,
\newblock {\it Analytic Combinatorics}, 0th ed., 3rd printing, 2005.
\newblock \href{http://algo.inria.fr/flajolet/Publications/AnaCombi1to9.pdf}{\tt http://algo.inria.fr/flajolet/Publications/AnaCombi1to9.pdf}.

\bibitem{gh}
W.~M.~Y. Goh and P.~Hitczenko,
\newblock Average number of distinct part sizes in a random Carlitz
  composition,
\newblock {\em Europ. J. Combinatorics} {\bf 23} (2002), 647--657.

\bibitem{hm}
S.~Heubach and T.~Mansour,
\newblock Counting rises, levels, and drops in compositions,
\newblock {\em Integers} {\bf 5} (1) (2005), Paper A11.  Available at
\href{http://www.integers-ejcnt.org/vol5.html}{\tt http://www.integers-ejcnt.org/vol5.html}.

\bibitem{hwang}
H.--~K.~Hwang,
\newblock On convergence rates in the central limit theorems for combinatorial
  structures,
\newblock {\em European J. Combin.} {\bf 19} (1998), 329--343.

\bibitem{khey3}
B.~L.~Kheyfets,
\newblock The average number of distinct part sizes of a given multiplicity in
  a random Carlitz composition,
\newblock {\em Adv. Appl. Math.} {\bf 35} (2005), 335--354.

\bibitem{kpcarlitz}
A.~Knopfmacher and H.~Prodinger,
\newblock On {C}arlitz compositions,
\newblock {\em European J. Combin.} {\bf 19} (1998), 579--589. 

\bibitem{lpcarlitz}
G.~Louchard and H.~Prodinger,
\newblock Probabilistic analysis of {C}arlitz compositions,
\newblock {\em Disc. Math. Theor. Comp. Sci.} {\bf 5} (2002), 71--96. 

\bibitem{s}
N.~J.~A. Sloane,
\newblock The On-Line Encyclopedia of Integer Sequences, published electronically at 
\newblock \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 05A15, 05A16.\\

\noindent {\it Keywords}: integer composition, Carlitz composition, generalized composition.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A003242}, \seqnum{A129921},
and \seqnum{A129922}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 6 2007;
revised versions received August 3 2007; August 19 2007.
Published in {\it Journal of Integer Sequences}, August 19 2007.

\bigskip
\hrule
\bigskip

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


\end{document}