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,2

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

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

Prog

(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
(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

Crossrefs

Sequence in context: A002836 A116720 A116731 * A368638 A116730 A240847

Adjacent sequences: A116719 A116720 A116721 * A116723 A116724 A116725

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

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

Status

approved