A164870 The number of permutations of length n that can be sorted by 2 pop stacks in parallel.
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
Offset: 1
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], 2010-2011.
- 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 626-629.
- Index entries for linear recurrences with constant coefficients, signature (6,-10,6)
Programs
-
Mathematica
LinearRecurrence[{6,-10,6},{1,2,6},30] (* Harvey P. Dale, Oct 12 2023 *) -
PARI
Vec(x*(1 - 2*x)^2 / (1 - 6*x + 10*x^2 - 6*x^3) + O(x^30)) \\ Colin Barker, Oct 31 2017
Formula
G.f.: -x*(2*x-1)^2 / ( -1+6*x-10*x^2+6*x^3 ).
a(n) = 6*a(n-1) - 10*a(n-2) + 6*a(n-3) for n>3. - Colin Barker, Oct 31 2017