login
Number of permutations sortable using two parallel stacks.
4

%I #28 May 31 2020 21:57:50

%S 1,1,2,6,23,103,513,2760,15741,93944,581303,3704045,24180340,

%T 161082639,1091681427,7508269793,52302594344,368422746908,

%U 2620789110712,18806093326963,136000505625886,990406677136685,7258100272108212

%N Number of permutations sortable using two parallel stacks.

%H Daniel Denton and Peter Doyle, <a href="/A216040/b216040.txt">Table of n, a(n) for n = 0..100</a>

%H Daniel Denton, <a href="http://arxiv.org/abs/1208.1532">Methods of computing deque sortable permutations given complete and incomplete information</a>, arXiv:1208.1532 [math.CO], 2012.

%H Andrew Elvey-Price and Anthony J. Guttmann, <a href="http://arxiv.org/abs/1508.02273">Permutations sortable by deques and by two stacks in parallel</a>, arxiv:1508.02273 [math.CO], 2015-2016.

%H Andrew Elvey-Price and Anthony J. Guttmann, <a href="https://doi.org/10.1016/j.ejc.2016.08.002">Permutations sortable by deques and by two stacks in parallel</a>, European Journal of Combinatorics, 59 (2017), 71-95.

%e 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.)

%Y Cf. A182216, A215252, A215257.

%K nonn

%O 0,3

%A _Peter Doyle_, Aug 30 2012

%E a(0)=1 added by _N. J. A. Sloane_, Sep 12 2012