% ---------------------------------------------------------------------------- \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} % ----------------------------------------------------------------------------