

A182216


Number of permutations sortable by a doubleended queue.


4



1, 1, 2, 6, 24, 116, 634, 3762, 23638, 154816, 1046010, 7239440, 51069582, 365879686, 2654987356, 19473381290, 144138193538, 1075285161294, 8076634643892, 61028985689976, 463596673890280, 3538275218777642
(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
Michael Albert, Mike Atkinson, Steve Linton, Permutations generated by stacks and deques, Annals of Combinatorics, 14 (2010) 316. (gives method of computation).
Daniel Denton, Methods of computing deque sortable permutations given complete and incomplete information, arXiv:1208.1532.
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
Andrew ElveyPrice and Anthony J. Guttmann, Permutations sortable by deques and by two stacks in parallel, arxiv:1508.02273, 2015
Philippe Flajolet, Bruno Salvy and Paul Zimmermann, LambdaUpsilonOmega, The 1989 CookBook, page 105.
Paul Zimmermann, C program for A182216
P. Zimmermann, Introduction to Automatic Analysis, 2012.


EXAMPLE

Up to n=4 all permutations can be sorted by a doubleended queue (deque for short).
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).


CROSSREFS

Cf. A215257, A216040, A215252.
Sequence in context: A228395 A082631 A212198 * A097483 A210591 A342141
Adjacent sequences: A182213 A182214 A182215 * A182217 A182218 A182219


KEYWORD

nonn


AUTHOR

Paul Zimmermann, Apr 19 2012


EXTENSIONS

a(13)a(14) confirmed by Michael Albert, Apr 19 2012
a(16)a(21) from Michael Albert, Jun 27 2012
a(0)=1 added by N. J. A. Sloane, Sep 12 2012


STATUS

approved



