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: