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
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.
- Permutation Pattern Avoidance Library (PermPAL), Av(123,2431)
- 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).
Programs
-
Mathematica
LinearRecurrence[{5, -9, 7, -2}, {1, 2, 5, 13}, 33] (* Jean-François Alcover, Jan 09 2019 *) -
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
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)
Extensions
Edited by N. J. A. Sloane, Mar 16 2008
Comments