ON CARLITZ COMPOSITIONS

Arnold Knopfmacher and Helmut Prodinger

Department of Computational and Applied Mathematics University of Witwatersrand, Johannesburg, South Africa Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

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.

— October 14, 1997 —

1. Introduction

A restricted composition of a natural number n in the sense of Carlitz [4], which we shall call a Carlitz composition, is defined to be a composition

n = a_{1} + a_{2} + ⋯ + a_{k} such that a_{i} ≠ a_{i+1} for i = 1, …, k − 1.

We refer to n as the size and to k as the 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 [4], Carlitz found the generating function

C(z) := ∑_{n≥0} 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 [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^{n}u^{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) + δ_{k,0} for k ≥ 0, f_{0}(z, u) = 1. (∗)

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) := ∑_{k≥1} f_{k}(z, u) and summing on k ≥ 0, 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 iterated and gives

F (z, 1) = σ(z) + F (z, 1) σ(z),

with

σ(z) = ∑_{j≥1} \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 − σ(z)}.

Here are the first few values:

1 + z + z^{2} + 3z^{3} + 4z^{4} + 7z^{5} + 14z^{6} + 23z^{7} + 39z^{8} + 71z^{9} + 124z^{10} + …;

it is sequence A003242 in [14].

In his paper, Carlitz noted only that the radius of convergence of C(z) is at least \frac{1}{2}. Now we can go further than that and notice that there is a dominant pole ρ, which is the unique real solution in the interval [0, 1] of the equation σ(z) = 1. Numerically we find ρ = 0.571349 … The other poles are further away, which can proved by Rouché’s theorem very much as in [6,9,11,12,13].

Consequently, in a neighbourhood of z = ρ,

C(z) ∼ \frac{A}{1 − z/ρ}, with A = \frac{1}{ρσ′(ρ)} = 0.456387 …

Therefore,

c(n) ∼ Aρ^{−n} = 0.456387 · (1.750243)^{n}.

2. The number of parts

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) := ∑_{k≥1} w^{k}f_{k}(z, u), we find by multiplying (∗) by w^{k+1} and summing over k ≥ 0,

G(z, u, w) = wG(z, 1, w)\frac{zu}{1 − zu} + w \frac{zu}{1 − zu} − wG(z, zu, w).

Carlitz compositions 3 Iterating this as before we find

G(z, 1, w) = \frac{τ(z, w)}{1 − τ(z, w)},

with

τ(z, w) = ∑_{j≥1} \frac{z^{j}w^{j}(−1)^{j−1}}{1 − z^{j}} .

n\k 1 2 3 4 5 6 7 8
1 1
2 1
3 1 2
4 1 2 1
5 1 4 2
6 1 4 7 2
7 1 6 9 6 1
8 1 6 15 14 3
9 1 8 21 24 15 2
10 1 8 28 46 30 10 1
11 1 10 35 66 68 30 4
12 1 10 46 100 119 76 24 2

Table 1. Carlitz compositions by size and number of parts To compute the average value, we need the function

\overline{G}(z) := \frac{∂}{∂w} G(z, 1, w)|_{w=1},

for which we easily find

\overline{G}(z) = \frac{μ(z)}{(1 − σ(z))^{2}} with μ(z) = ∑_{j≥1} \frac{jz^{j}(−1)^{j−1}}{1 − z^{j}} .

Consequently,

\overline{G}(z) ∼ \frac{B}{(1 − zρ)^{2}} , with B = μ(ρ)A^{2} = 0.159996.

Therefore

[z^{n}]\overline{G}(z) ∼ B n ρ^{−n},

and thus the average number of parts in a Carlitz composition of size n is asymptotic to

\frac{B n ρ^{−n}}{A ρ^{−n}} = 0.350571 · n.

By contrast, an unrestricted composition of n has \frac{n+1}{2} parts on average.

3. Counting adjacent equal parts

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)δ_{k,0} for k ≥ 0,

and f_{0}(z, u, v) = 1. Defining F (z, u, v) := ∑_{k≥1} 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 − σ(z, v)} with σ(z, v) = ∑_{j≥1} \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 − σ(z, v)} = \frac{1}{m!} \frac{∂^{m}}{∂v^{m}} \frac{1}{1 − σ(z, v)}|_{v=0}.

For instance, we get for m = 1

\frac{σ′(z, 0)}{(1 − σ(z))^{2}} ,

the derivative being w.r.t. v. For general m we get something of the form

\frac{p_{m}(z)}{(1 − σ(z))^{m+1}} ,

with a function p_{m}(z) that is built up from derivatives of the function σ(z, v). Consequently, for fixed m and n → ∞ the number of compositions with exactly m equal adjacent parts has the following asymptotic behaviour

C_{m} n^{m} ρ^{−n}

with explicitly computable constants C_{m}. The first few are

C_{0} = 0.4563,
C_{1} = 0.0482,
C_{2} = 0.0025.

Carlitz compositions 5

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 ≥ 1 the coefficient of z^{n} therein is

\frac{1}{12}(n + 1)2^{n} − \frac{1}{18}2^{n} + \frac{2}{9}(−1)^{n},

which gives (upon division by 2^{n−1}) our average as

\frac{3n + 1}{18} + O(2^{−n}).

n\k 0 1 2 3 4 5 6 7 8 9 10 11
1 1
2 1 1
3 3 0 1
4 4 3 0 1
5 7 6 2 0 1
6 14 7 8 2 0 1
7 23 20 10 8 2 0 1
8 39 42 22 13 9 2 0 1
9 71 72 58 28 14 10 2 0 1
10 124 141 112 72 33 16 11 2 0 1
11 214 280 219 150 92 36 18 12 2 0 1
12 378 516 466 311 189 112 40 20 13 2 0 1

Table 2. Compositions C(n, k) by size and number of adjacent equal parts Remark. We notice formulæ such as

C(n, n − 1) = 1, n ≥ 1,
C(n, n − 2) = 0, n ≥ 3,
C(n, n − 3) = 2, n ≥ 5,
C(n, n − 4) = n + 1, n ≥ 7,
C(n, n − 5) = 2n − 4, n ≥ 9,
C(n, n − 6) = 4n − 8, n ≥ 11,
C(n, n − 7) = \frac{n^{2} + 15n − 102}{2}, n ≥ 13, …

They are all easy to prove by considering

\frac{1}{1 − σ(zv, v^{−1})}

and looking for the coefficient of a fixed power of v.

4. The largest part in Carlitz compositions

For ordinary partitions, the statistic “largest part of a composition” has obtained a lot of attention, [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) + ⋯ + (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 − σ_{h}(z)},

with

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

The dominant pole ρ_{h} is now the (positive real) solution of the equation σ_{h}(z) = 1. It is clear that ρ_{h} tends to ρ, but we have to determine how fast. We will use the “bootstrapping method” from [11].

Now, around z = ρ we have the approximate equation

1 ≈ σ(z) − ρ^{h+1}.

Using Taylor’s theorem and setting ρ_{h} = ρ(1 + ε_{h}), we arrive at

0 ≈ ρε_{h}σ′(ρ) − ρ^{h+1},

or

ε_{h} ≈ \frac{1}{σ′(ρ)}ρ^{h}.

Therefore the number of Carlitz compositions with largest part ≤ h is approximated by

\frac{1}{ρ_{h}σ′(ρ_{h})}ρ_{h}^{−n} ≈ \frac{1}{ρσ′(ρ)}ρ^{−n}(1 + ε_{h})^{−n}.

Consequently the probability that a Carlitz composition has largest part ≤ h is approximated by

(1 + ε_{h})^{−n} ≈ (1 − \frac{1}{σ′(ρ)}ρ^{h})^{n}.

For the probability that the largest part is > h we have then approximately

1 − (1 − \frac{1}{σ′(ρ)}ρ^{h})^{n},

and to get the desired average value E_{n} we must sum this up over h ≥ 0. The next step is to use the exponential approximation (1 − a)^{n} ≈ e^{−an};

E_{n} ≈ ∑_{h≥0} (1 − e^{−nρ^{h}/σ′(ρ)}).

But this quantity is quite well studied [5] (we might even set N := n/σ′(ρ) for the moment to make it look closer to already existing formulæ).

The answer is

E_{n} ∼ log_{1/ρ} N − \frac{γ}{log ρ} + \frac{1}{2} + δ(log_{1/ρ} N),

with a certain periodic function δ(x) that has period 1, mean 0, and small amplitude.

Rewriting this we find

E_{n} ∼ log_{1/ρ} n − log_{1/ρ} σ′(ρ) − \frac{γ}{log ρ} + \frac{1}{2} + \overline{δ}(log_{1/ρ} n),

where \overline{δ}(x) = δ(x − log_{1/ρ} σ′(ρ)), which has the same properties as δ(x). The numerical constant is − log_{1/ρ} σ′(ρ) − \frac{γ}{log ρ} + \frac{1}{2} = −0.870252.

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

5. Carlitz Compositions with zeros

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 makes sense, since one can have at most n + 1 zeros, so the number \overline{c}(n) of Carlitz compositions with zeros allowed is meaningful.

In [4] Carlitz gave an erroneous formula for the generating function

\overline{C}(z) = ∑_{n≥0} \overline{c}(n)z^{n}

viz.

\overline{C}(z) = \frac{1}{1 − \overline{σ}(z)} with \overline{σ}(z) = (1 − z) ∑_{j≥1} \frac{z^{2j−1}}{(1 − z^{2j−1})(1 − z^{2j})}.

A simple rearrangement shows that C(z) = \overline{C}(z), so this cannot be correct. Here is a brief explanation of the flaw in the derivation.

Carlitz gives mutatis mutandis

f_{k+1}(z, u) = f_{k}(z, 1)\frac{1}{1 − zu} − f_{k}(z, zu) + δ_{k,0} for k ≥ 0, 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 constant term.

Here is a corrected version: We dissect the set of compositions into those with last part ≥ 1 (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 ≥ 1)

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) = ∑_{k≥1} 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 is now amenable to iteration, and consequently we get (with the function σ(z) from the introduction)

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

Therefore

\overline{C}(z) = 1 + 2G(z, 1) = \frac{1 + 2σ(z)}{1 − 2σ(z)}.

Again, there is a dominant singularity \overline{ρ}, which is the solution in the interval [0, 1] of the equation σ(z) = \frac{1}{2}.

Numerically we find \overline{ρ} = 0.386960. This is also in contrast to Carlitz’s comment that is should be close to \frac{1}{2}.

Thus

\overline{c}(n) ∼ \frac{1 + 2σ(\overline{ρ})}{2\overline{ρ}σ′(\overline{ρ})}\overline{ρ}^{−n} = 1.337604 · (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 \overline{c}(n) with the total number of compositions (zeros allowed) having at most 2n + 1 parts. This number is given by

∑_{k=1}^{2n+1} \binom{n + k − 1}{n} = \binom{3n + 1}{n + 1} ∼ \frac{3\sqrt{3}}{2\sqrt{πn}}(\frac{27}{4})^{n}.

Note that \frac{27}{4} = 6.75.

6. 1–compositions

If we impose the conditions a_{2} ≤ a_{1} + 1, a_{3} ≤ a_{2} + 1, etc. on an ordinary composition, we encounter a different family of restricted compositions which are termed “1–composition” in [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} + ⋯ + (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^{2}u^{2}}{1 − zu}f_{k}(z, zu)

for k ≥ 1 and f_{1}(z, u) = \frac{zu}{1−zu}. With F (z, u) = ∑_{k≥1} f_{k}(z, u) this means

F (z, u) = \frac{zu}{1 − zu}F (z, 1) − \frac{z^{2}u^{2}}{1 − zu}F (z, zu) + \frac{zu}{1 − zu},

and upon iteration

1 + F (z, 1) = \frac{1}{1 − σ(z)},

with

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

There is again a dominant pole at ρ = 0.576148, and ρσ′(ρ) = 1.089257, so the number of 1–compositions of n is asymptotic to

\frac{1}{ρσ′(ρ)}ρ^{−n} = 0.918056 · (1.735662)^{n}.

Now we can also count how many times the condition a_{i} ≤ a_{i+1} + 1 is 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^{2}u^{2}(1 − v)}{1 − zu}F (z, zu, v) + \frac{zu}{1 − zu},

Carlitz compositions 10 and

1 + F (z, 1, v) = \frac{1}{1 − σ(z, v)},

with

σ(z, v) = ∑_{j≥1} \frac{(v − 1)^{j−1}z^{j^{2}}}{(1 − z)(1 − z^{2}) … (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}).

n\k 0 1 2 3
1 1
2 2
3 4
4 7 1
5 13 3
6 23 9
7 41 23
8 72 55 1
9 127 123 6
10 222 267 23
11 388 561 75
12 677 1150 220 1

Table 3. Compositions by size and number of adjacent parts a, b with b > a + 1

If we consider “0–compositions” (a_{1} ≤ a_{2} ≤ …), which actually means 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 − σ(z)},

with

σ(z) = ∑_{j≥1} \frac{(−1)^{j−1}z^{\binom{j+1}{2}}}{(1 − z)(1 − z^{2}) … (1 − z^{j})}.

Since

1 + F (z, 1) = ∏_{k≥1} \frac{1}{1 − z^{k}} ,

we find in this way one of Euler’s partition identities, [1].

This time, there is no dominant pole, since the equation σ(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 [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 [13]; however, we don’t intend to be encyclopedic.

7. Concluding Remarks

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 [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.

The referee has kindly informed us about a different approach using Smirnov words; see [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, … of a composition as words and use letters x_{1}, x_{2}, . . .. 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(\frac{x_{1}}{1 − x_{1}} , \frac{x_{2}}{1 − x_{2}} , …) = \frac{1}{1 − ∑_{i≥1} x_{i}} .

Since

\frac{x}{1 − x} = y ⟷ \frac{y}{1 + y} = x,

the above relation can be inverted:

S(y_{1}, y_{2}, …) = \frac{1}{1 − ∑_{i≥1} \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 − ∑_{i≥1} \frac{z^{i}}{1+z^{i}}} .

Carlitz compositions 12

It is not hard to see that the two version coincide; one has to show that

∑_{i≥1} \frac{z^{i}}{1 + z^{i}} = ∑_{j≥1} \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}.)

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.

References

1. G. E. Andrews, The Theory of Partitions, Addison–Wesley, 1976.

2. G. E. Andrews, The hard-hexagon model and Rogers–Ramanujan type identities, Proc. Natl. Acad. Sci. USA 78 (1981), 5290–5292.

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

4. L. Carlitz, Restricted Compositions, The Fibonacci Quarterly 14 (1976), 254–264.

5. P. Flajolet, X. Gourdon, and P. Dumas, Mellin transform and asymptotics: Harmonic sums, Theoretical Computer Science 144 (1995), 3–58.

6. P. Flajolet and H. Prodinger, Level Number Sequences for Trees, Discrete Mathematics 65 (1987), 149–156.

7. I. Goulden and D. Jackson, Combinatorial Enumeration, John Wiley, 1983.

8. X. Gourdon, Combinatoire, Algorithmique et Géométrie des Polynômes, Thèse, École polytechnique, 1996.

9. H. K. Hwang and Y. N. Yeh, Measures of Distinctness for Random Partitions and Compositions of an Integer, Advances in Applied Mathematics 19 (1997), 378–414.

10. A. Knopfmacher and M. E. Mays, Compositions with m distinct parts, Ars Combinatoria, to appear.

11. D. E. Knuth, The Average Time for Carry Propagation, Indagationes Mathematicæ 40 (1978), 238–242.

12. A. M. Odlyzko and L. B. Richmond, On the Compositions of an Integer, Lecture Notes in Mathematics 829 (1979), 199–209.

13. A. M. Odlyzko and H. Wilf, n Coins in a Fountain, American Mathematical Monthly 40 (1978), 238–242.

14. N. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995.

15. G. X. Viennot, Bijections for the Rogers–Ramanujan reciprocal, J. Indian Math. Soc., New Series 52 (1987), 171–183.

Arnold Knopfmacher Department of Computational and Applied Mathematics University of Witwatersrand (Wits) 2050 Johannesburg South Africa

email: arnoldk@gauss.cam.wits.ac.za
www: http://sunsite.wits.ac.za/wits/science/number theory/arnold.htm

Carlitz compositions 13

Helmut Prodinger Department of Algebra and Discrete Mathematics TU Vienna Wiedner Hauptstrasse 8-10 A-1040 Vienna Austria

email: Helmut.Prodinger@tuwien.ac.at
www: http://info.tuwien.ac.at/theoinf/proding.htm