% ----------------------------------------------------------------------------
  \documentclass[12pt]{article}
% ----------------------------------------------------------------------------

\setlength{\topmargin}{ -1.5cm }
\setlength{\oddsidemargin}{ -0.5cm }
\textwidth  16.5cm
\textheight 22.4cm

\usepackage{amsfonts}
\usepackage{amsmath}

\newcommand{\tab}{\hspace*{6mm}} % -- To be used at the beginning of Sections

\newcommand{\ii}{ {\rm i} } % ---------------------------------------------- i
\newcommand{\NN}{ \mathbb{N} } % -------------------------------- Natural Numbers
\newcommand{\ZZ}{ \mathbb{Z} } % -------------------------------- Integer Numbers
\newcommand{\WW}{ \mathcal{W} } % ------------------------ Binary words without zigzags
\newcommand{\UU}{ \mathcal{U} } % ----------------------- Ternary words without zigzags
\newcommand{\map}[3]{ { #1 } : { #2 } \rightarrow { #3 } } % ------ Morphism
%\newcommand{\displayfrac}[2]{\frac{\displaystyle #1}{\displaystyle #2}}
\newcommand{\mchoose}[2]{ { \left(\!\!\!\left( { #1 \atop #2 } \right)\!\!\!\right) } }
\newcommand{\Mchoose}[2]{ { \left(\!\!\left( { #1 \atop #2 } \right)\!\!\right) } }
\renewcommand{\mod}{ {\; {\rm mod}\; } }

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}

\newcommand{\eproof}{ \hspace*{ \fill } $ \Box $ \vspace*{ 0.3cm } }
\newenvironment{proof}{ {\em Proof}. }{ \eproof }
\newenvironment{examples}{ {\bf Examples} }{ }

\title{ Binary strings without zigzags }
\author{ Emanuele Munarini - Norma Zagaglia Salvi }
\date{} % Novembre, 2002

% ----------------------------------------------------------------------------
  \begin{document}
% ----------------------------------------------------------------------------

\maketitle

\vspace{3mm}

{\bf Summary.}
\emph{We study several enumerative properties of the set of all binary strings without zigzags,
i.e., without substrings equal to $\; 101 \;$ or $\; 010 \,$.
Specifically we give the generating series, a recurrence and two explicit formulas
for the number $\; w_{m,n} \;$ of these strings with $m$ $1$'s and $n$ $0$'s
and in particular for the numbers $\; w_n = w_{n,n} \;$ of central strings.
We also consider two matrices generated by the numbers $\; w_{m,n} \;$
and we prove that one is a Riordan matrix
and the other one has a decomposition $\; L T L^t \;$
where $\; L \;$ is a lower triangular matrix
and $\; T \;$ is a tridiagonal matrix,
both with integer entries.
Finally, we give a combinatorial interpretation of the strings under consideration
as binomial lattice paths without zigzags.
Then we consider the more general case of Motzkin, Catalan, and trinomial paths without zigzags.}

\vspace{5mm}

{\em AMS Classification}:
05A15, % exact enumeration problems, generating functions
05A05, % combinatorial choice problems (subsets, representatives, permutations)
05A10, % factorials, binomial coefficients, combinatorial functions
05A16. % asymptotic enumeration

\vspace{3mm}

{\em Keywords}:
{\footnotesize
  Binary strings, binary words, zigzags,
  Riordan matrix, secondary structures,
  Catalan-like paths, lattice paths, trinomial paths. }

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 49 \rms (2004), Article~B49h\hfill}
\def\thepage{}
%
%

% ----------------------------------------------------------------------------
  \section{ Introduction }
% ----------------------------------------------------------------------------

\tab
We say that a binary string has a \emph{zigzag} when $010$ or $101$ occur as substrings.
Here $\; \sigma \;$ is a substring, or a factor, of a string $\; \alpha \;$
when there exist two strings $\; \alpha_1 \;$ and $\; \alpha_2 \;$
such that $\; \alpha = \alpha_1 \sigma \alpha_2 \,$.
For instance, the strings $011001$ and $1100111$ are without zigzags,
while the strings $110100$ and $010011$ both present a zigzag.

Our aim is to obtain enumerative and combinatorial properties
of the set $\; \WW \;$ of all binary strings without zigzags.
Specifically we obtain the generating series, a recurrence and two explicit formulas
for the numbers $\; w_{m,n} \;$ of all strings in $\; \WW \;$ with $m$ $0$'s and $n$ $1$'s,
and in particular for the numbers $\; w_n = w_{n,n} \;$
of central strings in $\; \WW \,$, i.e., strings with an equal number of zeros and ones.
%In particular we express $ w_n $ in terms of the numbers $ f_{2n,n} $
%of order ideals of the fence $ \mathcal{Z}_{2n} $ \cite{MunaZaga}.

Then we consider the infinite matrix $\; W = [ w_{i,j} ]_{i,j \geq 0} \;$
and we prove that it admits a decomposition $\; L T L^t \;$
where $\; L \;$ is a lower triangular matrix and $\; T \;$ is a tridiagonal matrix.
Both the matrices $\; L \;$ and $\; T \;$ have nonnegative integer entries 
and those of $\; L \;$ have a combinatorial interpretation as connection constants
between two suitable persistent polynomial sequences.

We also consider the matrix $\; R = [ r_{i,j} ]_{i,j \geq 0} \,$,
where $\; r_{i,j} = w_{i,i-j} \;$ for $\; i \geq j \;$ and $\; r_{i,j} = 0 \;$ otherwise,
and we prove that it is a Riordan matrix \cite{Shapiro}.
This means that the generating series of the columns of such a matrix have the form
$\; \sum_{ n \geq 0 } r_{n,k} \; t^n = g(t) f(t)^k \;$
for suitable series $\; g(t) \;$ and $\; f(t) \;$.
In our case $\; g(t) \;$ is the generating series for the numbers $\; w_n \;$
and $\; f(t) \;$ is the generating series
for the numbers of irreducible secondary structures \cite{Stanley2}.

Our interest in binary strings without zigzags 
stems out also from the fact they can be interpreted as particular lattice paths
considering $\; 0 \;$ as the step $\; (1,-1) \;$ and $\; 1 \;$ as the step $\; (1,1) \,$.
This interpretation leads us to consider also the case of
Motzkin, Catalan (or Dyck) and trinomial paths without zigzags
\cite{AignerCatalanLike,AignerTheme,Deutsch}.
In particular we give the generating series and a recurrence
for the numbers $\; u_n \;$ of all central trinomial paths without zigzags
ending on the $x$-axis at $\; (n,0) \,$.
Finally we give the first-order asymptotic formula for $\; w_n \;$ and $\; u_n \,$.

The analogous problem for circular strings
has been studied in a separate work \cite{CircularWu}.
Both the problems, for linear and circular strings,
were posed by Jie Wu in the particular case
in which the number of $1$'s equals the number of $0$'s.
In \cite{DaiDhawanWuWu} the problem for linear strings is solved algorithmically,
but no explicit formula is given.


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL STEEN RYOM--HANSEN}{\SMALL LITTELMANN'S REFINED DEMAZURE 
%CHARACTER FORMULA}

% ----------------------------------------------------------------------------
  \section{ Generating series }
% ----------------------------------------------------------------------------

\tab
We say that a binary string has a \emph{zigzag}
when it has a substring equal to $\; 101 \;$ or $\; 010 \,$.
Let $\; \WW \;$ be the set of all binary strings without zigzags
and let $\; \WW_{m,n} \;$ be the set of all strings in $\; \WW \;$
with $\; m \;$ 1's and $\; n \;$ 0's.
Let $\; v_n \;$ be the number of all strings in $\; \WW \;$ of length $\; n \;$
and let $\; w_{m,n} = | \WW_{m,n} | \,$. Then consider the generating series
$$
 v(t) = \sum_{ n \geq 0 } v_n \; t^n \, , \qquad
 w(x,y) = \sum_{ m, n \geq 0 } w_{m,n} \; x^m y^n \, .
$$

A closed form for these series can be easily obtained in the following way
(see \cite{GuibasOdlyzko,Odlyzko} for a general approach to this kind of problems).
Let $\; \WW_0 \;$ ($\, \WW_1 \,$) be the set of all strings in $\; \WW \;$
starting with $\; 0 \;$ (with $\; 1 \,$).
Then $\; \WW = \varepsilon + \WW_0 + \WW_1 \,$,
where $\; \varepsilon \;$ is the empty string.
The sets $\; \WW_0 \;$ and $\; \WW_1 \;$ can be easily decomposed.
Indeed, any string $\; \alpha \in \WW_0 \;$ is exactly of one of the following forms:
i) $\; \alpha = 0 \alpha' \;$ with $\; \alpha' = \varepsilon \;$ or $\; \alpha' \in \WW_0 \,$,
ii) $\; \alpha = 01 \alpha'' \;$
with $\; \alpha'' = \varepsilon \;$ or $\; \alpha'' \in \WW_1 \,$.
Dually, any string $\; \alpha \in \WW_1 \;$ is exactly of one of the following forms:
i) $\; \alpha = 1 \alpha' \;$ with $\; \alpha' = \varepsilon \;$ or $\; \alpha' \in \WW_1 \,$,
ii) $\; \alpha = 10 \alpha'' \;$
with $\; \alpha'' = \varepsilon \;$ or $\; \alpha'' \in \WW_0 \,$.
Hence
\begin{equation}\label{Wsystem}
 \left\{
 \begin{array}{l}
  \WW_0 = 0 + 0\; \WW_0 + 01 + 01\; \WW_1 \\
  \WW_1 = 1 + 1\; \WW_1 + 10 + 10\; \WW_0 \, .
 \end{array}
 \right.
\end{equation}

To obtain the series $\; v(t) \;$
consider the morphism $\; \map{ \varphi }{ \{ 0, 1 \}^* }{ \ZZ[\![ t ]\!] } \;$
defined by $\; \varphi( 1 ) = \varphi( 0 ) = t \,$.
Then system (\ref{Wsystem}) becomes the following system in $\; \ZZ[\![t]\!] \;$
$$
 \left\{
 \begin{array}{l}
  ( 1 - t )\; w_0( t ) - t^2\; w_1( t ) = t + t^2 \\
  - t^2\; w_0( t ) + ( 1 - t )\; w_1( t ) = t + t^2
 \end{array}
 \right.
$$
whose solution is
$$
 w_0( t ) = w_1( t ) = \frac{ t + t^2 }{ 1 - t - t^2 } = \frac{ 1 }{ 1 - t - t^2 } - 1 
          = \sum_{ n \geq 0 } f_n \; t^n - 1 
$$
where the $\; f_n $'s are the Fibonacci numbers (with $\; f_0 = f_1 = 1 \,$).
Then
$$
 v( t ) = 1 + w_0( t ) + w_1( t )
        = \frac{ 1 + t + t^2 }{ 1 - t - t^2 }
        = \frac{ 2 }{ 1 - t - t^2 } - 1
$$
and hence $\; v_n = 2 f_n - \delta_{n,0} \,$,
where $\; \delta_{i,j} \;$ is the usual Kronecker delta.
Since $\; \WW_0 \;$ and $\; \WW_1 \;$ are sets of complementary strings, there is a bijection between them.
Then system (\ref{Wsystem}) allow to prove directly that 
$\; f_n \;$ is the number of all strings in $\; \WW \;$ of length $\; n \;$
not starting with $\; 0 \;$ (or, equivalently, not starting with $\; 1 \,$)
and the identity $\; v_n = 2 f_n - \delta_{n,0} \,$.
This last identity can also be explained combinatorially in the following way.
It is well known that the Fibonacci numbers $\; f_{n+1} \;$ count 
all binary strings of length $\; n \;$ not containing the pattern $\; 11 \,$.
For $\; n \geq 1 \;$ to any binary string $\; \alpha = a_1 \cdots a_n \;$
associate the binary string $\; \beta = b_1 \cdots b_{n-1} \;$
where $\; b_k = \textrm{xor}(a_k,a_{k+1}) \,$.
This is a 2-1-mapping where complementary strings are mapped onto the same string.
Moreover $\; \alpha \;$ does not contain the patterns $\; 101 \;$ and $\; 010 \;$
if and only if $\; \beta \;$ does not contain the pattern $\; 11 \,$.

To obtain the series $\; w(x,y) \;$ consider the morphism $\;  \;$
$\; \map{ \psi }{ \{ 0, 1 \}^* }{ \ZZ[\![x,y]\!] } \;$
defined by $\; \psi( 1 ) = x \;$ and $\; \psi( 0 ) = y \,$.
In this case system (\ref{Wsystem}) becomes the following system in $\; \ZZ[\![x,y]\!] \;$
$$
 \left\{
 \begin{array}{l}
  ( 1 - y )\; w_0( x, y ) - x y\; w_1( x, y ) = y + x y \\
  - x y\; w_0( x, y ) + ( 1 - x )\; w_1( x, y ) = x + x y
 \end{array}
 \right.
$$
whose solution is
$$
 w_0( x, y ) = \frac{ y + x^2 y^2 }{ 1 - x - y + x y - x^2 y^2 } \, , \quad
 w_1( x, y ) = \frac{ x + x^2 y^2 }{ 1 - x - y + x y - x^2 y^2 } \, .
$$
Since $\; w( x, y ) = 1 + w_0( x, y ) + w_1( x, y ) \,$, we have
\begin{equation}\label{WuSeries2}
 w( x, y ) = \frac{ 1 + x y + x^2 y^2 }{ 1 - x - y + x y - x^2 y^2 } \, .
\end{equation}
Notice that the form of this series implies the linear recurrence
\begin{equation}\label{WRec}
 w_{m+2,n+2} = w_{m+1,n+2} + w_{m+2,n+1} - w_{m+1,n+1} + w_{m,n} + \delta_{m,0} \delta_{n,0} \, .
\end{equation}

Finally, since $\; \WW_{m,n} \;$ and $\; \WW_{n,m} \;$ are sets of complementary strings,
it immediately follows the symmetry $\; w_{m,n} = w_{n,m} \,$.

%Define now the conjugate string $\; \overline{\alpha} \;$ of a binary string $\; \alpha \;$
%as the string obtained interchanging $\; 0 \;$ and $\; 1 \;$ in $\; \alpha \,$.
%For instance, if $\; \alpha = 100110 \;$ then $\; \overline{\alpha} = 011001 \,$.

%\begin{figure}
%$$
% \begin{array}{|c|ccccccccc|}
%  \hline
%  w_{m,n} & 0 & 1 &  2 &  3 &  4 &   5 &   6 &   7 &   8 \\
%  \hline
%        0 & 1 & 1 &  1 &  1 &  1 &   1 &   1 &   1 &   1 \\
%        1 & 1 & 2 &  2 &  2 &  2 &   2 &   2 &   2 &   2 \\
%        2 & 1 & 2 &  4 &  5 &  6 &   7 &   8 &   9 &  10 \\
%        3 & 1 & 2 &  5 &  8 & 11 &  14 &  17 &  20 &  23 \\
%        4 & 1 & 2 &  6 & 11 & 18 &  26 &  35 &  45 &  56 \\
%        5 & 1 & 2 &  7 & 14 & 26 &  42 &  62 &  86 & 114 \\
%        6 & 1 & 2 &  8 & 17 & 35 &  62 & 100 & 150 & 213 \\
%        7 & 1 & 2 &  9 & 20 & 45 &  86 & 150 & 242 & 367 \\
%        8 & 1 & 2 & 10 & 23 & 56 & 114 & 213 & 367 & 592 \\
%  \hline
% \end{array}
%$$
%\caption{Table of the numbers $w_{m,n}$}
%\end{figure}

% ----------------------------------------------------------------------------
  \section{Explicit formulas}
% ----------------------------------------------------------------------------

\tab
In this section we will give two explicit formulas for the numbers $\; w_{m,n} \,$.
One is obtained formally by expanding the generating series (\ref{WuSeries2})
while the other one is obtained combinatorially
giving an explicit canonical decomposition of the strings in $\; \WW \,$.

\paragraph{First formula.}
The first formula is obtained expanding series (\ref{WuSeries2}) in the following way:
\begin{eqnarray*}
 w(x,y)
 & = & \frac{ 1 + x y + x^2 y^2 }{ ( 1 - x ) ( 1 - y ) }\,
       \frac{ 1 }{\displaystyle 1 - \frac{ x^2 y^2 }{ ( 1 - x ) ( 1 - y ) } } \\
 & = & ( 1 + x y + x^2 y^2 ) \sum_{ k \geq 0 }
       \frac{ x^{2k} }{ ( 1 - x )^{k+1} } \frac{ y^{2k} }{ ( 1 - y )^{k+1} } \\
% & = & \sum_{ k \geq 0 } \frac{ x^{2k} }{ ( 1 - x )^{k+1} } \frac{ y^{2k} }{ ( 1 - y )^{k+1} } + \\
% & + & \sum_{ k \geq 0 } \frac{ x^{2k+1} }{ ( 1 - x )^{k+1} } \frac{ y^{2k+1} }{ ( 1 - y )^{k+1} } + \\
% & + & \sum_{ k \geq 0 } \frac{ x^{2k+2} }{ ( 1 - x )^{k+1} } \frac{ y^{2k+2} }{ ( 1 - y )^{k+1} }  \\
 & = & \sum_{ k \geq 0 }
       \frac{ x^{ k - \lfloor k/3 \rfloor } }{ ( 1 - x )^{ \lfloor k/3 \rfloor + 1 } }
       \frac{ y^{ k - \lfloor k/3 \rfloor } }{ ( 1 - y )^{ \lfloor k/3 \rfloor + 1 } } \, . \\
\end{eqnarray*}
Since
$$
 \frac{ t^r }{ ( 1 - t )^{s+1} } = \sum_{ n \geq 0 } {\binom {n - r + s} s } t^n \, ,
$$
%where the coefficients
%$$
% \Mchoose{ n }{ k } := \frac{ n^{\overline{k}}}{ k! } = \frac{ n ( n + 1 ) ( n + 2 ) \cdots ( n + k - 1 ) }{ k! }
%$$
%are the number of multisets of order $\; k \;$ on an $n$-set \cite{Stanley1}.
%Hence it is straightforward to obtain the following expression
%\begin{eqnarray}
% w_{m,n} & = &
% \sum_{ k \geq 0 } \mchoose{ k + 1 }{ m - 2 k } \mchoose{ k + 1 }{ n - 2 k } + \nonumber \\
% & + & \sum_{ k \geq 0 } \mchoose{ k + 1 }{ m - 2 k - 1 } \mchoose{ k + 1 }{ n - 2 k - 1 } + \nonumber \\
% & + & \sum_{ k \geq 0 } \mchoose{ k + 1 }{ m - 2 k - 2 } \mchoose{ k + 1 }{ n - 2 k - 2 }
%\end{eqnarray}
we have the expansion
\begin{eqnarray*}
 w(x,y)
 & = &
  \sum_{ k \geq 0 }
  \left( \sum_{ m \geq 0 } { \binom {m - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }} x^m \right)
  \left( \sum_{ n \geq 0 } { \binom {n - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }} y^n \right) \\
 & = &
  \sum_{ m, n, k \geq 0 }
  {\binom { m - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }}
  {\binom { n - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }} x^m y^n \\
\end{eqnarray*}
which yields the identity
\begin{equation}
 \label{IExpForm}
 w_{m,n} = \sum_{ k \geq 0 }
 {\binom { m - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }}
 {\binom { n - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }}
\end{equation}
where the index $\; k \;$ in the summation is at most
$\; \min( m + \lfloor m/2 \rfloor, n + \lfloor n/2 \rfloor ) \,$.

\paragraph{Second formula.}
A second expression for $\; w_{m,n} \;$ can be obtained 
by keeping track of the number of factors $\; 01 \;$ and $\; 10 \;$ (``switches'') in words without zigzags. 
Note that occurrences of these factors cannot overlap, 
which leads to a simple description in terms of regular expressions. 
Indeed, let $\; A \;$ be the set of words denoted by the regular expression $\; 0^+1^+10 \,$. 
We then have $\; \WW_0 = \sum_{ k \geq 0 } \WW_0^{(k)} \,$, where
$$
 \WW_0^{(0)} = 0^+ \, , \quad
 \WW_0^{(2k)} = A^k 0^* \;\; ( k > 0 ) \, , \quad
 \WW_0^{(2k+1)}= A^k 0^+1^+ \;\; ( k \geq 0 ) \, ,
$$
and similarly for $\; \WW_1 \,$. 
The generating function for $\; A \;$ w.r.t. the number of zeros and ones is $\; x^2y^2/((1-x)(1-y)) \,$, 
so that by binomial expansion of the obvious generating functions for the $\; \WW_i^{(k)}~(i=0,1) \,$
one finds the following expressions for the numbers $\; w_{m,n}^{(k)} \;$ 
of strings without zigzags with $\; m \;$ ones and $\; n \;$ zeros 
and with precisely $\; k \;$ occurrences of ``switches'':
\begin{eqnarray*}
 w_{m,n}^{(0)}  & = & \delta_{m,0}+ \delta_{n,0} - \delta_{m,0}\delta_{n,0} \\
 w_{m,n}^{(2k)} & = & \binom{m-k}{k} \binom{n-k-1}{k-1} + \binom{m-k-1}{k-1}  \binom{n-k-1}{k} \\
                & = & \frac{k\,(m+n-2k)}{(m-k)(n-k)} \binom{m-k}{k}\binom{n-k}{k}~(k>0) \\
 w_{m,n}^{(2k+1)} & = & 2 \binom{m-k-1}{k}\binom{n-k-1}{k} 
                    = 2\, \frac{(m-2k)(n-2k)}{(m-k)(n-k)} \binom{m-k}{k}\binom{n-k}{k}~(k \geq 0) \, .
\end{eqnarray*}
This leads to
\begin{equation}\label{IIExpFormBis}
 w_{m,n} = \sum_{ k \geq 0 } {\binom { m - k } k } {\binom { n - k } k }
 \frac{ 2 m n - 3 ( m + n ) k + 6 k^2 }{ ( m - k ) ( n - k ) } \qquad ( m, n > 0 ) \, .
\end{equation}

The generating function 
$$
 \sum_{m,n,k \geq 0} w_{m,n}^{(k)}\,  x^m y^n z^k = \frac{(1-xyz)^2 - xy}{(1-x)(1-y)-(xyz)^2} \,
$$
can be obtained by routine calculation from
$$
 \WW = \varepsilon + \sum_{k \geq 0} \left( \WW_0^{(k)} + \WW_1^{(k)} \right)
$$
or from an obvious generalization of the system of equations given in Section 2.

% -----------------------------------------------------------------------------------------------------------
  \section{Central strings}
% -----------------------------------------------------------------------------------------------------------

\tab
We say that a binary string is \emph{central}
when the number of $\; 1 $'s is equal to the number of $\; 0 $'s.
Let $\; w_n = w_{n,n} \;$ be the number of all {\em central binary strings without zigzags}.
The first values of $\; w_n \;$ are
1, 2, 4, 8, 18, 42, 100, 242, 592, 1460, 3624, 9042, 22656, 56970, 143688
(sequence \#A078678 in \cite{Sloane}).

Of course the explicit formulas (\ref{IExpForm}) and (\ref{IIExpFormBis}) for the numbers $\; w_{m,n} \;$
yield explicit formulas for the numbers $\; w_n \,$. Specifically
$$
 w_n = \sum_{ k = 0 }^{ n + \lfloor n/2 \rfloor }
 {\binom { n - k + 2 \lfloor k/3 \rfloor } { \lfloor k/3 \rfloor }}^{\hspace{-1.1mm}2}
 \, , \qquad
 w_n = \sum_{ k \geq 0 }^{ \lfloor n / 2 \rfloor } { \binom {n - k } k }^{\hspace{-1.1mm}2}
 \; \frac{ 2 n^2 - 6 n k + 6 k^2 }{ ( n - k )^2 } \, .
$$
%\begin{eqnarray}
% w_n & = & \sum_{ k = 0 } \mchoose{k}{n-2k} \mchoose{k+1}{n-2k+2} + \nonumber \\
%     &   & 2 \sum_{ k = 0 } \mchoose{k}{n-2k-1} \mchoose{k+1}{n-2k} + \nonumber \\
%     &   & \sum_{ k = 0 } \mchoose{k}{n-2k-2} \mchoose{k+1}{n-2k-2} \, .
%\end{eqnarray}

The generating function for the numbers $\; w_n \;$
is the diagonal of the double series $\; w( x, y ) \,$.
By Cauchy's integral theorem \cite{Comtet,HautusKlarner,Stanley2} it is given by
%\begin{eqnarray*}
% w( t )
% & = & \sum_{ n \geq 0 } w_n \; t^n
%   =   \frac{ 1 }{ 2 \pi \ii }
%       \oint w\left( z, \frac{ t }{ z } \right) \;
%       \frac{ {\rm d} z }{ z } \\
% & = & \frac{ 1 }{ 2 \pi \ii }
%       \oint \frac{ 1 + t + t^2 }{ - z^2 + ( 1 + t - t^2 ) z - t } \; {\rm d} z \\
%\end{eqnarray*}
$$
 w( t ) =  \sum_{ n \geq 0 } w_n \; t^n  =   
 \frac{ 1 }{ 2 \pi \ii } \oint w\left( z, \frac{ t }{ z } \right) \; \frac{ {\rm d} z }{ z }  =  
 \frac{ 1 }{ 2 \pi \ii } \oint \frac{ 1 + t + t^2 }{ - z^2 + ( 1 + t - t^2 ) z - t } \; {\rm d} z 
$$       
where the integral is taken over a simple contour
containing all the singularities $\; s( t ) \;$ of the series
such that $\; s( t ) \to 0 \;$ as $\; t \to 0 \,$.
The polynomial $\; z^2 - ( 1 + t - t^2 ) z + t \;$ at the denominator has roots
$$
 z^\pm = \frac{ 1 + t - t^2 \pm \sqrt{ ( 1 + t - t^2 )^2 - 4 t } }{ 2 } \, .
$$
Notice that under the radical we have the polynomial
$$
 ( 1 + t - t^2 )^2 - 4 t = 1 - 2 t - t^2 - 2 t^3 + t^4 = ( 1 + t + t^2 )( 1 - 3 t + t^2 ) \, .
$$
Since only $\; z^- \to 0 \;$ as $\; t \to 0 \,$, by the residue theorem, we have
$$
 w( t ) = \lim_{ z \to z^- } \frac{ 1 + t + t^2 }{ - ( z - z^+ ) } =
 \frac{ 1 + t + t^2 }{ z^+ - z^- }
$$
that is
\begin{equation}\label{centralSeries}
 w( t ) = \frac{ 1 + t + t^2 }{ \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }
        = \sqrt{ \frac{ 1 + t + t^2 }{ 1 - 3 t + t^2 } } \, .
\end{equation}
Since
$$
 \frac{ 1 + t + t^2 }{ 1 - 3 t + t^2 } = 1 + \frac{ 4 t }{ 1 - 3 t + t^2 } = 1 + 4 t \sum_{ n \geq 0 } f_{2n+1}\, t^n \, ,
$$
one has, from identity (\ref{centralSeries}), 
a convolution representation of the odd-indexed Fibonacci numbers in terms of the $\; w_n $
$$
 4 f_{ 2 n - 1 } = \sum_{ k = 0 }^n w_k w_{n-k} \qquad ( n > 0 )
$$
which is very much reminiscent of the familiar
$$
 4^n = \sum_{ k = 0 }^n \binom{2k}{k} \binom{2(n-k)}{n-k} \, .
$$

Finally, taking the logarithmic derivative of $\; w(t) \,$, we obtain the identity
%$$
% w'(t) = \frac{2+2t+2t^3+2t^4}{1-2t-t^2-2t^3+t^4} F(t)
%       = \frac{2+2t+2t^3+2t^4}{1-2t-t^2-2t^3+t^4} \frac{w(t)}{1+t+t^2}
%$$
%from which we have the identity
$$
 ( 1 - 2 t - t^2 - 2 t^3 + t^4 )\; w'( t ) = 2 ( 1 - x^2 )\; w( t )
$$
which implies the following linear recurrence for the numbers $\; w_n \;$
$$
 ( n + 4 )\, w_{ n + 4 } - 2 ( n + 4 )\, w_{ n + 3 } - ( n + 2 )\, w_{ n + 2 } - 2\, n\, w_{ n + 1 } + n\, w_n = 0 \, .
$$

%In \cite{MunaZaga} we obtained the following generating series
%$$
% F( t ) = \sum_{ n \geq 0 } f_{2n,n} \; t^n = \frac{1}{\sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 }}
%$$
%for the numbers $\; f_{2n,n} \;$ of all order ideals of size $\; n \;$ of the fence $\; \mathcal{Z}_{2n} \,$.
%Since $\; w( t ) = ( 1 + t + t^2 ) F( t ) \,$, we have the relation
%\begin{equation}
% \label{wf1}
% w_{n+2} = f_{ 2 n + 4, n + 2 } + f_{ 2 n + 2, n + 1 } + f_{ 2 n, n } \, .
%\end{equation}
%It could be interesting to have a combinatorial explanation of this identity.

%Here we notice that, since
%$$
% Q( x, y ) = \sum_{ n, k \geq 0 } {\binom  n  k }^{\!2} \; x^n y^k =
% \frac{1}{\sqrt{ 1 - 2 x + x^2 - 2 x y - 2 x^2 y + x^2 y^2 }}
%$$
%and
%$$
% Q( t, t ) = \sum_{ n \geq 0 } \left[ \sum_{ k \geq 0 } { n - k \choose k }^{\!2} \right] t^n =
% \frac{1}{\sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 }} \, ,
%$$
%we have
%$$
% f_{2n,n} = \sum_{ k \geq 0 } { n - k \choose k }^{\!2} \, .
%$$
%Hence identity (\ref{wf1}) can be rewritten as
%\begin{equation}
% \label{wf2}
% w_{n+2} = \sum_{ k \geq 0 } { n - k + 2 \choose k }^{\!2} +
% \sum_{ k \geq 0 } { n - k + 1 \choose k }^{\!2} +
% \sum_{ k \geq 0 } { n - k \choose k }^{\!2} \, ,
%\end{equation}
%which is essentially identity (\ref{IExpFormCent}).

% -----------------------------------------------------------------------------------------------------------
  \section{The matrix $\; W \;$}
% -----------------------------------------------------------------------------------------------------------

\tab
We now turn to consider the infinite matrix
$$
 W = [ w_{i,j} ]_{i,j \geq 0} =
 \begin{bmatrix}
  1 & 1 &  1 &  1 &  1 &   1 &   1 &   1 &   1 \\
  1 & 2 &  2 &  2 &  2 &   2 &   2 &   2 &   2 \\
  1 & 2 &  4 &  5 &  6 &   7 &   8 &   9 &  10 \\
  1 & 2 &  5 &  8 & 11 &  14 &  17 &  20 &  23 \\
  1 & 2 &  6 & 11 & 18 &  26 &  35 &  45 &  56 \\
  1 & 2 &  7 & 14 & 26 &  42 &  62 &  86 & 114 \\
  1 & 2 &  8 & 17 & 35 &  62 & 100 & 150 & 213 \\
  1 & 2 &  9 & 20 & 45 &  86 & 150 & 242 & 367 \\
  1 & 2 & 10 & 23 & 56 & 114 & 213 & 367 & 592 \\
  \ldots
 \end{bmatrix} \, .
$$
We will prove that it can be decomposed as $\; L T L^t \;$
where $\; L \;$ is the lower triangular matrix
$$
 L = [ l_{i,j} ]_{i,j \geq 0} =
 \begin{bmatrix}
  1 &   &   &   &   &    &   &   &   \\
  1 & 1 &   &   &   &    &   &   &   \\
  1 & 1 & 1 &   &   &    &   &   &   \\
  1 & 1 & 1 & 1 &   &    &   &   &   \\
  1 & 1 & 1 & 2 & 1 &    &   &   &   \\
  1 & 1 & 1 & 3 & 2 &  1 &   &   &   \\
  1 & 1 & 1 & 4 & 3 &  3 & 1 &   &   \\
  1 & 1 & 1 & 5 & 4 &  6 & 3 & 1 &   \\
  1 & 1 & 1 & 6 & 5 & 10 & 6 & 4 & 1 \\
  \ldots
 \end{bmatrix}
$$
with entries given by
$$
 l_{i,0} = 1 \, , \qquad
 l_{i+1,j+1} = {\binom { i - \lceil j / 2 \rceil } { i - j} }
             = {\binom { i - \lceil j / 2 \rceil } { \lfloor j / 2 \rfloor} } \, ,
$$
$\: L^t \;$ is the transpose of $\; L \;$
and $\; T \;$ is the tridiagonal matrix
$$
 T = [ t_{i,j} ]_{i,j \geq 0} =
 \begin{bmatrix}
  1 & 0 &   &   &   &   &   &     \\
  0 & 1 & 0 &   &   &   &   &     \\
    & 0 & 2 & 1 &   &   &   &     \\
    &   & 1 & 2 & 0 &   &   &     \\
    &   &   & 0 & 2 & 1 &   &     \\
    &   &   &   & 1 & 2 & 0 &     \\
    &   &   &   &   & 0 & 2 & 1   \\
    &   &   &   &   &   &   & \ldots
 \end{bmatrix}
$$
with entries
$$
 t_{i,j} = [ j \mod 2 = 0, j \ne 0 ]\, \delta_{i,j+1} +
 ( 2 - [ i = 0, 1 ] )\, \delta_{i,j} + [ i \mod 2 = 0, i \ne 0 ]\, \delta_{i+1,j}
$$
where the square brackets denote the Iverson notation
for the characteristic function of a proposition \cite{Knuth}
and $\; \delta_{i,j} = [ i = j ] \;$ is the usual Kronecker delta.

The decomposition $\; W = L T L^t \;$ is equivalent to the identity
\begin{equation}\label{WuMatId}
 \sum_{ h, k \geq 0 } l_{i,h} t_{h,k} l_{j,k} = w_{i,j} \, .
\end{equation}
To prove such an identity we consider the series
$$
 S(x,y) = \sum_{ i, j \geq 0 }
 \left( \sum_{ h, k \geq 0 } l_{i,h} t_{h,k} l_{j,k} \right) x^i y^j \, .
$$
Substituting $\; t_{h,k} \;$ with its explicit expression and using the formulas
$$
 \sum_{ i \geq 0 } l_{i,0}\; x^i = \frac{1}{1-x} \, , \qquad
 \sum_{ i \geq 0 } l_{i,k}\; x^i = \frac{x^k}{(1-x)^{\lceil k/2 \rceil}} \, ,
$$
after some straightforward computations we obtain $\; S( x, y ) = w( x, y ) \,$,
proving identity (\ref{WuMatId}).

The stated decomposition for the matrix $\; W \;$ also holds
for the finite matrix $\; W_n = [ w_{i,j} ]_{i,j=0}^n \,$.
More precisely $\; W_n = L_n T_n L_n^t \;$ where
$\; L_n = [ l_{i,j} ]_{i,j=0}^n \;$ and $\; T_n = [ t_{i,j} ]_{i,j=0}^n \,$.
Hence $\; \det W_n = \det T_n \;$
and $\; \det T_n = \det T'_{n-2} \;$ where $\; T'_{n-2} $ is the matrix
obtained deleting the first two rows and columns of $\; T_n \,$.
Moreover, if $\; d_n = \det T'_n \;$ it is easy to see that
$\; d_{n+2} = 3 d_n \;$ and $\; d_0 = 2 \,$, $\; d_1 = 3 \,$.
Hence it follows that $\; d_n = \frac{ 5 - ( -1 )^n }{ 2 }\; 3^{\lfloor n / 2 \rfloor} \,$.
So $\; \det W_n = 1 \;$ for $\; n = 0, 1 \;$ and $\; \det W_n = d_{n-2} \;$ for $\; n \geq 2 \,$.
%$$
% \det W_n =
% \begin{cases}
%  1       & \text{for}\;\, n = 0, 1 \\
%  d_{n-2} & \text{for}\;\, n \geq 2 \, .
% \end{cases}
%$$
Since the entries of the matrix $\; W \;$ count certain lattice paths (see Section 7)
it could be interesting to prove the above result combinatorially in the style of Gessel-Viennot theorem 
for the number of configurations of non-intersecting lattice paths \cite{GesselViennot}.

We conclude this section noticing that the coefficients $\; l_{i+1,j+1} \;$ 
are connection constants between two persistent polynomial sequences. Specifically 
$$
 x^n = \sum_{ k = 0 }^n {\binom { n - \lceil k / 2 \rceil } { n - k} } \;
 x^{ \lfloor k / 2 \rfloor } ( x - 1 )^{ \lceil k / 2 \rceil } \, .
$$
%To prove this identity it is sufficient to consider the polynomials
%$$
% x^{ \lfloor n / 2 \rfloor } ( x - 1 )^{ \lceil n / 2 \rceil } =
% \sum_{ k = 0 }^n { \lceil n / 2 \rceil \choose n - k } ( - 1 )^{n-k} \; x^k
%$$
%and to show that the matrices
%$$
% \left[ { i - \lceil j / 2 \rceil \choose i - j } \right]_{i,j \geq 0} \, , \qquad
% \left[ { \lceil i / 2 \rceil \choose i - j } ( - 1 )^{i-j} \right]_{i,j \geq 0}
%$$
%are inverses of each others, that is
%$$
% \sum_{ k \geq 0 } { i - \lceil k / 2 \rceil \choose i - k }
% { \lceil k / 2 \rceil \choose k - j } ( - 1 )^{k-j} = \delta_{i,j} \, .
%$$
%Finally this identity can be proved writing explicitly
%the series of first and second member.

% -----------------------------------------------------------------------------------------------------------
  \section{A Riordan matrix}
% -----------------------------------------------------------------------------------------------------------

\tab
Let $\; r_{n,k} = w_{n,n-k} \;$ for $\; k \leq n \;$ and $\; r_{n,k} = 0 \;$ otherwise.
Then the matrix
$$
 R = [ r_{n,k} ]_{n,k \geq 0} =
 \left[
 \begin{array}{rrrrrrrrr}
    1 &     &     &     &    &    &    &   &   \\
    2 &   1 &     &     &    &    &    &   &   \\
    4 &   2 &   1 &     &    &    &    &   &   \\
    8 &   5 &   2 &   1 &    &    &    &   &   \\
   18 &  11 &   6 &   2 &  1 &    &    &   &   \\
   42 &  26 &  14 &   7 &  2 &  1 &    &   &   \\
  100 &  62 &  35 &  17 &  8 &  2 &  1 &   &   \\
  242 & 150 &  86 &  45 & 20 &  9 &  2 & 1 &   \\
  592 & 367 & 213 & 114 & 56 & 23 & 10 & 2 & 1 \\
  \ldots
 \end{array}
 \right]
$$
is a Riordan matrix \cite{Shapiro,MRSV}. Indeed recurrence (\ref{WRec})
yields the following recurrence for the coefficients $\; r_{n,k} \,$:
\begin{equation}\label{RRec}
 r_{n+2,k+1} = r_{n+1,k} + r_{n+2,k+2} - r_{n+1,k+1} + r_{n,k+1} \, .
\end{equation}
Considering the series $\; r_k( t ) = \sum_{ n \geq k } r_{n,k} \; t^n \,$,
recurrence (\ref{RRec}) becomes
$$
 r_{k+2}( t ) - ( 1 + t - t^2)\, r_{k+1}( t ) + t \; r_k( t ) = 0 \, .
$$
Now suppose there exist two series $\; g( t ) \;$ and $\; f( t ) \;$ such that
$\; r_k( t ) = g( t ) f( t )^k \;$ for all $\; k \in \NN \,$.
Then $\; g( t ) = r_0( t ) = w( t ) \;$ and $\; f( t ) \;$ is defined by the quadratic equation
$$
 f(t)^2 - ( 1 + t - t^2 ) f(t) + t = 0
$$
whose solution is
$$
 f(t) = \frac{ 1 + t - t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 } \, .
$$
Then 
$$
 r_k( t ) = \sqrt{ \frac{ 1 + t + t^2 }{ 1 - 3 t + t^2 } }
 \left( \frac{ 1 + t - t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 } \right)^k \, .
$$
%In particular
%$$
% \sum_{ n \geq 0 } w_{ n + k, k } \; t^n = \sqrt{ \frac{ 1 + t + t^2 }{ 1 - 3 t + t^2 } }
% \left( \frac{ 1 + t - t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 t } \right)^k \, .
%$$
In conclusion, since $\; g_0 = 1 \,$, $\; f_0 = 0 \;$ and $\; f_1 \ne 0 \,$,
$\; R \;$ is the Riordan matrix
$$
 \left( \sqrt{ \frac{ 1 + t + t^2 }{ 1 - 3 t + t^2 } } \, ,
 \frac{ 1 + t - t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 } \right) \, .
$$

The first few coefficients in the expansion of $\; f(t) \;$ are
$$
 f(t) = t + t^3 + t^4 + 2 t^5 + 4 t^6 + 8 t^7 + 17 t^8 + 37 t^9 + 82 t^{10} + \cdots
$$
which suggests (looking at entry A004148, formerly M1141, of \cite{Sloane}) 
that these coefficients are the numbers of (irreducible) \emph{secondary structures} 
in the sense of \cite{SteinWaterman,Stanley2}. 
Indeed, while $\; f(t) \;$ is the generating function for irreducible secondary structures, 
the generating function $\; s(t) \;$ for all secondary structures is simply the iteration of $\; f(t) \,$, i.e.,
$$
 s( t ) = \sum_{ n \geq 0 } s_n \; t^n = \frac{ 1 }{ 1 - f( t ) }
 = \frac{ 1 - t + t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 t^2 }
$$

%Recall that a \emph{secondary structure} 
%is a simple graph on the vertex set $\; \{ 1, 2, \ldots, n \} \;$ such that
%(a) $\; \{ i, i + 1 \} \;$ is an edge for all $\; 1 \leq i \leq n - 1 \,$,
%(b) for all $\; i \;$ there is at most one $\; j \;$ such that $\; \{ i, j \} \;$
%is an edge and $\; | i - j | \ne 1 \,$,
%(c) if $\; \{ i, j \} \;$ and $\; \{ h, k \} \;$ are edges with $\; i < h < j \;$ then $\; i \leq k \leq j \,$.
%A secondary structure is \emph{irreducible} if either $\; n = 1 \;$ or there is an edge from $\; 1 \;$ to $\; n \,$.
%The generating series of the numbers of irreducible secondary structures is the series $\; f(t) \,$, while
%the generating series of the numbers of secondary structures is given by
%$$
% s( t ) = \sum_{ n \geq 0 } s_n \; t^n = \frac{ 1 }{ 1 - f( t ) }
% = \frac{ 1 - t + t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 t^2 }
%$$
%(see \cite{Stanley2}, pp. 241-242, 275-276).

Consider now the row sums $\; r_n = \sum_{ k = 0}^n r_{n,k} \;$ of the matrix $\; R \,$.
The first values of $\; r_n \;$ are 1, 3, 7, 16, 38, 92, 225, 555, 1378, 3439, 8619, 21678, 54687, 
and their generating series is given by
$$
 r(t) = \sum_{ n \geq 0 } r_n \; t^n = \frac{ w( t ) }{ 1 - f( t ) } = w( t ) s( t ) \, .
$$
This implies the convolution identity
$$
 r_n = \sum_{ k = 0 }^n w_k s_{ n - k} \, .
$$

Finally we notice that the matrix $\; R \;$ is completely determined by the recurrences
%(which can be easily derived by (\ref{RRec}))
$$
 \left\{
 \begin{array}{l}
  r_{n+2,k+1} = r_{n+1,k} + r_{n,k+1} + r_{n,k+2} + \cdots + r_{n,n} \\
  r_{n+2,0} = r_{n+1,0} + r_{n,0} + 2 r_{n,1} + \cdots + 2 r_{n,n}
 \end{array} 
 \right.
$$
and by the initial condition $\; r_{0,0} = 1 \,$.

% -----------------------------------------------------------------------------------------------------------
  \section{Lattice paths}
% -----------------------------------------------------------------------------------------------------------

\tab
A \emph{Motzkin path} \cite{AignerTheme} of length $\; n \;$ is
a lattice path in $\; \NN \times \ZZ \;$ 
which starts at $\; (0,0) \;$ and ends at $\; (n,0) \,$,
has steps $\; (1,1) \,$, $\; (1,0) \,$, $\; (1,-1) \;$
and never falls below $\; y = 0 \,$.
A \emph{Catalan}, or \emph{Dyck}, \emph{path}
is a Motzkin path without horizontal steps.
A \emph{central trinomial path} is defined as a Motzkin path
with the possibility to go below $\; y = 0 \,$,
while a \emph{central binomial path} is a central trinomial path without horizontal steps.

Binary strings with $\; m \;$ $1$'s and $\; n \;$ $0$'s
can be interpreted as lattice paths in $\; \NN \times \ZZ \;$
from the origin $\; ( 0, 0 ) \;$ to the point $\; ( m + n, m - n ) \;$
considering $\; 1 \;$ and $\; 0 \;$ as the unitary diagonal steps
$\; ( 1, 1 ) \;$ and $\; ( 1, -1 ) \,$, respectively.
For instance the string $\; \alpha = 110001101100 \;$ corresponds to the path
\begin{center}
\setlength{\unitlength}{1mm}
 \begin{picture}( 70, 30 )(0,-5)
  \put(  0, 5 ){ \vector( 1, 0 ){ 70 } }
  \put(  0, -5 ){ \vector( 0, 1 ){ 30 } }
  \put(  0,  5 ){ \circle*{ 1.5 } }
  \put(  5, 10 ){ \circle*{ 1.5 } }
  \put( 10, 15 ){ \circle*{ 1.5 } }
  \put( 15, 10 ){ \circle*{ 1.5 } }
  \put( 20,  5 ){ \circle*{ 1.5 } }
  \put( 25,  0 ){ \circle*{ 1.5 } }
  \put( 30,  5 ){ \circle*{ 1.5 } }
  \put( 35, 10 ){ \circle*{ 1.5 } }
  \put( 40,  5 ){ \circle*{ 1.5 } }
  \put( 45, 10 ){ \circle*{ 1.5 } }
  \put( 50, 15 ){ \circle*{ 1.5 } }
  \put( 55, 10 ){ \circle*{ 1.5 } }
  \put( 60,  5 ){ \circle*{ 1.5 } }
  \put(  0,  5 ){ \line( 1,  1 ){ 10 } }
  \put( 10, 15 ){ \line( 1, -1 ){ 15 } }
  \put( 25,  0 ){ \line( 1,  1 ){ 10 } }
  \put( 35, 10 ){ \line( 1, -1 ){  5 } }
  \put( 40,  5 ){ \line( 1,  1 ){ 10 } }
  \put( 50, 15 ){ \line( 1, -1 ){ 10 } }
 \end{picture}
\end{center}
This implies that the strings in $\; \WW \;$ can be interpreted as binomial paths without zigzags,
i.e., without a sequence of consecutive steps of the form
\setlength{\unitlength}{1mm}
\begin{picture}( 12, 5 )
 \put(  0, 0 ){ \circle*{ 1 } }
 \put(  4, 4 ){ \circle*{ 1 } }
 \put(  8, 0 ){ \circle*{ 1 } }
 \put( 12, 4 ){ \circle*{ 1 } }
 \put(  0, 0 ){ \line( 1,  1 ){ 4 } }
 \put(  4, 4 ){ \line( 1, -1 ){ 4 } }
 \put(  8, 0 ){ \line( 1,  1 ){ 4 } }
\end{picture}\;\; and
\begin{picture}( 13, 5 )
 \put(  0, 4 ){ \circle*{ 1 } }
 \put(  4, 0 ){ \circle*{ 1 } }
 \put(  8, 4 ){ \circle*{ 1 } }
 \put( 12, 0 ){ \circle*{ 1 } }
 \put(  0, 4 ){ \line( 1, -1 ){ 4 } }
 \put(  4, 0 ){ \line( 1,  1 ){ 4 } }
 \put(  8, 4 ){ \line( 1, -1 ){ 4 } }
\end{picture}\, . 
In particular $\; w_{m,n} \;$ is the number
of all binomial paths without zigzags ending at $\; ( m + n, m - n ) \,$,
and $\; w_n \;$ is the number of all central binomial paths without zigzags ending at $\; ( 2 n, 0 ) \,$.
In the above example $\; \alpha \;$ is central but is not without zigzags.

This interpretation leads to consider the more general problem to enumerate
all Motzkin, Catalan and central trinomial paths without zigzags.

\paragraph{Motzkin paths.}
Let $\; \mathcal{Z}_n \;$ be the set of all Motzkin paths of length $\; n \;$ without zigzags.
To each horizontal step we assign a weight $\; s \,$. 
For any $\; \gamma \in \mathcal{Z}_n \;$ define the weight $\; w(\gamma) \;$
as the product of the weights of all its steps. Then let
$$
 Z_n^{(s)} = \sum_{\gamma \in \mathcal{Z}_n} w(\gamma)
 \qquad \textrm{and} \qquad
 Z^{(s)}(t) = \sum_{n \geq 0} Z_n^{(s)} \; t^n \, .
$$
For $\; s = 1 \;$ we have the Motzkin paths while for $\; s = 0 \;$ we have the Catalan paths.
Any Motzkin path can be uniquely decomposed in the product 
of horizontal steps on the $x$-axis and elevated Motzkin paths,
i.e., paths of the form $\; (1,1)\; \gamma \;(1,-1) \;$ where $\; \gamma \;$ is any Motzkin path.
Such a decomposition holds also for the Motzkin paths without zigzags,
even though clearly not all the possible patterns are allowed.
Let $\; \mathcal{Z}_{hs} \,$, $\; \mathcal{Z}_{hill} \;$ and $\; \mathcal{Z}_{ep} \;$
be the sets of all Motzkin paths without zigzags whose final factor is
a horizonal step, a hill (i.e., $\; (1,1)(1,-1) \,$) or an elevated path respectively.
It is easy to see that
$$
 \left\{
 \begin{array}{l}
  Z^{(s)}(t) = 1 + Z^{(s)}_{hs}(t) + Z^{(s)}_{hill}(t) + Z^{(s)}_{ep}(t) \\
  Z^{(s)}_{hs}(t) = s t Z^{(s)}(t) \\
  Z^{(s)}_{hill}(t) = t^2 + s t^3 Z^{(s)}(t) \\
  Z^{(s)}_{ep}(t) = ( 1 + Z^{(s)}_{hs}(t) + Z^{(s)}_{ep}(t) )\, ( Z^{(s)}(t) - 1 )\; t^2 \, .
 \end{array}
 \right.
$$
Solving this system it is easy to obtain the equation
$$
 (1-st^3) Z^{(s)}(t)^2 - ( 1 - st + t^2 - s t^3 + t^4 - s t^5 ) Z^{(s)}(t) + 1 + t^2 + t^4 = 0 \, .
$$
Then
$$
 Z^{(s)}(t) = \frac{1-st+t^2-st^3+t^4-st^5-\sqrt{\Delta}}{2t^2(1-st^3)} 
$$
where $\; \Delta = 1 - 2s t + (s^2 - 2) t^2 - 4s t^3 + (2s^2 - 1) t^4 - 
2s t^5 + (3 s^2 - 2) t^6 + (2s^2 + 1) t^8 + 2s t^9 + s^2 t^{10} \,$.
Moreover we have the recurrence
$$
 Z_{n+5}^{(s)} = s Z_{n+4}^{(s)} - Z_{n+3}^{(s)} + s Z_{n+2}^{(s)} - Z_{n+1}^{(s)} + s Z_n^{(s)} +
 \sum_{k=0}^{n+3} Z_k^{(s)} Z_{n+3-k}^{(s)} - s \sum_{k=0}^n Z_k^{(s)} Z_{n-k}^{(s)} \, .
$$

This result can be generalized to the case in which 
we assign a weight $\; a \;$ to all horizontal steps on $x$-axis 
and a weight $\; s \;$ to all other horizontal steps.
In this way, for instance, for $\; a = 0 \;$ and $\; s = 1 \;$ 
we have all \emph{Riordan paths} \cite{AignerTheme,AignerCatalanLike,Bernhart} without zigzags 
while for $\; a = 0 \;$ and $\; s = 2 \;$ 
we have all \emph{Fine paths} \cite{AignerTheme,AignerCatalanLike,DeutschShapiro} without zigzags.
In this (generalized) case we have the system
$$
 \left\{
 \begin{array}{l}
  Z^{(a,s)}(t) = 1 + Z^{(a,s)}_{hs}(t) + Z^{(a,s)}_{hill}(t) + Z^{(a,s)}_{ep}(t) \\
  Z^{(a,s)}_{hs}(t) = a t Z^{(a,s)}(t) \\
  Z^{(a,s)}_{hill}(t) = t^2 + a t^3 Z^{(a,s)}(t) \\
  Z^{(a,s)}_{ep}(t) = ( 1 + Z^{(a,s)}_{hs}(t) + Z^{(a,s)}_{ep}(t) )\, ( Z^{(s)}(t) - 1 )\; t^2
 \end{array}
 \right.
$$
which yield the generating function
$$
 Z^{(a,s)}(t) = 
 \frac{1-(2a-s)t+t^2-(2a-s)t^3+t^4-(2a-s)t^5-\sqrt{\Delta}}{s-a+(a^2-as+1)t+(s-a)t^2+a(a-s)t^3-at^4+a(a-s)t^5} \, .
$$

\paragraph{Central trinomial paths.}
To study these paths when they avoid zigzags 
it seems more convenient to consider them as trinomial strings
and use the results obtained on binary strings without zigzags.
Specifically we see a \emph{trinomial path} as a word on the alphabet $\; \{ 0, 1, h \} \,$,
considering $\; 1 \;$ and $\; 0 \;$ as unitary diagonal steps as before
and $\; h \;$ as the unitary horizontal step $\; ( 1, 0 ) \,$.
A zigzag is still one of the strings $\; 101 \;$ or $\; 010 \,$.
Let $\; \UU \;$ be the set of all ternary strings without zigzags.
Since, in terms of regular expressions, $\; \UU = \WW ( h \WW )^* \,$,
we obtain from the morphism $\; \map{\nu}{\{ 0, 1, h \}^*}{\ZZ[\![x,y,z]\!]} \,$, 
defined by $\; \nu( 1 ) = x \,$, $\; \nu( 0 ) = y \;$ and $\; \nu( h ) = z \,$,  
the generating function
$$
 u( x, y, z ) = \sum_{ n \geq 0 } w( x, y )^{n+1} z^n
              = \frac{ w( x, y ) }{ 1 - w( x, y ) z }
$$
that is
$$
 u( x, y, z ) = \frac{ 1 + x y + x^2 y^2 }{ 1 - x - y + xy - x^2 y^2 - ( 1 + x y + x^2 y^2 ) z }
$$
where the coefficient $\; u_{i,j,k} \;$ of $\; x^i y^j z^k \;$ in $\; u( x, y, z ) \;$
is the number of all strings in $\; \UU \;$
with $\; i \;$ $1$'s, $\; j \;$ $0$'s and $\; k \;$ $h$'s.

%any string in $\; \UU \;$ can be uniquely decomposed as
%$\; \alpha_1 h \alpha_2 h \alpha_3 h \cdots h \alpha_n h \alpha_{n+1} \,$,
%where $\; \alpha_1, \ldots, \alpha_{n+1} \in \WW \,$, it follows that
%$$
% \UU = \sum_{ n \geq 0 } \underbrace{\WW\; h\; \WW\; h\; \WW\; h\; \cdots h\; \WW\; h\; \WW}_{\textrm{with}\; n\; h\textrm{'s}} \, .
%$$

We say that a string in $\; \UU \;$ is \emph{central}
when the number of $1$'s is equal to the number of $0$'s.
Hence the central strings in $\; \UU \;$ correspond to trinomial paths without zigzags ending on the $x$-axis.
Let $\; u_n \;$ be the number of such paths ending at $\; ( n, 0 ) \,$.
To obtain the generating function for these numbers we consider first the series
$$
 u( x, y ) = \sum_{ i,j \geq 0 } u_{i,i,j} \; x^i y^j \, .
$$
By Cauchy's integral theorem we have
%\begin{eqnarray*}
% u( x, y )
% & = & \frac{ 1 }{ 2 \pi \ii } \oint u\left( z, \frac{ x }{ z }, y \right) \; \frac{ {\rm d} z }{ z } \\
% & = & \frac{ 1 }{ 2 \pi \ii } \oint \frac{ 1 + x + x^2 }{ - z^2 + ( 1 + x - y - x^2 - x y - x^2 y ) z - x } \; {\rm d} z \, .
%\end{eqnarray*}
$$
 u( x, y ) =  
 \frac{ 1 }{ 2 \pi \ii } \oint u\left( z, \frac{ x }{ z }, y \right) \; \frac{ {\rm d} z }{ z } =  
 \frac{ 1 }{ 2 \pi \ii } \oint \frac{ 1 + x + x^2 }{ - z^2 + ( 1 + x - y - x^2 - x y - x^2 y ) z - x } \; {\rm d} z \, .
$$       
The polynomial at the denominator has roots
$$
 z^\pm = \frac{ 1 + x - y - x^2 - x y - x^2 y \pm
 \sqrt{ ( 1 + x - y - x^2 - x y - x^2 y )^2 - 4 x } }{ 2 }
$$
of which only $\; z^- \to 0 \;$ as $\; x \to 0 \,$.
Hence, by the residue theorem, we have
$$
 u( x, y ) = \lim_{ z \to z^- } \frac{ 1 + x + x^2 }{ - ( z - z^+ ) }
           = \frac{ 1 + x + x^2 }{ z^+ - z^- }
$$
that is
$$
 u( x, y ) = \frac{ 1 + x + x^2 }{ \sqrt{ ( 1 + x - y - x^2 - x y - x^2 y )^2 - 4 x } } \, .
$$
Then the generating function for the numbers $\; u_n \;$
is given by $\; u( t ) = u( t^2, t ) \,$, that is
$$
 u( t ) = \sqrt{ \frac{ 1 - t + t^2 }{ ( 1 - t )( 1 - 2 t - 2 t^2 - t^3 ) } }
        = \sqrt{ \frac{ 1 - t + t^2 }{ 1 - 3 t + t^3 + t^4 } } \, .
$$
Taking the logarithmic derivative of this series we obtain the identity
$$
 ( 1 - 4 t + 4 t^2 - 2 t^3 + t^6 )\; u'( t ) = ( 1 + t - 3 t^2 - t^3 + t^4 - t^5 )\; u( t )
$$
which yields the recurrence
$$
 ( n + 6 )\, u_{n+6} - ( 4 n + 21 )\, u_{n+5} 
 + ( 4 n + 15 )\, u_{n+4} - ( 2 n + 3 )\, u_{n+3} + u_{n+2} - u_{n+1} + ( n + 1 )\, u_n = 0 \, .
$$
The first few values of $\; u_n \;$ are 1, 1, 3, 7, 17, 43, 111, 291, 771, 2059, 5533, 14943, 40523
(sequence \#A078079 in \cite{Sloane}).

We can treat the case in which each horizontal step has weight $\; s \;$ in the same way.
We have only to define $\; \nu( h ) = s z \,$. In particular 
$$
 u^{(s)}( t ) = \sqrt{ \frac{1 + t^2 + t^4}{ 1 - 2st + (s^2-3)t^2 - 2st^3 + (s^2+1)t^4 + 2st^5 + s^2t^6 } } \, .
$$

% -----------------------------------------------------------------------------------------------------------
  \section{Asymptotics}
% -----------------------------------------------------------------------------------------------------------

\tab
In this final section we give the first-order asymptotic formulas for $\; w_n \,$ and $\; u_n \,$.
To obtain such a formula we use the following theorem (\cite{BergeronLabelleLeroux}, p. 252):
given a complex number $\; \xi \ne 0 \;$ and
a complex function $\; f( t ) \;$ analytic at the origin,
if $\; f( t ) = ( 1 - t / \xi )^{ - \alpha } \psi( t ) \;$
where $\; \psi( t ) \;$ is a series with radius of convergence $\; R > | \xi | \;$
and $\; \alpha \not \in \{ 0, -1, -2, \ldots \} \,$, then
$$
 [t^n]f(t) \sim \frac{ \psi( \xi ) }{ \xi^n }\, \frac{ n^{ \alpha - 1 } }{ \Gamma( \alpha ) } 
$$
where $\; \Gamma \;$ is Euler's gamma function.
For the series $\; w(t) \;$ we have
$$
 w( t ) = \left( 1 - \frac{ t }{ \xi } \right)^{\hspace{-1mm}-\alpha} \sqrt{ \frac{ 1 + t + t^2 }{ 1 - \xi t } }
$$
with $\; \xi = ( 3 - \sqrt{5} )/2 \;$ and $\; \alpha = 1/2 \,$.
Hence, since $\; \Gamma(1/2) = \sqrt{\pi} \,$, it follows that
$$
 w_n \sim  \frac{ 2 }{ \sqrt{n \pi \sqrt{5} } } \left( \frac{ 3 + \sqrt{5} }{ 2 } \right)^{\hspace{-1.2mm}n} 
     =     \frac{ 2\; \varphi^{2n} }{ \sqrt{n \pi \sqrt{5} } } 
$$
where $\; \varphi = ( 1 + \sqrt{5} ) / 2 \;$ is the golden ratio.
In particular
$$
 \lim_{ n \to \infty } \frac{ w_{n+1} }{ w_n } = \frac{ 3 + \sqrt{5} }{ 2 } = \varphi^2 \, .
$$
It could be interesting to explain combinatorially the appearance of $\; \varphi \;$.  

Since for the numbers of the secondary structures we have the asymptotic formula \cite{SteinWaterman}
$$
 s_n \sim \sqrt{ \frac{ 15 + 7 \sqrt{5} }{ 8 \pi } }
          \left( \frac{ 3 + \sqrt{5}}{ 2 } \right)^n \frac{ 1 }{ n^{3/2} }
$$
it follows that
$$
 \lim_{ n \to + \infty } \frac{ n s_n }{ w_n } = \frac{ 5 + 3 \sqrt{5} }{ 8 } \, .
$$

%Similarly the generating series $\; F(t) \;$ of the numbers $\; f_{2n,n} \;$ can be written as
%$$
% F( t ) = \left( 1 - \frac{ t }{ \xi } \right)^{\hspace{-1mm}-\alpha} \frac{ 1 }{ \sqrt{ ( 1 + t + t^2 ) ( 1 - \xi t ) } }
%$$
%with $\; \xi = ( 3 - \sqrt{5} )/2 \;$ and $\; \alpha = 1/2 \,$, as before. Hence it follows that
%\begin{equation}
% f_{2n,n} \sim \frac{ 1 }{ 2 \sqrt{ n \pi \sqrt{5} } }
% \left( \frac{ 3 + \sqrt{5} }{ 2 } \right)^{\hspace{-1.2mm}n+1} \, .
%\end{equation}
%In particular
%$$
% \lim_{ n \to \infty } \frac{ f_{2n,n} }{ w_n } = \frac{ 3 + \sqrt{5} }{ 8 } \, .
%$$

Finally, the series $\; u(t) \;$ can be written as
$$
 u(t) = \left( 1 - \frac{t}{\xi} \right)^{\hspace{-1mm}-1/2}
 \sqrt{ \frac{ 1 - t + t^2 }{ ( 1 - t ) ( 1 - t/\xi_1 ) ( 1 - t/\xi_2 ) } }
$$
where
$$
 \xi = \frac{1}{6} \sqrt[3]{ 188 + 12 \sqrt{249}} -
       \frac{4}{3} \frac{1}{ \sqrt[3]{ 188 + 12 \sqrt{249}} } - \frac{2}{3}
       \simeq 0.353 \, .
$$
Then $\; u_n \sim a b^n / \sqrt{ n \pi } \,$,
where $\; a = \psi( \xi ) \simeq 0.944 \;$ and $\; b = 1/\xi \simeq 2.831 \,$.

\bigskip

{\bf Acknowledgments.}
The authors are grateful to Volker Strehl and Douglas Rogers for some useful suggestions.

% -----------------------------------------------------------------------------------------------------------
\begin{thebibliography}{99}
 \bibitem{AignerCatalanLike}
  M. Aigner,
  Catalan-like Numbers and Determinants,
  \textit{J. Combin. Theory} Ser. A {\bf 87} (1999), 33--51.
 \bibitem{AignerTheme}
  M. Aigner,
  Catalan and other numbers: a recurrent theme,
  in \textit{Algebraic Combinatorics and Computer Science}, 347--390, Springer Italia, Milan, 2001.
 \bibitem{BergeronLabelleLeroux}
  F. Bergeron, G. Labelle, P. Leroux,
  \textit{Combinatorial Species and Tree-like Structures},
  Encyclopedia of Mathematics and Its Applications {\bf 67},
  Cambridge University Press, Cambridge, 1998.
 \bibitem{Bernhart}
  F.R. Bernhart,
  Catalan, Motzkin, and Riordan numbers,
  \textit{Discrete Math.} {\bf 204} (1999), 73--112  
 \bibitem{Comtet}
  L. Comtet,
  \textit{Advanced Combinatorics},
  Reidel, Dordrecht-Holland, Boston, 1974.
 \bibitem{Deutsch}
  E. Deutsch,
  Dyck path enumeration,
  \textit{Discrete Math.} {\bf 204} (1999), 167--202.
 \bibitem{DeutschShapiro}
  E. Deutsch, L. Shapiro,
  A survey of the Fine numbers,
  \textit{Discrete Math.} {\bf 241} (2001), 241--265.  
 \bibitem{GesselViennot}
  I.M. Gessel, X. Viennot,
  Binomial determinants, paths, and hook length formulae,
  \textit{Advances in Mathematics} {\bf 58} (1985), 300–-321.  
 \bibitem{Knuth}
  R.L. Graham, D.E. Knuth, O. Patashnik,
  \textit{Concrete Mathematics},
  Addison-Wesley, Reading, MA, 1989.
 \bibitem{GuibasOdlyzko}
  L.J. Guibas, A.M. Odlyzko, 
  String Overlappings, Pattern Matching, and Nontransitive Games,
  \textit{J. of Combin. Theory} A \textbf{30} (1981), 183--208.  
 \bibitem{HautusKlarner}
  M.L.J. Hautus, D.A. Klarner,
  The Diagonal of a Double Power Series,
  \textit{Duke Math. J.} {\bf 38} (1971), 229--235.
 \bibitem{MRSV}
  D. Merlini, D. Rogers, R. Sprugnoli, M.C. Verri, 
  On some alternative characterizations of Riordan arrays,
  \textit{Canad. J. Math.} \textbf{49} (1997), 301--320.
 \bibitem{MunaZaga}
  E. Munarini, N. Zagaglia Salvi,
  On the rank polynomial of the lattice of order ideals of fences and crowns,
  \textit{Discrete Math.} \textbf{259} (2002), 163--177.
 \bibitem{CircularWu}
  E. Munarini, N. Zagaglia Salvi,
  Circular binary strings without zigzags,
  \textit{Integers} \textbf{3} (2003), A19, 17 pages (electronic).
 \bibitem{Odlyzko}
  A.M. Odlyzko,
  Enumeration of strings,
  in \textit{Combinatorial Algorithms on Words}, A. Apostolico and Z. Galil (eds.), Springer 1985, 205--228 .  
 \bibitem{Shapiro}
  L.W. Shapiro, S. Getu, W. J. Woan, L. C. Woodson,
  The Riordan group,
  \textit{Discrete Appl. Math.} \textbf{34} (1991), 229--239.
 \bibitem{Sloane}
  N.J.A. Sloane,
  \textit{On-Line Encyclopedia of Integer Sequences},
  published electronically at \texttt{http://www.research.att.com/{\~\null}njas/sequences/}.  
 \bibitem{Stanley1}
  R.P. Stanley,
  \textit{Enumerative Combinatorics},
  Volume 1, Cambridge Studies in Advanced Mathematics \textbf{49},
  Cambridge University Press, Cambridge, 1997.
 \bibitem{Stanley2}
  R.P. Stanley,
  \textit{Enumerative Combinatorics},
  Volume 2, Cambridge Studies in Advanced Mathematics \textbf{62},
  Cambridge University Press, Cambridge, 1999.
 \bibitem{SteinWaterman}
  P.R. Stein, M.S. Waterman,
  On some new sequences generalizing the Catalan and Motzkin numbers,
  \textit{Discrete Math.} \textbf{26} (1979), 261--272.
 \bibitem{DaiDhawanWuWu}
  F. Dai, M. Dhawan, C. Wu, J. Wu, 
  On Solutions to a Seating Problem.
  \textit{2002 ISCA International Conference on Parallel and Distributed Computing Systems}, 2002. 
\end{thebibliography}
% -----------------------------------------------------------------------------------------------------------

\bigskip
\bigskip

\footnotesize
\noindent\textbf{Emanuele Munarini} (munarini@mate.polimi.it),
Dipartimento di Matematica, Politecnico di Milano, P.zza Leonardo da Vinci 32, 20133 Milano, Italy.

\medskip

\noindent\textbf{Norma Zagaglia Salvi} (norzag@mate.polimi.it),
Dipartimento di Matematica, Politecnico di Milano, P.zza Leonardo da Vinci 32, 20133 Milano, Italy.

% ----------------------------------------------------------------------------
  \end{document}
% ---------------------------------------------------------------------------- 
