login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216040 Number of permutations sortable using two parallel stacks. 4
1, 1, 2, 6, 23, 103, 513, 2760, 15741, 93944, 581303, 3704045, 24180340, 161082639, 1091681427, 7508269793, 52302594344, 368422746908, 2620789110712, 18806093326963, 136000505625886, 990406677136685, 7258100272108212 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Daniel Denton and Peter Doyle, Table of n, a(n) for n = 0..100

Daniel Denton, Methods of computing deque sortable permutations given complete and incomplete information, arXiv:1208.1532.

Andrew Elvey-Price and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, arxiv:1508.02273, 2015.

EXAMPLE

Up to n=4 the only permutation that can't be sorted is 2341.  This fails because after moving 2 to one stack, you must move 3 to the other stack, and now the 4 will block either the 2 or the 3.  (If you use a double-ended queue instead of two stacks, then this permutation becomes sortable: Cf. A182216.)

CROSSREFS

Cf. A215252, A182216, A215257.

Sequence in context: A301897 A022558 A004040 * A005802 A061552 A263778

Adjacent sequences:  A216037 A216038 A216039 * A216041 A216042 A216043

KEYWORD

nonn

AUTHOR

Peter Doyle, Aug 30 2012

EXTENSIONS

a(0)=1 added by N. J. A. Sloane, Sep 12 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 13:37 EDT 2019. Contains 327253 sequences. (Running on oeis4.)