A116845 Number of permutations of length n which avoid the patterns 231, 12534.

1, 2, 5, 14, 41, 121, 355, 1032, 2973, 8496, 24111, 68017, 190885, 533294, 1484021, 4115186, 11375765, 31358377, 86223943, 236540916, 647556621, 1769374932, 4826148315, 13142564449, 35736448201, 97037995226, 263156279525, 712795854422, 1928547574913

Offset

1,2

Links

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

Giulio Cerbai, Anders Claesson, Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.

Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.

Guo-Niu Han, Enumeration of Standard Puzzles. [Cached copy]

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (7,-17,17,-7,1).

Formula

G.f.: x*(1 - 5*x + 8*x^2 - 4*x^3 + x^4) / ((1 - x)*(1 - 3*x + x^2)^2). [restored by Michael D. Weiner, Jul 05 2018]

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

a(n) = 1 + Fibonacci(2*n)/5 + Lucas(2*n - 3)*n/5. - Vaclav Kotesovec, Aug 04 2018

Mathematica

Rest[CoefficientList[Series[x*(1 - 5*x + 8*x^2 - 4*x^3 + x^4) / ((1 - x)*(1 - 3*x + x^2)^2), {x, 0, 30}], x]] (* Vaclav Kotesovec, Aug 04 2018 *)
RecurrenceTable[{a[1] == 1, a[2] == 2, a[3] == 5, a[4] == 14, a[5] == 41, a[n] == 7*a[n-1] - 17*a[n-2] + 17*a[n-3] - 7*a[n-4] + a[n-5]}, a, {n, 1, 30}] (* Vaclav Kotesovec, Aug 04 2018 *)
Table[1 + Fibonacci[2*n]/5 + LucasL[2*n - 3]*n/5, {n, 1, 30}] (* Vaclav Kotesovec, Aug 04 2018 *)

Prog

(PARI) Vec(x*(1 - 5*x + 8*x^2 - 4*x^3 + x^4) / ((1 - x)*(1 - 3*x + x^2)^2) + O(x^40)) \\ Colin Barker, Oct 19 2017

Crossrefs

Cf. A059502 (first differences).

Sequence in context: A370800 A122055 A244885 * A307466 A116849 A371427

Adjacent sequences: A116842 A116843 A116844 * A116846 A116847 A116848

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved