A224232 a(n) = n! if n <= 3, otherwise a(n) = 2*(a(n-1) + a(n-3)) + a(n-2).

1, 1, 2, 6, 16, 42, 112, 298, 792, 2106, 5600, 14890, 39592, 105274, 279920, 744298, 1979064, 5262266, 13992192, 37204778, 98926280, 263041722, 699419280, 1859732842, 4944968408, 13148508218, 34961450528, 92961346090, 247181159144, 657246565434, 1747596982192, 4646802848106, 12355695809272, 32853388431034, 87356078367552, 232276936784682

Offset

0,3

Comments

Also the number of permutations that are sortable after two passes through a pop stack. (See the Pudwell-Smith link.) - Lara Pudwell, Jun 01 2017

Links

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

G. Aleksandrowich et al., Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3, Discrete Math., 313 (2013), 1078-1086.

Anders Claesson and Bjarki Ágúst Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack, arXiv:1710.04978 [math.CO], 2017.

Lara Pudwell and Rebecca Smith, Sorting with Pop Stacks, Special Session on Algebraic and Enumerative Combinatorics with Applications, AMS Central Section Spring Meeting, 2017.

Lara Pudwell and Rebecca Smith, Two-stack-sorting with pop stacks, arXiv:1801.05005 [math.CO], 2018.

Index entries for linear recurrences with constant coefficients, signature (2,1,2).

Formula

G.f.: (x^3 + x^2 + x - 1) / (2*x^3 + x^2 + 2*x - 1). - Colin Barker, Jun 07 2015

a(n) = (b(n) + b(n-1))/2 for b(n) = A077996(n). - Hanzhang Fang, Aug 27 2022

Mathematica

CoefficientList[Series[(x^3 + x^2 + x - 1)/(2 x^3 + x^2 + 2 x - 1), {x, 0, 35}], x] (* Michael De Vlieger, Jun 01 2017 *)
LinearRecurrence[{2, 1, 2}, {1, 1, 2, 6}, 40] (* Harvey P. Dale, Aug 28 2023 *)

Prog

(PARI) Vec((x^3+x^2+x-1)/(2*x^3+x^2+2*x-1) + O(x^100)) \\ Colin Barker, Jun 07 2015

Crossrefs

Cf. A077996, A293774, A293775, A293776, A293784.

Sequence in context: A358464 A115730 A191694 * A217661 A244399 A291142

Adjacent sequences: A224229 A224230 A224231 * A224233 A224234 A224235

Keyword

nonn,easy

Author

N. J. A. Sloane, Apr 11 2013

Status

approved