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 #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