A058986 -id:A058986 - cp's OEIS frontend

A092113 Triangle read by rows: T(n,k) is the number of stacks of n pancakes requiring k = 0, ..., A058986(n) flips to sort.

1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 11, 3, 1, 4, 12, 35, 48, 20, 1, 5, 20, 79, 199, 281, 133, 2, 1, 6, 30, 149, 543, 1357, 1903, 1016, 35, 1, 7, 42, 251, 1191, 4281, 10561, 15011, 8520, 455, 1, 8, 56, 391, 2278, 10666, 38015, 93585, 132697, 79379, 5804, 1, 9, 72, 575

Offset: 1

Eric W. Weisstein, Feb 21 2004

Last term of row k is A067607(k).

Row n has length A058986(n) + 1. - Martin Renner, Jul 23 2017

			Triangle begins:
  1;
  1,  1;
  1,  2,  2,  1;
  1,  3,  6, 11,  3;
  1,  4, 12, 35, 48, 20;
  ...
From _Jon E. Schoenfield_, Dec 16 2021: (Start)
For n=3, the 3! = 6 permutations are {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, and {3,2,1}. Of these,
T(3,0)=1 permutation (namely, {1,2,3}) requires no prefix reversals (because it is already sorted);
T(3,1)=2 permutations (namely, {2,1,3} and {3,2,1}) require one prefix reversal, e.g., {2,1,3} -> {1,2,3};
T(3,2)=2 permutations (namely, {2,3,1} and {3,1,2}) require two prefix reversals, e.g., {2,3,1} -> {3,2,1} -> {1,2,3}; and
T(3,3)=1 permutation (namely, {1,3,2}) requires 3 prefix reversals: {1,3,2} -> {3,1,2} -> {2,1,3} -> {1,2,3};
thus, the terms in row n=3 are 1, 2, 2, 1. (End)

Sean A. Irvine, Table of n, a(n) for n = 1..97 (terms 1..68 from Martin Renner)

Cf. A058986, A067607.

A359141 First differences of the pancake flipping (or sorting by prefix reversal) sequence A058986.

Original entry on oeis.org

1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2

Offset: 1

N. J. A. Sloane, Jan 26 2023

A comment in A058986 implies that the terms are at most 2. Furthermore a zero term seems unlikely.

The initial terms consist of runs of 1, 2, 4, and 7 1's separated by 2's, which allows for a large number of extensions.

Cf. A058986.

A066533 Erroneous version of A058986.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15

Offset: 1

dead

A048200 Minimal length pair-exchange / set-rotate sequence to reverse n distinct ordered elements.

Original entry on oeis.org

0, 1, 2, 4, 10, 15, 23, 32, 42, 55, 67, 84, 98, 119

Offset: 1

Tony Bartoletti

"Rotate" is always a left-rotate (moves leftmost element to the right end) and "Exchange" is always a pair-exchange of the two leftmost elements.

a(15)<=135 and a(16)<=160. See example solutions in the links section. - Dmitry Kamenetsky, Jun 19 2025

			a(4) = 4 since "xrrx" is the shortest sequence reversing "ABCD". Explicitly, (begin) ABCD, (x)-> BACD, (r)-> ACDB, (r) -> CDBA, (x)-> DCBA.

Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, Primality tests, linear recurrent sequences and the Pell equation, arXiv:2002.08062 [math.NT], 2020.
Sean A. Irvine, Java program (github)
Dmitry Kamenetsky, Best known solutions for n <= 16.
Sai Satwik Kuppili, C++ program for generating the moves for a given n
Sai Satwik Kuppili and Bhadrachalam Chitturi, Exact upper bound for sorting R_n with LE, University of Texas at Dallas (2019).
Sai Satwik Kuppili and Bhadrachalam Chitturi, An upper bound for sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.
Sai Satwik Kuppili and Bhadrachalam Chitturi, Exact upper bound for sorting R_n with LE, Discrete Mathematics, Algorithms and Applications, 2020.
Kevin Ryde, C Code

Cf. A058986, A065603, A186752.

C
```
/* See links. */
```
Java
```
/* See links. */
```

Conjecture: a(n) = (3*n^2/4)-2*n if n is even and a(n) = (3*n^2-10*n+15)/4 if n is odd. See links for more information. - Sai Satwik Kuppili and Bhadrachalam Chitturi, Jun 09 2020

a(11) added by Sai Satwik Kuppili and Srinath T, Bhadrachalam Chitturi, Jan 02 2019
a(12) from Sean A. Irvine, Jun 04 2021
a(13) from Kevin Ryde, Dec 19 2024
a(14) from Zachary DeStefano, Jan 03 2025

A078941 Flipping burnt pancakes. Maximum number of spatula flips to sort a stack of n pancakes of different sizes, each burnt on one side, so that the smallest ends up on top, ..., the largest at the bottom and each has its burnt side down.

Original entry on oeis.org

1, 4, 6, 8, 10, 12, 14, 15, 17, 18, 19, 21

Offset: 1

Dean Hickerson, Dec 18 2002

In a 'spatula flip', a spatula is inserted below any pancake and all pancakes above the spatula are lifted and replaced in reverse order.

It is conjectured that the initial configuration in which the pancakes are in the correct order but all of the burnt sides are up is a worst case for the problem. If so, then this sequence is identical to A078942.

David S. Cohen and Manuel Blum, "On the problem of sorting burnt pancakes", Discrete Applied Math., 61 (1995) 105-120.

J. Cibulka, Pancake Sorting [From D.J. Schreffler (dj_schreffler(AT)hotmail.com), Apr 17 2010]
Douglas B. West, The Pancake Problems (1975, 1979, 1973) - From _N. J. A. Sloane_, Jul 26 2012

Cf. A078942. A058986 treats the unburnt case.

a(n) >= A078942(n). a(n+1) <= a(n) + 2. 3n/2 <= a(n) <= 2n-2, where the upper bound holds for n>=10.

Two new terms added from a 2009 presentation. See the University of Montreal link below. D.J. Schreffler (dj_schreffler(AT)hotmail.com), Apr 17 2010

A067607 Number of stacks of n pancakes requiring a maximum number of flips to order.

Original entry on oeis.org

1, 1, 1, 3, 20, 2, 35, 455, 5804, 73232, 6, 167, 2001, 24974, 339220, 4646117, 65758725

Offset: 1

Eric W. Weisstein

a(n) is the last term in row n in A092113. - Joerg Arndt, Mar 01 2023

a(18) >= 12357059, a(19) >= 410 from J. Cibulka's webpage. - Dan Dima, Feb 19 2024

Josef Cibulka, Average number of flips in pancake sorting, arXiv:0901.3119 [cs.DM], 2009.
Josef Cibulka, On average and highest number of flips in pancake sorting, Theoretical Computer Science, Volume 412, Issue 8-10, March 2011, pp 822-834.
Josef Cibulka, Pancake sorting, webpage.
Mohammad Hossain Heydari and Ivan Hal Sudborough, On the Diameter of the Pancake Network, Journal of Algorithms, Volume 25, Issue 1 Oct. 1997, pp. 67-94.
Eric Weisstein's World of Mathematics, Pancake Sorting.
Wikipedia, Pancake sorting.

Cf. A058986, A092113.

Corrected and extended by Rob Pratt, Feb 21 2004
a(11)-a(12) from Sean A. Irvine, Dec 23 2023
a(13)-a(17) from Dan Dima, Feb 10 2024

A078942 Flipping burnt pancakes. Given a sorted stack of n burnt pancakes of different sizes (smallest on top, ..., largest at the bottom), each with its burnt side up, a(n) is the number of spatula flips needed to restore them to their initial order but with the burnt sides down.

Original entry on oeis.org

1, 4, 6, 8, 10, 12, 14, 15, 17, 18, 19, 21, 22, 23, 24, 26, 28, 29

Offset: 1

Dean Hickerson, Dec 18 2002

In a 'spatula flip', a spatula is inserted below any pancake and all pancakes above the spatula are lifted and replaced in reverse order.

It is conjectured that this initial configuration is a worst case for the general problem of sorting burnt pancakes. If so, then this sequence is identical to A078941.

David S. Cohen and Manuel Blum, "On the problem of sorting burnt pancakes", Discrete Applied Math., 61 (1995) 105-120.

Douglas B. West, The Pancake Problems (1975, 1979, 1973) - From _N. J. A. Sloane_, Jul 26 2012

Cf. A078941, A058986.

a(n) <= A078941(n). a(n+1) <= a(n) + 2. 3n/2 <= a(n) <= 47n/30 + c for some constant c.

A131209 Maximal distance between two signed permutations of n elements.

Original entry on oeis.org

0, 1, 3, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69

Offset: 0

Brian Hayes, Oct 26 2007, based on email from Glenn Tesler (gptesler(AT)math.ucsd.edu)

nonn

See also the comments in A058986 for background information.
From Glenn Tesler: (Start)
Let d_max = a(n) be the maximal distance.
Then d_max = n for n=0,1,3; d_max = n+1 except for n=0,1,3; however, there are many permutations achieving the max, not just the 2 Gollan permutations as in the unsigned case.
The formula for reversal distance is d = n + 1 - c + h + f,
where c is the number of cycles in the breakpoint graph, h is the number of "hurdles" and f is the number of "fortresses" (0 or 1).
It turns out that c >= h+f.
This is because each hurdle is composed of one or more cycles, distinct from those in other hurdles, and fortresses can be worked into that, too.
So we may rewrite distance as d = n+1 - (c-h-f), where c-h-f>=0. Thus d_max <= n+1.
Except for n=0,1,3, it turns out we can make c-h-f=0.
When n=0: d(null,null) = 0, so d_max = 0 (has c=1, h=0)
When n=1: d( 1, -1 ) = 1, d( 1, 1 ) = 0, so d_max = 1 (first one has c=1, h=0)
When n=2: d( 2 1, 1 2 ) = 3, all other d(sigma, 1 2) < 3 (has c=h=1)
When n=3: d_max = 3 (25 solutions, found by brute force; 20 with c=1, h=0; 5 with c=2, h=1)
When n>3: d_max = n+1 and there are many solutions, obtained by creating a situation in which c=h, f=0. One of them is
n=2m: n 1 m+1 2 m+2 3 m+3 ... m-1 2m-1 m (has c=h=1)
n=2m+1: n 1 m+1 2 m+2 3 m+3 ... m 2m (has c=h=2)
Note that these are indeed signed permutations, in which all signs happen to be positive. This is because "hurdles" require all the signs to be the same.
Also note that these are just examples to show that at least one permutation has d=n+1, which proves d_max=n+1 by the bound; however, there are many more signed permutations that also achieve d=n+1. (End)

Brian Hayes, Sorting out the genome, Amer. Scientist, 95 (2007), 386-391.

Cf. A058986, A078941.

a(n) = n+1 except for n=0,1,3.

A271474 Maximal number of flips required to sort a stack of n unburnt pancakes using the big-3 flips.

Original entry on oeis.org

0, 1, 3, 4, 8, 12, 15, 21, 27, 35, 42, 50

Offset: 1

N. J. A. Sloane, Apr 09 2016

J. Sawada and A. Williams, Successor rules for flipping pancakes and burnt pancakes, Preprint 2015.

Cf. A058986.

cp's OEIS Frontend

A092113 Triangle read by rows: T(n,k) is the number of stacks of n pancakes requiring k = 0, ..., A058986(n) flips to sort.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A359141 First differences of the pancake flipping (or sorting by prefix reversal) sequence A058986.

Views

Author

Keywords

Comments

Crossrefs

A066533 Erroneous version of A058986.

Views

Author

Keywords

A048200 Minimal length pair-exchange / set-rotate sequence to reverse n distinct ordered elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Java

Formula

Extensions

A078941 Flipping burnt pancakes. Maximum number of spatula flips to sort a stack of n pancakes of different sizes, each burnt on one side, so that the smallest ends up on top, ..., the largest at the bottom and each has its burnt side down.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A067607 Number of stacks of n pancakes requiring a maximum number of flips to order.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A078942 Flipping burnt pancakes. Given a sorted stack of n burnt pancakes of different sizes (smallest on top, ..., largest at the bottom), each with its burnt side up, a(n) is the number of spatula flips needed to restore them to their initial order but with the burnt sides down.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A131209 Maximal distance between two signed permutations of n elements.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A271474 Maximal number of flips required to sort a stack of n unburnt pancakes using the big-3 flips.

Views

Author

Keywords

Links

Crossrefs