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

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

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

Examples

			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.
		

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)

Crossrefs

Cf. A000108, A001263.

Programs

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 *)

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

a(n)-a(n-1) = A081489(n-1). - R. J. Mathar, Mar 08 2025

Extensions

Entry revised by N. J. A. Sloane, Jul 25 2006

a(0)=1 prepended by Alois P. Heinz, Nov 28 2021