Some Generalizations of a Simion-Schmidt Bijection

Abstract

In 1985 Simion and Schmidt gave a constructive bijection yc from the set of all length (n 1) binary strings having no two consecutive is to the set of all length n permutations avoiding all patterns in {123,132,213}. In this paper we generalize yc to an injective function from Mir' to the set ST, of all length n permutations and derive from it four bijections yc : P Q where P C {0, 1}n-1 and Q C S. The domains are sets of restricted binary strings and the codomains are sets of pattern-avoiding permutations. As a particular case we retrieve the original Simion-Schmidt bijection. We also show that the bijections obtained are actually combinatorial isomorphisms, i.e., closeness-preserving bijections. Three of them have known Gray codes and generating al¬gorithms for their domains and we present similar results for each corresponding codomain, under the appropriate combinatorial isomorphism.