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, 138462, 151835

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Qi Liu, Sergey Kitaev, and Philip B. Zhang, Simultaneous avoidance of length-4 patterns in ascent sequences, arXiv:2604.06735 [math.CO], 2026. See p. 4 (Table 1).

Shuzhen Lv and Sergey Kitaev, Stoimenow matchings avoiding multiple Catalan patterns simultaneously, arXiv:2509.12726 [math.CO], 2025. See pp. 3, 13.

Â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>6. - Colin Barker, Oct 24 2017

Mathematica

A116722[n_] := If[n == 1, 1, #*(# + 38)/24 + 5 & [n*(n - 3)]]; Array[A116722, 50] (* or *)
LinearRecurrence[{5, -10, 10, -5, 1}, {1, 2, 5, 12, 25, 47}, 50] (* Paolo Xausa, Apr 13 2026 *)

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