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

%I #14 Oct 12 2023 15:26:20

%S 1,2,6,22,84,320,1212,4576,17256,65048,245184,924160,3483408,13129952,

%T 49490592,186544480,703140672,2650342784,9989916864,37654917376,

%U 141932392320,534984681344,2016513669120,7600829555200,28649748728064,107989278831104,407043163037184

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

%H Colin Barker, <a href="/A164870/b164870.txt">Table of n, a(n) for n = 1..1000</a>

%H Anders Claesson, Mark Dukes and Martina Kubitzke, <a href="http://arxiv.org/abs/1006.1312">Partition and composition matrices</a>, arXiv:1006.1312 [math.CO], 2010-2011.

%H R. Smith and V. Vatter, <a href="http://www-groups.mcs.st-and.ac.uk/~vince/publications/popstacks/pop-stacks.pdf">The enumeration of permutations sortable by pop stacks in parallel</a>, Information Processing Letters, Volume 109, Issue 12, 31 May 2009, Pages 626-629.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-10,6)

%F G.f.: -x*(2*x-1)^2 / ( -1+6*x-10*x^2+6*x^3 ).

%F a(n) = 6*a(n-1) - 10*a(n-2) + 6*a(n-3) for n>3. - _Colin Barker_, Oct 31 2017

%t LinearRecurrence[{6,-10,6},{1,2,6},30] (* _Harvey P. Dale_, Oct 12 2023 *)

%o (PARI) Vec(x*(1 - 2*x)^2 / (1 - 6*x + 10*x^2 - 6*x^3) + O(x^30)) \\ _Colin Barker_, Oct 31 2017

%K nonn,easy

%O 1,2

%A _Vincent Vatter_, Aug 29 2009