<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{graphicx}
\usepackage{dsfont}
\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{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}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]



%\usepackage{stmaryrd}
%\usepackage{dsfont}
%\usepackage{mathenv}
%\usepackage{epsfig}

%\makeatletter
%\newfont{\footsc}{cmcsc10 at 8truept}
%\newfont{\footbf}{cmbx10 at 8truept}
%\newfont{\footrm}{cmr10 at 10truept}

%\makeatother
%\pagestyle{plain}


\begin{center}
\vskip 1cm{\LARGE\bf On $k$-colored Motzkin words} \vskip 1cm \large
A. Sapounakis and P. Tsikouras \\
Department of Informatics \\
University of Piraeus\\
Karaoli \&amp; Dimitriou 80 \\
18534 Piraeus \\
Greece\\
\href{mailto:arissap@unipi.gr}{arissap@unipi.gr}\\
\href{mailto:pgtsik@unipi.gr}{pgtsik@unipi.gr} \\
\end{center}
\vskip .2 in



\newtheorem{tm}{Theorem}[section]
\newtheorem{pr}[tm]{Proposition}

\begin{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.
\bigskip

%\noindent {\textit Keywords}: Motzkin words, Motzkin paths, Langrange inversion
%formula
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                            Section 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{sec1}

There exists an extended literature on Dyck and Motzkin paths and their
relationship with many other combinatorial objects
\cite{Deutsch3,Donaghey,DoS,Mansour,Peart,Pattisina,Sulanke}.
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$
(\htmladdnormallink{A000108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108})
and the Motzkin numbers $M_n$
(\htmladdnormallink{A001006}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001006}),
respectively.
More generally, there is
great interest in $k$-colored Motzkin paths
\cite{Barrucci}, 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 \ref{sec2}, some basic definitions and notations referring to the sets
$\mathcal{M}_k$ and $\mathcal{M}_k^c$ of ($k$-colored) Motzkin and $c$-Motzkin words respectively
are given.

In section \ref{sec3}, using the generating functions $F_k$ and $G_k$ of $\mathcal{M}_k$ and
$\mathcal{M}_k^c$ respectively, according to the parameters ``length'', ``number of rises'' and
``length of the initial rise'', the cardinalities of several subsets of $\mathcal{M}_k$ are
evaluated. Furthermore, using the Lagrange inversion formula, the coefficients
of the powers of $F_k$ are determined.

Finally, in section \ref{sec4}, the decomposition of the elements of $\mathcal{M}_k^c$ to
prime words is studied. The generating function $G_k$ of $\mathcal{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 \in \mathcal{M}_k^c$ with $s$
prime components and length of the initial rise equal to $m$ is equal to the
number of all $u \in \mathcal{M}_k^c$ with $m$ prime components and length of the initial
rise equal to $s$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Section 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}\label{sec2}

Throughout this paper, let $E$ be an alphabet with $k+2$ letters, where
$k \in \mathds{N}$ and $a, \bar{a}$ are two given elements of $E$. For $k \ne 0$,
the elements of the set
$E \backslash \{ a,\bar{a} \} = \{ \beta_1, \beta_2, \ldots, \beta_k \}$ are called
\textit{colors} of $E$. The number of occurrences of the letter $x \in 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 $\epsilon$. A word $u \in E^*$ is called
\textit{$\mathit{k}$-colored Motzkin word} if $|u|_a = |u|_{\bar{a}}$ and for
every factorization $u = wv$ we have $|w|_{\bar{a}} \le |w|_a$.

A \textit{Motzkin path} of length $n$ is a lattice path of $\mathds{N}^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 \textit{rise}, \textit{fall}
and \textit{level step}, respectively. If the level steps are labelled by $k$
colors we obtain the \textit{$\mathit{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 \cdots u_n \in E^*$ so that every rise (resp., fall)
corresponds to the letter $a$ (resp., $\bar{a}$) and every colored level
corresponds to a certain color of $E$; see Fig. \ref{fig1}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{fig1.eps} \\
$u = a \enspace a \enspace \beta_1 \enspace \bar{a} \enspace a \enspace \bar{a}
       \enspace \bar{a} \enspace \beta_1 \enspace a \enspace \beta_2 \enspace a
       \enspace a \enspace \bar{a} \enspace \bar{a} \enspace \bar{a} \enspace \beta_1
       \enspace a \enspace \beta_2 \enspace \bar{a}$\\
\caption{A $2$-colored Motzkin path and its corresponding Motzkin word} \label{fig1}
\end{center}
\end{figure}

We denote by $\mathcal{M}_{k,n}$ (resp., $\mathcal{M}_{k,n,r}$) the set of all
$u \in \mathcal{M}_k$ with $l(u) = n$ (resp., $l(u)=n$ and $r(u)=r$) and we set
$\mu_{k,n} = |\mathcal{M}_{k,n}|$ (resp., $\mu_{k,n,r} = |\mathcal{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 \cite{DS2}. More precisely, we
have:
\begin{align*}
\mu_{0,n} &amp; = \begin{cases}
        C_{n \over 2}, &amp; \text{if } n \text{ is even;}\\
        0, &amp; \text{if } n \text{ is odd,}
        \end{cases}
&amp; \mu_{1,n} &amp; = M_n,  &amp;  \mu_{2,n} &amp; = C_{n+1}. \end{align*}

The $3$-colored Motzkin paths correspond to the tree-like polyhexes defined by
Harary \cite{Harary}, as we will see in the next section.

Let $u = u_1 u_2 \cdots u_n \in \mathcal{M}_{k,n}$. Two indices $i,j \in [n] =
\{1,2, \ldots, n \}$ with $i &lt; j$ are called \textit{conjugates} with respect to
$u$ if and only if $j$ is the smallest number in $\{ i+1, i+2, \ldots, n \}$ for
which the segment $u_i u_{i+1} \cdots u_j$ of $u$ is a $k$-colored Motzkin
word.

A word $u \in \mathcal{M}_{k,n}$ is called ($k$-colored)
\textit{$\mathit{c}$-Motzkin word} if and only if every $i \in [n]$ with $u_i
\notin \{a,\bar{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. \ref{fig2}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{fig2.eps}\\
$u = a \enspace \beta_1 \enspace a \enspace \bar{a} \enspace \bar{a} \enspace a
       \enspace \beta_1 \enspace \beta_2 \enspace a \enspace \beta_1
       \enspace a \enspace a \enspace \bar{a} \enspace \bar{a}
       \enspace \bar{a} \enspace \beta_1 \enspace \beta_2 \enspace \beta_2 \enspace \bar{a}
       \enspace a \enspace \beta_1 \enspace \beta_1 \enspace \bar{a}$
\caption{A $2$-colored Motzkin path and its corresponding $c$-Motzkin word} \label{fig2}
\end{center}
\end{figure}

The $c$-Motzkin words have been introduced and studied in the
case $k=1$, \cite{PS2}.

In the following sections we will refer to the sets
$\mathcal{M}_{k,n}^c = \mathcal{M}_k^c \cap \mathcal{M}_{k,n}$ and
$\mathcal{M}_{k,n,r}^c = \mathcal{M}_k^c \cap \mathcal{M}_{k,n,r}$ with
cardinalities $\mu_{k,n}^c$ and $\mu_{k,n,r}^c$, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Section 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Enumeration of sets of $k$-colored Motzkin words}\label{sec3}

In this section we evaluate the cardinal number of several subsets of
$\mathcal{M}_k$ defined by various parameters. We first need the following
definition.

The \textit{initial rise} of a non-empty word $u = u_1 u_2 \cdots u_n \in \mathcal{M}_k$
with $u_1 = a$ is the segment $u_1 u_2 \cdots u_j$ where $u_{\nu} = a$ for every
$\nu \in [j]$ and $u_{j+1} \ne a$. If $u = \epsilon$ or $u_1 \ne 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 $\mathcal{M}_k$ and
$\mathcal{M}_k^c$, respectively, according to the parameters $l$, $r$, $p$
(coded by $x$, $y$, $z$), i.e.,
\begin{equation*}
F_k (x,y,z) = \sum\limits_{u \in \mathcal{M}_k} x^{l(u)} y^{r(u)} z^{p(u)}
\end{equation*}
and
\begin{equation*}
G_k (x,y,z) = \sum\limits_{u \in \mathcal{M}^c_k} x^{l(u)} y^{r(u)} z^{p(u)}.
\end{equation*}

\begin{pr}\label{pr3.1}
The generating functions $F_k$, $G_k$ are given by the formulae
\begin{equation}
F_k (x,y,z) = {1 + k x F_k(x,y) \over 1 - x^2 y z F_k(x,y)} \label{equation1}
\end{equation}
and
\begin{equation}
G_k (x,y,z) = {1 \over 1 - x^2 y z F_k (x,y) }, \label{equation2}
\end{equation}
where the generating function $F_k (x,y) = F_k(x,y,1)$ satisfies the equation
\begin{equation}
x^2 y F^2_k (x,y) + (kx -1) F_k(x,y) + 1 = 0 \label{equation3}
\end{equation}
and hence
\begin{equation}
F_k(x,y) = {1 - kx - \sqrt{ {(1-kx)}^2 - 4 x^2 y} \over 2 x^2 y}. \label{equation4}
\end{equation}
\end{pr}

\noindent \textit{Proof}:
We can easily verify that for $k \ne 0$ each nonempty $u \in \mathcal{M}_k$ can be uniquely written in
either of the forms $u = \beta_\nu v$ for some $v \in \mathcal{M}_k$ and $\nu \in [k]$, or
$u = a w \bar{a} v$ for some $v,w \in \mathcal{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
\begin{align*}
F_k (x,y,z) &amp; = 1 + \sum \limits_{ \nu=1 }^{ k } \sum \limits_{v} x^{ l( \beta_ {\nu} v) } y^{r(v)}
        +\sum \limits_{w,v} x^{ l(w)+l(v)+2 } y^{ r(w)+r(v)+1 } z^{ p (w)+ 1 } \\
        &amp; = 1 + k x F_k (x,y) + x^2 y z F_k (x,y,z) F_k (x,y).
\end{align*}
Thus,
\begin{equation*}
F_k (x,y,z) = {1 + k x F_k (x,y) \over 1 - x^2 y z F_k (x,y) }.
\end{equation*}

Moreover, applying the above equality for $z=1$ we deduce that
\begin{equation*}
x^2 y F^2_k (x,y) + (kx-1) F_k (x,y) + 1 = 0.
\end{equation*}

The proof of \eqref{equation1} for $k=0$ follows as above with some simple
modifications.

The proof of \eqref{equation2} is similar and it is omitted. \hfill{$\Box$}\\

\medskip

\noindent \textbf{Remark} The generating function $F_k$ can be obtained as an
application of a continued fraction result \cite{Flajolet}. More precisely if we apply
theorem 1 of \cite{Flajolet} by counting the rises by $xy$, the falls by $x$ and the level steps by $kx$
we conclude that
\begin{equation*}
 F_k (x,y) = {1 \over \displaystyle {1 - kx - {x^2 y \over \displaystyle {1 - kx - {x^2 y \over 1 - kx - \displaystyle {x^2 y \over \displaystyle \cdots}}}}}}
\end{equation*}
which easily leads to equation \eqref{equation3}.


\bigskip

\noindent \textbf{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
\eqref{equation2} for the generating function $G_k (x) = G_k (x,1,1)$ of
$\mathcal{M}_k^c$ according to the length.


\bigskip

1) For $k=1$, we have that
\begin{align*}
G_1 (x) &amp; = {1 \over 1- x^2 F_1(x)} = {1 \over 1- x^2 M(x)} =
        {1 + x M(x) \over 1 + x} \\
    &amp; = ( \sum\limits_{n=0}^{\infty} (-1)^n x^n )
        ( \sum\limits_{n=0}^{\infty} \gamma_n x^n ) \\
    &amp; = \sum\limits_{n=0}^{\infty} ( \sum\limits_{i=0}^n (-1)^i
        \gamma_{n-i} ) x^n,
\end{align*}
where
\begin{equation*}
\gamma_n =  \begin{cases}
        M_{n-1}, &amp; \text{if } n \ge 1; \\
        0, &amp; \text{if } n=0.
        \end{cases}
\end{equation*}

Thus,
\begin{equation*}
\mu_{1,n}^c = \sum\limits_{i=0}^{n} (-1)^i \gamma_{n-i} =
        \sum\limits_{i=0}^{n-2} (-1)^i M_{n-i-1},
\end{equation*}
for every $n \ge 2$.

We note that from the above formula we deduce that for every $n \ge 2$,
\begin{equation*}
\mu_{1,n}^c + \mu_{1,n-1}^c = M_{n-1}
\end{equation*}
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 \cite{Manoj}.

\bigskip

2) For $k=2$ and since
\begin{equation*}
F_2(x) = \sum\limits_{n=0}^{\infty} \mu_{2,n} x^n
       = \sum\limits_{n=0}^{\infty} C_{n+1} x^n = {1 \over x} [C(x) -1]
       = C^2(x),
\end{equation*}
we obtain that
\begin{equation*}
G_2(x) ={1 \over 1 -x^2 C^2 (x)}.
\end{equation*}

So, the generating function $G_2(x)$ coincides with the generating function of
Fine numbers $\mathit{f}_n$ \cite{DS1} and hence we conclude that
$\mu_{2,n}^c  = \mathit{f}_n$.

\bigskip

In the following result we give recursive formulae for the sequences
$\mu_{k,n,r}$ and $\mu_{k,n}$.

\begin{pr}\label{pr3.2}
For every $k,\nu,n,r \in \mathds{N}$ with $r \le {[{n \over 2}]}$ we have that
\begin{equation}
\mu_{k+\nu, n, r} = \sum\limits_{m=2r}^{n} {n \choose m} \mu_{k,m,r}
        {\nu}^{n-m} = \sum\limits_{m=2r}^{n} {n \choose m}
        {\mu}_{\nu,m,r} k^{n-m} \label{equation5}
\end{equation}
and
\begin{equation}
\mu_{k+\nu,n} = \sum\limits_{m=0}^{n} {n \choose m} \mu_{k,m} {\nu}^{n-m} =
        \sum\limits_{m=0}^n {n \choose m} \mu_{\nu, m} k^{n-m}. \label{equation6}
\end{equation}
\end{pr}

\noindent \textit{Proof}: From relation \eqref{equation4} we easily obtain that
\begin{equation*}
F_{k+\nu} (x,y) = {F_k ({x \over 1-\nu x}, y) \over 1 - \nu x}
        = {F_n ({x \over 1 -k x}, y) \over 1 - kx}
\end{equation*}
for every $k,\nu \in \mathds{N}$.

On the other hand, we have that
\begin{align*}
{F_k( {x \over 1 - \nu x}, y) \over  1- \nu x}
    &amp; = \sum\limits_{m=0}^{\infty} \sum\limits_{r=0}^{[{m \over 2}]} \mu_{k,m,r}
        x^m y^r {1 \over (1-\nu x)^{m+1}} \\
    &amp; = \sum\limits_{m=0}^{\infty} \sum\limits_{r=0}^{[{m \over 2}]} \mu_{k,m,r}
        x^m y^r \sum\limits_{j=0}^{\infty} {-m-1 \choose j} (-\nu x)^{j} \\
    &amp; = \sum\limits_{m=0}^{\infty} \sum\limits_{r=0}^{[{m \over 2}]} \sum\limits_{j=0}^{\infty}
        \mu_{k,m,r} {m + j \choose j} \nu^{j} x^{j+m} y^{r} \\
    &amp; = \sum\limits_{n=0}^{\infty} \sum\limits_{r=0}^{[{n \over 2}]} {\biggl [ \sum\limits_{m=2r}^{n}
        \mu_{k,m,r} {n \choose m} \nu^{n-m} \biggr ]} x^n y^r.
\end{align*}

It follows that

\begin{equation*}
\mu_{k+\nu, n, r} = \sum\limits_{m=2r}^{n} {n \choose m} \mu_{k,m,r} \nu^{n-m}.
\end{equation*}

Moreover, using the above relations we obtain that
\begin{equation*}
\mu_{k+\nu, n} = \sum\limits_{r=0}^{[{n \over 2}]} \mu_{k+\nu,n,r}
= \sum\limits_{m=0}^{n} {n \choose m} \nu^{n-m} \sum\limits_{r=0}^{[{m \over 2}]} \mu_{k,m,r}
= \sum\limits_{m=0}^{n} {n \choose m} \mu_{k,m} \nu^{n-m}.
\end{equation*}

The proofs of the second parts of relations \eqref{equation5} and \eqref{equation6}
are similar and they are omitted.~\hfill{$\Box$}

\bigskip

\noindent \textbf{Remark 1} Since
\begin{equation*}
\mu_{0,m,r} = \begin{cases}
        C_r, &amp; \text{if } m =2r; \\
        0,   &amp; \text{if } m \ne 2r
          \end{cases}
\end{equation*}
and
\begin{equation*}
\mu_{0,m} = \begin{cases}
        C_{m \over 2}, &amp; \text{if } m \text{ is even}; \\
        0,         &amp; \text{if } m \text{ is odd},
        \end{cases}
\end{equation*}
setting $\nu=0$ in relations \eqref{equation5} and \eqref{equation6} we obtain
that
\begin{equation}
\mu_{k,n,r} = {n \choose 2r} C_{r} k^{n -2r} = {1 \over n+1} {n+1 \choose r+1, r, n-2r} k^{n-2r} \label{equation7}
\end{equation}
and
\begin{equation}
\mu_{k,n} = \sum\limits_{r=0}^{[{n \over 2}]} {n \choose 2r} C_r k^{n-2r} \label{equation8}
\end{equation}
which give (for $k=1$) the well-known corresponding relations for Motzkin words \cite{Alonzo}.

Furthermore, for $k=2$, relation \eqref{equation8} gives the well-known relation of
Touchard
\begin{equation*}
C_{n+1} = \sum\limits_{r=0}^{[{n \over 2}]} {n \choose 2r} 2^{n-2r} C_r.
\end{equation*}

\medskip

\noindent \textbf{Remark 2} From relation \eqref{equation6} we can easily deduce relations
\begin{equation}
\mu_{k+1,n} = \sum\limits_{m=0}^n {n \choose m} \mu_{k,m} \label{equation9}
\end{equation}
and
\begin{equation}
\mu_{k+1,n+1} = \sum\limits_{m=0}^n {n \choose m} (\mu_{k,m} + \mu_{k,m+1}). \label{equation10}
\end{equation}

It is easy to check that from the above two relations, for $k=0$ and $k=1$, relations
\eqref{equation1}, \eqref{equation2}, \eqref{equation3} and \eqref{equation4} of \cite{Donaghey} follow.

\medskip

\noindent \textbf{Remark 3} Applying relation \eqref{equation9} for $k=2$, we obtain the number of all
$3$-colored Motzkin words of length $n$:
\begin{equation*}
\mu_{3,n} = \sum\limits_{m=0}^n {n \choose m} C_{m+1}.
\end{equation*}

This number also gives the cardinality of the set of all tree-like polyhexes
with $n+1$ hexagons
(\htmladdnormallink{A002212}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002212})
(for detailed definitions see \cite{Harary}),
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 $\epsilon$. 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 \in \mathcal{M}_{3,n}$ is $\beta_1 w$ ($\beta_2 w$ or $\beta_3 w$, respectively),
where the word
$w \in \mathcal{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. \ref{fig3} a,b,c.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{fig3.eps}
$
\enspace \enspace \enspace u = \beta_1 w \enspace \enspace \enspace \enspace \enspace \enspace
u = \beta_2 w \enspace \enspace \enspace \enspace \enspace \enspace \enspace
u = \beta_3 w \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace
        \enspace \enspace \enspace
u = a w_1 \bar{a} w_2 $\\
$
\enspace \enspace \enspace a \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace
\enspace \enspace \enspace \enspace
b \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace
\enspace
c \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace
\enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace
d \enspace \enspace \enspace $
\caption{The recursive coding of polyhexes}\label{fig3}
\end{center}
\end{figure}


If on the other hand the only points of the root hexagon with degree $3$ are
$C,D,E,F$ then the corresponding $u \in \mathcal{M}_{3,n}$ is the word
$a w_1 \bar{a} 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 $FA$; see Fig. \ref{fig3} d.


We continue by evaluating the coefficients of the powers of $F_k (x,y)$.

\begin{pr}\label{pr3.3}
The coefficients of $F_k^s (x,y)$, with $s \in \mathds{N}^*$, are given by the
formula
\begin{equation}
\label{equation11} [x^n y^r] F_k^s = {s \over n+s} {n + s \choose s+r,r,n-2r} k^{n-2r},
\end{equation}
where $n,r \in \mathds{N}$, with $r \le {[{n \over 2}]}$.
\end{pr}

\noindent \textit{Proof}: We define the function $H(x) = x F_k(x,y)$.
It follows easily by equation \eqref{equation3}
that
\begin{equation*}
H(x) = x [y H^2 (x) + k H (x) + 1].
\end{equation*}

Thus, if we set $P(\lambda) = y \lambda^2 + k \lambda + 1$ we obtain that
$H (x) = x P(H(x))$ and $P(0)=1$. Using Lagrange inversion formula \cite{Stanley}
we obtain
\begin{equation*}
\label{null1} [x^n] H^s = {1 \over n} [\lambda^{n-1}] \{s \lambda^{s-1} (P(\lambda))^n \}.
\end{equation*}

Moreover, we have
\begin{align*}
{s \over n} \lambda^{s-1} (P(\lambda))^n
    &amp; = {s \over n} \lambda^{s-1} \sum\limits_{i=0}^n {n \choose i} \lambda^i (y \lambda + k)^i \\
    &amp; = {s \over n} \lambda^{s-1} \sum\limits_{i=0}^n {n \choose i} \lambda^i
        \sum\limits_{\nu=0}^i {i \choose \nu} y^{\nu} \lambda^{\nu} k^{i-\nu} \\
    &amp; = {s \over n} \sum\limits_{m=0}^{2n} \sum\limits_{\nu = (m-n)^+}^{[{m \over 2}]}
        {n \choose m-\nu} {m - \nu \choose \nu} k^{m-2\nu} y^{\nu} \lambda^{m+s -1},
\end{align*}
where $(m-n)^{+} = \max \{0, m-n\}$.

Thus, for $m = n-s$ we deduce that
\begin{equation*}
\label{null2} [x^n] H^s = {s \over n} \sum\limits_{\nu=0}^{[{n-s \over 2}]} {n \choose n -s - \nu}
        {n -s-\nu \choose \nu} k^{n-s-2\nu} y^{\nu}
\end{equation*}
for every $n \ge s$.

Finally, applying the above equality for $n+s$ instead of $s$ and setting
$\nu = r$, we conclude that
\begin{align*}
[x^n y^r] F_k^s &amp; = {s \over n+s} {n+s \choose n-r} {n -r \choose r} k^{n-2r}\\
              &amp; = {s \over n+s} {n+s \choose s+r,r,n-2r} k^{n-2r}.
\end{align*} \hfill{$\Box$}

\bigskip

We note that relation \eqref{equation7} is a special case of relation
\eqref{equation11}, for $s=1$.

\bigskip

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

\begin{pr}\label{pr3.4}
The number of all $u \in \mathcal{M}^c_{k,n,r}$ that have initial rise of
length $s$ is equal to
\begin{equation*}
\label{null3} [x^n y^r z^s ] G_k = {s \over n-s} {n -s \choose r,r-s,n-2r} k^{n-2r},
\end{equation*}
where $1 \le s \le r \le [{n \over 2}]$.
\end{pr}

\noindent \textit{Proof}: By relation \eqref{equation2} and proposition
\ref{pr3.3} we obtain that
\begin{align*}
[x^n y^r z^s] G_k
    &amp; = [x^n y^r z^s] \{ \sum\limits_{s=0}^{\infty} x^{2s} y^s F_k^s (x,y) z^s \} \\
    &amp; = [x^n y^r] \{ x^{2s} y^s F_k^s (x,y) \}\\
    &amp; = [x^{n-2s} y^{r-s}] F_k^s \\
    &amp; = {s \over n-s} {n-s \choose r,r-s,n-2r} k^{n-2r}.
\end{align*} \hfill{$\Box$}

Using proposition \ref{pr3.1} and the same arguments as in the proof of
proposition \ref{pr3.4} we obtain the following result:

\begin{pr}\label{pr3.5}
The number of all $u \in \mathcal{M}_{k,n,r}$ that have initial rise of length $s$ is equal to
\begin{equation*}
\label{null4} [x^n y^r z^s] F_k  = {ns -rs +n + s-2r \over (n-s)(n-s+1)} {n-s+1 \choose r+1,r-s,n-2r} k^{n-2r},
\end{equation*}
where $1 \le s \le r \le [{n \over 2}]$.
\end{pr}

Notice that if $n=2r$ then both propositions \ref{pr3.4} and \ref{pr3.5} give the number of Dyck words
with prescribed height of the first peak \cite{Deutsch2}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Section 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Decomposition into prime words}\label{sec4}


A non-empty word $u \in \mathcal{M}_k^c$ is called \textit{prime} if and only if
it is not the product of two non-empty $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 \in \mathcal{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 \cite{PS1} and $c$-Motzkin \cite{PS2} words
is naturally extended to $k$-colored $c$-Motzkin words.

\begin{pr}\label{pr4.1}
Every $u \in \mathcal{M}_k^c$ is uniquely decomposed into a product of prime words.
\end{pr}

It is clear that the words $u \in \mathcal{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 \in \mathcal{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, \cite{Deutsch3,PS1}) and it is
extended here for arbitrary $k$. For this, we consider one more parameter $d$ of
$\mathcal{M}_k^c$, defined by the number of prime components. Let $G_k$ be the
generating function of $\mathcal{M}_k^c$ according to the parameters $l,r,p,d$
(coded by $x,y,z,\phi$), i.e.,
\begin{equation*}
G_k(x,y,z,\phi) = \sum\limits_{u} x^{l(u)} y^{r(u)} z^{p(u)} \phi^{d(u)}.
\end{equation*}

\begin{pr}\label{pr4.2}
The generating function $G_k (x,y,z,\phi)$ is given by the formula
\begin{equation*}
G_k (x,y,z,\phi) = 1 + {x^2 y z \phi (1 + k x F_k (x,y)) \over (1 - x^2 y z F_k (x,y)) ( 1 - x^2 y
\phi F_k (x, y))}.
\end{equation*}
\end{pr}

\noindent \textit{Proof}: Every non-empty $u \in \mathcal{M}_k^c$ can be
uniquely written in the form $u = a w \bar{a} v$, where $w \in \mathcal{M}_k$,
$v \in \mathcal{M}_k^c$, $r(u) = r(w) + r(v) + 1$, $p(u) = p(w) + 1$ and
$d(u)=d(v)+1$. Thus, by proposition \ref{pr3.1} follows that
\begin{align*}
G_k (x,y,z,\phi) &amp; = 1 + \sum\limits_{w,v} x^{l(w)+l(v)+2} y^{r(w)+r(v)+1} z^{p(w)+1} \phi^{d(w)+1} \\
           &amp; = 1 + x^2 y z \phi (\sum\limits_{w} x^{l(w)} y^{r(w)} z^{p(w)}) (\sum\limits_{v} x^{l(v)} y^{r(v)} \phi^{d(v)}) \\
           &amp; = 1 + x^2 y z \phi F_k (x,y,z) G_k (x,y,1,\phi) \\
           &amp; = 1 + x^2 y z \phi {1 + k x F_k (x,y) \over 1 - x^2 y z F_k (x,y)} G_k (x,y,1,\phi).
\end{align*}

Further, applying the previous equality for $z = 1$ and using relation
\eqref{equation3} we conclude that
\begin{equation*}
G_k (x,y,1,\phi) = {1 \over 1 - x^2 y \phi F_k (x,y)}
\end{equation*}
which implies the required formula. \hfill{$\Box$}

\bigskip

\noindent \textbf{Remark} Since $G_k (x,y,1,\phi) = 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
\cite{Deutsch1a,Deutsch1b,Deutsch2,Deutsch3}.

Furthermore, since $G_k(x,y,z,\phi) = G_k (x,y,\phi,z)$ we obtain the following
result.

\begin{pr}\label{pr4.3}
The number of all $u \in \mathcal{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 \in \mathcal{M}_{k,n,r}^{c}$ with $m$ prime components and length of the
initial rise equal to $s$.
\end{pr}

Proposition \ref{pr4.3} can also be proved directly, by constructing an involution
of $\mathcal{M}^c_k$ as follows:

We first define the mapping
\begin{equation*}
\phi : \{ u \in \mathcal{M}_k^c : p(u) \ge 2\}
\to \{u \in \mathcal{M}^c_k : d(u) \ge 2 \}
\end{equation*}
such that if $u = a a w \bar{a} v \bar{a} z$
with $w,v \in \mathcal{M}_k$, $z \in \mathcal{M}^c_k$, $l(w)+3$ conjugate of $2$
and $l(w)+l(v)+4$  conjugate of $1$, then $\phi(u) = a w \bar{a} a v \bar{a} z$.
Obviously, $\phi$ is a bijection. Next we define the mapping
\begin{equation*}
\theta : \mathcal{M}_k^c \to \mathcal{M}_k^c
\end{equation*}
with $\theta(u) = \phi^{p(u)-d(u)}(u)$, for every $u \in \mathcal{M}^c_k$;
(here $\phi^j$ stands for $\phi \circ \cdots \circ \phi$).
This mapping is well defined, with $l(\theta(u)) = l(u)$ and $r(\theta(u)) = r(u)$.

It is easy to check, by induction on the number $\nu(u) = {|p(u)-d(u)|}$
that $p(\theta(u)) = d(u)$ and $d(\theta(u)) = p(u)$ for every
$u \in \mathcal{M}^c_k$. It follows that $\theta$ is the required involution
of $\mathcal{M}^c_k$.

In order to construct $\theta(u)$ from $u \in \mathcal{M}^c_k$, we note that
if $p(u) = d(u)$ then $\theta(u)=u$. If $p(u) &gt; d(u)$, we delete the
first $\nu(u)$ $a$'s of $u$ and we insert one $a$ after each $\bar{a}$ of $u$
which corresponds to a conjugate of $2,3,\ldots, \nu(u)+1$. Finally, if
$p(u) &lt; d(u)$, we add $\nu(u)$ $a$'s in the beginning of $u$, whereas
we delete the initial $a$ from each one of the $2$nd, $3$rd, $\ldots$, ($\nu(u)+1$)st
prime component of $u$.

For example, for\\[-14pt]
\begin{equation*}
u = a \enspace a \enspace a \enspace a \enspace a \enspace \beta_1 \enspace \bar{a}
       \enspace \bar{a} \enspace a \enspace \bar{a} \enspace \bar{a} \enspace \beta_2
       \enspace a \enspace \bar{a} \enspace \bar{a} \enspace \bar{a} \enspace a
       \enspace \beta_2 \enspace a \enspace \bar{a} \enspace \bar{a} \enspace a
       \enspace \beta_1 \enspace \bar{a} \in \mathcal{M}^c_{2,24}
\end{equation*}\\[-18pt]
we obtain \\[-12pt]
\begin{equation*}
\theta(u) = a \enspace a \enspace a \enspace \beta_1 \enspace \bar{a} \enspace \bar{a}
           \enspace a \enspace \bar{a} \enspace \bar{a} \enspace a \enspace \beta_2
           \enspace a \enspace \bar{a} \enspace \bar{a} \enspace a \enspace \bar{a} \enspace a
           \enspace \beta_2 \enspace a \enspace \bar{a} \enspace \bar{a} \enspace a
           \enspace \beta_1 \enspace \bar{a} \in \mathcal{M}^c_{2,24}.
\end{equation*}

This is illustrated by the corresponding $2$-colored paths of $u$ and $\theta(u)$
in Fig. \ref{fig4}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=5in]{fig4.eps}
\caption{The $2$-colored Motzkin paths corresponding to $u$ and $\theta(u)$} \label{fig4}
\end{center}
\end{figure}

\noindent \textbf{Remark} From propositions \ref{pr3.4} and \ref{pr4.3} follows
that the number of all $u \in \mathcal{M}^{c}_{k,n,r}$ with $s$ prime
components is equal to
\begin{equation*}
{s \over n -s} {n -s \choose r, r-s, n-2r} k^{n-2r},
\end{equation*}
where $1 \le s \le r \le [{n \over 2}]$.

This extends a well-known result on Dyck words (i.e., for $k=0$)
\cite{Deutsch3,PS1}, to $k$-colored $c$-Motzkin words for arbitrary $k$.

Furthermore, by summing the above numbers for all $s \in [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
\begin{equation*}
\mu_{k,n,r}^c = {1 \over n-r+1}{n \choose r}{n-r-1 \choose r-1} k^{n-2r}.
\end{equation*}

This formula has been proved for $k=1$ in a different way \cite{PS2}.

\begin{thebibliography}{99}

\bibitem{Alonzo}
L. Alonzo, Uniform generation of a Motzkin word, \textit{Theoret. Comput. Sci.}, \textbf{134} (1994), 529--536.

\bibitem{Barrucci}
E. Barrucci, A. Del Lungo, E. Pergola and R. Pinzani, A construction for \mbox{enumerating} $k$-coloured
Motzkin paths, \textit{Proc.\ of the First Annual International Conference on Computing and
Combinatorics}, Springer, 1995, pp. 254-263.

\bibitem{Benchekroun}
S. Benchekroun and P. Moszkowski, A new bijection between ordered trees and legal bracketings, \textit{European J. Combin.} \textbf{17} (1996), 605--611.

\bibitem{Deutsch1a}
E. Deutsch, A bijection on Dyck paths and its consequences, \textit{Discrete Math.} \textbf{179} (1998), 253--256.

\bibitem{Deutsch1b}
E. Deutsch, A bijection on Dyck paths and its consequences-Corrigendum, \textit{Discrete Math.} \textbf{187} (1998), 297.

\bibitem{Deutsch2}
E. Deutsch, An involution on Dyck paths and its consequences, \textit{Discrete Math.} \textbf{204} (1999), 163--166.

\bibitem{Deutsch3}
E. Deutsch, Dyck path enumeration, \textit{Discrete Math.} \textbf{204} (1999), 167--202.

\bibitem{DS1}
E. Deutsch and L. Shapiro, A survey of the Fine numbers, \textit{Discrete Math.} \textbf{241} (2001), 241--265.

\bibitem{DS2}
E. Deutsch and L. W. Shapiro, A bijection between ordered trees and $2$-Motzkin paths, and its many consequences, \textit{Discrete Math.} \textbf{256} (2002), 655--670.

\bibitem{Donaghey}
R. Donaghey, Restricted plane tree representations on four Motzkin-Catalan equations, \textit{J.
Combin. Theory Ser. B} \textbf{22} (1977), 114--121.

\bibitem{DoS}
R. Donaghey and L. W. Shapiro, Motzkin numbers, \textit{J. Combin. Theory Ser. A} \textbf{23} (1977), 291--301.

\bibitem{Flajolet}
P. Flajolet, Combinatorial aspects of continued fractions, \textit{Discrete Math.} \textbf{32} (1980), 125--161.


\bibitem{Harary}
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, \textit{Proc. Edinbourgh Math. Soc.} \textbf{17} (1970), 1-13.

\bibitem{Manoj}
K. N. Manoj, Problem 10816, Amer. Math. Monthly, \href{http://www.geocities.com/kummini/maths/10816.ps}{http://www.geocities.com/ \mbox{kummini/maths/10816.ps}}

\bibitem{Mansour}
T. Mansour, Counting peaks at height $k$ in a Dyck path, \textit{J. Integer Seq.} \textbf{5} (2002), Article 02.1.1.

\bibitem{Peart}
P. Paert and W.-J. Woan, Dyck paths with no peaks at height $k$, \textit{J. Integer Seq.} \textbf{4} (2001), Article 01.1.3.

\bibitem{PS1}
A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck words, \textit{J. Combin.
Math. Comb. Comput.} \textbf{40} (2002), 33--39.

\bibitem{PS2}
A. Panayotopoulos and A. Sapounakis, On Motzkin words and noncrossing partitions, \textit{Ars
Combin.} \textbf{69} (2003), 109--116.

\bibitem{Pattisina}
R. Pattisina and V. Vajnovszki, On the reconstruction of a Motzkin tree from its code, \textit{J.
Inf. Optim. Sci.} \textbf{24} (2003), 583--589.

\bibitem{Stanley}
R. P. Stanley, \textit{Enumerative Combinatorics}, Vol. 2, Cambridge University Press, 1999.

\bibitem{Sulanke}
R. A. Sulanke, Bijective recurrences for Motzkin paths, \textit{Adv. in Appl. Math.} \textbf{27} (2001), 627--640.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A19.

\noindent \emph{Keywords: }
Motzkin words, Motzkin numbers, Dyck words, Catalan numbers, Polyhexes.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 1 2004;
revised version received June 8 2004.
Published in {\it Journal of Integer Sequences}, June 8 2004.

\bigskip
\hrule
\bigskip

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



\end{document}
</pre></body></html>