|
%I #57 May 20 2021 22:40:24
%S 1,1,2,6,24,116,634,3762,23638,154816,1046010,7239440,51069582,
%T 365879686,2654987356,19473381290,144138193538,1075285161294,
%U 8076634643892,61028985689976,463596673890280,3538275218777642
%N Number of permutations sortable by a double-ended queue.
%H Daniel Denton and Peter Doyle, <a href="/A182216/b182216.txt">Table of n, a(n) for n = 0..100</a>
%H Michael Albert, Mike Atkinson, Steve Linton, <a href="http://www.springerlink.com/content/h273247258k76101/">Permutations generated by stacks and deques</a>, Annals of Combinatorics, 14 (2010) 3-16. (gives method of computation).
%H Daniel Denton, Methods of computing deque sortable permutations given complete and incomplete information, <a href="http://arxiv.org/abs/1208.1532">arXiv:1208.1532</a>.
%H Stoyan Dimitrov, <a href="https://arxiv.org/abs/2103.04332">Sorting by shuffling methods and a queue</a>, arXiv:2103.04332 [math.CO], 2021.
%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, 2015
%H Philippe Flajolet, Bruno Salvy and Paul Zimmermann, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5141">Lambda-Upsilon-Omega, The 1989 CookBook</a>, page 105.
%H Paul Zimmermann, <a href="/A182216/a182216.c.txt">C program for A182216</a>
%H P. Zimmermann, <a href="http://www.stat.purdue.edu/~mdw/ChapterIntroductions/AutomaticAnalysisZimmermann.pdf">Introduction to Automatic Analysis</a>, 2012.
%e Up to n=4 all permutations can be sorted by a double-ended queue (deque for short).
%e For n=5 the permutation 24351 cannot: you first queue 2 on either side, then 4 on either side, then 3 has to be queued on the same side as 4 otherwise it will "block" 2 between 3 and 4, but then whatever side you queue 5, you will block either 2 (between 4 and 5) or 3 (between 4 and 5).
%Y Cf. A215257, A216040, A215252.
%K nonn
%O 0,3
%A _Paul Zimmermann_, Apr 19 2012
%E a(13)-a(14) confirmed by _Michael Albert_, Apr 19 2012
%E a(16)-a(21) from _Michael Albert_, Jun 27 2012
%E a(0)=1 added by _N. J. A. Sloane_, Sep 12 2012
| 