American Review of Mathematics and Statistics

An Algorithm for the Exhaustive Generation of Binary Words avoiding up-down Sequences
Stefano Bilotta, Elisabetta Grazzini, Elisa Pergola

Abstract
In this paper we propose an algorithm to generate binary words with no more 0's than 1's having a fixed number of 1's and avoiding the sequence (10) j1 for any fixed j  1. Any binary word w can be represented as a path on the Cartesian plane by associating a rise step, defined by (1,1), with each bit 1 in w and a fall step, defined by (1,-1), with each bit 0 in w. Given a path  with n rise steps associated with the binary word w avoiding the sequence (10) j1, we generate a given number of paths with n+h rise steps, 1  h  j, avoiding the same sequence, by means of constructive rules. The number and the shape of the generated paths depend on the ordinate k of the endpoint of  and on its suffix. We will prove that this generation is exhaustive, that is, all binary words with n bit 1 and avoiding the sequence (10) j1 are generated.

Full Text: PDF     DOI: 10.15640/arms.v3n1a2