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,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], 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)

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

Mathematica

LinearRecurrence[{6, -10, 6}, {1, 2, 6}, 30] (* Harvey P. Dale, Oct 12 2023 *)

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