\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 \& 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 < 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, & \textit{if \enspace \enspace $u_i = u'_i =a$;} \\
\bar{a}, & \textit{if \enspace \enspace $u_i = u'_i = \bar{a}$;} \\
b, & \textit{if \enspace \enspace $u_i = a$, $u'_i = \bar{a}$;} \\
\bar{b}, & \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 < |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 < |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, & \textrm{if $w_i =a$ or $b$;} \\
\bar{a}, & \textrm{if $w_i = \bar{a}$ or $\bar{b}$,}
\end{array}} \right.} \enspace \enspace
r'_{i} = {\left\{ {\begin{array}{ll}
a, & \textrm{if $w_i =a$ or $\bar{b}$;} \\
\bar{a}, & \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, & \textrm{if $w_i \in \{a,\bar{a} \}$;} \\
b, & \textrm{if $w_i = \bar{b}$;} \\
\bar{b}, & \textrm{if $w_i = b$,} \\
\end{array}} \right.}
\end{array}$$
$$\begin{array}{l}
w^{+} _i = {\left\{ {\begin{array}{ll}
\bar{a}, & \textrm{if $w_{2n+1-i} = a$;} \\
a, & \textrm{if $w_{2n+1-i} = \bar{a}$;} \\
w_{2n+1-i}, & \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, & \textit{if \enspace \enspace $i < j,h$;} \\
\bar{a}, & \textit{if \enspace \enspace $h,j