%I #55 Feb 07 2022 03:44:56
%S 1,1,2,5,13,31,66,127,225,373,586,881,1277,1795,2458,3291,4321,5577,
%T 7090,8893,11021,13511,16402,19735,23553,27901,32826,38377,44605,
%U 51563,59306,67891,77377,87825,99298,111861,125581,140527,156770,174383,193441,214021
%N Number of permutations of length n that avoid the patterns 132, 4321.
%C Also, number of permutations of length n which avoid the patterns 312, 1234, 4312; or avoid the patterns 132, 1324, 4321, etc.
%C a(n) is the number of Dyck n-paths (A000108) with <= 3 peaks. For example, a(4)=13 counts all 14 Dyck 4-paths except the "sawtooth" path UDUDUDUD which has 4 peaks. - _David Callan_, Oct 13 2012
%C Apparently the number of Dyck paths of semilength n+1 in which the sum of the first 3 ascents adds to n+1. (Nonexistent ascents count as zero length.) - _David Scambler_, Apr 22 2013
%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 H. Cheballah, S. Giraudo and R. Maurice, <a href="http://arxiv.org/abs/1306.6605">Combinatorial Hopf algebra structure on packed square matrices</a>, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,10,-5,1)
%F G.f.: -(3*x^4 - 5*x^3 + 7*x^2 - 4*x + 1)/(x-1)^5.
%F a(n) = (n^4 - 4n^3 + 11n^2 - 8n + 12)/12. - _Franklin T. Adams-Watters_, Sep 16 2006
%F Binomial transform of [1, 1, 2, 3, 2, 0, 0, 0, ...]. - _Gary W. Adamson_, Oct 23 2007
%F Equals A001263 * [1, 1, 1, 0, 0, 0, ...], where A001263 = the Narayana triangle. - _Gary W. Adamson_, Nov 19 2007
%F E.g.f.: (1/12)*exp(x)*(12 + 12*x + 12*x^2 + 6*x^3 + x^4). - _Stefano Spezia_, Jan 09 2019
%F a(n) = binomial(n+1,4) + binomial(n,4) + binomial(n,2) + 1. - _Michael Coopman_, Oct 24 2021
%e a(4)=13 because we have 11 permutations of [4] that do not avoid the patterns 132 and 4321; namely: 1324, 1342, 1432, 4132, 1423, 3142, 2431, 2413, 2143, 1243 and 4321.
%p G:=1+(x*(x^4-2*x^3+5*x^2-3*x+1))/(1-x)^5: Gser:=series(G,x=0,48): seq(coeff(Gser,x,n),n=0..45); # _Emeric Deutsch_, Jul 29 2006
%t LinearRecurrence[{5, -10, 10, -5, 1}, {1, 2, 5, 13, 31}, 40] (* _Jean-François Alcover_, Jan 09 2019 *)
%Y Cf. A000108, A001263.
%K nonn,easy
%O 0,3
%A _Lara Pudwell_, Feb 26 2006
%E Entry revised by _N. J. A. Sloane_, Jul 25 2006
%E a(0)=1 prepended by _Alois P. Heinz_, Nov 28 2021