<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{amssymb}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{color}
\usepackage{stmaryrd}
\usepackage{textcomp}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{color}
\usepackage{epsf}
\usepackage{epsfig}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\setlength{\textwidth}{6in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.2in}
\setlength{\textheight}{8.1in}

%\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in}
%\setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in}
%\setlength{\textheight}{8.9in}

\def\dom{{\rm dom}~}



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

\makeatother
\pagestyle{plain}


\begin{document}

\begin{center}
\epsfxsize=4in \leavevmode\epsffile{logo129.eps}
\end{center}


\begin{center}
\vskip 1cm{\LARGE\bf Meanders and Motzkin Words} \vskip 1cm \large
A. Panayotopoulos and P. Tsikouras \\
Deptartment of Informatics \\
University of Pireaus\\
Karaoli \&amp; Dimitriou 80 \\
18534 Pireaus \\
Greece\\
\href{mailto:antonios@unipi.gr}{antonios@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}
We study the construction of closed meanders and systems
of closed meanders, using Motzkin words with four letters.
These words are generated by applying 
binary operation on the set of Dyck words.
The procedure is based on the various kinds of intersection of the
meandric curve with the horizontal line.

\bigskip

\end{abstract}


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

Among various efforts to study and to generate meanders, Jensen
\cite{[4]} has used sequences related to the intervals between the
crossing points along the horizontal line, Franz and Earnshaw
\cite{[3]} have used noncrossing partitions, whereas the authors
\cite{[8]} as well as Barraud et al. \cite{[1]} have used planar
permutations which follow the meandric curve.

This paper refers to the study and construction of closed meanders and systems
of closed meanders, using Motzkin words.

The following definitions and notation refer to notions that are necessary for
the development of the paper.

A word $u \in \{a,\bar{a} \}^*$ is called a \textit{Dyck word} if
$|u|_a = |u|_{\bar{a}}$ and for every factorization $u = pq$ we
have $|p|_{a} \ge |p|_{\bar{a}}$ where $|u|_{a}$, $|p|_{a}$ (resp.
$|u|_{\bar{a}}$, $|p|_{\bar{a}}$) denote the number of occurrences
of $a$ (resp. $\bar{a}$) in the words $u$,$p$.

A word $w \in \{a, \bar{a}, x, y \}^*$ is called a \textit{Motzkin
word} if $|w|_a = |w|_{\bar{a}}$ and for every factorization $w =
pq$ we have $|p|_{a} \ge |p|_{\bar{a}}$, or equivalently if the
word obtained by deleting every occurence of $x, y$ from $w$ is a
Dyck word of $\{ a, \bar{a} \}^* $.

Let $\mathcal{D}_{2n}$ denote the set of all Dyck words of
length $2n$. It is well known that the cardinality of
$\mathcal{D}_{2n}$ equals to the Catalan number $C_n =
{\frac{1}{n+1}}{2n \choose n}$
(\htmladdnormallink{A000108}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108});
%and that to each Dyck word $u \in \mathcal{D}_{2n}$ corresponds a
%unique nested set $S_u$ on $[2n]=\{1,2,\ldots,2n\}$;
Panayotopoulos and Sapounakis \cite{[6]} have presented a
construction of $\mathcal{D}_{2n}$.

Let $u = u_1 u_2 \cdots u_{2n}$ with $u \in D_{2n}$. Two indices
$i,j$ such that $i &lt; j$, $u_i =a, u_j=\bar{a}$ are called
\textit{conjugates} with respect to $u$ if $j$ is the smallest
element of $\{i+1, i+2, \ldots, 2n \}$ for which the subword $u_i
u_{i+1} \cdots u_j$ is a Dyck word.

There exists a bijection between $D_{2n}$ and $N_{2n}$, since for
each $u \in D_{2n}$ we can determine its corresponding nested set
$S_u \in N_{2n}$ as follows : $\{i,j\} \in S_u$ if and only if
$i,j$ are conjugate indices with respect to $u$.

For example, the nested set $\{\{1,6\}, \{2,5\}, \{3,4\},
\{7,8\}, \{9,10\} \}$ corresponds to the Dyck word $u = a \enspace
a \enspace a \enspace \bar{a} \enspace \bar{a} \enspace \bar{a}
\enspace a \enspace \bar{a} \enspace a \enspace \bar{a}$.


We also recall that if we denote by $\dom S$ all the elements of
$N^*$ that belong to some pair of a nested set of pairs $S$, we
say that two nested set $S_1,S_2$ are \textit{matching} if $\dom S_1
= \dom S_2$ and $\dom A = \dom B$, $A \subseteq S_1$, $B \subseteq S_2$
imply that either $A = B = \emptyset$ or $\dom A = \dom S_1$.

Furthermore, we call $B \subseteq \dom S$ \textit{complete} if for
every $a \in B$ with $\{a, b\} \in S$, we have $b \in B$. We write
$S/B =\{ \{a,b\} \in S : a \in B \}$. For every two nested sets
$S_1, S_2$ with $\dom S_1 = \dom S_2$ that are not matching, there
exists a partition $B_1, B_2, \ldots, B_k$ of $\dom S_1$ with $B_i$
complete, such that the sets $S_1 / B_i, S_2 / B_i$, $i \in [k]$
are matching; we then call $S_1, S_2$ \textit{$k$-matching}
\cite{[7]}.

Geometrically, if we draw two matching nested sets, one above and
the other underneath the horizontal axis, they form a simple,
closed curve, whereas two $k$-matching nested sets create $k$ such
curves; (see Figures \ref{fig1} and \ref{fig2}).

In section~\ref{sec2} we define the $m$-Motzkin words. To each
such word corresponds a pair of nested sets which are either
matching or $k$-matching. The set of $m$-Motzkin words is
partitioned into classes of either two or four elements.

In section~\ref{sec3} we prove that there exists a bijection
between the set of closed meanders and the set of $m$-Motzkin
words which correspond to matching nested sets. Using this
bijection, we can generate closed meanders from $m$-Motzkin words.

In section~\ref{sec4} we extend the above results to systems of meanders and
we present a recursive generation of these systems.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                     Section 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{m-Motzkin words}\label{sec2}

For every pair $u = u_1 u_2 \cdots u_{2n}$, $u'=u'_1 u'_2 \cdots
u'_{2n}$ of elements of $\mathcal{D}_{2n}$, we define $u {\small
\circ} u'$ to be the word $w = w_1 w_2 \cdots w_{2n}$, with

\[
w _i = {\left\{ {\begin{array}{ll}
  a, &amp; \textit{if \enspace \enspace $u_i = u'_i =a$;} \\
  \bar{a}, &amp; \textit{if \enspace \enspace  $u_i = u'_i = \bar{a}$;} \\
  b, &amp; \textit{if \enspace \enspace $u_i = a$, $u'_i = \bar{a}$;} \\
  \bar{b}, &amp; \textit{if \enspace \enspace $u_i = \bar{a}$, $u'_i =a$.}
 \end{array}} \right.}
\]

\noindent For example, from  $u = a \enspace a \enspace a \enspace
\bar{a} \enspace \bar{a} \enspace \bar{a} \enspace a \enspace
\bar{a} \enspace a \enspace \bar{a}$ and $u' = a \enspace \bar{a}
\enspace a \enspace a \enspace \bar{a} \enspace a \enspace \bar{a}
\enspace a \enspace \bar{a} \enspace \bar{a}$ we obtain $u {\small
\circ} u' = a \enspace b \enspace a \enspace \bar{b} \enspace
\bar{a} \enspace \bar{b} \enspace b \enspace \bar{b} \enspace b
\enspace \bar{a}$.

We write $\widehat{W}_{2n} = \{ w: w = u {\small \circ} u',
\enspace u,u' \in \mathcal{D}_{2n} \}$.

\begin{pr}\label{2.1}
If $\mathit{w \in \widehat{W}_{2n}}$ then $w$ is a Motzkin word of
$\{a,\bar{a}, b, \bar{b}\}^*$, with $\mathit{|w|_b =
|w|_{\bar{b}}}$.
\end{pr}

\noindent \textit{Proof} : Let $I_1 = \{ i \in [2n] : u_i = u'_i = a \} $,
$I_2 = \{ i \in [2n] : u_i = a, u'_i = \bar{a} \} $, \\
\noindent $I_3 = \{ i \in [2n] : u_i = \bar{a} , u'_i = a \} $,
$I_4 = \{ i \in [2n] : u_i = u'_i = \bar{a} \} $. \\
\noindent Given that $u, u' \in \mathcal{D}_{2n}$ we have that:
$|I_1| + |I_2| = |I_3| + |I_4|$ and $|I_1| + |I_3| = |I_2| + |I_4|$;
so we get $|I_3| = |I_2|$ and $|I_1| = |I_4|$, i.e. $|w|_b = |w|_{\bar{b}}$
and $|w| _a = |w|_{\bar{a}}$.

Let now $z$ be the word that we obtain by deleting every
occurrence of $b, \bar{b}$ in $w$.

Obviously $|z|_a = |w|_a = |w|_{\bar{a}} = |z|_{\bar{a}}$. In order to show
that $z$ is a Dyck word, we must also have $|s|_a \ge |s|_{\bar{a}}$, for
every factorization $z = st$. This is true, since if $|s|_a &lt; |s|_{\bar{a}}$,
for some such factorization, then for at least one of the words  $u,u'$ we
would have a factorization $pq$ with $|p|_a &lt; |p|_{\bar{a}}$, contradicting
the assumption that both $u$ and $u'$ are Dyck words. \hfill{$\square$}

\bigskip

We call the elements of $\widehat{W}_{2n}$ \textit{meandric
Motzkin words} (or \textit{$m$-Motzkin words}) of length $2n$.

Let now $w = w_1 w_2 \cdots w_{2n}$, with $w \in
\widehat{W}_{2n}$. From $w$ we obtain two words $ r = r_1 r_2
\cdots r_{2n}$, $r' = r_1' r_2' \cdots r_{2n}'$ of $\{a, \bar{a}
\}^*$, with

\[
r _i = {\left\{ {\begin{array}{ll}
  a, &amp;  \textrm{if $w_i =a$ or $b$;} \\
 \bar{a}, &amp; \textrm{if $w_i = \bar{a}$ or $\bar{b}$,}
 \end{array}} \right.} \enspace \enspace
r'_{i} = {\left\{ {\begin{array}{ll}
  a, &amp;  \textrm{if $w_i =a$ or $\bar{b}$;} \\
 \bar{a}, &amp; \textrm{if $w_i = \bar{a}$ or $b$.}
 \end{array}} \right.}
\]

\noindent We call $r$ and $r'$ \textit{relatives} of $w$.

Practically, in order to obtain $r$ we change each occurrence of
$b,\bar{b}$ of $w$ into $a,\bar{a}$ respectively, whereas in order
to obtain $r'$ we change $b,\bar{b}$ into $\bar{a},a$
respectively.

\begin{pr}\label{2.2}
Let $\mathit{w \in \widehat{W}_{2n}}$  with  $w=u {\small \circ}
u'$, $u,u' \in \mathcal{D}_{2n}$ and let $\mathit{r,r'}$ be its
relatives. Then $\mathit{r}=u$ and $\mathit{r' = u'}$.
\end{pr}

\noindent \textit{Proof} : Let $w_i = a$ (resp. $\bar{a}$). Then
$r_i = a = u_i$ and $r'_i = a = u'_i$ (resp. $r_i = \bar{a} = u_i$
and $r'_i = \bar{a} = u'_i$). Let now $w_i = b$ (resp. $\bar{b}$).
Then $r _i = a = u_i$ and $r'_i = \bar{a} = u'_i$ (resp. $r_i =
\bar{a} = u_i$ and $r'_i = a = u'_i$).

So, we realize that in every case the elements of $r$ and $u$ as
well as the elements of $r'$ and $u'$ coincide, giving the
required result. $\hfill{\square}$

\bigskip

From the bijection between the sets $\mathcal{D}_{2n} \times \mathcal{D}_{2n}$
and $\widehat{W}_{2n}$ that we have established, we obviously get the following
relation :

\begin{center} $\mathit{|\widehat{W}_{2n}| = (C_n)^2}$. \end{center}

Notice that from the word $u {\small \circ} u'$ we immediately
obtain the word $u' {\small \circ} u$, by interchanging the
letters $b$ and $\bar{b}$. So, in order to generate the set
$\widehat{W}_{2n}$ it is actually enough to construct half of its
elements.

So, by the above procedure we also create for each $w \in
\widehat{W}_{2n}$ two nested sets $S_w, S'_w$ on $[2n]$
corresponding to the words $r,r' \in \mathcal{D}_{2n}$.

We denote with $W _{2n}$ (resp $W^k _{2n})$ the set of al the words
$w \in \widehat{W}_{2n}$ for which $S_w, S' _w$ are matching
(resp. $k$-matching).

For example, the word $w = a \enspace b \enspace a \enspace
\bar{b} \enspace \bar{a} \enspace \bar{b} \enspace b \enspace
\bar{b} \enspace b \enspace \bar{a}$ is an $m$-Motzkin word, for
which we have $r = a \enspace \! a \enspace \! a \enspace \!
\bar{a} \enspace \! \bar{a} \enspace \! \bar{a} \enspace \! a
\enspace \! \bar{a} \enspace \! a \enspace \! \bar{a}$ and $r'= a
\enspace \! \bar{a} \enspace \! a \enspace \! a \enspace \!
\bar{a} \enspace \! a \enspace \! \bar{a} \enspace  \! a \enspace
\! \bar{a} \enspace \! \bar{a}$.

The corresponding nested sets $S_w = \{\{1,6\},\{2,5\},\{3,4\},
\{7,8\},\{9,10\}\}$ and $S'_w = \{\! \{1,2\!\}, \!\{3,10\!\},$ 
$ \{4,5\}, \{6,7\}, \{8,9\}\}$ are matching.

Similarly, the word $w = a \enspace a \enspace b \enspace \bar{b}
\enspace \bar{a} \enspace \bar{b} \enspace a \enspace \bar{a}
\enspace b \enspace \bar{a}$ is a m-Motzkin word, for which we
have $r = a \enspace \! a \enspace \! a \enspace \! \bar{a}
\enspace \! \bar{a} \enspace \! \bar{a} \enspace \! a \enspace \!
\bar{a} \enspace \! a \enspace \! \bar{a}$ and $r'= a \enspace \!
a \enspace \! \bar{a} \enspace \! a \enspace \! \bar{a} \enspace
\! a \enspace \! a \enspace  \! \bar{a} \enspace \! \bar{a}
\enspace \! \bar{a}$. The corresponding nested sets 
$$S_w =\{
\{1,6\}, \{2,5\},\{3,4\}, \{7,8\}, \{9,10\} \}$$
and
$$S' _w
=\{ \{1,10\}, \{2,3\}, \{4,5\}, \{6,9\}, \{7,8\} \}$$
are
3-matching, with $B_1 = \{1,6,9,10\}$, $B_2 = \{2,3,4,5\}$ and
$B_3 = \{7,8\}$, thus determining the matching nested sets :

\noindent $S_{w} / B_1 = \{\{1,6\},\{9,10\}\}$, $S_{w} / B_2 = \{\{2,5\},\{3,4\}\}$, $S_{w} / B_3 = \{\{7,8\}\}$

\noindent $S'_{w} / B_1 = \{\{1,10\},\{6,9\}\}$, $S'_{w} / B_2 = \{\{2,3\},\{4,5\}\}$, $S'_{w} / B_3 = \{\{7,8\}\}$.

It is easy to obtain the following result.

\begin{pr}\label{2.3}
If $w \in W^{k}_{2n}$ then there exist $k$ subwords $w^j \in
W_{2s_{j}}$, $j=1,2,\ldots,k$ with $s_1 + s_2 + \cdots + s_k = n$
which can be recognized in $w$.
\end{pr}

For example, in the word
$w = a \enspace a \enspace b \enspace \bar{b} \enspace \bar{a} \enspace \bar{b} \enspace a \enspace \bar{a} \enspace b \enspace \bar{a} \in W_{10}^{3}$,
we recognize the subwords
$w^1 = w_1  w_6  w_9  w_{10} = a \enspace \bar{b} \enspace b \enspace \bar{a} \in W_4$, $w^2 = w_2  w_3  w_4  w_5 = a \enspace b \enspace \bar{b} \enspace \bar{a} \in W_{4}$ and $w^3 = w_7  w_8 = a \enspace \bar{a} \in W_2$.

\bigskip

We continue by introducing three internal operations in the set
$\widehat{W}_{2n}$:

For $w \in \widehat{W}_{2n}$, we define the words $w^{\enspace \!
\! \! \Mapsfromchar}$, $w^{-}$ and $w^{+}$ as follows:
$$\begin{array}{c}

$$\begin{array}{l}
w^{\enspace \! \! \! \Mapsfromchar}_i = \bar{w}_{2n+1-i} \enspace \enspace (\textit{where} \enspace \bar{\bar{w}}_j = w_j)
\end{array}$$ \\

\\

$$\begin{array}{l}
w^{-} _i = {\left\{ {\begin{array}{ll}
  w_i, &amp; \textrm{if $w_i  \in \{a,\bar{a} \}$;} \\
  b,   &amp; \textrm{if $w_i = \bar{b}$;} \\
  \bar{b}, &amp; \textrm{if $w_i = b$,} \\
 \end{array}} \right.}
\end{array}$$



$$\begin{array}{l}
w^{+} _i = {\left\{ {\begin{array}{ll}
  \bar{a}, &amp;  \textrm{if $w_{2n+1-i} = a$;} \\
  a,   &amp;  \textrm{if $w_{2n+1-i} = \bar{a}$;} \\
  w_{2n+1-i}, &amp; \textrm{if $w_{2n+1-i} \in \{b,\bar{b} \}$,} \\
 \end{array}} \right.}

\end{array}$$
\end{array}$$
\noindent for every $i \in [2n]$. We may call these operations
\textit{mirror}, \textit{overturn} and \textit{mirror-overturn}
respectively.

For example, if $w = a \enspace b \enspace a \enspace \bar{b}
\enspace \bar{a} \enspace \bar{b} \enspace b \enspace \bar{b}
\enspace b \enspace \bar{a}$ $\enspace \! \! \!$ then $w^{\enspace
\! \! \! \Mapsfromchar} = a \enspace \bar{b} \enspace b \enspace
\bar{b} \enspace b \enspace a \enspace b \enspace \bar{a} \enspace
\bar{b} \enspace \bar{a}$, $w^- = a \enspace \bar{b} \enspace a
\enspace b \enspace \bar{a} \enspace b \enspace$  $\bar{b}
\enspace b \enspace \bar{b} \enspace \bar{a}$ and $w^+ = a
\enspace b \enspace \bar{b} \enspace b \enspace \bar{b} \enspace a
\enspace \bar{b} \enspace \bar{a} \enspace b \enspace \bar{a}$.

\bigskip

It is obvious that for any $w \in \widehat{W}_{2n}$, the words
$w^{\enspace \! \! \! \Mapsfromchar}$, $w^-$ and $w^+$ also belong to
$\widehat{W}_{2n}$.
We have that $w^{\enspace \! \! \! \Mapsfromchar} = w$ (resp. $w^{+} = w$) iff
$w^+ = w^-$ (resp. $w^- = w^{\enspace \! \! \! \Mapsfromchar}$) as well as that
$w^- \ne w$ and $w^+ \ne w^{\enspace \! \! \! \Mapsfromchar}$.
We thus obtain the following result.

\begin{pr}\label{2.4}
The set $\widehat{W}_{2n}$ can be partitioned into classes of either two or
four elements.
\end{pr}

Let $A_{2n} =  \{w  \in \widehat{W}_{2n}: w_2 =a, w_{2n-1} = \bar{a}\}$ and
$B_{2n} = \{w  \in \widehat{W}_{2n}: w_2 =\bar{b}\}$.
By the previous properties of $w^{\enspace \! \! \! \Mapsfromchar}$, $w^-$ and
$w^+$ we have the following proposition.

\begin{pr}\label{2.5}
i) If $w \in A_{2n}$, then $w^{\enspace \! \! \! \Mapsfromchar}, w^-, w^+ \in A_{2n}$.\\
ii) If $w \notin A_{2n}$, then at least one of the words $w$, $w^{\enspace \! \! \! \Mapsfromchar}, w^-, w^+ $ belongs to $B_{2n}$.
\end{pr}

From the previous results it is clear that in order to construct
$\widehat{W}_{2n}$ it is enough to have $A_{2n}$ and $B_{2n}$.
In order now to generate each element
$w = u \textbf{\small \textopenbullet} u'$ of $A_{2n}$ (resp. $B_{2n}$),
it is enough to consider only the words
$u = u_1 u_2\cdots u_{2n}$, $u' = u'_1 u'_2 \cdots u'_{2n}$ of $\mathcal{D}_{2n}$ with
$u_2 = u'_2 =a $ and $u_{2n-1} = u'_{2n-1} = \bar{a}$ (resp. $u_2 = \bar{a}$, $u'_2 =a $).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                Section 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Meanders}\label{sec3}

We recall that a \textit{closed meander of order $n$}
is a closed self avoiding curve, crossing an infinite horizontal line $2n$ times
(\htmladdnormallink{A005315}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005315}).

\begin{figure}[h]
\begin{center}
\includegraphics[width=3in]{fig1.eps}
\caption{A closed meander of order 5} \label{fig1}
\end{center}
\end{figure}

Let $M_{2n}$ be the set of all closed meanders of order $n$.

As opposed to previous papers \cite{[1]}, \cite{[8]}, the study of
meanders will follow here the order of the crossings of the
horizontal line rather than the meandric curve itself.

It is clear that if $\mu \in M_{2n}$, the lines above (resp. underneath) the
horizontal line uniquely define a nested set $U_\mu$ (resp. $L_\mu$) on $[2n]$
with $U_\mu$, $L_\mu$ being matching and conversely two matching nested sets
$U_\mu$ and $L_\mu$ uniquely define the meander $\mu$.
This allows us to actually identify a meander $\mu \in M_{2n}$ to a pair
($U_\mu$,$L_\mu$) of nested sets of $[2n]$.

For example, for the closed meander $\mu$ of Figure~\ref{fig1} we have:

\noindent $U_{\mu} = \{ \{1,6\}, \{2,5\}, \{3,4\}, \{7,8\}, \{9,10\} \}$,

\noindent $L_{\mu} = \{ \{1,2\}, \{3,10\}, \{4,5\}, \{6,7\}, \{8,9\} \}$.\\

To each meander of $M_{2n}$ corresponds a unique word of $W_{2n}$. Intuitively,
this correspondence becomes obvious when we assign the letters
$a,\bar{a}, b, \bar{b}$ to the various kinds of intersection \textit{opening},
\textit{closing}, \textit{proceeding upwards}, \textit{proceeding downwards}
respectively, occurring along the horizontal line.

So, the word $w = a \enspace b \enspace a \enspace \bar{b} \enspace \bar{a} \enspace \bar{b} \enspace b \enspace \bar{b} \enspace b \enspace \bar{a}$
corresponds to the closed meander of Figure~\ref{fig1}.

In order to develop formally these ideas we need the following
result, obtained by considering all the possible orderings for the
elements $i,j,h$ of the pairs $\{i,j\} \in U_{\mu}$ and $\{i,h\}
\in L_{\mu}$.

To every  $\mu \in M_{2n}$ corresponds a unique word $w \in W_{2n}$, with

\[
w _i = {\left\{ {\begin{array}{ll}
  a, &amp; \textit{if \enspace \enspace $i &lt; j,h$;} \\
  \bar{a}, &amp; \textit{if \enspace \enspace  $h,j &lt;i$;} \\
  b, &amp; \textit{if \enspace \enspace $h &lt; i &lt; j$;} \\
  \bar{b}, &amp; \textit{if \enspace \enspace $j &lt; i &lt;h$,}
 \end{array}} \right.}
\]

\noindent where $\{i,j\} \in U_\mu$ , $\{i,h\} \in L_\mu$.

So, from the nested sets $U_{\mu}, L_{\mu}$ of the previous example  we create
again the word $w = a \enspace \! b \enspace \! a \enspace \! \bar{b} \enspace \! \bar{a} \enspace \! \bar{b} \enspace \! b \enspace \! \bar{b} \enspace \! b \enspace \! \bar{a}$.

Conversely, to every word $w \in W_{2n}$ with $S_w, S'_w$ matching, corresponds
a unique meander $\mu \in M_{2n}$ with $U_\mu = S_w$, $L_\mu = S'_w$.

From the above, we have the following result.

\begin{pr}\label{3.1}
There exists a bijection between the sets $M_{2n}$ and $W_{2n}$.
\end{pr}

In order to determine $U_\mu$ and $L_\mu$ (and hence construct the
meander $\mu \in M_{2n}$) we use the notion of conjugate indices
of a Dyck word. So, given a word $w \in W_{2n}$, we create its
relatives $r, r'$ and we find the conjugate indices of these Dyck
words, which indicate the pairs of $U_\mu$ and $L_\mu$
respectively.

We recall that a pair $\{a,b\}$ of a nested set $S$ is called
\textit{short pair} if there is no $c \in \dom S$ with either $a &lt; c
&lt; b$ or $b &lt; c &lt; a$, \cite{[7]}. We have the following result.

\begin{pr}\label{3.2}
Each digram $a\bar{a}, a\bar{b}, b\bar{a}, b\bar{b}$
(resp. $a\bar{a}, ab, \bar{b}\bar{a},\bar{b}b$) of a word $w \in W_{2n}$
corresponds to a short pair of $U_\mu$ (resp. $L_\mu$) in the associated
meander $\mu$.
\end{pr}

So, we can also determine the meander $\mu \in M_{2n}$ by repetitively
contracting the given word $w \in W_{2n}$, using each time propositions
\ref{3.1} and \ref{3.2}.

So for $w = a \enspace b \enspace a \enspace \bar{b} \enspace \bar{a} \enspace  \bar{b} \enspace b \enspace \bar{b} \enspace b \enspace \bar{a}$, we have:

\begin{tabular}{l}

\indent \begin{tabular}{ccccc|cc|cc|cc||cc|}
\cline{6-7} \cline{10-11} \cline{12-13}
\rule{0pt}{3ex} &amp;  &amp; $w$ = &amp; $a$ &amp; $b$ &amp; $a$ &amp; $\bar{b}$ &amp; $\bar{a}$ &amp;
$\bar{b}$ &amp; $b$ &amp; $\bar{b}$ &amp; $b$ &amp; $\bar{a}$\\
%\cline{6-7} \cline{10-11} \cline{12-13}
\rule{0pt}{3ex} &amp; &amp; &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$ &amp; $5$ &amp; $6$ &amp; $7$ &amp; $8$ &amp; $9$ &amp; $10$\\[1pt]
\end{tabular} \\[14pt]

\indent \begin{tabular}{cccccc|cc|ccccc}
\cline{7-8}
\rule{0pt}{3ex} &amp; &amp; &amp; &amp;  &amp; $a$ &amp; $b$ &amp; $\bar{a}$ &amp; $\bar{b}$  &amp; &amp; &amp; &amp;\\
%\cline{7-8}
\rule{0pt}{3ex} &amp; &amp; &amp; &amp; &amp; $1$ &amp; $2$ &amp; $5$ &amp; $6$  &amp; &amp; &amp; &amp;\\
\end{tabular} \\[14pt]

\indent \begin{tabular}{ccccc|cc|cccccccc}
\cline{6-7}
\rule{0pt}{3ex} &amp; &amp; &amp; &amp; &amp; $a$ &amp; $\bar{b}$ &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;\\
%\cline{6-7}
\rule{0pt}{3ex} &amp; &amp; &amp; &amp; &amp; $1$ &amp; $6$ &amp; &amp; &amp; &amp; &amp; &amp; &amp; &amp;\\
\end{tabular}

\end{tabular}

\noindent giving $U_\mu =\{\{1,6\}, \{2,5\}, \{3,4\}, \{7,8\}, \{9,10\}  \}$.

Similarly, we have

\begin{tabular}{l}

\indent \begin{tabular}{ccc|cc|c|cc||cc||cc|c}
\cline{4-5} \cline{7-8} \cline{9-10} \cline{11-12}
\rule{0pt}{3ex} &amp;  &amp; $w$  = &amp; $a$ &amp; $b$ &amp; $a$ &amp; $\bar{b}$ &amp; $\bar{a}$ &amp;
$\bar{b}$ &amp; $b$ &amp; $\bar{b}$ &amp; $b$ &amp; $\bar{a}$\\
%\cline{4-5} \cline{7-8} \cline{9-10} \cline{11-12}
\rule{0pt}{3ex} &amp; &amp; &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$ &amp; $5$ &amp; $6$ &amp; $7$ &amp; $8$ &amp; $9$ &amp; $10$\\[1pt]
\end{tabular} \\[14pt]

\indent \begin{tabular}{ccccc|cc|ccccccc}
\cline{6-7}
\rule{0pt}{3ex} &amp; &amp; &amp; &amp; &amp; $a$ &amp; $\bar{a}$  &amp; &amp; &amp; &amp; &amp; &amp; &amp; \\
%\cline{6-7}
\rule{0pt}{3ex} &amp; &amp; &amp; &amp; &amp; $3$ &amp; $\!\!\!10$  &amp; &amp; &amp; &amp; &amp; &amp; &amp; \\
\end{tabular}

\end{tabular}

\noindent giving $L_\mu =\{\{1,2\}, \{3,10\}, \{4,5\}, \{6,7\}, \{8,9\}  \}$.

We thus finally get the meander $\mu$ of Figure~\ref{fig1} again.

\bigskip

Let $\mu \in M_{2n}$ and $w \in W_{2n}$ its corresponding word. If we draw the
meanders $\mu^{\enspace \! \! \! \Mapsfromchar}$, $\mu^-$, $\mu^+$ that
correspond to the words $w^{\enspace \! \! \! \Mapsfromchar}$, $w^-$, $w^+$ we
realize that the above operations define meanders symmetric to the meander
$\mu$ that corresponds to $w$, with respect to a vertical axis, to the
horizontal line and to their intersection respectively.

It is easy to check that:

\noindent $\{i,j\} \in U_{\mu^{\enspace \! \! \! \Mapsfromchar}}$ iff
$\{2n+1-i, 2n+1-j\} \in U_\mu$, \\
\noindent $\{i,j\} \in L_{\mu^{\enspace \! \! \! \Mapsfromchar}}$, iff
$\{2n+1-i, 2n+1-j\} \in L_\mu$, \\
\noindent $U_{\mu^-} = L_\mu$, $L_{\mu^-} = U_\mu$, \\
\noindent $U_{\mu^+} = L_{\mu^{\enspace \! \! \! \Mapsfromchar}}$,
$L_{\mu^+} = U_{\mu^{\enspace \! \! \! \Mapsfromchar}}$.

Hence, according to Proposition~\ref{2.4} we have the following
result.

\begin{pr}\label{3.3}
The set $M_{2n}$ can be partitioned into classes of either two or four elements.
\end{pr}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                Section 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Systems of meanders}\label{sec4}

We can extend the definition of closed meanders to \textit{systems
of closed meanders with $k$ components} (or \textit{k-meanders})
by allowing configurations with $k$ disconnected meanders
\cite{[5]}. We will denote the set of all $k$-meanders of order
$n$ with $M^k_{2n}, k \in \{2,3,\ldots,n\}$.

\begin{figure}[h]
\begin{center}
\includegraphics[width=3in]{fig2.eps}
\caption{A $3$-meander of order 5} \label{fig2}
\end{center}
\end{figure}

Obviously, like in the case of meanders, a $k$-meander $\nu$ also determines
the corresponding nested sets $U_\nu$, $L_\nu$ that are now $k$-matching.

For example, for the $3$-meander $\nu$ of Figure~\ref{fig2} we have:

\noindent $U_{\nu} =\{ \{1,6\}, \{2,5\}, \{3,4\}, \{7,8\}, \{9,10\} \}$ \\
\noindent $L_{\nu} =\{ \{1,10\}, \{2,3\}, \{4,5\}, \{6,9\}, \{7,8\} \}$.

We can still assign the letters $a, \bar{a}, b, \bar{b}$ to the various kinds
of intersection, thus creating the corresponding word of $W_{2n}^{k}$.

So, the word $w = a \enspace a \enspace b \enspace \bar{b} \enspace \bar{a} \enspace \bar{b} \enspace a \enspace \bar{a} \enspace b \enspace \bar{a}$
 corresponds to the 3-meander of Figure~\ref{fig2}.

It is easy to check that if we refer to meanders of $M_{2n}^k$ instead of
$M_{2n}$, to $W_{2n}^k$ instead of $W_{2n}$ and to $k$-matching instead of
matching nested sets, we can apply propositions \ref{3.1}, \ref{3.2} and
\ref{3.3} to $k$-meanders.

So, similarly to proposition \ref{3.1}, there exists a bijection between the
sets $M_{2n}^k$ and $W_{2n}^k$, i.e., to every $\nu \in M_{2n}^k$ corresponds
a unique word $w \in W_{2n}^k$ obtained by the formula for $w_i$.

Conversely, to every $w \in W_{2n}^k$ with $S_w, S'_w$
$k$-matching, corresponds a unique system of meanders $\nu \in
M_{2n}^k$ with $U_{\nu} = S_{w}$, $L_{\nu} = S'_{w}$.

P. Di Francesco et al. \cite{[2]} have given formulae for the cardinality of $M_{2n}^k$,
for $k=n-3, n-2, n-1$, whereas for $k=n$ we have $|M_{2n}^n| = C_{2n}$, given
that $W_{2n}^n = \mathcal{D}_{2n}$.

Similarly to proposition \ref{3.2}, we can now determine the system of meanders
$\nu \in M_{2n}^k$ from the word $w \in W_{2n}^k$.

\bigskip

Let now $S$ be a member of the set $N_{2n}$ of the nested sets of pairs on
$[2n]$; let $\{a,d\},\{b,c\} \in S$ with $a &lt; b &lt; c &lt; d$ and such that for
every $\{e,f\} \in S$ with $e &lt; b &lt; f$ we have $e \le a$; then $\{a,d\}$
(resp. $\{b,c\}$) is called \textit{father} (resp. \textit{child}) of
$\{b,c\}$ (resp. $\{a,d\}$). We call two elements $\{i,j\}, \{k,l\}$ of $S$
\textit{brothers} if the have the same father, or if they have no father.

\bigskip

We define two operations in $N_{2n}$ as follows:

If $\{b,c\}$ and its father $\{a,d\}$ belong to $S \in N_{2n}$ with
$a &lt; b &lt; c &lt; d$, then $\sigma(S;a,b)$ is the set obtained if we replace the
pairs $\{a,d\}$ and $\{b,c\}$ with the pairs $\{a,b\}$ and $\{c,d\}$.
It is obvious that $\sigma(S;a,b) \in N_{2n}$ and that $\{a,b\}$ and
$\{c,d\}$ are brothers in $\sigma (S;a,b)$.

If $\{a,b\},\{c,d\}$ are brothers in $S \in N_{2n}$, with $a &lt; b &lt; c &lt; d$,
then $\tau(S;a,c)$ is the set obtained if we replace the pairs $\{a,b\}$ and
$\{c,d\}$ with the pair $\{a,d\}$ and $\{b,c\}$.
It is obvious that $\tau(S;a,c) \in N_{2n}$ and that $\{a,d\}$ is the father
of $\{b,c\}$ in $\tau (S;a,c)$.

\bigskip

The above definitions imply that if $\{a,d\}$ is the father of $\{b,c\}$ in
the set $S \in N_{2n}$, then $\tau ( \sigma(S;a,b);a,c)=S$, whereas if
$\{a,b\},\{c,d\}$ are brothers, then 
$$\sigma(\tau(S;a,c);a,b)=S.$$

We also have the following result.

\begin{pr} \label{4.1}
Let $\nu \in M_{2n}^{k}$. If the father $\{a,d\}$ and the child $\{b,c\}$
(resp. the brothers $\{a,b\}, \{c,d\}$) of $U_{\nu}$ belong to the same
component of $\nu$ then the set $U = \sigma (U_{\nu};a,b)$
(resp. $U = \tau(U_{\nu};a,c)$) and $L_\nu$ are $(k+1)$-matching, thus defining
a meander $\xi \in M_{2n}^{k+1}$, whereas if they belong to different
components of $\nu$, then $\xi$ belongs to $M_{2n}^{k-1}$.
\end{pr}

It is obvious that the above result still holds if we interchange \mbox{$L$
with $U$}.

\bigskip

Proposition~\ref{4.1} is important since it enables us to recursively construct
the sets $M_{2n}^k, k = j+1,j+2,\ldots,n$ if the set $M_{2n}^{j}$ is known for
some $j \in [n-1]$.

For example, if $\mu \in M_{10}$ is the meander of
Figure~\ref{fig1}, we have that the sets $U_\nu = U_\mu$ and
$L_\nu =\tau (L_\mu;6,8) =\{ \{1,2\}, \{3,10\}, \{4,5\}, \{6,9\},
\{7,8\}\}$ determine a meander $\nu \in M_{10}^2$; a second
application of proposition~\ref{4.1} gives $U_\xi = U_\nu$ and
$$L_\xi = \tau (L_\nu;1,3) = \{\{1,10\},\{2,3\},\{4,5\}, \{6,9\},
\{7,8\} \}$$ which determine the meander $\xi \in M_{10}^3$ of
Figure~\ref{fig2}.

%\pagebreak

\begin{thebibliography}{99}

\bibitem{[1]}
J. Barraud, A. Panayotopoulos and P. Tsikouras, Properties of
closed meanders, \textit{Ars Combin.} \textbf{67} (2003),
189--197.
\bibitem{[2]}
P. Di Francesco, O. Golinelli and E. Guitter, Meander, folding and arch statistics, \textit{Math.
Comput. Modelling} \textbf{26} (1997), 97--147.
\bibitem{[3]}
R. O. W. Franz and B. A. Earnshaw, A constructive enumeration of
meanders, \textit{Ann. Comb.} \textbf{6} (2002), 7--17.
\bibitem{[4]}
I. Jensen, A transfer matrix approach to the enumeration of plane meanders,
\textit{J. Phys. A} \textbf{33} (2000), 5953--5963.
\bibitem{[5]}
S. K. Lando and A. K. Zvonkin, Plane and projective meanders, \textit{Theoret. Comput. Sci.} \textbf{117}
(1993), 227--241.
\bibitem{[6]}
A. Panayotopoulos and A. Sapounakis, On binary trees and Dyck paths, \textit{Math. Inf. Sci. Hum.}
\textbf{131} (1995), 39--51.
\bibitem{[7]}
A. Panayotopoulos and P. Tsikouras, The multimatching property of nested sets, \textit{Math. Sci.
Hum.} \textbf{149} (2000), 23--30.
\bibitem{[8]}
A. Panayotopoulos and P. Tsikouras, Properties of meanders,
\textit{J. Combin. Math. Combin. Comput.}, \textbf{46} (2003),
181--190.
\end{thebibliography}


\bigskip
\hrule
\bigskip

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

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

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108} and \seqnum{A005315}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 21 2003;
revised version received  January 20 2004.
Published in {\it Journal of Integer Sequences}, February 10 2004.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


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