#####
Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.

# Emanuele Munarini and Norma Zagaglia Salvi

#
Binary Strings Without Zigzags

**Summary.**
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 *LTL*^{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.

Received: March 14, 2003.
Revised: July 30, 2003 and December 22, 2003.
Accepted: March 16, 2004.

The following versions are available: