Whole mirror duplication-random loss model and pattern avoiding permutations

Abstract : In this paper we study the problem of the whole mirror duplication-random loss model in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this model after a given number p of duplications of the identity is the class of permutations avoiding the alternating permutations of length p2+1. We also compute the number of duplications necessary and sufficient to obtain any permutation of length n. We provide two efficient algorithms to reconstitute a possible scenario of whole mirror duplications from identity to any permutation of length n. One of them uses the well-known binary reflected Gray code (Gray, 1953). Other relative models are also considered.
Liste complète des métadonnées

Contributeur : Jean-Luc Baril <>
Soumis le : mardi 5 février 2013 - 18:00:54
Dernière modification le : mercredi 12 septembre 2018 - 01:26:11




Jean-Luc Baril, Rémi Vernay. Whole mirror duplication-random loss model and pattern avoiding permutations. Information Processing Letters, Elsevier, 2010, 110 (11), pp.474-480. ⟨http://www.sciencedirect.com/science/article/pii/S0020019010000979⟩. ⟨10.1016/j.ipl.2010.04.016⟩. ⟨hal-00785281⟩



Consultations de la notice