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

1, 1, 2, 6, 24, 118, 644, 3622, 20366, 113686, 630464, 3481084, 19171838, 105444400, 579547826, 3184321642, 17493771830, 96100287256, 527905628552, 2899911094078, 15929870658308, 87506389326742, 480692570563526, 2640554790693958, 14505177373598504

Offset

0,3

Links

Colin Barker, Table of n, a(n) for n = 0..1000

R. Smith and V. Vatter, The enumeration of permutations sortable by pop stacks in parallel

Index entries for linear recurrences with constant coefficients, signature (14,-75,201,-288,216,-72).

Formula

G.f.: (1 -13*x +63*x^2 -148*x^3 +177*x^4 -98*x^5 +18*x^6) / (1 -14*x +75*x^2 -201*x^3 +288*x^4 -216*x^5 +72*x^6).

a(n) = 14*a(n-1) - 75*a(n-2) + 201*a(n-3) - 288*a(n-4) + 216*a(n-5) - 72*a(n-6) for n>6. - Colin Barker, Jul 02 2019

Mathematica

LinearRecurrence[{14, -75, 201, -288, 216, -72}, {1, 1, 2, 6, 24, 118, 644}, 30] (* Harvey P. Dale, Mar 09 2022 *)

Prog

(PARI) Vec((1 - x)*(1 - 12*x + 51*x^2 - 97*x^3 + 80*x^4 - 18*x^5) / ((1 - 2*x)*(1 - 12*x + 51*x^2 - 99*x^3 + 90*x^4 - 36*x^5)) + O(x^30)) \\ Colin Barker, Jul 02 2019

Crossrefs

Sequence in context: A369832 A319027 A228397 * A226436 A224318 A079106

Adjacent sequences: A164868 A164869 A164870 * A164872 A164873 A164874

Keyword

nonn,easy

Author

Vincent Vatter, Aug 29 2009

Status

approved