Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #52 Aug 28 2023 16:34:23
%S 1,1,2,6,16,42,112,298,792,2106,5600,14890,39592,105274,279920,744298,
%T 1979064,5262266,13992192,37204778,98926280,263041722,699419280,
%U 1859732842,4944968408,13148508218,34961450528,92961346090,247181159144,657246565434,1747596982192,4646802848106,12355695809272,32853388431034,87356078367552,232276936784682
%N a(n) = n! if n <= 3, otherwise a(n) = 2*(a(n-1) + a(n-3)) + a(n-2).
%C 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
%H Colin Barker, <a href="/A224232/b224232.txt">Table of n, a(n) for n = 0..1000</a>
%H G. Aleksandrowich et al., <a href="https://doi.org/10.1016/j.disc.2013.01.028">Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3</a>, Discrete Math., 313 (2013), 1078-1086.
%H Anders Claesson and Bjarki Ágúst Guðmundsson, <a href="https://arxiv.org/abs/1710.04978">Enumerating permutations sortable by k passes through a pop-stack</a>, arXiv:1710.04978 [math.CO], 2017.
%H Lara Pudwell and Rebecca Smith, <a href="http://faculty.valpo.edu/lpudwell/slides/AMS2017_pudwell.pdf">Sorting with Pop Stacks</a>, Special Session on Algebraic and Enumerative Combinatorics with Applications, AMS Central Section Spring Meeting, 2017.
%H Lara Pudwell and Rebecca Smith, <a href="https://arxiv.org/abs/1801.05005">Two-stack-sorting with pop stacks</a>, arXiv:1801.05005 [math.CO], 2018.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,2).
%F G.f.: (x^3 + x^2 + x - 1) / (2*x^3 + x^2 + 2*x - 1). - _Colin Barker_, Jun 07 2015
%F a(n) = (b(n) + b(n-1))/2 for b(n) = A077996(n). - _Hanzhang Fang_, Aug 27 2022
%t 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 *)
%t LinearRecurrence[{2,1,2},{1,1,2,6},40] (* _Harvey P. Dale_, Aug 28 2023 *)
%o (PARI) Vec((x^3+x^2+x-1)/(2*x^3+x^2+2*x-1) + O(x^100)) \\ _Colin Barker_, Jun 07 2015
%Y Cf. A077996, A293774, A293775, A293776, A293784.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, Apr 11 2013