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 wm,n of these strings with m 1's
and n 0's
and in particular for the numbers wn =
wn,n of central strings.
We also consider two matrices generated by the numbers
wm,n
and we prove that one is a Riordan matrix
and the other one has a decomposition LTLt
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: