

A164870


The number of permutations of length n that can be sorted by 2 pop stacks in parallel.


2



1, 2, 6, 22, 84, 320, 1212, 4576, 17256, 65048, 245184, 924160, 3483408, 13129952, 49490592, 186544480, 703140672, 2650342784, 9989916864, 37654917376, 141932392320, 534984681344, 2016513669120, 7600829555200, 28649748728064, 107989278831104, 407043163037184
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

Colin Barker, Table of n, a(n) for n = 1..1000
Anders Claesson, Mark Dukes and Martina Kubitzke, Partition and composition matrices, arXiv:1006.1312 [math.CO], 20102011.
R. Smith and V. Vatter, The enumeration of permutations sortable by pop stacks in parallel, Information Processing Letters, Volume 109, Issue 12, 31 May 2009, Pages 626629.
Index entries for linear recurrences with constant coefficients, signature (6,10,6)


FORMULA

G.f.: x*(2*x1)^2 / ( 1+6*x10*x^2+6*x^3 ).
a(n) = 6*a(n1)  10*a(n2) + 6*a(n3) for n>3.  Colin Barker, Oct 31 2017


PROG

(PARI) Vec(x*(1  2*x)^2 / (1  6*x + 10*x^2  6*x^3) + O(x^30)) \\ Colin Barker, Oct 31 2017


CROSSREFS

Sequence in context: A150242 A150243 A200316 * A121686 A245904 A128723
Adjacent sequences: A164867 A164868 A164869 * A164871 A164872 A164873


KEYWORD

nonn,easy


AUTHOR

Vincent Vatter, Aug 29 2009


STATUS

approved



