A116702 Number of permutations of length n which avoid the patterns 123, 3241.

1, 2, 5, 13, 32, 74, 163, 347, 722, 1480, 3005, 6065, 12196, 24470, 49031, 98167, 196454, 393044, 786241, 1572653, 3145496, 6291202, 12582635, 25165523, 50331322, 100662944, 201326213, 402652777, 805305932, 1610612270, 3221224975, 6442450415, 12884901326

Offset

1,2

Comments

Also number of permutations of length n which avoid the patterns 321, 2314, 2431; or avoid the patterns 123, 2314, 2431, etc.

Links

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

A. M. Baxter and L. K. Pudwell, Ascent sequences avoiding pairs of patterns, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #P1.58.

Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.

V. Jelinek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Example 4.16, H_{1221}(x), including a(0)=1.

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.

L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, Joint Mathematics Meetings, AMS Special Session on Enumerative Combinatorics, January 11, 2015.

L. Pudwell and A. Baxter, Ascent sequences avoiding pairs of patterns, Permutation Patterns 2014, East Tennessee State University, July 7, 2014.

Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Formula

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

Binomial transform of [1, 1, 2, 3, 3, 3, 3, ...]. - Gary W. Adamson, Oct 23 2007

a(n+1) = -A000217(n+1) + 3*2^n - 1. - R. J. Mathar, Jan 12 2013

From Colin Barker, Oct 19 2017: (Start)

a(n) = 3*2^(n-1) + n - (n+1)*(2+n)/2.

a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4) for n > 4.

(End)

Mathematica

LinearRecurrence[{5, -9, 7, -2}, {1, 2, 5, 13}, 33] (* Jean-François Alcover, Jan 09 2019 *)

Prog

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

Crossrefs

Sequence in context: A095134 A086758 A179257 * A098156 A267862 A098586

Adjacent sequences: A116699 A116700 A116701 * A116703 A116704 A116705

Keyword

nonn,easy

Author

Lara Pudwell, Feb 26 2006

Extensions

Edited by N. J. A. Sloane, Mar 16 2008

Status

approved