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

Author

Lara Pudwell, Feb 26 2006

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, Catalan words avoiding a pattern of length four, Univ. de Bourgogne (France, 2024). See p. 3.
• Giulio Cerbai, Anders Claesson, and 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).

Crossrefs

Cf. A059502 (first differences).

Programs

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

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

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