On k-colored Motzkin words

A. Sapounakis and P. Tsikouras Department of Informatics University of Piraeus Karaoli & Dimitriou 80 18534 Piraeus Greece arissap@unipi.gr pgtsik@unipi.gr

Abstract

This paper deals with the enumeration of k-colored Motzkin words according to various parameters, such as the length, the number of rises, the length of the initial rise and the number of prime components.

1 Introduction

There exists an extended literature on Dyck and Motzkin paths and their relationship with many other combinatorial objects [7, 10, 11, 15, 16, 19, 21]. It is well known that the sets of Dyck paths of length 2n and Motzkin paths of length n are enumerated by the Catalan numbers C_{n} (A000108) and the Motzkin numbers M_{n} (A001006), respectively. More generally, there is great interest in k-colored Motzkin paths [2], which have horizontal steps colored by means of k colors.

This paper deals with the set of k-colored Motzkin words (or equivalently paths) and with some subsets of it, defined by various parameters.

In section 2, some basic definitions and notations referring to the sets M_{k} and M_{k}^{c} of (k-colored) Motzkin and c-Motzkin words respectively are given.

In section 3, using the generating functions F_{k} and G_{k} of M_{k} and M_{k}^{c} respectively, according to the parameters “length”, “number of rises” and “length of the initial rise”, the cardinalities of several subsets of M_{k} are evaluated. Furthermore, using the Lagrange inversion formula, the coefficients of the powers of F_{k} are determined.

Finally, in section 4, the decomposition of the elements of M_{k}^{c} to prime words is studied. The generating function G_{k} of M_{k}^{c} according to the three previous parameters and to the parameter “number of prime components” is determined. This is used to show that the number of all u ∈ M_{k}^{c} with s prime components and length of the initial rise equal to m is equal to the number of all u ∈ M_{k}^{c} with m prime components and length of the initial rise equal to s.

2 Preliminaries

Throughout this paper, let E be an alphabet with k + 2 letters, where k ∈ ℕ and a, ā are two given elements of E. For k ≠ 0, the elements of the set E\{a, ā} = {β_{1}, β_{2}, …, β_{k}} are called colors of E. The number of occurrences of the letter x ∈ E in the word u is denoted by |u|_{x}, the length of u by l(u), and the number of rises of u by r(u).

We denote by E^{∗} the set which contains all the words with letters in E as well as the empty word ϵ. A word u ∈ E^{∗} is called k-colored Motzkin word if |u|_{a} = |u|ā and for every factorization u = wv we have |w|ā ≤ |w|_{a}.

A Motzkin path of length n is a lattice path of ℕ^{2} running from (0, 0) to (n, 0) that never passes below the x-axis and whose permitted steps are the up diagonal step (1, 1), the down diagonal step (1, −1) and the horizontal step (1, 0), called rise, fall and level step, respectively. If the level steps are labelled by k colors we obtain the k-colored Motzkin paths.

It is clear that each k-colored Motzkin path is coded by a k-colored Motzkin word u = u_{1}u_{2} ⋯ u_{n} ∈ E^{∗} so that every rise (resp., fall) corresponds to the letter a (resp., ā) and every colored level corresponds to a certain color of E; see Fig. 1.

u = a a β_{1} ā a ā ā β_{1} a β_{2} a a ā ā ā β_{1} a β_{2} ā

Figure 1: A 2-colored Motzkin path and its corresponding Motzkin word

We denote by M_{k,n} (resp., M_{k,n,r}) the set of all u ∈ M_{k} with l(u) = n (resp., l(u) = n and r(u) = r) and we set μ_{k,n} = |M_{k,n}| (resp., μ_{k,n,r} = |M_{k,n,r}|).

It is well known that if k = 0, 1 we obtain the sets of Dyck and Motzkin words, respectively. The 2-colored Motzkin words have been studied in [9]. More precisely, we have:

μ_{0,n} = \begin{cases}C\frac{n}{2} , & if n is even; \\ 0, & if n is odd, \end{cases}  μ_{1,n} = M_{n},  μ_{2,n} = C_{n+1}.

The 3-colored Motzkin paths correspond to the tree-like polyhexes defined by Harary [13], as we will see in the next section.

Let u = u_{1}u_{2} ⋯ u_{n} ∈ M_{k,n}. Two indices i, j ∈ [n] = {1, 2, …, n} with i < j are called conjugates with respect to u if and only if j is the smallest number in {i + 1, i + 2, …, n} for which the segment u_{i}u_{i+1} ⋯ u_{j} of u is a k-colored Motzkin word.

A word u ∈ M_{k,n} is called (k-colored) c-Motzkin word if and only if every i ∈ [n] with u_{i} ∉ {a, ā}, lies between two conjugate indices. It is clear that the c-Motzkin words code exactly those k-colored paths that have no level steps on the x-axis; see Fig. 2.

u = a β_{1} a ā ā a β_{1} β_{2} a β_{1} a a ā ā ā β_{1} β_{2} β_{2} ā a β_{1} β_{1} ā

Figure 2: A 2-colored Motzkin path and its corresponding c-Motzkin word

The c-Motzkin words have been introduced and studied in the case k = 1, [18].

In the following sections we will refer to the sets M_{k,n}^{c} = M_{k}^{c} ∩ M_{k,n} and M_{k,n,r}^{c} = M_{k}^{c} ∩ M_{k,n,r} with cardinalities μ_{k,n}^{c} and μ_{k,n,r}^{c}, respectively.

3 Enumeration of sets of k-colored Motzkin words

In this section we evaluate the cardinal number of several subsets of M_{k} defined by various parameters. We first need the following definition.

The initial rise of a non-empty word u = u_{1}u_{2} ⋯ u_{n} ∈ M_{k} with u_{1} = a is the segment u_{1}u_{2} ⋯ u_{j} where u_{ν} = a for every ν ∈ [j] and u_{j+1} ≠ a. If u = ϵ or u_{1} ≠ a, the initial rise of u is the empty word. We denote by p(u) the length of the initial rise of u.

Let F_{k} and G_{k} be the generating functions of M_{k} and M_{k}^{c}, respectively, according to the parameters l, r, p (coded by x, y, z), i.e.,

F_{k}(x, y, z) = ∑_{u∈M_{k}} x^{l(u)}y^{r(u)}z^{p(u)}

and

G_{k}(x, y, z) = ∑_{u∈M_{k}^{c}} x^{l(u)}y^{r(u)}z^{p(u)}.

Proposition 3.1 The generating functions F_{k}, G_{k} are given by the formulae

F_{k}(x, y, z) = \frac{1 + kxF_{k}(x, y)}{1 − x^{2}yzF_{k}(x, y)}  (1)

and

G_{k}(x, y, z) = \frac{1}{1 − x^{2}yzF_{k}(x, y)},  (2)

where the generating function F_{k}(x, y) = F_{k}(x, y, 1) satisfies the equation

x^{2}yF_{k}^{2}(x, y) + (kx − 1)F_{k}(x, y) + 1 = 0  (3)

and hence

F_{k}(x, y) = \frac{1 − kx − \sqrt{(1 − kx)^{2} − 4x^{2}y}}{2x^{2}y} .  (4)

Proof : We can easily verify that for k ≠ 0 each nonempty u ∈ M_{k} can be uniquely written in either of the forms u = β_{ν}v for some v ∈ M_{k} and ν ∈ [k], or u = awāv for some v, w ∈ M_{k}, where indices 1, l(w) + 2 are conjugates with respect to u.

Obviously, since in the first case p(u) = 0, r(u) = r(v) and in the second case r(u) = r(w) + r(v) + 1, p(u) = p(w) + 1, we obtain that

F_{k}(x, y, z) = 1 + ∑_{ν=1}^{k} ∑_{v} x^{l(β_{ν}v)}y^{r(v)} + ∑_{w,v} x^{l(w)+l(v)+2}y^{r(w)+r(v)+1}z^{p(w)+1}
= 1 + kxF_{k}(x, y) + x^{2}yzF_{k}(x, y, z)F_{k}(x, y).

Thus,

F_{k}(x, y, z) = \frac{1 + kxF_{k}(x, y)}{1 − x^{2}yzF_{k}(x, y)}.

Moreover, applying the above equality for z = 1 we deduce that

x^{2}yF_{k}^{2}(x, y) + (kx − 1)F_{k}(x, y) + 1 = 0.

The proof of (1) for k = 0 follows as above with some simple modifications.

The proof of (2) is similar and it is omitted. □

Remark The generating function F_{k} can be obtained as an application of a continued fraction result [12]. More precisely if we apply theorem 1 of [12] by counting the rises by xy, the falls by x and the level steps by kx we conclude that

F_{k}(x, y) = \frac{1}{1 − kx − \frac{x^{2}y}{1 − kx − \frac{x^{2}y}{1 − kx − \frac{x^{2}y}{⋯}}}}

which easily leads to equation (3).

Example We compute the number of k-colored c-Motzkin words of length n, for k = 1 and k = 2, using the generating functions C(x) and M(x) of Catalan and Motzkin numbers, respectively. For this we use formula (2) for the generating function G_{k}(x) = G_{k}(x, 1, 1) of M_{k}^{c} according to the length.

1) For k = 1, we have that

G_{1}(x) = \frac{1}{1 − x^{2}F_{1}(x)} = \frac{1}{1 − x^{2}M(x)} = \frac{1 + xM(x)}{1 + x}

= (∑_{n=0}^{∞}(−1)^{n}x^{n})(∑_{n=0}^{∞} γ_{n}x^{n})

= ∑_{n=0}^{∞}(∑_{i=0}^{n}(−1)^{i}γ_{n−i})x^{n},

where

γ_{n} = \begin{cases}M_{n−1}, & if n ≥ 1; \\ 0, & if n = 0. \end{cases}

Thus,

μ_{1,n}^{c} = ∑_{i=0}^{n}(−1)^{i}γ_{n−i} = ∑_{i=0}^{n−2}(−1)^{i}M_{n−i−1},

for every n ≥ 2.

We note that from the above formula we deduce that for every n ≥ 2,

μ_{1,n}^{c} + μ_{1,n−1}^{c} = M_{n−1}

which implies that the number of c-Motzkin paths of length n is equal to the number of Motzkin paths of length n − 1 with at least one level step on the x-axis [14].

2) For k = 2 and since

F_{2}(x) = ∑_{n=0}^{∞} μ_{2,n}x^{n} = ∑_{n=0}^{∞} C_{n+1}x^{n} = \frac{1}{x}[C(x) − 1] = C^{2}(x),

we obtain that

G_{2}(x) = \frac{1}{1 − x^{2}C^{2}(x)}.

So, the generating function G_{2}(x) coincides with the generating function of Fine numbers f_{n} [8] and hence we conclude that μ_{2,n}^{c} = f_{n}.

In the following result we give recursive formulae for the sequences μ_{k,n,r} and μ_{k,n}.

Proposition 3.2 For every k, ν, n, r ∈ ℕ with r ≤ [\frac{n}{2}] we have that

μ_{k+ν,n,r} = ∑_{m=2r}^{n} \binom{n}{m}μ_{k,m,r}ν^{n−m} = ∑_{m=2r}^{n} \binom{n}{m}μ_{ν,m,r}k^{n−m}  (5)

and

μ_{k+ν,n} = ∑_{m=0}^{n} \binom{n}{m}μ_{k,m}ν^{n−m} = ∑_{m=0}^{n} \binom{n}{m}μ_{ν,m}k^{n−m}.  (6)

Proof : From relation (4) we easily obtain that

F_{k+ν}(x, y) = \frac{F_{k}(\frac{x}{1−νx}, y)}{1 − νx} = \frac{F_{n}(\frac{x}{1−kx}, y)}{1 − kx}

for every k, ν ∈ ℕ.

On the other hand, we have that

\frac{F_{k}(\frac{x}{1−νx}, y)}{1 − νx} = ∑_{m=0}^{∞} ∑_{r=0}^{[ \frac{m}{2} ]} μ_{k,m,r}x^{m}y^{r} \frac{1}{(1 − νx)^{m+1}}

= ∑_{m=0}^{∞} ∑_{r=0}^{[ \frac{m}{2} ]} μ_{k,m,r}x^{m}y^{r} ∑_{j=0}^{∞} \binom{−m − 1}{j}(−νx)^{j}

= ∑_{m=0}^{∞} ∑_{r=0}^{[ \frac{m}{2} ]} ∑_{j=0}^{∞} μ_{k,m,r}\binom{m + j}{j}ν^{j}x^{j+m}y^{r}

= ∑_{n=0}^{∞} ∑_{r=0}^{[ \frac{n}{2} ]} [ ∑_{m=2r}^{n} μ_{k,m,r}\binom{n}{m}ν^{n−m}]x^{n}y^{r}.

It follows that

μ_{k+ν,n,r} = ∑_{m=2r}^{n} \binom{n}{m}μ_{k,m,r}ν^{n−m}.

Moreover, using the above relations we obtain that

μ_{k+ν,n} = ∑_{r=0}^{[ \frac{n}{2} ]} μ_{k+ν,n,r} = ∑_{m=0}^{n} \binom{n}{m}ν^{n−m} ∑_{r=0}^{[ \frac{m}{2} ]} μ_{k,m,r} = ∑_{m=0}^{n} \binom{n}{m}μ_{k,m}ν^{n−m}.

The proofs of the second parts of relations (5) and (6) are similar and they are omitted. □

Remark 1 Since

μ_{0,m,r} = \begin{cases}C_{r}, & if m = 2r; \\ 0, & if m ≠ 2r \end{cases}

and

μ_{0,m} = \begin{cases}C\frac{m}{2} , & if m is even; \\ 0, & if m is odd, \end{cases}

setting ν = 0 in relations (5) and (6) we obtain that

μ_{k,n,r} = \binom{n}{2r}C_{r}k^{n−2r} = \frac{1}{n + 1}\binom{n + 1}{r + 1, r, n − 2r}k^{n−2r}  (7)

and

μ_{k,n} = ∑_{r=0}^{[ \frac{n}{2} ]} \binom{n}{2r}C_{r}k^{n−2r}  (8)

which give (for k = 1) the well-known corresponding relations for Motzkin words [1]. Furthermore, for k = 2, relation (8) gives the well-known relation of Touchard

C_{n+1} = ∑_{r=0}^{[ \frac{n}{2} ]} \binom{n}{2r}2^{n−2r}C_{r}.

Remark 2 From relation (6) we can easily deduce relations

μ_{k+1,n} = ∑_{m=0}^{n} \binom{n}{m}μ_{k,m}  (9)

and

μ_{k+1,n+1} = ∑_{m=0}^{n} \binom{n}{m}(μ_{k,m} + μ_{k,m+1}).  (10)

It is easy to check that from the above two relations, for k = 0 and k = 1, relations (1), (2), (3) and (4) of [10] follow.

Remark 3 Applying relation (9) for k = 2, we obtain the number of all 3-colored Motzkin words of length n:

μ_{3,n} = ∑_{m=0}^{n} \binom{n}{m}C_{m+1}.

This number also gives the cardinality of the set of all tree-like polyhexes with n + 1 hexagons (A002212) (for detailed definitions see [13]), which can be coded by the 3-colored Motzkin words in the following, recursive way:

If the polyhex consists of the root hexagon ABCDEF only (with root edge AB), then the corresponding 3-colored Motzkin word is ϵ. If the polyhex consists of n + 1 hexagons, then we have the following cases: If the only points of ABCDE with degree 3 are C, D (D, E or E, F, respectively) then the corresponding u ∈ M_{3,n} is β_{1}w (β_{2}w or β_{3}w, respectively), where the word w ∈ M_{3,n−1} corresponds to the polyhex with n hexagons and root edge CD (DE or EF, respectively) that we obtain if we delete the points of the root hexagon that have degree 2, as well as the edges incident with these points; see Fig. 3 a,b,c.

u = β_{1}w  u = β_{2}w  u = β_{3}w  u = aw_{1}āw_{2}
a  b  c  d

Figure 3: The recursive coding of polyhexes

If on the other hand the only points of the root hexagon with degree 3 are C, D, E, F then the corresponding u ∈ M_{3,n} is the word aw_{1}āw_{2}, where w_{1} (resp., w_{2}) is the 3-colored Motzkin word which corresponds to the polyhex with less than n-hexagons and root edge CD (resp., EF) that we obtain if we delete the points A, B as well as the edges AB, BC, DE and F A; see Fig. 3 d.

We continue by evaluating the coefficients of the powers of F_{k}(x, y).

Proposition 3.3 The coefficients of F_{k}^{s}(x, y), with s ∈ ℕ^{∗}, are given by the formula

[x^{n}y^{r}]F_{k}^{s} = \frac{s}{n + s}\binom{n + s}{s + r, r, n − 2r}k^{n−2r},  (11)

where n, r ∈ ℕ, with r ≤ [\frac{n}{2}].

Proof : We define the function H(x) = xF_{k}(x, y). It follows easily by equation (3) that

H(x) = x[yH^{2}(x) + kH(x) + 1].

Thus, if we set P (λ) = yλ^{2} + kλ + 1 we obtain that H(x) = xP (H(x)) and P (0) = 1. Using Lagrange inversion formula [20] we obtain

[x^{n}]H^{s} = \frac{1}{n}[λ^{n−1}]\{sλ^{s−1}(P (λ))^{n}\}.

Moreover, we have

\frac{s}{n}λ^{s−1}(P (λ))^{n} = \frac{s}{n}λ^{s−1} ∑_{i=0}^{n} \binom{n}{i}λ^{i}(yλ + k)^{i}

= \frac{s}{n}λ^{s−1} ∑_{i=0}^{n} \binom{n}{i}λ^{i} ∑_{ν=0}^{i} \binom{i}{ν}y^{ν}λ^{ν}k^{i−ν}

= \frac{s}{n} ∑_{m=0}^{2n} ∑_{ν=(m−n)^{+}}^{[ \frac{m}{2} ]} \binom{n}{m − ν}\binom{m − ν}{ν}k^{m−2ν}y^{ν}λ^{m+s−1},

where (m − n)^{+} = max{0, m − n}.

Thus, for m = n − s we deduce that

[x^{n}]H^{s} = \frac{s}{n} ∑_{ν=0}^{[ \frac{n−s}{2} ]} \binom{n}{n − s − ν}\binom{n − s − ν}{ν}k^{n−s−2ν}y^{ν}

for every n ≥ s.

Finally, applying the above equality for n + s instead of s and setting ν = r, we conclude that

[x^{n}y^{r}]F_{k}^{s} = \frac{s}{n + s}\binom{n + s}{n − r}\binom{n − r}{r}k^{n−2r}

= \frac{s}{n + s}\binom{n + s}{s + r, r, n − 2r}k^{n−2r}.

□

We note that relation (7) is a special case of relation (11), for s = 1.

We use the last proposition in order to prove the following result:

Proposition 3.4 The number of all u ∈ M_{k,n,r}^{c} that have initial rise of length s is equal to

[x^{n}y^{r}z^{s}]G_{k} = \frac{s}{n − s}\binom{n − s}{r, r − s, n − 2r}k^{n−2r},

where 1 ≤ s ≤ r ≤ [\frac{n}{2}].

Proof : By relation (2) and proposition 3.3 we obtain that

[x^{n}y^{r}z^{s}]G_{k} = [x^{n}y^{r}z^{s}]{∑_{s=0}^{∞} x^{2s}y^{s}F_{k}^{s}(x, y)z^{s}}

= [x^{n}y^{r}]{x^{2s}y^{s}F_{k}^{s}(x, y)}

= [x^{n−2s}y^{r−s}]F_{k}^{s}

= \frac{s}{n − s}\binom{n − s}{r, r − s, n − 2r}k^{n−2r}.

□

Using proposition 3.1 and the same arguments as in the proof of proposition 3.4 we obtain the following result:

Proposition 3.5 The number of all u ∈ M_{k,n,r} that have initial rise of length s is equal to

[x^{n}y^{r}z^{s}]F_{k} = \frac{ns − rs + n + s − 2r}{(n − s)(n − s + 1)}\binom{n − s + 1}{r + 1, r − s, n − 2r}k^{n−2r},

where 1 ≤ s ≤ r ≤ [\frac{n}{2}].

Notice that if n = 2r then both propositions 3.4 and 3.5 give the number of Dyck words with prescribed height of the first peak [6].

4 Decomposition into prime words

A non-empty word u ∈ M_{k}^{c} is called prime if and only if it is not the product of two nonempty c-Motzkin words. It is clear that the k-colored Motzkin paths coded by a prime word are the paths whose only intersections with the x-axis are their initial and final points. It is evident that the word u ∈ M_{k} is prime if and only if the indices 1, l(u) are conjugates with respect to u.

The following result, known for Dyck [17] and c-Motzkin [18] words is naturally extended to k-colored c-Motzkin words.

Proposition 4.1 Every u ∈ M_{k}^{c} is uniquely decomposed into a product of prime words.

It is clear that the words u ∈ M_{k,n}^{c} which are decomposed into s prime words (components) are the ones whose corresponding k-colored Motzkin paths meet the x-axis at exactly s − 1 points, in addition to the points (0, 0) and (n, 0).

In this section, among others, the number of all u ∈ M_{k,n}^{c} with a fixed number of prime components is evaluated. This is a well-known result in the case of k = 0 (i.e., for Dyck words, [7, 17]) and it is extended here for arbitrary k. For this, we consider one more parameter d of M_{k}^{c}, defined by the number of prime components. Let G_{k} be the generating function of M_{k}^{c} according to the parameters l, r, p, d (coded by x, y, z, ϕ), i.e.,

G_{k}(x, y, z, ϕ) = ∑_{u} x^{l(u)}y^{r(u)}z^{p(u)}ϕ^{d(u)}.

Proposition 4.2 The generating function G_{k}(x, y, z, ϕ) is given by the formula

G_{k}(x, y, z, ϕ) = 1 + \frac{x^{2}yzϕ(1 + kxF_{k}(x, y))}{(1 − x^{2}yzF_{k}(x, y))(1 − x^{2}yϕF_{k}(x, y))}.

Proof : Every non-empty u ∈ M_{k}^{c} can be uniquely written in the form u = awāv, where w ∈ M_{k}, v ∈ M_{k}^{c}, r(u) = r(w) + r(v) + 1, p(u) = p(w) + 1 and d(u) = d(v) + 1. Thus, by proposition 3.1 follows that

G_{k}(x, y, z, ϕ) = 1 + ∑_{w,v} x^{l(w)+l(v)+2}y^{r(w)+r(v)+1}z^{p(w)+1}ϕ^{d(w)+1}

= 1 + x^{2}yzϕ(∑_{w} x^{l(w)}y^{r(w)}z^{p(w)})(∑_{v} x^{l(v)}y^{r(v)}ϕ^{d(v)})

= 1 + x^{2}yzϕF_{k}(x, y, z)G_{k}(x, y, 1, ϕ)

= 1 + x^{2}yzϕ\frac{1 + kxF_{k}(x, y)}{1 − x^{2}yzF_{k}(x, y)}G_{k}(x, y, 1, ϕ).

Further, applying the previous equality for z = 1 and using relation (3) we conclude that

G_{k}(x, y, 1, ϕ) = \frac{1}{1 − x^{2}yϕF_{k}(x, y)}

which implies the required formula. □

Remark Since G_{k}(x, y, 1, ϕ) = G_{k}(x, y, z, 1), we obtain that the parameters p and d are equidistributed. This is a well-known result for Dyck paths, i.e., for the case k = 0, see [4, 5, 6, 7].

Furthermore, since G_{k}(x, y, z, ϕ) = G_{k}(x, y, ϕ, z) we obtain the following result.

Proposition 4.3 The number of all u ∈ M_{k,n,r}^{c} with s prime components and length of the initial rise equal to m, is equal to the number of all u ∈ M_{k,n,r}^{c} with m prime components and length of the initial rise equal to s.

Proposition 4.3 can also be proved directly, by constructing an involution of M_{k}^{c} as follows:

We first define the mapping

ϕ : {u ∈ M_{k}^{c} : p(u) ≥ 2} → {u ∈ M_{k}^{c} : d(u) ≥ 2}

such that if u = aawāvāz with w, v ∈ M_{k}, z ∈ M_{k}^{c}, l(w)+3 conjugate of 2 and l(w)+l(v)+4 conjugate of 1, then ϕ(u) = awāavāz. Obviously, ϕ is a bijection. Next we define the mapping

θ : M_{k}^{c} → M_{k}^{c}

with θ(u) = ϕ^{p(u)−d(u)}(u), for every u ∈ M_{k}^{c}; (here ϕ^{j} stands for ϕ ∘ ⋯ ∘ ϕ). This mapping is well defined, with l(θ(u)) = l(u) and r(θ(u)) = r(u).

It is easy to check, by induction on the number ν(u) = |p(u) − d(u)| that p(θ(u)) = d(u) and d(θ(u)) = p(u) for every u ∈ M_{k}^{c}. It follows that θ is the required involution of M_{k}^{c}.

In order to construct θ(u) from u ∈ M_{k}^{c}, we note that if p(u) = d(u) then θ(u) = u. If p(u) > d(u), we delete the first ν(u) a’s of u and we insert one a after each ā of u which corresponds to a conjugate of 2, 3, …, ν(u) + 1. Finally, if p(u) < d(u), we add ν(u) a’s in the beginning of u, whereas we delete the initial a from each one of the 2nd, 3rd, …, (ν(u) + 1)st prime component of u.

For example, for

u = a a a a a β_{1} ā ā a ā ā β_{2} a ā ā ā a β_{2} a ā ā a β_{1} ā ∈ M_{2,24}^{c}

we obtain θ(u) = a a a β_{1} ā ā a ā ā a β_{2} a ā ā a ā a β_{2} a ā ā a β_{1} ā ∈ M_{2,24}^{c}.

This is illustrated by the corresponding 2-colored paths of u and θ(u) in Fig. 4.

Figure 4: The 2-colored Motzkin paths corresponding to u and θ(u)

Remark From propositions 3.4 and 4.3 follows that the number of all u ∈ M_{k,n,r}^{c} with s prime components is equal to

\frac{s}{n − s}\binom{n − s}{r, r − s, n − 2r}k^{n−2r},

where 1 ≤ s ≤ r ≤ [\frac{n}{2}].

This extends a well-known result on Dyck words (i.e., for k = 0) [7, 17], to k-colored c-Motzkin words for arbitrary k.

Furthermore, by summing the above numbers for all s ∈ [r] we easily obtain that the number of all k-colored c-Motzkin words of length n, with r rises is given by the formula

μ_{k,n,r}^{c} = \frac{1}{n − r + 1}\binom{n}{r}\binom{n − r − 1}{r − 1}k^{n−2r}.

This formula has been proved for k = 1 in a different way [18].

References

[1] L. Alonzo, Uniform generation of a Motzkin word, Theoret. Comput. Sci., 134 (1994), 529–536.

[2] E. Barrucci, A. Del Lungo, E. Pergola and R. Pinzani, A construction for enumerating k-coloured Motzkin paths, Proc. of the First Annual International Conference on Computing and Combinatorics, Springer, 1995, pp. 254-263.

[3] S. Benchekroun and P. Moszkowski, A new bijection between ordered trees and legal bracketings, European J. Combin. 17 (1996), 605–611.

[4] E. Deutsch, A bijection on Dyck paths and its consequences, Discrete Math. 179 (1998), 253–256.

[5] E. Deutsch, A bijection on Dyck paths and its consequences-Corrigendum, Discrete Math. 187 (1998), 297.

[6] E. Deutsch, An involution on Dyck paths and its consequences, Discrete Math. 204 (1999), 163–166.

[7] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[8] E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math. 241 (2001), 241–265.

[9] E. Deutsch and L. W. Shapiro, A bijection between ordered trees and 2-Motzkin paths, and its many consequences, Discrete Math. 256 (2002), 655–670.

[10] R. Donaghey, Restricted plane tree representations on four Motzkin-Catalan equations, J. Combin. Theory Ser. B 22 (1977), 114–121.

[11] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A 23 (1977), 291–301.

[12] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[13] F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinbourgh Math. Soc. 17 (1970), 1-13.

[14] K. N. Manoj, Problem 10816, Amer. Math. Monthly, http://www.geocities.com/ kummini/maths/10816.ps

[15] T. Mansour, Counting peaks at height k in a Dyck path, J. Integer Seq. 5 (2002), Article 02.1.1.

[16] P. Paert and W.-J. Woan, Dyck paths with no peaks at height k, J. Integer Seq. 4 (2001), Article 01.1.3.

[17] A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck words, J. Combin. Math. Comb. Comput. 40 (2002), 33–39.

[18] A. Panayotopoulos and A. Sapounakis, On Motzkin words and noncrossing partitions, Ars Combin. 69 (2003), 109–116.

[19] R. Pattisina and V. Vajnovszki, On the reconstruction of a Motzkin tree from its code, J. Inf. Optim. Sci. 24 (2003), 583–589.

[20] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[21] R. A. Sulanke, Bijective recurrences for Motzkin paths, Adv. in Appl. Math. 27 (2001), 627–640.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Motzkin words, Motzkin numbers, Dyck words, Catalan numbers, Polyhexes.

(Concerned with sequences \underline{A000108}, \underline{A001006} and \underline{A002212}.)

Received April 1 2004; revised version received June 8 2004. Published in Journal of Integer Sequences, June 8 2004.

Return to Journal of Integer Sequences home page.