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