On the Extended Patterns in a Simion-Schmidt's Bijection

Abstract

In 1985 Simion and Schmidt gave a constructive bijection ' : Fn¡1 ! Sn(123; 132; 213), where Fn¡1 is the set of all length (n ¡ 1) binary strings having no two consecutive 1s, also known as the set of Fibonacci strings (of 2-nd order), and Sn(123; 132; 213) is the set of all permutations of f1; 2; : : : ; ng that avoid all patterns in the set f123; 132; 213g. In this paper we extend the set of patterns f123; 132; 213g while to generalize the domain such that we get three following new bijections: '1 : F(n¡1) n¡1 ! Sn(12 : : : p; 132; 213), '2 : F(n¡1) n¡1 ! Sn(123; 1p(p ¡ 1) : : : 2; 213), and '3 : F(n¡1) n¡1 ! Sn(123; 132; (p ¡ 1)(p ¡ 2) : : : p), where '3 actually is exactly same as the original mapping ' due to Simion-Schmidt. Furthermore, we show that the three bijections are actually combinatorial isomorphisms, i.e., closeness preserving bijections. Since each domain of the bijections has known Gray code, therefore, through the corresponding combinatorial isomorphism, we construct similar Gray code for each of corresponding codomain.