Some generalizations of a simion-schmidt bijection

Juarna, Asep and Vajnovszki, Vincent Some generalizations of a simion-schmidt bijection. Skripsi Program Studi Psikologi.

[img]
Preview
Text
SOME GENERALIZATIONS OF A SIMION-SCHMIDT BIJECTION_UG.pdf - Submitted Version

Download (208Kb) | Preview

Abstract

In 1985 Simion and Schmidt gave a constructive bijection 4 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 4 to an inject ive function from {O, i}n_1 to the set S, of all length n permutations and derive from it four bijections : P —* Q where P ç {O, i}?_1 and Q C S,. The doniaiiis 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 bij ect ion. We also show that the l)ijections obtained are actually combinatorial isomorphisms, i.e., closeness—preserving bijections. Three of them have known Cray codes and generating alg orithms for their domains and we present similar results for each corresponding codomain, under the appropriate combinatorial isomorphism.

Item Type: Article
Uncontrolled Keywords: pattern-avoiding permutations; fibonacciand lucas string; constructive bijection; combinational; gray codes
Subjects: A General Works > AI Indexes (General)
Divisions: Fakultas Psikologi > Program Studi Psikologi
Depositing User: Mr Reza Chandra
Date Deposited: 25 Feb 2014 04:51
Last Modified: 25 Feb 2014 04:51
URI: http://repository.gunadarma.ac.id/id/eprint/57

Actions (login required)

View Item View Item