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 |
| _version_ | 1797270004929921024 |
|---|---|
| author | Saúl A. Blanco Charles Buehrle Akshay Patidar |
| author_facet | Saúl A. Blanco Charles Buehrle Akshay Patidar |
| author_sort | Saúl A. Blanco |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-25T01:57:23Z |
| format | Article |
| id | doaj.art-5d20ec6bf2a9415c85083ed9e676346f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:23Z |
| publishDate | 2019-11-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-5d20ec6bf2a9415c85083ed9e676346f2024-03-07T15:38:27ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-11-01Vol. 21 no. 2, Permutation...10.23638/DMTCS-21-2-55214On the number of pancake stacks requiring four flips to be sortedSaúl A. BlancoCharles BuehrleAkshay PatidarUsing 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$.https://dmtcs.episciences.org/5214/pdfcomputer science - discrete mathematicsmathematics - combinatorics05a15, 05a05, 68r10g.2.0g.2.1g.2.2 |
| spellingShingle | Saúl A. Blanco Charles Buehrle Akshay Patidar On the number of pancake stacks requiring four flips to be sorted Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics mathematics - combinatorics 05a15, 05a05, 68r10 g.2.0 g.2.1 g.2.2 |
| title | On the number of pancake stacks requiring four flips to be sorted |
| title_full | On the number of pancake stacks requiring four flips to be sorted |
| title_fullStr | On the number of pancake stacks requiring four flips to be sorted |
| title_full_unstemmed | On the number of pancake stacks requiring four flips to be sorted |
| title_short | On the number of pancake stacks requiring four flips to be sorted |
| title_sort | on the number of pancake stacks requiring four flips to be sorted |
| topic | computer science - discrete mathematics mathematics - combinatorics 05a15, 05a05, 68r10 g.2.0 g.2.1 g.2.2 |
| url | https://dmtcs.episciences.org/5214/pdf |
| work_keys_str_mv | AT saulablanco onthenumberofpancakestacksrequiringfourflipstobesorted AT charlesbuehrle onthenumberofpancakestacksrequiringfourflipstobesorted AT akshaypatidar onthenumberofpancakestacksrequiringfourflipstobesorted |