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
Keywords
Examples
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.)
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.
Extensions
a(0)=1 added by N. J. A. Sloane, Sep 12 2012