On the number of pancake stacks requiring four flips to be sorted

MaRDI QIDQ5207835zbMATH OpenFDO

Authors Saúl A. Blanco, Charles Buehrle, Akshay Patidar

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1902.04055, https://dmtcs.episciences.org/5879/pdf

zbMATH Keywords

burnt pancake graphCayley graphscycle embeddingpancake graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 $5leqkleq9$.

Recommendations

• On average and highest number of flips in pancake sorting
• On the problem of sorting burnt pancakes
• On the Diameter of the Pancake Network
• Polynomial-time sortable stacks of burnt pancakes
• Greedy flipping of pancakes and burnt pancakes

Cited in

(7)

• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Lengths of cycles in generalized pancake graphs
• An Algorithm to Enumerate Grid Signed Permutation Classes
• Polynomial-time sortable stacks of burnt pancakes
• Some integer values in the spectra of burnt pancake graphs
• On the spectra of prefix-reversal graphs
• Enumerating polynomial colored permutation classes

This page was built for publication: On the number of pancake stacks requiring four flips to be sorted

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207835)