%I #47 Feb 07 2022 03:45:20
%S 1,2,5,13,32,74,163,347,722,1480,3005,6065,12196,24470,49031,98167,
%T 196454,393044,786241,1572653,3145496,6291202,12582635,25165523,
%U 50331322,100662944,201326213,402652777,805305932,1610612270,3221224975,6442450415,12884901326
%N Number of permutations of length n which avoid the patterns 123, 3241.
%C Also number of permutations of length n which avoid the patterns 321, 2314, 2431; or avoid the patterns 123, 2314, 2431, etc.
%H Colin Barker, <a href="/A116702/b116702.txt">Table of n, a(n) for n = 1..1000</a>
%H A. M. Baxter and L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #P1.58.
%H Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson, <a href="https://arxiv.org/abs/1705.04109">Automatic discovery of structural rules of permutation classes</a>, arXiv:1705.04109 [math.CO], 2017.
%H V. Jelinek, T. Mansour, and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50 (2) (2013) 292-326, Example 4.16, H_{1221}(x), including a(0)=1.
%H Myrto Kallipoliti, Robin Sulzgruber, and Eleni Tzanaki, <a href="https://arxiv.org/abs/2006.06949">Patterns in Shi tableaux and Dyck paths</a>, arXiv:2006.06949 [math.CO], 2020.
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.
%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, Joint Mathematics Meetings, AMS Special Session on Enumerative Combinatorics, January 11, 2015.
%H L. Pudwell and A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, Permutation Patterns 2014, East Tennessee State University, July 7, 2014.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-9,7,-2).
%F G.f.: x*(1 - 3*x + 4*x^2 - x^3) / ((1 - x)^3*(1 - 2*x)).
%F Binomial transform of [1, 1, 2, 3, 3, 3, 3, ...]. - _Gary W. Adamson_, Oct 23 2007
%F a(n+1) = -A000217(n+1) + 3*2^n - 1. - _R. J. Mathar_, Jan 12 2013
%F From _Colin Barker_, Oct 19 2017: (Start)
%F a(n) = 3*2^(n-1) + n - (n+1)*(2+n)/2.
%F a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n > 4.
%F (End)
%t LinearRecurrence[{5, -9, 7, -2}, {1, 2, 5, 13}, 33] (* _Jean-François Alcover_, Jan 09 2019 *)
%o (PARI) Vec(x*(1 - 3*x + 4*x^2 - x^3) / ((1 - x)^3*(1 - 2*x)) + O(x^40)) \\ _Colin Barker_, Oct 19 2017
%K nonn,easy
%O 1,2
%A _Lara Pudwell_, Feb 26 2006
%E Edited by _N. J. A. Sloane_, Mar 16 2008