The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A116701 Number of permutations of length n that avoid the patterns 132, 4321. 3
 1, 1, 2, 5, 13, 31, 66, 127, 225, 373, 586, 881, 1277, 1795, 2458, 3291, 4321, 5577, 7090, 8893, 11021, 13511, 16402, 19735, 23553, 27901, 32826, 38377, 44605, 51563, 59306, 67891, 77377, 87825, 99298, 111861, 125581, 140527, 156770, 174383, 193441, 214021 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Also, number of permutations of length n which avoid the patterns 312, 1234, 4312; or avoid the patterns 132, 1324, 4321, etc. 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 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 LINKS Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017. H. Cheballah, S. Giraudo and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013. Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005. Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1) FORMULA G.f.: -(3*x^4 - 5*x^3 + 7*x^2 - 4*x + 1)/(x-1)^5. a(n) = (n^4 - 4n^3 + 11n^2 - 8n + 12)/12. - Franklin T. Adams-Watters, Sep 16 2006 Binomial transform of [1, 1, 2, 3, 2, 0, 0, 0, ...]. - Gary W. Adamson, Oct 23 2007 Equals A001263 * [1, 1, 1, 0, 0, 0, ...], where A001263 = the Narayana triangle. - Gary W. Adamson, Nov 19 2007 E.g.f.: (1/12)*exp(x)*(12 + 12*x + 12*x^2 + 6*x^3 + x^4). - Stefano Spezia, Jan 09 2019 a(n) = binomial(n+1,4) + binomial(n,4) + binomial(n,2) + 1. - Michael Coopman, Oct 24 2021 EXAMPLE a(4)=13 because we have 11 permutations of  that do not avoid the patterns 132 and 4321; namely: 1324, 1342, 1432, 4132, 1423, 3142, 2431, 2413, 2143, 1243 and 4321. MAPLE 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 MATHEMATICA LinearRecurrence[{5, -10, 10, -5, 1}, {1, 2, 5, 13, 31}, 40] (* Jean-François Alcover, Jan 09 2019 *) CROSSREFS Cf. A000108, A001263. Sequence in context: A073683 A098501 A180302 * A068739 A063636 A076501 Adjacent sequences:  A116698 A116699 A116700 * A116702 A116703 A116704 KEYWORD nonn,easy AUTHOR Lara Pudwell, Feb 26 2006 EXTENSIONS Entry revised by N. J. A. Sloane, Jul 25 2006 a(0)=1 prepended by Alois P. Heinz, Nov 28 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 27 12:49 EDT 2022. Contains 357057 sequences. (Running on oeis4.)