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

%I #47 Feb 07 2022 03:45:20

%S 1,2,5,13,32,74,163,347,722,1480,3005,6065,12196,24470,49031,98167,

%T 196454,393044,786241,1572653,3145496,6291202,12582635,25165523,

%U 50331322,100662944,201326213,402652777,805305932,1610612270,3221224975,6442450415,12884901326

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

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

%H Colin Barker, <a href="/A116702/b116702.txt">Table of n, a(n) for n = 1..1000</a>

%H A. M. Baxter and L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #P1.58.

%H Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson, <a href="https://arxiv.org/abs/1705.04109">Automatic discovery of structural rules of permutation classes</a>, arXiv:1705.04109 [math.CO], 2017.

%H V. Jelinek, T. Mansour, and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.aam.2012.09.002">On multiple pattern avoiding set partitions</a>, Adv. Appl. Math. 50 (2) (2013) 292-326, Example 4.16, H_{1221}(x), including a(0)=1.

%H Myrto Kallipoliti, Robin Sulzgruber, and Eleni Tzanaki, <a href="https://arxiv.org/abs/2006.06949">Patterns in Shi tableaux and Dyck paths</a>, arXiv:2006.06949 [math.CO], 2020.

%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/maple/webbook/bookmain.html">Systematic Studies in Pattern Avoidance</a>, 2005.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, Joint Mathematics Meetings, AMS Special Session on Enumerative Combinatorics, January 11, 2015.

%H L. Pudwell and A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, Permutation Patterns 2014, East Tennessee State University, July 7, 2014.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-9,7,-2).

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

%F Binomial transform of [1, 1, 2, 3, 3, 3, 3, ...]. - _Gary W. Adamson_, Oct 23 2007

%F a(n+1) = -A000217(n+1) + 3*2^n - 1. - _R. J. Mathar_, Jan 12 2013

%F From _Colin Barker_, Oct 19 2017: (Start)

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

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

%F (End)

%t LinearRecurrence[{5, -9, 7, -2}, {1, 2, 5, 13}, 33] (* _Jean-François Alcover_, Jan 09 2019 *)

%o (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

%K nonn,easy

%O 1,2

%A _Lara Pudwell_, Feb 26 2006

%E Edited by _N. J. A. Sloane_, Mar 16 2008