\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 \& 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} & = \begin{cases} C_{n \over 2}, & \text{if } n \text{ is even;}\\ 0, & \text{if } n \text{ is odd,} \end{cases} & \mu_{1,n} & = M_n, & \mu_{2,n} & = 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 < 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) & = 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 } \\ & = 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) & = {1 \over 1- x^2 F_1(x)} = {1 \over 1- x^2 M(x)} = {1 + x M(x) \over 1 + x} \\ & = ( \sum\limits_{n=0}^{\infty} (-1)^n x^n ) ( \sum\limits_{n=0}^{\infty} \gamma_n x^n ) \\ & = \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}, & \text{if } n \ge 1; \\ 0, & \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} & = \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}} \\ & = \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} \\ & = \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} \\ & = \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, & \text{if } m =2r; \\ 0, & \text{if } m \ne 2r \end{cases} \end{equation*} and \begin{equation*} \mu_{0,m} = \begin{cases} C_{m \over 2}, & \text{if } m \text{ is even}; \\ 0, & \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 & = {s \over n} \lambda^{s-1} \sum\limits_{i=0}^n {n \choose i} \lambda^i (y \lambda + k)^i \\ & = {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} \\ & = {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 & = {s \over n+s} {n+s \choose n-r} {n -r \choose r} k^{n-2r}\\ & = {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 & = [x^n y^r z^s] \{ \sum\limits_{s=0}^{\infty} 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 \\ & = {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) & = 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} \\ & = 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)}) \\ & = 1 + x^2 y z \phi F_k (x,y,z) G_k (x,y,1,\phi) \\ & = 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) > 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) < 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}