\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