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_j1-|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 $0n_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}