Journal of Combinatorics

Volume 2 (2011)

Number 2

On the inverse image of pattern classes under bubble sort

Pages: 231 – 243

DOI: https://dx.doi.org/10.4310/JOC.2011.v2.n2.a3

Authors

Michael H. Albert (Department of Computer Science, University of Otago, Dunedin, New Zealand)

M.D. Atkinson (Department of Computer Science, University of Otago, Dunedin, New Zealand)

Mathilde Bouvel (CNRS, LaBRI, Université Bordeaux 1, Talence, France)

Anders Claesson (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Mark Dukes (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Abstract

Let $B$ be the operation of re-ordering a sequence by one pass of bubble sort.We completely answer the question of when the inverse image of a principal pattern class under $B$ is a pattern class.

Keywords

permutation, bubble sort, pattern class

Full Text (PDF format)

Published 25 October 2011