On the number of pancake stacks requiring four flips to be sorted
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 for...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5214/pdf |
| Summary: | 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$. |
|---|---|
| ISSN: | 1365-8050 |