% ---------------------------------------------------------------------------- \documentclass[12pt]{article} % ---------------------------------------------------------------------------- \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amsfonts} \usepackage{amsmath} \usepackage{amssymb} \newcommand{\ii}{ {\rm i} } % ---------------------------------------------- i \newcommand{\ff}{ \varphi } % ---------------------------------------------- phi \newcommand{\NN}{ \mathbb{N} } % -------------------------------- Natural Numbers \newcommand{\ZZ}{ \mathcal{Z} } % ------------------ Circular binary words without zigzags \newcommand{\LL}{ \mathcal{L} } % ----------------------- Logarithmic species \newcommand{\GG}{ \mathcal{G} } % ----------------------- Geometric species \newcommand{\XX}{ \mathcal{X} } % ----------------------- Singleton species \newcommand{\Card}{ \mathbf{Card} } % ----------------------- Cardinality \newcommand{\mchoose}[2]{ { \left(\!\!\!\left( { #1 \atop #2 } \right)\!\!\!\right) } } \newcommand{\Mchoose}[2]{ { \left(\!\!\left( { #1 \atop #2 } \right)\!\!\right) } } \renewcommand{\mod}{ {\; {\rm mod}\; } } %\newcommand{\eproof}{ \hspace*{ \fill } $ \Box $ \vspace*{ 0.3cm } } %\newenvironment{proof}{ {\em Proof}. }{ \eproof } %\newenvironment{examples}{ {\bf Examples} }{ } % ---------------------------------------------------------------------------- \begin{document} % ---------------------------------------------------------------------------- \begin{center} {\bf CIRCULAR BINARY STRINGS WITHOUT ZIGZAGS} \vskip 20pt {\bf Emanuele Munarini}\\ {\smallit Dipartimento di Matematica, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy}\\ {\tt munarini@mate.polimi.it}\\ \vskip 10pt {\bf Norma Zagaglia Salvi}\\ {\smallit Dipartimento di Matematica, Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy}\\ {\tt norzag@mate.polimi.it}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 4/11/03, Revised: 11/20/03, Accepted: 12/9/03, Published: 12/11/03 } \vskip 40pt \centerline{\bf Abstract} \noindent We study several enumerative properties of the set of all circular binary strings without zigzags and of the set of all $(0,1)$-necklaces without zigzags, where a zigzag is a $1$ followed and preceded by a $0$ or a $0$ followed and preceded by a $1$. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#A19\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt % {\em AMS Classification}: % 05A15, % exact enumeration problems, generating functions % 05A05, % combinatorial choice problems (subsets, representatives, permutations) % 05A10, % factorials, binomial coefficients, combinatorial functions % \vspace{3mm} % {\em Keywords}: % {\footnotesize % Circular binary strings, % Circular binary words, % necklaces, % zigzags, % species, % cyclic species, % types. } % ---------------------------------------------------------------------------- \section*{\normalsize 1. Introduction} % ---------------------------------------------------------------------------- A \emph{circular binary string} is a function defined on a cycle with values in $\; \{ 0, 1 \} \,$. As usual we write a circular binary string as a linear string with the convention that the first and the last letter are adjacent. A \emph{$(0,1)$-necklace} is a circular binary string defined up to cyclic shifts. Hence a $(0,1)$-necklace is an equivalence class of circular binary strings. However, for simplicity, we write circular binary strings and necklaces in the same way. For instance $\; 001 \,$, $\; 010 \;$ and $\; 100 \;$ are different circular binary strings but represent the same necklace. We say that a circular binary string has a \emph{zigzag} when a $1$ is followed and preceded by a $0$ or, dually, when a $0$ is followed and preceded by a $1$. Recall that a linear string $\; \sigma \;$ is a substring of a circular string $\; \alpha \;$ when there exist two linear strings $\; \alpha_1 \;$ and $\; \alpha_2 \;$ such that $\; \alpha = \alpha_1 \sigma \alpha_2 \;$ or when $\; \sigma = \sigma_1 \sigma_2 \;$ and there exists a linear string $\; \beta \;$ such that $\; \alpha = \sigma_2 \beta \sigma_1 \,$. For instance the substrings of length $3$ of the circular string $\; \alpha = 1011 \;$ are $\; 101 \,$, $\; 011 \,$,$\; 111 \;$ and $\; 110 \,$. For linear strings a zigzag is equivalent to a substring equal to $\; 010 \;$ or $\; 101 \,$. This is still true for circular binary strings of length $\; n \ne 2 \,$, but when $\; n = 2 \;$ also the circular strings $\; 10 \;$ and $\; 01 \;$ have a zigzag. The aim of this paper is to obtain enumerative properties for the circular binary strings without zigzags and for the $(0,1)$-necklaces without zigzags. Specifically we obtain the recurrences, the generating series and several explicit formulas for the numbers $\; z_{m,n} \;$ of all circular binary strings without zigzags with $\; m \;$ $1$'s and $\; n \;$ $0$'s and in particular for the numbers $\; z_n = z_{n,n} \;$ of central strings. In particular for the numbers $\; z_n \;$ we also give a first-order asymptotic formula. Then we consider the infinite matrix $\; Z = [ z_{i,j} ]_{i,j\geq 0} \;$ and we prove that it can be decomposed as $\; L T L^t \;$ where $\; L \;$ is a lower triangular matrix and $\; T \;$ is a tridiagonal matrix. Both such matrices have non-negative integer entries. Moreover we show that the lower triangular matrix $\; R = [ r_{i,j} ]_{i,j \geq 0} \,$, where $\; r_{i,j} = z_{i,i-j} \;$ for $\; i \geq j \,$, $\; i \ne 0 \,$, $\; r_{0,0} = 1 \;$ and $\; r_{i,j} = 0 \;$ otherwise, is a Riordan matrix \cite{Shapiro}. Finally we consider the cyclic species of all circular binary strings without zigzags and we prove that it can be decomposed as a suitable composition of species. Such a decomposition passes to types allowing to obtain an explicit formula for the numbers $\; \widetilde{z}_{m,n} \;$ of all $(0,1)$-necklaces without zigzags with $\; m \;$ $1$'s and $\; n \;$ $0$'s. In \cite{MunaZagaWuW} we studied the same problem for linear binary strings. Both the problems, for linear and circular strings, were posed by Jie Wu in the particular case in which the number of $1$'s is equal to the number of $0$'s. See \cite{DaiDhawanWuWu} for an algorithmic approach to this particular case for linear strings. % ---------------------------------------------------------------------------- \section*{\normalsize 2. Explicit formulas and generating functions} % ---------------------------------------------------------------------------- Let $\; \ZZ \;$ be the set of all circular binary strings without zigzags. Then let $\; \ZZ_{m,n} \;$ be the set of all strings in $\; \ZZ \;$ with $\; m \;$ $1$'s and $\; n \;$ $0$'s and let $\; z_{m,n} = | \ZZ_{m,n} | \,$. The conjugate string $\; \overline{\alpha} \;$ of a binary string $\; \alpha \;$ is the string obtained by interchanging $\; 0 \;$ and $\; 1 \;$ in $\; \alpha \,$. For instance, if $\; \alpha = 100110 \;$ then $\; \overline{\alpha} = 011001 \,$. Clearly conjugation establishes a bijection between $\; \ZZ_{m,n} \;$ and $\; \ZZ_{n,m} \;$ which implies the symmetry $\; z_{m,n} = z_{n,m} \,$. \paragraph{First formula.} Here we give a canonical decomposition for the strings in $\; \ZZ_{m,n} \;$ similar to the one used in \cite{MunaZagaWuW} for linear strings. Let $\; \alpha \;$ be any string in $\; \ZZ_{m,n} \,$. Since $\; \alpha \;$ has no zigzags, each maximal block of $1$'s and $0$'s has length at least two, except possibly for the first and the last maximal block. This implies that $\; \alpha \;$ can be uniquely decomposed as a product of strings of the form $\; 01 \,$, $\; 10 \,$, $\; 0 \cdots 0 \,$, $\; 1 \cdots 1 \;$ in one of the following way $$ ( 1 \cdots 1 ) (10) ( 0 \cdots 0 ) (01) ( 1 \cdots 1 ) \cdots $$ $$ ( 0 \cdots 0 ) (01) ( 1 \cdots 1 ) (10) ( 0 \cdots 0 ) \cdots $$ where any block $\; 01 \;$ is followed by a block $\; 1 \cdots 1 \;$ and is preceded by a block $\; 0 \cdots 0 \,$, and dually any block $\; 10 \;$ is followed by a block $\; 0 \cdots 0 \;$ and is preceded by a block $\; 1 \cdots 1 \,$. For instance, the string $\; \alpha = 000011110001100 \;$ decomposes as $\; \alpha = (000)(01)(11)(10)(0)(01)(10)(0) \,$. We say that $\; 01 \;$ and $\; 10 \;$ are the \emph{principal blocks}. The non principal blocks can also be empty. To enumerate all the stings in $\; \ZZ_{m,n} \;$ we have to consider two cases, according to the parity of the number of principal blocks. Suppose first there are $\; 2 k \;$ (with $\; k \geq 1 \,$) principal blocks. Then to obtain all the strings $\; \alpha \;$ of the form $$ \framebox{$ 0 \cdots 0 $} \; \framebox{01} \; \framebox{$ 1 \cdots 1 $} \; \framebox{10} \; \framebox{$ 0 \cdots 0 $} \; \cdots \; \framebox{01} \; \framebox{$ 1 \cdots 1 $} \; \framebox{10} \; \framebox{$ 0 \cdots 0 $} $$ we fix the principal blocks and then we distribute $\; m - 2 k \;$ $1$'s in $\; k \;$ places and $\; n - 2 k \;$ $0$'s in $\; k + 1 \;$ places. Hence the total number of the strings of this form is \begin{equation} \mchoose{ k }{ m - 2 k } \mchoose{ k + 1 }{ n - 2 k } \, . \end{equation} Similarly, the total number of the strings $\; \alpha \;$ of the form $$ \framebox{$ 1 \cdots 1 $} \; \framebox{10} \; \framebox{$ 0 \cdots 0 $} \; \framebox{01} \; \framebox{$ 1 \cdots 1 $} \; \cdots \; \framebox{10} \; \framebox{$ 0 \cdots 0 $} \; \framebox{01} \; \framebox{$ 1 \cdots 1 $} $$ turns out to be \begin{equation} \mchoose{ k + 1 }{ m - 2 k } \mchoose{ k }{ n - 2 k } \, . \end{equation} Suppose now that $\; \alpha \;$ contains $\; 2 k + 1 \;$ principal blocks. Then $\; \alpha \;$ has one of the following forms: $$ \framebox{$ 0 \cdots 0 $} \; \framebox{0} \; \framebox{01} \; \framebox{$ 1 \cdots 1 $} \; \framebox{10} \; \framebox{$ 0 \cdots 0 $} \; \cdots \; \framebox{01} \; \framebox{1} \; \framebox{$ 1 \cdots 1 $} $$ $$ \framebox{$ 1 \cdots 1 $} \; \framebox{1} \; \framebox{10} \; \framebox{$ 0 \cdots 0 $} \; \framebox{01} \; \framebox{$ 1 \cdots 1 $} \; \cdots \; \framebox{10} \; \framebox{0} \; \framebox{$ 0 \cdots 0 $} $$ In both cases we have $\; m - 2 k - 2 \;$ $1$'s to distribute in $\; k + 1 \;$ places and $\; n - 2 k - 2 \;$ 0's to distribute in $\; k + 1 \;$ places. Then the total number of the strings of this second case is equal to \begin{equation} 2 \mchoose{ k + 1 }{ m - 2 k - 2 } \mchoose{ k + 1 }{ n - 2 k - 2 } \, . \end{equation} All this implies the identity \begin{eqnarray} \label{EF1} z_{m,n} & = & \sum_{ k \geq 1 } \mchoose{ k }{ m - 2 k } \mchoose{ k + 1 }{ n - 2 k } + \sum_{ k \geq 1 } \mchoose{ k + 1 }{ m - 2 k } \mchoose{ k }{ n - 2 k } + \nonumber \\ & + & 2 \sum_{ k \geq 0 } \mchoose{ k + 1 }{ m - 2 k - 2 } \mchoose{ k + 1 }{ n - 2 k - 2 } \, . \end{eqnarray} \paragraph{Generating series.} To obtain the generating series for the numbers $\; z_{m,n} \;$ we use the Sch\"utzenberger symbolic method \cite{Schutzenberger,FlajoletSedgewick}. The above analysis also implies that the set $\; \ZZ \,$, considered as a language, is given by \begin{align*} & Z = 0^+ + 1^+ + \\ & + \sum_{ k \geq 1 } \underbrace{0^* (01) 1^* (10) \cdots (01) 1^* (10) 0^*}_{2k \;\; \textrm{principal blocks}} + \sum_{ k \geq 1 } \underbrace{1^* (10) 0^* (01) \cdots (10) 0^* (01) 1^*}_{2k \;\; \textrm{principal blocks}} + \\ & + \sum_{ k \geq 0 } \underbrace{0^* (0)(01) 1^* (10) \cdots (10) 0^* (01)(1) 1^*}_{2k+1 \;\; \textrm{principal blocks}} + \sum_{ k \geq 0 } \underbrace{1^* (1)(10) 0^* (01) \cdots (01) 1^* (10)(0) 0^*}_{2k+1 \;\; \textrm{principal blocks}} \end{align*} where $\; 0^* = \{ \varepsilon, 0, 00, 000, \ldots \} \,$, $\; 0^+ = 0^* \setminus \{ \varepsilon \} \,$, etc. Substituting $\; 1 \;$ and $\; 0 \;$ with the indeterminates $\; x \;$ and $\; y \;$ respectively, the above identity yields the following geometric series \begin{eqnarray*} Z(x,y) & = & \sum_{ m, n \geq 0 } z_{m,n} \; x^m y^n \\ & = & \frac{x}{1-x} + \frac{y}{1-y} + \sum_{ k \geq 1 } \frac{x^{2k}}{(1-x)^k} \frac{y^{2k}}{(1-y)^{k+1}} + \\ & & + \sum_{ k \geq 1 } \frac{x^{2k}}{(1-x)^{k+1}} \frac{y^{2k}}{(1-y)^k} + 2 \sum_{ k \geq 0 } \frac{x^{2k+2}}{(1-x)^{k+1}} \frac{y^{2k+2}}{(1-y)^{k+1}} \end{eqnarray*} which turns out to be equal to \begin{equation}\label{ZGeoSeries} Z(x,y) = \frac{x+y-2xy+4x^2y^2}{1-x-y+xy-x^2y^2} \, . \end{equation} The form of this series immediately implies the recurrence \begin{equation}\label{zRec} z_{m+2,n+2} = z_{m+1,n+2} + z_{m+2,n+1} - z_{m+1,n+1} + z_{m,n} + 4 \delta_{m,0} \delta_{n,0} \end{equation} where $\; \delta_{n,k} \;$ is the usual Kronecker delta. \begin{figure} $$ \begin{array}{|c|ccccccccccc|} \hline z_{m,n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 1 & 0 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 4 & 1 & 0 & 6 & 7 & 12 & 18 & 25 & 33 & 42 & 52 & 63 \\ 5 & 1 & 0 & 7 & 8 & 18 & 30 & 44 & 60 & 78 & 98 & 120 \\ 6 & 1 & 0 & 8 & 9 & 25 & 44 & 70 & 104 & 147 & 200 & 264 \\ 7 & 1 & 0 & 9 & 10 & 33 & 60 & 104 & 168 & 255 & 368 & 510 \\ 8 & 1 & 0 & 10 & 11 & 42 & 78 & 147 & 255 & 412 & 629 & 918 \\ 9 & 1 & 0 & 11 & 12 & 52 & 98 & 200 & 368 & 629 & 1014 & 1558 \\ 10 & 1 & 0 & 12 & 13 & 63 & 120 & 264 & 510 & 918 & 1558 & 2514 \\ \hline \end{array} $$ \caption{Numbers of circular binary strings without zigzags.} \end{figure} \paragraph{Second formula.} The formal series (\ref{ZGeoSeries}) yields another expression for the coefficients $\; z_{m,n} \,$. First notice that it can be rewritten as $$ Z(x,y) = -1 + \frac{1+xy+x^2y^2}{1-x-y+xy-x^2y^2} - 2 \frac{xy-x^2y^2}{1-x-y+xy-x^2y^2} \, . $$ Since we have \begin{eqnarray*} \lefteqn{ \frac{1+xy+x^2y^2}{1-x-y+xy-x^2y^2} = \frac{1}{(1-x)(1-y)} \frac{1+xy+x^2y^2}{\displaystyle 1-\frac{x^2}{1-x}\frac{y^2}{1-y}} = } \\ & = & \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}} \\ & = & \sum_{ m, n \geq 0 } \left[ \sum_{ k \geq 0 } { m - k + 2 \lfloor k/3 \rfloor \choose \lfloor k/3 \rfloor } { n - k + 2 \lfloor k/3 \rfloor \choose \lfloor k/3 \rfloor } \right] x^m y^n \end{eqnarray*} and \begin{eqnarray*} \lefteqn{ \frac{ x y -x^2y^2}{1-x-y+xy-x^2y^2} = \frac{1}{(1-x)(1-y)} \frac{xy-x^2y^2}{\displaystyle 1-\frac{x^2}{1-x}\frac{y^2}{1-y}} = } \\ & = & \sum_{ k \geq 0 } (-1)^k \frac{x^{k+1}}{(1-x)^{\lfloor k/2 \rfloor +1}} \frac{y^{k+1}}{(1-y)^{\lfloor k/2 \rfloor +1}} \\ & = & \sum_{ m, n \geq 0 } \left[ \sum_{ k \geq 0 } { m - \lceil k/2 \rceil - 1 \choose \lfloor k/2 \rfloor } { n - \lceil k/2 \rceil - 1 \choose \lfloor k/2 \rfloor } (-1)^k \right] x^m y^n \, , \end{eqnarray*} then, for $\; m,n \ne 0 \,$, we have the identity \begin{eqnarray} \label{EF2} \lefteqn{ z_{m,n} = \sum_{ k \geq 0 } { m - k + 2 \lfloor k/3 \rfloor \choose \lfloor k/3 \rfloor } { n - k + 2 \lfloor k/3 \rfloor \choose \lfloor k/3 \rfloor } + } && \nonumber \\ && - 2 \sum_{ k \geq 0 } { m - \lceil k/2 \rceil - 1 \choose \lfloor k/2 \rfloor } { n - \lceil k/2 \rceil - 1 \choose \lfloor k/2 \rfloor } (-1)^k \, . \end{eqnarray} \paragraph{Total number of circular binary strings without zigzags.} Let $\; s_n \;$ be the total number of all circular binary strings without zigzags of length $\; n \,$. Then the generating series $\; S(t) = \sum_{ n \geq 0 } s_n\; t^n \;$ of these numbers is given by \begin{equation} \label{SGeoSeries} S(t) = Z(t,t) = \frac{2t-2t^2+4t^4}{1-2t+t^2-t^4} = \frac{ 2 t ( 1 - t + 2 t^3 ) }{ ( 1 - t - t^2 ) ( 1 - t + t^2 ) } \, . \end{equation} Since $\; (1-2t+t^2-t^4) S(t) = 2t-2t^2+4t^4 \,$, we have the linear recurrence \begin{equation} s_{n+4} = 2 s_{n+3} - s_{n+2} + s_n + 4 \delta_{n,0} \, . \end{equation} The first few terms of this sequence are: 0, 2, 2, 2, 6, 12, 20, 30, 46, 74, 122, 200, 324, 522, 842, 1362, 2206, 3572, 5780, 9350, 15126, 24474. Moreover, since series (\ref{SGeoSeries}) can be written as $$ S(t) = \frac{ 2 - t }{ 1 - t - t^2 } + \frac{ 2 - t }{ 1 - t + t^2 } - 4 = \sum_{ n \geq 0 } L_n \; t^n + \sum_{ n \geq 0 } H_n \; t^n - 4 \, , $$ we have that $\; s_n = L_n + H_n - 4 \delta_{n,0} \;$ where the $\; L_n $'s are Lucas numbers and the $\; H_n $'s are the numbers defined by the recurrence $\; H_{n+2} = H_{n+1} - H_n \;$ with the initial values $\; H_0 = 2 \;$ and $\; H_1 = 1 \,$. It is easy to see that the sequence $\; \{ H_n \}_n \;$ is periodic with period $\; 2, 1, -1, -2, -1, 1 \,$. % ----------------------------------------------------------------------------------------------------------- \section*{\normalsize 3. Central strings} % ----------------------------------------------------------------------------------------------------------- We say that a circular binary string is \emph{central} when the number of $1$'s is equal to the number of $0$'s. Let $\; z_n \;$ be the number of all central circular binary strings without zigzags, with length $\; 2 n \,$. The first few values of $\; z_n \;$ are: 0, 2, 4, 6, 12, 30, 70, 168, 412, 1014, 2514, 6270, 15702, 39468, 99516, 251586, 637500. Identities (\ref{EF1}), (\ref{EF2}), (\ref{EF4}) immediately imply that \begin{eqnarray} z_n = 2 \sum_{ k \geq 1 } \mchoose{ k }{ n - 2 k } \mchoose{ k + 1 }{ n - 2 k } + 2 \sum_{ k \geq 0 } \mchoose{ k + 1 }{ n - 2 k - 2 }^2 \end{eqnarray} \begin{equation} z_n = \sum_{ k \geq 0 } { n - k + 2 \lfloor k/3 \rfloor \choose \lfloor k/3 \rfloor }^2 - 2 \sum_{ k \geq 0 } { n - \lceil k/2 \rceil - 1 \choose \lfloor k/2 \rfloor }^2 (-1)^k \end{equation} \begin{equation} z_n = \sum_{ k \geq 0 } { n - k - 2 \choose k }^2 \frac{2n}{k+1} \, . \end{equation} Now we will find the geometric series, a recurrence and a first-order asymptotic formula for the numbers $\; z_n \,$. The geometric series of the numbers $\; z_n \;$ is the diagonal series of (\ref{ZGeoSeries}) and, by Cauchy's integral theorem, is given by \cite{Comtet,HautusKlarner,Stanley2,GreeneKnuth} \begin{eqnarray*} z( t ) & = & \sum_{ n \geq 0 } z_n \; t^n = \frac{ 1 }{ 2 \pi \ii } \oint Z\left( z, \frac{ t }{ z } \right) \; \frac{ {\rm d} z }{ z } \\ & = & \frac{ 1 }{ 2 \pi \ii } \oint \frac{ z^2 - ( 2 t - 4 t^2 ) z + t }{ - z ( z^2 - ( 1 + t - t^2 ) z + t ) } {\rm d} z \\ \end{eqnarray*} 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 } $$ of which only $\; z^- \to 0 \;$ as $\; t \to 0 \,$. Hence $\; z=0 \;$ and $\; z=z^- \;$ are the only poles (of first order) which tend to zero as $\; t \to 0 \,$. By the residue theorem, we have $$ z( t ) = \lim_{ z \to 0 } \frac{ z^2 - ( 2 t - 4 t^2 ) z + t }{ - ( z^2 - ( 1 + t - t^2 ) z + t ) } + \lim_{ z \to z^- } \frac{ z^2 - ( 2 t - 4 t^2 ) z + t }{ - z ( z - z^+ ) } $$ that is \begin{equation} \label{ZCentralSeries} z( t ) = \frac{ 1 - t + 3 t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } } \, . \end{equation} Now to obtain a recurrence for the numbers $\; z_n \;$ we rewrite identity (\ref{ZCentralSeries}) as $$ \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } = \frac{(1-2t-t^2-2t^3+t^4)(z(t)+1)}{1-t+3t^2} \, . $$ Then, differentiating such an identity, we obtain the identity \begin{eqnarray*} \lefteqn{ ( 1 - 3 t + 4 t^2 - 7 t^3 - 7 t^5 + 3 t^6 ) z'(t) + } \\ && - ( 8 t - 6 t^2 - 6 t^3 - 2 t^4 ) z(t) - 8 t + 6 t^2 + 6 t^3 + 2 t^4 = 0 \end{eqnarray*} which implies the linear recurrence \begin{eqnarray} \lefteqn{ ( n + 6 ) z_{n+6} - 3 ( n + 5 ) z_{n+5} + 4 ( n + 2 ) z_{n+4} + \nonumber } \\ & - ( 7 n + 15 ) z_{n+3} + 6 z_{n+2} - ( 7 n + 5 ) z_{n+1} + 3 n z_n = 0 \, . \end{eqnarray} Finally we give a first-order asymptotic formula for $\; z_n \,$. Recall (\cite{BergeronLabelleLeroux} p. 252) that 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 ) } \, . $$ Since \begin{eqnarray*} z(t) & = & \frac{1-t+3t^2}{\sqrt{1-2t-t^2-2t^3+t^4}} - 1 \\ & = & \left( 1 - \frac{t}{\xi} \right)^{-1/2} \frac{1-t+3t^2}{\sqrt{( 1 + t + t^2 )( 1 - \xi t )}} - 1 \end{eqnarray*} where $\; \xi = ( 3 - \sqrt{5} )/2 \;$ and $\; \alpha = 1/2 \,$, we have \begin{equation} z_n \sim \frac{\sqrt{5}-1}{2} \sqrt{\frac{\sqrt{5}}{n\pi}} \left( \frac{3+\sqrt{5}}{2} \right)^n \, . \end{equation} In particular \begin{equation} \lim_{ n \to \infty } \frac{z_{n+1}}{z_n} = \frac{ 3 + \sqrt{5} }{ 2 } \, . \end{equation} In \cite{MunaZagaWuW} we proved that for the number $\; w_n \;$ of all central binary strings, without zigzags, of length $\; 2 n \;$ we have the asymptotic formula $$ w_n \sim \sqrt{ \frac{ 4 }{ n \pi \sqrt{5} } } \left( \frac{ 3 + \sqrt{5} }{ 2 } \right)^{\hspace{-1.2mm}n} \, . $$ This implies that $$ \lim_{ n \to \infty } \frac{w_n}{z_n} = \frac{ 4 }{ \sqrt{5} - 1 } \simeq 3.24 $$ or equivalently $\; w_n \simeq 3.24\, z_n \,$. % ----------------------------------------------------------------------------------------------------------- \section*{\normalsize 4. The matrix $\; Z \;$} % ----------------------------------------------------------------------------------------------------------- In this section we will prove that the matrix $$ Z = [ z_{i,j} ]_{i,j \geq 0} = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 0 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 1 & 0 & 6 & 7 & 12 & 18 & 25 & 33 & 42 \\ 1 & 0 & 7 & 8 & 18 & 30 & 44 & 60 & 78 \\ 1 & 0 & 8 & 9 & 25 & 44 & 70 & 104 & 147 \\ 1 & 0 & 9 & 10 & 33 & 60 & 104 & 168 & 255 \\ 1 & 0 & 10 & 11 & 42 & 78 & 147 & 255 & 412 \\ \ldots \end{bmatrix} $$ has a factorization $\; L T L^t \;$ where $\; L \;$ is the lower triangular matrix $$ L = [ l_{i,j} ]_{i,j \geq 0} = \begin{bmatrix} 1 & & & & & & & & \\ 0 & 1 & & & & & & & \\ 0 & 1 & 1 & & & & & & \\ 0 & 1 & 1 & 1 & & & & & \\ 0 & 1 & 1 & 2 & 1 & & & & \\ 0 & 1 & 1 & 3 & 2 & 1 & & & \\ 0 & 1 & 1 & 4 & 3 & 3 & 1 & & \\ 0 & 1 & 1 & 5 & 4 & 6 & 3 & 1 & \\ 0 & 1 & 1 & 6 & 5 & 10 & 6 & 4 & 1 \\ \ldots \end{bmatrix} $$ with entries given by $$ l_{i,0} = 0^i \, , \qquad l_{i,j} = { i - \lfloor j / 2 \rfloor - 1 \choose i - j } \quad \textrm{for} \quad i \geq j > 1 \, , $$ $\: L^t \;$ is the transpose of $\; L \;$ and $\; T \;$ is the tridiagonal matrix $$ T = [ t_{i,j} ]_{i,j \geq 0} = \begin{bmatrix} 0 & 1 & & & & & & & \\ 1 & 0 & 0 & & & & & & \\ & 0 & 4 & 1 & & & & & \\ & & 1 & 0 & 0 & & & & \\ & & & 0 & 4 & 1 & & & \\ & & & & 1 & 0 & 0 & & \\ & & & & & 0 & 4 & 1 & \\ & & & & & & 1 & 0 & 0 \\ & & & & & & & 0 & 4 \\ & & & & & & & & \ldots \end{bmatrix} $$ with entries $$ t_{i,j} = [\, j \mod 2 = 0 \,]\, \delta_{i,j+1} + 4 [\, i \mod 2 = 0, i \ne 0 \,] \delta_{i,j} + [\, i \mod 2 = 0 \,]\, \delta_{i+1,j} $$ where the square brackets denote the Iverson notation \cite{Knuth} for the characteristic function of a proposition and $\; \delta_{i,j} = [\, i = j \,] \;$ is the usual Kronecker delta. To prove the stated decomposition it is sufficient to rewrite the series $\; Z(x,y) \;$ in the following way: \begin{eqnarray*} \lefteqn{ Z(x,y) = \frac{ x ( 1 - y ) + 4 x^2 y^2 + y ( 1 - y ) }{ ( 1 - x ) ( 1 - y ) - x^2 y^2 } } \\ & = & \frac{x}{1-x} \frac{1}{\displaystyle 1-\frac{x^2}{1-x} \frac{y^2}{1-y}} + 4 \frac{x^2}{1-x} \frac{y^2}{1-y} \frac{1}{\displaystyle 1-\frac{x^2}{1-x} \frac{y^2}{1-y}} + \frac{y^2}{1-y} \frac{1}{\displaystyle 1-\frac{x^2}{1-x} \frac{y^2}{1-y}} \\ & = & \sum_{ k \geq 0 } \frac{x^{2k+1}}{(1-x)^{k+1}} \frac{y^{2k}}{(1-y)^k} + 4 \sum_{ k \geq 1 } \frac{x^{2k}}{(1-x)^k} \frac{y^{2k}}{(1-y)^k} + \sum_{ k \geq 0 } \frac{x^{2k}}{(1-x)^k} \frac{y^{2k+1}}{(1-y)^{k+1}} \\ & = & \sum_{ h, k \geq 0 } \frac{x^h}{(1-x)^{\lceil h/2 \rceil}} [\, k \mod 2 = 0 \,] \delta_{h,k+1} \frac{y^k}{(1-y)^{\lceil k/2 \rceil}} + \\ && \sum_{ h, k \geq 0 } \frac{x^h}{(1-x)^{\lceil h/2 \rceil}} [\, k \mod 2 = 0\, , k \geq 1 \,] \delta_{h,k} \frac{y^k}{(1-y)^{\lceil k/2 \rceil}} + \\ && \sum_{ h, k \geq 0 } \frac{x^h}{(1-x)^{\lceil h/2 \rceil}} [\, k \mod 2 = 0 \,] \delta_{h+1,k} \frac{y^k}{(1-y)^{\lceil k/2 \rceil}} \\ & = & \sum_{ h, k \geq 0 } \frac{x^h}{(1-x)^{\lceil h/2 \rceil}} t_{h,k} \frac{y^k}{(1-y)^{\lceil k/2 \rceil}} \\ & = & \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 \end{eqnarray*} where the numbers $\; l_{i,j} \;$ are the coefficients of the series $$ \sum_{ i \geq 1 } l_{i,j} \; x^i = \frac{x^j}{(1-x)^{\lceil j/2 \rceil}} \, . $$ Then it follows that $$ l_{i,j} = { i - j + \lceil j/2 \rceil - 1 \choose \lceil j/2 \rceil - 1 } = { i - \lfloor j/2 \rfloor - 1 \choose i - j } \, . $$ Hence we have the identity \begin{equation} \sum_{ h, k \geq 0 } l_{i,h} t_{h,k} l_{j,k} = z_{i,j} \end{equation} which is equivalent to the decomposition $\; W = L T L^t \,$. % ----------------------------------------------------------------------------------------------------------- \section*{\normalsize 5. A Riordan Matrix} % ----------------------------------------------------------------------------------------------------------- In \cite{MunaZagaWuW} we observed that the numbers $\; w_{i,j} \;$ of all linear binary strings without zigzags with $i$ $1$'s and $j$ $0$'s can be used to generate a Riordan matrix. This is also true for the numbers $\; z_{i,j} \,$. Let $\; r_{n,k} = z_{n,n-k} \;$ for $\; k \leq n \,$, $\; n \ne 0 \,$, $\; r_{0,0} = 1 \;$ and $\; r_{n,k} = 0 \;$ otherwise. Then $$ R = [ r_{n,k} ]_{n,k \geq 0} = \left[ \begin{array}{rrrrrrrrr} 1 & & & & & & & & \\ 0 & 1 & & & & & & & \\ 4 & 0 & 1 & & & & & & \\ 6 & 5 & 0 & 1 & & & & & \\ 12 & 7 & 6 & 0 & 1 & & & & \\ 30 & 18 & 8 & 7 & 0 & 1 & & & \\ 70 & 44 & 25 & 9 & 8 & 0 & 1 & & \\ 168 & 104 & 60 & 33 & 10 & 9 & 0 & 1 & \\ 412 & 255 & 147 & 78 & 42 & 11 & 10 & 0 & 1 \\ \ldots \end{array} \right] $$ is a Riordan matrix \cite{Shapiro,MRSV}. Indeed also this time we have the recurrence \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} which can be obtained by (\ref{zRec}). Moreover the matrix $\; R \;$ is completely determined by the recurrences $$ \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} + 3 \delta_{n,0} \end{array} \right. $$ with the initial conditions $\; r_{0,0} = 1 \,$, $\; r_{1,0} = 0 \;$ and $\; r_{1,1} = 1 \,$. It is easy to see that the recurrence (\ref{RRec}) imply that the generating series $\; r_k( t ) = \sum_{ n \geq k } r_{n,k} \; t^n \;$ of the columns of the matrix $\; R \;$ have the form $\; r_k( t ) = g( t ) f( t )^k \;$ where $\; g( t ) = r_0( t ) = z( t ) + 1 \;$ and $$ f(t) = \frac{ 1 + t - t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 } \, . $$ This last series is the generating series of the numbers of irreducible secondary structures \cite{SteinWaterman,Stanley2}. Since $\; g_0 = 1 \,$, $\; f_0 = 0 \;$ and $\; f_1 \ne 0 \,$, $\; R \;$ is the Riordan matrix $$ \left( \frac{ 1 - t + 3 t^2 }{ \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } } \, , \frac{ 1 + t - t^2 - \sqrt{ 1 - 2 t - t^2 - 2 t^3 + t^4 } }{ 2 } \right) \, . $$ Finally, since (for $\; k \geq 1 \,$) $$ r_{n,k} = [t^n]\; g(t) f(t)^k = \left( 1 - \frac{t}{\xi} \right)^{-1/2} \frac{1-t+3t^2}{\sqrt{( 1 + t + t^2 )( 1 - \xi t )}} \; f(t)^k $$ where $\; \xi = ( 3 - \sqrt{5} )/2 \;$ and $\; \alpha = 1/2 \,$, using the theorem we recalled in Section 3, it follows that (for every fixed $\; k \,$) \begin{equation} r_{n,k} \sim \frac{\sqrt{5}-1}{2} \sqrt{\frac{\sqrt{5}}{n\pi}} \left( \frac{3+\sqrt{5}}{2} \right)^n \left( \frac{\sqrt{5}-1}{2} \right)^k = \sqrt{\frac{\sqrt{5}}{n\pi}}\; (\phi+1)^n (\phi-1)^{k+1} \end{equation} where $\; \phi = ( 1 + \sqrt{5} ) / 2 \;$ is the golden ratio. More in general we have \cite{Sprugnoli} $$ \sum_{ k = 0 }^n a_k r_{n,k} = [t^n]\; g(t)\, a(f(t)) $$ where $\; a(t) \;$ is the ordinary generating series for the numbers $\; a_k \,$. For instance, for $\; a_k = 1 \;$ and $\; a_k = k \,$, we have $$ \sum_{ k = 0 }^n r_{n,k} = [t^n]\; g(t)\, f(t) \sim \frac{3-\sqrt{5}}{2}\; \sqrt{\frac{\sqrt{5}}{n\pi}}\; \phi^{2n} $$ $$ \sum_{ k = 0 }^n k\, r_{n,k} = [t^n]\; g(t)\, \frac{f(t)}{1-f(t)} \sim \sqrt{\frac{\sqrt{5}}{n\pi}}\; \phi^{2n+2} \, . $$ % ---------------------------------------------------------------------------- \section*{\normalsize 6. Cyclic species and generating series} % ---------------------------------------------------------------------------- The theory of species allows to interpret combinatorially several algebraic operations on formal series. As well known \cite{Joyal,BergeronLabelleLeroux,FontanesiMunarini} ordinary species, linear species and cyclic species correspond to the combinatorics of sets, linearly ordered sets and cycles, respectively. Moreover their cardinalities are the exponential series, the ordinary power series and the logarithmic series. In this way several combinatorial operations on species become algebraic operations on series. In particular if a species $\; \mathcal{S} \;$ can be expressed by means of sums, products and compositions of other species $\; \mathcal{S}_1 \,$, \ldots, $\; \mathcal{S}_k \;$ then its cardinality can be expressed in the same way in terms of the cardinalities of $\; \mathcal{S}_1 \,$, \ldots, $\; \mathcal{S}_k \,$. This is true also for types, considering as cardinalities the indicatrice series. In this section we consider the cyclic species of circular binary strings without zigzags and we show that it can be decomposed in more elementary species. This decomposition allows to compute the logarithmic series for the numbers $\; s_n \;$ and $\; z_{m,n} \;$ and above all it allows to obtain the indicatrice series for types (see next section). Let $\; \ZZ \:$ be the cyclic species of circular binary strings without zigzags and let $\; \ZZ^{\geq 2} \:$ be the cyclic species of circular binary strings without zigzags with maximal blocks of length at least $2$. Then clearly $\; \ZZ = 2 \XX + \ZZ^{\geq 2} \:$ where $\; \XX \;$ is the linear species of singletons. Let $\; C \;$ be a cycle and $\; \alpha \in \ZZ^{\geq 2}[C] \,$. Decompose $\; \alpha \;$ in its maximal blocks of $1$'s and $0$'s. Then pair each maximal block of $1$'s with the next maximal block of $0$'s. For instance, if $\; \alpha = 110001111001 \;$ then we have the grouping $\; \alpha = 11)(000)][(1111)(00)][(1 \,$. The square brackets define a cyclic partition \cite{FontanesiMunarini} of the cycle $\; C \,$, while the parenthesis inside the square brackets define a linear partition of an interval in two classes of size $\, \geq 2 \,$. The blocks determined by the square brackets will be called \emph{external blocks}. Hence we have that to give a structure of species $\; \ZZ^{\geq 2} \:$ on a cycle $\; C \;$ is equivalent to assign a cyclic partition $\; \pi \;$ of $\; C \;$ and then to assign on each class of $\; \pi \;$ a pair of disjoint intervals with at least $2$ elements whose union is all the class. So it follows that \begin{equation} \label{CbswzSpecies} \ZZ^{\geq 2} = \LL \circ ( \GG^{\geq 2} \cdot \GG^{\geq 2} ) \end{equation} where $\; \LL \;$ is the logarithmic species (or the uniform cyclic species) and $\; \GG \;$ is the geometric species (or the uniform linear species). Relation (\ref{CbswzSpecies}) implies that \begin{eqnarray*} \Card( \ZZ^{\geq 2}; t ) & = & \Card( \LL; t ) \circ \Card( \GG^{\geq 2}; t )^2 \\ & = & \ln \frac{1}{1-t} \circ \left( \frac{t^2}{1-t} \right)^2 \\ & = & \ln \frac{(1-t)^2}{1-2t+t^2-t^4} \end{eqnarray*} that is \begin{equation} \Card( \ZZ^{\geq 2}; t ) = \ln \frac{1}{1-2t+t^2-t^4} - 2 \ln \frac{1}{1-t} \, . \end{equation} Since $\; \ZZ = 2 \XX + \ZZ^{\geq 2} \,$, it follows that \begin{equation} \Card( \ZZ; t ) = \sum_{ n \geq 1 } s_n \; \frac{t^n}{n} = \ln \frac{1}{1-2t+t^2-t^4} \, . \end{equation} This is the logarithmic generating series for the numbers $\; s_n \,$. This identity can be obtained directly by (\ref{SGeoSeries}) using the formula $$ \sum_{ n \geq 1 } s_n \; \frac{t^n}{n} = \int_0^t \frac{ S(u) - S(0) }{ u }\; \textrm{d} u \, . $$ To obtain a generating series for the numbers $\; z_{m,n} \;$ we can consider the weighted cyclic species $\; \ZZ_{x,y} \;$ where each maximal block of $1$'s have weight $\; x \;$ and each block of $0$'s have weight $\; y \,$. Then, exactly as before, we have \begin{equation} \ZZ^{\geq 2}_{x,y} = \LL \circ ( \GG^{\geq 2}_x \cdot \GG^{\geq 2}_y ) \end{equation} where $\; \GG^{\geq 2}_x \;$ is the weighted linear species of the linear orders of size at least $2$ with weight $\; x \,$. Hence we have \begin{eqnarray*} \Card( \ZZ^{\geq 2}_{x,y}; t ) & = & \Card( \LL; t ) \circ ( \Card( \GG^{\geq 2}_x; t ) \cdot \Card(\GG^{\geq 2}_y;t) ) \\ & = & \ln \frac{1}{1-t} \circ \left( \frac{x^2t^2}{1-x t} \frac{y^2t^2}{1-y t} \right) \\ & = & \ln \frac{(1-x t)(1- y t)}{1-xt-yt+xyt^2-x^2y^2t^4} \end{eqnarray*} that is $$ \Card( \ZZ^{\geq 2}_{x,y}; t ) = \ln \frac{1}{1-xt-yt+xyt^2-x^2y^2t^4}-\ln \frac{1}{(1-x t)(1- y t)} \, . $$ Since $\; \ZZ_{x,y} = \XX_x + \XX_y + \ZZ^{\geq 2}_{x,y} \,$, we have $$ \Card( \ZZ_{x,y}; t ) = \ln \frac{1}{1-xt-yt+xyt^2-x^2y^2t^4} \, . $$ In particular, for $\; t = 1 \,$, we obtain the series \begin{equation}\label{eqlog2} \sum_{ m + n \geq 1 } z_{m,n} \; \frac{ x^m y^n }{ m + n } = \ln \frac{ 1 }{ 1 - x - y + x y - x^2 y^2 } \end{equation} {from} which we have that $$ z_{m,n} = ( m + n ) [ x^m y^n ] \ln \frac{ 1 }{ 1 - x - y + x y - x^2 y^2 } \, . $$ Identity (\ref{eqlog2}) can also be obtained by (\ref{ZGeoSeries}) using the formula $$ \sum_{ m + n \geq 1 } z_{m,n} \; \frac{ x^m y^n }{ m + n } = \int_0^x Z\left( t, \frac{y}{x} t \right) \frac{\textrm{d}t}{t} \, . $$ \paragraph{Third formula.} We can obtain another explicit formula for the numbers $\; z_{m,n} \;$ expanding the series $\; \Card( \ZZ^{\geq 2}_{x,y}; 1 ) \,$. Indeed we have \begin{eqnarray*} \Card( \ZZ^{\geq 2}_{x,y}; 1 ) & = & \ln \frac{1}{\displaystyle 1-\frac{x^2}{1-x} \frac{y^2}{1-y}} \\ & = & \sum_{ k \geq 1 } \frac{1}{k} \left( \frac{ x^2 }{ 1 - x } \right)^k \left( \frac{ y^2 }{ 1 - y } \right)^k \\ & = & \sum_{ k \geq 1 } \frac{1}{k} \sum_{ m \geq 0 } { m - k - 1 \choose k - 1 } x^m \sum_{ n \geq 0 } { n - k - 1 \choose k - 1 } y^n \\ & = & \sum_{ m, n \geq 0 } \left[ \sum_{ k \geq 1 } { m - k - 1 \choose k - 1 } { n - k - 1 \choose k - 1 } \frac{m+n}{k} \right] \frac{ x^m y^n }{ m + n } \, . \end{eqnarray*} Hence, for $\; m, n \geq 2 \,$, we have the identity \begin{equation} \label{EF4} z_{m,n} = \sum_{ k \geq 0 } { m - k - 2 \choose k } { n - k - 2 \choose k } \frac{m+n}{k+1} \, . \end{equation} % ---------------------------------------------------------------------------- \section*{\normalsize 7. Types} % ---------------------------------------------------------------------------- Let $\; \widetilde{z}_{m,n} \;$ be the number of $(0,1)$-necklaces without zigzags with $\; m \;$ $1$'s and $\; n \;$ $0$'s. Equivalently $\; \widetilde{z}_{m,n} \;$ is the number of types of circular binary strings without zigzags with $\; m \;$ 1's and $\; n \;$ 0's. See \cite{Joyal,BergeronLabelleLeroux} for the theory of types of structures and \cite{FontanesiMunarini} for the theory of type of cyclic structures. Since $\; \ZZ^{\geq 2}_{x,y} = \LL \circ ( \GG^{\geq 2}_x \cdot \GG^{\geq 2}_y ) \,$, it follows that the corresponding species of types is given by $$ \widetilde{\ZZ^{\geq 2}_{x,y}} = \widetilde{\LL \circ ( \GG^{\geq 2}_x \cdot \GG^{\geq 2}_y )} = \LL^\circlearrowleft \circlearrowleft ( \GG^{\geq 2}_x \cdot \GG^{\geq 2}_y ) \, . $$ Similarly, if $\; \ZZ^{\geq 2}_{x,y,k} \;$ is the cyclic species of all circular binary strings without zigzags with exactly $\; k \;$ external blocks, then $$ \ZZ^{\geq 2}_{x,y,k} = \frac{\XX^k}{k} \circ ( \GG^{\geq 2}_x \cdot \GG^{\geq 2}_y ) $$ and consequently $$ \widetilde{\ZZ^{\geq 2}_{x,y,k}} = \left( \frac{\XX^k}{k} \right)^{\!\!\circlearrowleft} \circlearrowleft ( \GG^{\geq 2}_x \cdot \GG^{\geq 2}_y ) \, . $$ Hence it follows that $$ \Card( \widetilde{\ZZ^{\geq 2}_{x,y,k}}; t ) = Z_k\left( \frac{x^2 t^2}{1-xt} \frac{y^2t^2}{1-yt}, \frac{x^4 t^4}{1-x^2t^2} \frac{y^4 t^4}{1-y^2t^2}, \ldots, \frac{x^{2k}t^{2k}}{1-x^kt^k} \frac{y^{2k}t^{2k}}{1-y^kt^k} \right) $$ where $$ Z_k( x_1, x_2, \ldots, x_k ) = \frac{1}{k} \sum_{ d | k } \ff(d) x_d^{k/d} $$ is the indicatrice series for $k$-cycles \cite{BergeronLabelleLeroux,Joyal,FontanesiMunarini}, where $\; \ff \;$ is the Euler function. Then, for $\; t = 1 \,$, we have \begin{eqnarray*} \lefteqn{ \Card( \widetilde{\ZZ^{\geq 2}_{x,y,k}}; 1 ) = } \\ & = & \frac{1}{k} \sum_{ d | k } \ff(d) \left( \frac{x^{2d}}{1-x^d} \frac{y^{2d}}{1-y^d} \right)^{k/d} \\ & = & \frac{1}{k} \sum_{ d | k } \ff(d) \frac{(x^d)^{2k/d}}{1-x^d} \frac{(y^d)^{2k/d}}{1-y^d} \\ & = & \frac{1}{k} \sum_{ d | k } \ff(d) \sum_{ m \geq 0 } { m - k/d - 1 \choose k/d - 1 }\; x^{md} \; \sum_{ n \geq 0 } { n - k/d - 1 \choose k/d - 1 }\; y^{nd} \\ & = & \sum_{ m, n \geq 0 } \frac{1}{k} \sum_{ d | k } { m - k/d - 1 \choose k/d - 1 } { n - k/d - 1 \choose k/d - 1 } \ff(d) \; x^{md} y^{nd} \\ & = & \sum_{ m, n \geq 0 } \frac{1}{k} \sum_{ { d | m \, , \; d | n } \atop d | k } { m/d - k/d - 1 \choose k/d - 1 } { n/d - k/d - 1 \choose k/d - 1 } \ff(d) \; x^m y^n \\ & = & \sum_{ m, n \geq 0 } \left[ \frac{1}{k} \sum_{ { d | m \, , \; d | n } \atop d | k } { m/d - k/d \choose k/d } \frac{k/d}{(m-k)/d} { n/d - k/d \choose k/d } \frac{k/d}{(n-k)/d} \ff(d) \right] \; x^m y^n \, . \end{eqnarray*} It follows that the number of all $(0,1)$-necklaces without zigzags with $\; m \;$ $1$'s, $\; n \;$ $0$'s and $\; k \;$ external blocks is given by \begin{equation} \widetilde{z}_{m,n}(k) = \sum_{ d | ( m, n, k ) } { (m-k)/d \choose k/d } { (n-k)/d \choose k/d } \frac{ k \ff(d) }{ (m-k) (n-k) } \end{equation} where $\; (m,n,k) \;$ is the greatest common divisor of $\; m \,$, $\; n \;$ and $\; k \,$. Then, since $\; \widetilde{z}_{m,n} = \sum_{ k \geq 1 } \widetilde{z}_{m,n}( k ) \,$, we have \begin{equation}\label{necklaceswz} \widetilde{z}_{m,n} = \sum_{ k \geq 1 } \left[ \sum_{ d | ( m, n, k ) } { (m-k)/d \choose k/d } { (n-k)/d \choose k/d } \frac{ k \ff(d) }{ (m-k) (n-k) } \right] \end{equation} where in the sum the index $\; k \;$ is at most $\; \min(m/2,n/2) \,$. In particular we have \begin{equation} \widetilde{z}_n = \widetilde{z}_{n,n} = \sum_{k=1}^{\lfloor n/2 \rfloor} \left[ \sum_{ d | ( n, k ) } { (n-k)/d \choose k/d }^2 \frac{ k \ff(d) }{ (n-k)^2 } \right] \, . \end{equation} See Figure \ref{Neckaces} for the first values of $\; \widetilde{z}_{m,n} \,$. The first few values of $\; \widetilde{z}_n \;$ are: 0, 1, 1, 2, 3, 7, 12, 27, 57, 128, 285, 659, 1518, 3561, 8389, 19936, 47607, 114397, 276018, 669035. When $\; (m,n)=1 \;$ identity (\ref{necklaceswz}) simplifies in \begin{equation} \widetilde{z}_{m,n} = \sum_{ k \geq 1 } { m-k \choose k } { n-k \choose k } \frac{ k }{ (m-k)(n-k) } \, . \end{equation} \begin{figure} $$ \begin{array}{|c|ccccccccccc|} \hline \widetilde{z}_{m,n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 3 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 \\ 5 & 1 & 0 & 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 6 & 1 & 0 & 1 & 1 & 3 & 4 & 7 & 8 & 11 & 14 & 17 \\ 7 & 1 & 0 & 1 & 1 & 3 & 5 & 8 & 12 & 17 & 23 & 30 \\ 8 & 1 & 0 & 1 & 1 & 4 & 6 & 11 & 17 & 27 & 37 & 52 \\ 9 & 1 & 0 & 1 & 1 & 4 & 7 & 14 & 23 & 37 & 57 & 82 \\ 10 & 1 & 0 & 1 & 1 & 5 & 8 & 17 & 30 & 52 & 82 & 128 \\ \hline \end{array} $$ \label{Neckaces} \caption{Numbers of types of circular binary strings without zigzags.} \end{figure} Finally consider the number $\; \widetilde{s}_n \;$ of all $\; (0,1) $-necklaces of length $\; n \;$ without zigzags. Then $$ \widetilde{s}_n = \sum_{ k = 0 }^n \widetilde{z}_{n,n-k} \, . $$ The first few values of $\; \widetilde{s}_n \;$ are: 0, 2, 2, 2, 3, 4, 5, 6, 8, 10, 15, 20, 31, 42, 64, 94, 143, 212, 329, 494, 766, 1170, 1811, 2788, 4341. \textbf{Acknowledgments.}\; The authors are grateful to Gian-Carlo Meloni, Douglas Rogers and the referee for useful suggestions and comments. % ----------------------------------------------------------------------------------------------------------- \begin{thebibliography}{99} \footnotesize \bibitem{BergeronLabelleLeroux} F. Bergeron, G. Labelle, P. Leroux, \emph{``Combinatorial Species and Tree-like Structures''}, Encyclopedia of Mathematics and Its Applications \textbf{67}, Cambridge University Press, Cambridge, 1998. \bibitem{Comtet} L. Comtet, \emph{``Advanced Combinatorics''}, Reidel, Dordrecht-Holland, Boston, 1974. \bibitem{DaiDhawanWuWu} F. Dai, M. Dhawan, C. Wu, J. Wu, \emph{On Solutions to a Seating Problem}. 2002 ISCA International Conference on Parallel and Distributed Computing Systems, 2002. \bibitem{FlajoletSedgewick} P. Flajolet, R. Sedgewick, \emph{``An Introduction to the Analysis of Algorithms''}, Addison-Wesley 1996. \bibitem{FontanesiMunarini} S. Fontanesi, E. Munarini, \emph{Cyclic Species}, preprint. \bibitem{Knuth} R.L. Graham, D.E. Knuth, O. Patashnik, \emph{``Concrete Mathematics''}, Addison-Wesley, Reading, MA, 1989. \bibitem{GreeneKnuth} D.H. Greene, D.E. Knuth, \emph{``Mathematics for the Analysis of Algorithms''}, Birk\"auser 1982. \bibitem{HautusKlarner} M.L.J. Hautus, D.A. Klarner, \emph{The Diagonal of a Double Power Series}, Duke Math. J. \textbf{38} (1971), 229-235. \bibitem{Joyal} A. Joyal, \emph{Une th\'eorie combinatoire des s\'eries formelles}, Adv. in Math. \textbf{42} (1981), 1--82. \bibitem{MRSV} D. Merlini, D. Rogers, R. Sprugnoli, M.C. Verri, {\em On some alternative characterizations of Riordan arrays}, Canad. J. Math. \textbf{49} (1997), 301--320. \bibitem{MunaZagaWuW} E. Munarini, N. Zagaglia Salvi, \emph{Binary strings without zigzags}, to appear in the Seminaire Lotharingien de Combinatoire. \bibitem{Schutzenberger} M.P. Sch\"utzenberger, \emph{Context-free language and pushdown automata}, Information and Control \textbf{6} (1963), 246--264. \bibitem{Shapiro} L. W. Shapiro, S. Getu, W. J. Woan, L. C. Woodson, \emph{ The Riordan group}, Discrete Appl. Math. \textbf{34} (1991), 229--239. \bibitem{Sprugnoli} R. Sprugnoli, \emph{Riordan Arrays and Combinatorial Sums}, Discrete Math. \textbf{132} (1994), 267--290. \bibitem{Stanley2} R.P. Stanley, \emph{``Enumerative Combinatorics''}, Volume 2, Cambridge Studies in Advanced Mathematics \textbf{62}, Cambridge University Press, Cambridge, 1999. \bibitem{SteinWaterman} P.R. Stein, M.S. Waterman, \emph{On some new sequences generalizing the Catalan and Motzkin numbers}, Discrete Math. \textbf{26} (1979), 261--272. \end{thebibliography} % ----------------------------------------------------------------------------------------------------------- % ---------------------------------------------------------------------------- \end{document} % ----------------------------------------------------------------------------