Generalizations of Carlitz Compositions

Sylvie Corteel^{1} LRI CNRS Université Paris-Sud 91405 Orsay France

                 Sylvie.Corteel@lri.fr

Paweł Hitczenko^{2} LRI CNRS Université Paris-Sud 91405 Orsay France and Department of Mathematics Drexel University Philadelphia, PA 19104 USA

              phitczenko@math.drexel.edu

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.

1Supported in part by the NSF grant INT-0230800.

2Supported in part by the NSF grant INT-0230800 and by the NSA under Grant H98230-05-1-0016.

1 Introduction

The following function σ(z) defined by

σ(z) = ∑_{j=1}^{∞}(−1)^{j−1} \frac{z^{j}}{1 − z^{j}} .  (1)

has been introduced by Carlitz in [3]. 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 [9, 5, 10, 8]; see also \underline{A003242} in [11]). Specifically, if C(z) is the generating function of Carlitz compositions then

C(z) = \frac{1}{1 − σ(z)}.  (2)

If σ(z) had all coefficients non–negative the same would be true of C(z). However, σ(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 (1), we see that

σ(z) = ∑_{j=1}^{∞}(−1)^{j−1}z^{j} ∑_{k=0}^{∞} z^{jk} = ∑_{j,k≥1}(−1)^{j−1}z^{jk} = ∑_{n≥1} z^{n} ∑_{j≥1, j|n}(−1)^{j−1},

and so σ(z) is the generating function of a sequence ϕ(n) := ∑_{j≥1, j|n}(−1)^{j−1}, which is just the

number of odd divisors of n minus the number of even divisors of n. Equivalently, ϕ(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, σ_{p}(z) to be the generating function of a sequence “the number of all divisors of n minus p times the number of divisors of n that are divisible by p”. That is, let d_{q}(m) be the number of divisors of m that are multiples of q and let

ϕ_{p}(j) := d_{1}(j) − pd_{p}(j) = d_{1}(j) − pd_{1}(j/p).

We then define

σ_{p}(z) := ∑_{j=1}^{∞} ϕ_{p}(j)z^{j},

and set

C_{p}(z) := \frac{1}{1 − σ_{p}(z)},  (3)

(Thus, (2) is the special case of (3) 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.

Lemma 1. C_{p}(z) defined by (3) has non-negative, increasing, integer coefficients for every integer p ≥ 2.

Proof. Let C_{p}(z) = ∑_{n≥0} c_{p}(n)z^{n} and set Δ_{p}(n) := −ϕ_{p}(n), n ≥ 1, with Δ_{p}(0) = 1. Set

Ψ_{q}(x) = ∑_{m≤x} ϕ_{q}(m) = D_{1}(x) − qD_{q}(x).

Then, (3) can be written as

( ∑_{n≥0} c_{p}(n)z^{n}) · ( ∑_{n≥0} Δ_{p}(n)z^{n}) = 1,

which leads to an infinite system of linear equations

∑_{k=0}^{m} c_{p}(k)Δ_{p}(m − k) = 0, m = 1, 2, ….

Adding up the first m of them gives

c_{p}(0) ∑_{j=1}^{m} Δ_{p}(j) + ∑_{ℓ=1}^{m} c_{p}(ℓ) ∑_{j=0}^{m−ℓ} Δ_{p}(j) = 0,

which, after extracting the last term and using Δ_{p}(0) = 1 gives

c_{p}(m) = −c_{p}(0) ∑_{j=1}^{m} Δ_{p}(j) − ∑_{ℓ=1}^{m−1} c_{p}(ℓ) ∑_{j=0}^{m−ℓ} Δ_{p}(j)

= c_{p}(0)Ψ_{p}(m) + ∑_{ℓ=1}^{m−1} c_{p}(ℓ)(−1 + Ψ_{p}(m − ℓ)).

Since this is to hold for all m ≥ 1, by an inductive argument it is enough to know that all the Ψ_{p}(n)’s are positive. In order to show that let I(d, m) = 1 if d divides m, zero otherwise. Then

D_{1}(n) = ∑_{m≤n} ∑_{d=1}^{n} I(d, m) = ∑_{d=1}^{n} ∑_{m≤n} I(d, m)

= ∑_{d=1}^{n} ⌊\frac{n}{d}⌋.

Similarly,

pD_{p}(n) = p ∑_{m≤n} ∑_{d=1}^{n} I(dp, m) = ∑_{d=1}^{n} p⌊\frac{n}{pd}⌋.

Since ⌊n/d⌋ ≥ p⌊n/pd⌋ (just consider n = mpd + ℓ with 0 ≤ ℓ < pd), each term in the sum

∑_{d=1}^{n} (⌊\frac{n}{d}⌋ − p⌊\frac{n}{pd}⌋)

is nonnegative and for d = n the term is 1. Thus the whole sum is strictly positive.

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 [11] as \underline{A129921}, while p-Carlitz compositions (or more precisely, 3-Carlitz compositions) are given as \underline{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.

2 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}, …) such that ∑_{i} a_{i} = n. A composition of n can also be seen as a word b_{1}^{i_{1}}b_{2}^{i_{2}} … b_{k}^{i_{k}} with ∑_{j} b_{j}i_{j} = n, b_{j} > 0, i_{j} > 0 and b_{j} ≠ b_{j+1} for any j.

Definition 2. A generalized composition of n is a generalized word b_{1}^{i_{1}}b_{2}^{i_{2}} … b_{k}^{i_{k}} with ∑_{j} b_{j}i_{j} = n, b_{j} > 0, i_{j} > 0 for any j. The number of parts of the generalized composition is ∑_{j} i_{j} and the length is k.

Remark. Generalized compositions are compositions where the condition b_{j} ≠ 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}.

There are 7 generalized compositions of 3: 3^{1}, 1^{1}2^{1}, 2^{1}1^{1}, 1^{3}, 1^{2}1^{1}, 1^{1}1^{2} and 1^{1}1^{1}1^{1}.

Let g(n, ℓ, k) the number of generalized compositions of n with ℓ parts and length k. Let

G(z, x, y) = ∑_{n,ℓ,k} g(n, k, ℓ)z^{n}x^{ℓ}y^{k}.

Proposition 3. We have

G(z, x, y) = \frac{1}{1 − ∑_{n} \frac{xyz^{n}}{1−xz^{n}}} .  (4)

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) = ∑_{b≥0} ∑_{i≥0} yx^{i}z^{bi} = y ∑_{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.

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}} … with i_{j} = 1 and b_{j} ≠ b_{j+1} for all j.

Let c(n) the number of Carlitz compositions of n. A classical result is the following:

Proposition 4. [3] The generating function of Carlitz compositions C(z) is

\frac{1}{1 − ∑_{n} \frac{z^{n}}{1+z^{n}}} .

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 3, 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 ϕ 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}} … 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}.

• If no such index exists then B is a Carlitz composition and ϕ(B) = B.

• If i_{j} > 1 then ϕ(B) = b_{1}^{i_{1}}b_{2}^{i_{2}} … b_{j−1}^{i_{j−1}}b_{j}b_{j}^{i_{j}−1}b_{j+1}^{i_{j+1}} … b_{k}^{i_{k}}.

• If i_{j} = 1 then ϕ(B) = b_{1}^{i_{1}}b_{2}^{i_{2}} … b_{j−1}^{i_{j−1}}b_{j+1}^{i_{j+1}+1}b_{j+2}^{i_{j+2}} … b_{k}^{i_{k}}.

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 ϕ(B) is minus the sign of B. It is straightforward to check that ϕ is an involution. For example, if B = 5^{1}4^{1}4^{2}1^{2}, then ϕ(B) = 5^{1}4^{3}1^{2}.

Now we will generalize the previous idea to give a combinatorial characterization of Lemma 1.

Definition 5. A p-Carlitz composition is a generalized composition b_{1}^{i_{1}}b_{2}^{i_{2}} … 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} ≠ p.

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

Proposition 6. The generating function of p-Carlitz compositions ∑_{n} c_{p}(n)z^{n} is equal to

C_{p}(z) = \frac{1}{1 − ∑_{n} (\frac{z^{n}}{1−z^{n}} − p\frac{z^{np}}{1−z^{np}} )}.

Proof. We will generalize the ideas developed for Carlitz compositions. A p-generalized com-

position is two–rowed array ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}b_{1}^{i_{1}} & … & b_{k}^{i_{k}} \\ a_{1} & … & a_{k} \end{matrix} ), 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 ( \begin{matrix}B \\ A \end{matrix} ) is a p-generalized compositions and B is a p-Carlitz composition

then A = (0, …, 0).

Let g^{(p)}(n, ℓ, k, j) be the number of p-generalized compositions of n with ℓ parts and length k and j positive entries in A. Let

G^{(p)}(z, x, y, w) := ∑_{n,ℓ,k,j} g^{(p)}(n, k, ℓ, j)z^{n}x^{ℓ}y^{k}w^{j}.

Then

G^{(p)}(z, x, y, w) = \frac{1}{1 − ∑_{n} (\frac{yxz^{n}}{1−xz^{n}} − \frac{yx^{p}z^{np}}{1−x^{p}z^{np}} + (p − 1)\frac{ywx^{p}z^{np}}{1−x^{p}z^{np}} )}.  (5)

The arguments are the same as in the proof of Proposition 3. Each b^{i} gives a contribution yx^{i}z^{bi} to the generating function if i is not a multiple of p and wyx^{i}z^{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 ξ 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 ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}b_{1}^{i_{1}} & … & b_{k}^{i_{k}} \\ a_{1} & … & a_{k} \end{matrix} ), let j be the first index

such that:

• i_{j} ≥ p or

• i_{j} < p and b_{j} = b_{j+1} and i_{j+1} is a multiple of p or

• i_{j} < p and b_{j} = b_{j+1} and i_{j} + i_{j+1} is a multiple of p

If no such index exists then B is a p-Carlitz composition and ξ ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}B \\ A \end{matrix} ).

The involution is defined as:

• If i_{j} ≥ p then

– if i_{j} is a multiple of p then

ξ ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}b_{1}^{i_{1}} & … & b_{j−1}^{i^{j−1}} & b_{j}^{a_{j}} & b_{j}^{i_{j}−a_{j}} & b_{j+1} & … & b_{k} \\ a_{1} & … & a_{j−1} & 0 & 0 & a_{j+1} & … & a_{k} \end{matrix} ) ,

– otherwise

ξ(B, A) = ( \begin{matrix}b_{1}^{i_{1}} & … & b_{j−1}^{i_{j−1}} & b_{j}^{t} & b_{j}^{i_{j}−t} & b_{j+1} & … & b_{k} \\ a_{1} & … & a_{j−1} & 0 & p − t & a_{j+1} & … & a_{k} \end{matrix} ) ,

with t = i_{j} − p ⌊i_{j}/p⌋.

• If i_{j} < p and b_{j} = b_{j+1} and i_{j+1} is a multiple of p then

– if i_{j} + a_{j+1} = p then

ξ ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}b_{1}^{i_{1}} & … & b_{j−1}^{i_{j−1}} & b_{j}^{i_{j}+i_{j+1}} & b_{j+2}^{i_{k+2}} & … & b_{k} \\ a_{1} & … & a_{j−1} & 0 & a_{j+2} & … & a_{k} \end{matrix} ) ,

– otherwise

ξ ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}b_{1}^{i_{1}} & … & 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}} & … & b_{k}^{i_{k}} \\ a_{1} & … & a_{j} & 0 & 0 & a_{j+2} & … & a_{k} \end{matrix} ) .

• If i_{j} < p and b_{j} = b_{j+1} and i_{j} + i_{j+1} is a multiple of p then

ξ ( \begin{matrix}B \\ A \end{matrix} ) = ( \begin{matrix}b_{1}^{i_{1}} & … & b_{j−1}^{i^{j−1}} & b_{j}^{i_{j}+i_{j+1}} & b_{j+2} & … & b_{k}^{i_{k}} \\ a_{1} & … & a_{j−1} & i_{j} & a_{j+2} & … & a_{k} \end{matrix} ) .

It is straightforward to prove that ξ is a sign reversing involution. One can carefully check that the involution ξ for p = 2 and ϕ are identical.

3 The number of generalized and p-Carlitz compositions

We let G(z) = G(z, 1, 1) be the generating function of generalized compositions.

Proposition 7. The function G(z) has a dominant singularity which is a real root ρ of

σ(z) := ∑_{n≥1} \frac{z^{n}}{1 − z^{n}} = 1.

This root is approximately ρ = 0.406148005001 . . .. Hence, it follows that the number of generalized compositions of n is, asymptotically,

\frac{1}{ρσ′(ρ)}ρ^{−n} = \frac{1}{ρσ′(ρ)} (\frac{1}{ρ})^{n} ∼ (0.481225 …)(2.462156 …)^{n}.

Proof. This follows from general principles since all the coefficients (except the zeroth) in the power series of σ(z) are strictly positive (see, e.g., [2] for a discussion) but can be also proved directly: the function σ(z) treated as a function of a real variable is strictly increasing on the interval (0, 1). Since σ(0) = 0 and lim_{z→1−} σ(z) = ∞, it must have a unique real root ρ on the interval (0, 1). It is also the unique root in the disk |z| ≤ ρ since

|σ(z)| ≤ ∑_{n≥1} \frac{|z|^{n}}{|1 − z^{n}|} ≤ ∑_{n≥1} \frac{|z|^{n}}{1 − |z|^{n}} ≤ 1

and for |z| < ρ the last inequality is strict while for z = ρe^{iθ}, unless θ = 2kπ, |1 − z| > 1 − |z| and the middle inequality is strict. Hence, by Cauchy integral formula and residue calculation

g(n) = \frac{1}{2πi} ∮_{|z|=r} \frac{dz}{(1 − σ(z))z^{n+1}} = \frac{1}{σ′(ρ)ρ^{n+1}} + O ((ρ + ε)^{−n}) ,

for a suitably chosen ε > 0.

Proposition 8. Let p ≥ 2. The generating function of p-Carlitz compositions has a dominant singularity which is the unique real root ρ_{p} of

σ_{p}(z) = 1,

where

σ_{p}(z) := σ(z) − pσ(z^{p}) = ∑_{n≥1} (\frac{z^{n}}{1 − z^{n}} − p\frac{z^{pn}}{1 − z^{pn}} ).

Thus, the number of p-Carlitz compositions of n is, asymptotically,

c_{p}(n) ∼ \frac{1}{ρ_{p}σ′_{p}(ρ_{p})} (\frac{1}{ρ_{p}} )^{n} .

Proof. Each of the functions C_{p}(z) has a singularity at ρ_{p} which is a real solution of σ_{p}(z) = 1 for 0 < z < 1. This follows from the positivity of the coefficients of G_{p}(z) established in Lemma 1 (or by monotonicity of σ_{p}(z) on the positive half–line). To show its uniqueness requires a bit more work since the coefficients of σ_{p}(z) are not generally non-negative. We intend to apply Rouché’s theorem to show that ρ_{p} is the unique root of σ_{p}(z) = 1 in a disk |z| ≤ r, for some 0 < r < 1. To this end, we first observe that the roots ρ_{p} monotonically decrease to ρ as p ≥ 2 increases. For this, it is enough to show that σ_{p}(z) ≤ σ_{p+1}(z), i.e. that pσ(z^{p}) ≥ (p + 1)σ(z^{p+1}) for which it is enough that for n ≥ 1

p\frac{z^{np}}{1 − z^{np}} ≥ (p + 1)\frac{z^{n(p+1)}}{1 − z^{n(p+1)}} .

This last statement is equivalent to f_{p}(z^{n}) ≤ 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 ≥ 3 (the case p = 2 corresponds to Carlitz compositions and has been handled, by the same argument). Putting together the terms of ∑ z^{n}/(1 − z^{n}) in groups of p, rewrite σ_{p}(z) as

∑_{n≥1} ( ∑_{k=1}^{p} \frac{z^{(n−1)p+k}}{1 − z^{(n−1)p+k}} − p\frac{z^{np}}{1 − z^{np}} ) = ∑_{n≥1} ∑_{k=1}^{p−1} \{\frac{z^{(n−1)p+k}}{1 − z^{(n−1)p+k}} − \frac{z^{np}}{1 − z^{np}} \} .

The absolute value of the term in curly brackets is

| ∑_{k=1}^{p−1} (\frac{z^{(n−1)p+k}}{1 − z^{(n−1)p+k}} − \frac{z^{np}}{1 − z^{np}} )| ≤ ∑_{k=1}^{p−1} |\frac{z^{(n−1)p+k} − z^{np}}{(1 − z^{(n−1)p+k})(1 − z^{np})}|

≤ \frac{|z|^{(n−1)p}}{(1 − |z|^{np})(1 − |z|^{(n−1)p+1})} ∑_{k=1}^{p−1} |z|^{k}(1 + |z|^{p−k})

≤ \frac{|z|^{(n−1)p}}{(1 − |z|^{np})(1 − |z|^{(n−1)p+1})}(\frac{|z|}{1 − |z|} + (p − 1)|z|^{p})

≤ 2\frac{|z|^{(n−1)p+1}}{(1 − |z|)(1 − |z|^{np})(1 − |z|^{(n−1)p+1})}

Hence, the sum over n > n_{0} is bounded by

|h_{p}(z)| ≤ \frac{2|z|}{(1 − |z|)(1 − |z|^{(n_{0}+1)p})(1 − |z|^{n_{0}p+1})} ∑_{n>n_{0}} |z|^{(n−1)p}

= \frac{2|z|^{n_{0}p+1}}{(1 − |z|)(1 − |z|^{p})(1 − |z|^{(n_{0}+1)p})(1 − |z|^{n_{0}p+1})}
≤ \frac{2|z|^{3n_{0}+1}}{(1 − |z|)(1 − |z|^{3})(1 − |z|^{3(n_{0}+1)})(1 − |z|^{3n_{0}+1})}

where in the last step we used the fact that p ≥ 3. In particular, choosing n_{0} = 2, for |z| = 0.55, the above expression is bounded by 0.083. The rest of σ_{p}(z) is

∑_{k=1}^{2p} \frac{z^{k}}{1 − z^{k}} − p(\frac{z^{p}}{1 − z^{p}} + \frac{z^{2p}}{1 − z^{2p}} )

= ∑_{k=1}^{6} \frac{z^{k}}{1 − z^{k}} + ∑_{k≥7} \frac{z^{k}}{1 − z^{k}} − p(\frac{z^{p}}{1 − z^{p}} + \frac{z^{2p}}{1 − z^{2p}} ).

For |z| = 0.55 we have

| ∑_{k≥7} \frac{z^{k}}{1 − z^{k}} | ≤ \frac{|z|^{7}}{(1 − |z|)(1 − |z|^{7})} ≤ 0.035,

and whenever p ≥ 3

p|\frac{z^{p}}{1 − z^{p}} + \frac{z^{2p}}{1 − z^{2p}} | ≤ p(\frac{|z|^{p}}{1 − |z|^{p}} + \frac{|z|^{2p}}{1 − |z|^{2p}} ) ≤ 0.65

Also, on the circle |z| = 0.55,

| ∑_{k=1}^{6} \frac{z^{k}}{1 − z^{k}} − 1| ≥ 0.98 > 0.083 + 0.65 + 0.035.

Hence, by Rouché’s theorem the equations σ_{p}(z) = 1 and ∑_{k=1}^{6} z^{k}/(1 − z^{k}) = 1 have the same number of roots in the disc |z| ≤ 0.55. Since the latter equation has the unique root in that disk, we conclude that ρ_{p} is the dominant singularity of G_{p}(z). Hence, by Cauchy, we get

g_{p}(n) = \frac{1}{2πi} ∮_{|z|=r} \frac{dz}{(1 − σ_{p}(z))z^{n+1}} = \frac{1}{σ′_{p}(ρ_{p})ρ_{p}^{n+1}} + O ((ρ_{p} + ε)^{−n}) .

This completes the proof.

The approximate values of 1/ρ_{p} and the coefficients for the first few values of p are given in Table 1.

\begin{matrix}p & 1/(ρ_{p}σ′_{p}(ρ_{p})) & 1/ρ_{p} \\ 2 & 0.4563501674 & 1.750226659 \\ 3 & 0.5328099814 & 2.124758487 \\ 4 & 0.5325715914 & 2.303902594 \\ 5 & 0.5176390138 & 2.388474776 \\ 6 & 0.5039489021 & 2.428059753 \\ 7 & 0.4944459900 & 2.446480250 \\ 8 & 0.4885607176 & 2.455002608 \\ 9 & 0.4851499671 & 2.458917927 \\ 10 & 0.4832639100 & 2.460702209 \end{matrix}

Table 1: Approximate values of the coefficients and the bases

As p increases to infinity the condition in Definition 5 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 6.

4 Further remarks

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 (4) and (5) and limiting distributions of random variables represented by them are well understood thanks to work of Bender [1]. Bender’s work has been generalized by Hwang [7] and is now referred to as a quasi-power theorem. We follow a presentation by Flajolet and Sedgewick in their forthcoming book [4] (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,

G(z, u, 1) = \frac{1}{1 − ∑_{j=1}^{∞} \frac{z^{j}u}{1−z^{j}u}} ,  (6)

and

G(z, 1, u) = \frac{1}{1 − u ∑_{j=1}^{∞} \frac{z^{j}}{1−z^{j}}} .  (7)

According to a version of Bender’s theorem given by Flajolet and Sedgewick [4, Theorem IX.8, Section IX.6] M_{n} and L_{n} are both asymptotically normal with means and variances linear in n, that is for a real number t

Pr(\frac{M_{n} − μ_{m}n}{σ_{m}\sqrt{n}} ≤ t) ⟶ Φ(t) and Pr(\frac{L_{n} − μ_{ℓ}n}{σ_{ℓ}\sqrt{n}} ≤ t) ⟶ Φ(t),

where Φ(t) = \frac{1}{\sqrt{2π}} ∫_{∞}^{t} e^{−s^{2}/2}ds is the distribution function of the standard normal random variable. The values of μ’s, may be obtained by evaluating the derivative of ρ/ρ(u) at u = 1 (which gives −ρ′(1)/ρ) where ρ(u) is the solution of H(ρ(u), u) = 0, ρ(1) = ρ, and H(z, u) is the denominator on the right–hand side of (6) and (7), respectively. By implicit differentiation ρ′(1) = −H_{u}(ρ, 1)/H_{z}(ρ, 1) which gives

μ_{m} = \frac{∑_{j=1}^{∞} ρ^{j}/(1 − ρ^{j})^{2}}{ρ ∑_{j=1}^{∞} jρ^{j−1}/(1 − ρ^{j})^{2}} ∼ 0.728026753148681 …

and

μ_{ℓ} = \frac{1}{∑_{j=1}^{∞} jρ^{j}/(1 − ρ^{j})^{2}} ∼ 0.6610001082360630 …

Similarly, the coefficient in front of the variance is

((\frac{ρ}{ρ(u)})′′ + (\frac{ρ}{ρ(u)})′ − ((\frac{ρ}{ρ(u)})′)^{2})|_{u=1} = (\frac{ρ′(1)}{ρ})^{2} − \frac{ρ′(1)}{ρ} − \frac{ρ′′(1)}{ρ}.

The value of ρ′′(1) is obtained from the second differentiation of H(ρ(u), u) = 0 and leads to

σ_{m}^{2} ∼ 2.93020675623619 … σ_{ℓ}^{2} ∼ 0.183409175142911 …

Similar arguments work for joint distributions and p-Carlitz compositions. 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

R_{n} = 1 + ∑_{j=2}^{M_{n}} I_{κ_{j}≠κ_{j−1}}.  (8)

The quantity, W_{n} := M_{n} − R_{n} = ∑_{j=2}^{n} I_{κ_{j}=κ_{j−1}}, under the name the number of levels, has been studied by various authors. In particular, Heubach and Mansour [6] showed that the trivariate generating function of the number of compositions of n with k parts and ℓ levels is

A(z, u, w) := ∑_{n,k,ℓ} a(n, k, ℓ)x^{n}u^{k}w^{ℓ} = \frac{1}{1 − ∑_{j=1}^{∞} \frac{z^{j}u}{1−z^{j}u(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 (6) 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

Eu^{L_{n}}2^{W_{n}} = EE_{M_{n},R_{n}}u^{R_{n}+Bin(M_{n}−R_{n})}2^{W_{n}} = Eu^{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})} = (\frac{u+1}{2})^{W_{n}} we see that

Eu^{L_{n}}2^{W_{n}} = Eu^{R_{n}}2^{W_{n}}(\frac{u + 1}{2})^{W_{n}} = Eu^{M_{n}−L_{n}}(u + 1)^{W_{n}} = Eu^{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 (7).

5 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é 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.

References

[1] E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combinatorial Theory Ser. A 15 (1973), 91–111.

[2] E. A. Bender and E. R. Canfield, Locally restricted compositions, I. Restricted adjacent differences, Electron. J. Combin. 12 (2005), Paper R57. Available at

    http://www.combinatorics.org/Volume 12/Abstracts/v12i1r57.html.

[3] L. Carlitz, Restricted compositions, Fibonacci Quart. 14 (1976), 254–264.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, 0th ed., 3rd printing, 2005.

    http://algo.inria.fr/flajolet/Publications/AnaCombi1to9.pdf.

[5] W. M. Y. Goh and P. Hitczenko, Average number of distinct part sizes in a random Carlitz composition, Europ. J. Combinatorics 23 (2002), 647–657.

[6] S. Heubach and T. Mansour, Counting rises, levels, and drops in compositions, Integers

    5 (1) (2005), Paper A11. Available at http://www.integers-ejcnt.org/vol5.html.

[7] H.– K. Hwang, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin. 19 (1998), 329–343.

[8] B. L. Kheyfets, The average number of distinct part sizes of a given multiplicity in a random Carlitz composition, Adv. Appl. Math. 35 (2005), 335–354.

[9] A. Knopfmacher and H. Prodinger, On Carlitz compositions, European J. Combin. 19 (1998), 579–589.

[10] G. Louchard and H. Prodinger, Probabilistic analysis of Carlitz compositions, Disc. Math. Theor. Comp. Sci. 5 (2002), 71–96.

[11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: 05A15, 05A16.

Keywords: integer composition, Carlitz composition, generalized composition.

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

Received June 6 2007; revised versions received August 3 2007; August 19 2007. Published in Journal of Integer Sequences, August 19 2007.

Return to Journal of Integer Sequences home page.