A116722 Number of permutations of length n which avoid the patterns 312, 1324, 3421; or avoid the patterns 312, 1324, 2341, etc.

1, 2, 5, 12, 25, 47, 82, 135, 212, 320, 467, 662, 915, 1237, 1640, 2137, 2742, 3470, 4337, 5360, 6557, 7947, 9550, 11387, 13480, 15852, 18527, 21530, 24887, 28625, 32772, 37357, 42410, 47962, 54045, 60692, 67937, 75815, 84362, 93615, 103612, 114392, 125995

Offset: 1

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Ângela Mestre, José Agapito, Square Matrices Generated by Sequences of Riordan Arrays, J. Int. Seq., Vol. 22 (2019), Article 19.8.4.
• Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Programs

Magma

[1] cat [(n^4 - 6*n^3 + 47*n^2 - 114*n + 120)/24 : n in [2..50]]; // Wesley Ivan Hurt, Mar 25 2020

PARI

Vec(x*(1 - 3*x + 5*x^2 - 3*x^3 + x^5) / (1 - x)^5 + O(x^60)) \\ Colin Barker, Oct 24 2017

Formula

G.f.: x*(1 - 3*x + 5*x^2 - 3*x^3 + x^5) / (1 - x)^5.

For n >= 2, a(n) = (n^4 - 6*n^3 + 47*n^2 - 114*n + 120)/24. - Franklin T. Adams-Watters, Sep 16 2006

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>4. - Colin Barker, Oct 24 2017

Extensions

Extended beyond a(30) by R. J. Mathar, Aug 05 2008