

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 [math.CO], 2012.
Andrew ElveyPrice and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, arxiv:1508.02273 [math.CO], 20152016.
Andrew ElveyPrice and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, European Journal of Combinatorics, 59 (2017), 7195.


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 doubleended queue instead of two stacks, then this permutation becomes sortable; cf. A182216.)


CROSSREFS

Cf. A182216, A215252, A215257.
Sequence in context: A301897 A022558 A004040 * A005802 A061552 A338752
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



