Quantifying CDS sortability of permutations by strategic pile size

Marisa Gaetz, Bethany Flanagan, Marion Scheepers, Meghan Shanks

Research output: Contribution to journalArticlepeer-review

Abstract

The special purpose sorting operation, context directed swap (CDS), is an example of the block interchange sorting operation studied in prior work on permutation sorting. CDShas been postulated to model certain molecular sorting events that occur in the genome maintenance program of some species of ciliates. We investigate the mathematical structure of permutations not sortable by the CDSsorting operation. In particular, we present substantial progress towards quantifying permutations with a given strategic pile size, which can be understood as a measure of CDSnon-sortability. Our main results include formulas for the number of permutations in Sn with maximum size strategic pile. More generally, we derive a formula for the number of permutations in Sn with strategic pile size k, in addition to an algorithm for computing certain coefficients of this formula, which we call merge numbers.

Original languageEnglish
Article number2050014
JournalDiscrete Mathematics, Algorithms and Applications
Volume12
Issue number1
DOIs
StatePublished - 1 Feb 2020

Keywords

  • Permutation sorting
  • context directed swap
  • factorization into cycles
  • strategic pile

Fingerprint

Dive into the research topics of 'Quantifying CDS sortability of permutations by strategic pile size'. Together they form a unique fingerprint.

Cite this