Skip to main content
Article
Quantifying CDS Sortability of Permutations by Strategic Pile Size
Discrete Mathematics, Algorithms and Applications
  • Marisa Gaetz, Massachusetts Institute of Technology
  • Bethany Flanagan, Purdue University
  • Marion Scheepers, Boise State University
  • Meghan Shanks, University of Illinois at Urbana–Champaign
Document Type
Article
Publication Date
2-1-2020
Disciplines
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. CDS has 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 CDS sorting operation. In particular, we present substantial progress towards quantifying permutations with a given strategic pile size, which can be understood as a measure of CDS non-sortability. Our main results include formulas for the number of permutations in Sn with 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.

Copyright Statement

Discrete Mathematics, Algorithms and Applications, Volume 12, Issue 1 (2020), Doc No. 2050014. https://doi.org/10.1142/S1793830920500147. © 2020, World Scientific Publishing Company. https://www.worldscientific.com/worldscinet/dmaa.

Citation Information
Marisa Gaetz, Bethany Flanagan, Marion Scheepers and Meghan Shanks. "Quantifying CDS Sortability of Permutations by Strategic Pile Size" Discrete Mathematics, Algorithms and Applications (2020)
Available at: http://works.bepress.com/marion_scheepers/44/