Saúl A. Blanco ; Charles Buehrle ; Akshay Patidar - On the number of pancake stacks requiring four flips to be sorted

dmtcs:5214 - Discrete Mathematics & Theoretical Computer Science, November 4, 2019, Vol. 21 no. 2, Permutation Patters 2018 - https://doi.org/10.23638/DMTCS-21-2-5
On the number of pancake stacks requiring four flips to be sortedArticle

Authors: Saúl A. Blanco ; Charles Buehrle ; Akshay Patidar

    Using existing classification results for the 7- and 8-cycles in the pancake graph, we determine the number of permutations that require 4 pancake flips (prefix reversals) to be sorted. A similar characterization of the 8-cycles in the burnt pancake graph, due to the authors, is used to derive a formula for the number of signed permutations requiring 4 (burnt) pancake flips to be sorted. We furthermore provide an analogous characterization of the 9-cycles in the burnt pancake graph. Finally we present numerical evidence that polynomial formulae exist giving the number of signed permutations that require $k$ flips to be sorted, with $5\leq k\leq9$.


    Volume: Vol. 21 no. 2, Permutation Patters 2018
    Published on: November 4, 2019
    Accepted on: October 15, 2019
    Submitted on: February 27, 2019
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,05A15, 05A05, 68R10,G.2.0,G.2.1,G.2.2

    Consultation statistics

    This page has been seen 1312 times.
    This article's PDF has been downloaded 207 times.