A216040 Number of permutations sortable using two parallel stacks.

1, 1, 2, 6, 23, 103, 513, 2760, 15741, 93944, 581303, 3704045, 24180340, 161082639, 1091681427, 7508269793, 52302594344, 368422746908, 2620789110712, 18806093326963, 136000505625886, 990406677136685, 7258100272108212

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 Elvey-Price and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, arxiv:1508.02273 [math.CO], 2015-2016.

Andrew Elvey-Price and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, European Journal of Combinatorics, 59 (2017), 71-95.

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. 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