login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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) = 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=1..40.

Christian Bean, Bjarki Gudmundsson, Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.

H. Cheballah, S. Giraudo, 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.: -x*(x^4-2x^3+5x^2-3x+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

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:=(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=1..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. 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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 14:45 EDT 2019. Contains 328019 sequences. (Running on oeis4.)