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

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-00785281
Contributeur : Jean-Luc Baril <>
Soumis le : mardi 5 février 2013 - 18:00:54
Dernière modification le : mercredi 8 janvier 2020 - 11:26:10

Identifiants

Citation

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. ⟨10.1016/j.ipl.2010.04.016⟩. ⟨hal-00785281⟩

Partager

Métriques

Consultations de la notice

263