Abstract: Let
be
the set of all n-length
binary strings such that there are at least pconsecutive
0s between two 1s. Chinburg et al. [3] give a Gray code for the set such
that two consecutive elements differ in at most two positions which are optimal
for nlarge.
In this paper, we construct a more restrictive Gray code for in
the sense where our Gray code contains more transitions with one move than
theirs. Moreover, using a combinatorial isomorphism between the set ofn-length
binary strings and the set of n-length
permutations avoiding 123 and 132, we provide a bijection from to
that induces a Gray code for the set All these codes can be generated by implementing a recursive
algorithm in constant amortized time.
Keywords and phrases: composition of an integer, Fibonacci number, Gray code, permutation avoiding pattern.
