A116701 Number of permutations of length n that avoid the patterns 132, 4321.

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

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

Table of n, a(n) for n=0..41.

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 [4] 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: A098501 A363513 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