cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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

Views

Author

Lara Pudwell, Feb 26 2006

Keywords

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.
		

Crossrefs

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