A116847 Number of permutations of length n which avoid the patterns 123, 51432.

1, 2, 5, 14, 41, 119, 336, 924, 2492, 6636, 17536, 46137, 121095, 317434, 831571, 2177734, 5702191, 14929519, 39087182, 102332996, 267912946, 701407172, 1836310110, 4807524929, 12586266701, 32951277474, 86267568321, 225851430414, 591286726197, 1548008751831

Offset

1,2

Links

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

Myrto Kallipoliti, Robin Sulzgruber, and Eleni Tzanaki, Patterns in Shi tableaux and Dyck paths, arXiv:2006.06949 [math.CO], 2020.

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

Index entries for linear recurrences with constant coefficients, signature (7,-19,26,-19,7,-1)

Formula

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

a(n) = A001906(n) - A004006(n-1). - R. J. Mathar, Jan 12 2013

a(n) = 1 - ((3-sqrt(5))/2)^n/sqrt(5) + ((3+sqrt(5))/2)^n/sqrt(5) - (4*n)/3 + n^2/2 - n^3/6. - Colin Barker, Oct 31 2017

Prog

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

Crossrefs

Sequence in context: A116851 A038989 A116850 * A116848 A370800 A122055

Adjacent sequences: A116844 A116845 A116846 * A116848 A116849 A116850

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Status

approved