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

Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, Elect. J. Comb. 22(1) (2015), #P1.58.

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

Vít Jelínek, Toufik Mansour, and Mark 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.

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

Permutation Pattern Avoidance Library (PermPAL), Av(123,2431)

Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.

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

Lara Pudwell and Andrew 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