A165538 Number of permutations of length n which avoid the patterns 4312 and 3142.

1, 1, 2, 6, 22, 88, 367, 1568, 6810, 29943, 132958, 595227, 2683373, 12170778, 55499358, 254297805, 1170248190, 5406570910, 25068420955, 116617923611, 544157590706, 2546278167018, 11945937322413, 56180864428301, 264812677643417, 1250853429148333, 5920145717412047

Offset

0,3

Links

Table of n, a(n) for n=0..26.

M. H. Albert, M. D. Atkinson, and V. Vatter, Inflations of geometric grid classes: three case studies, arXiv:1209.0425 [math.CO], 2012.

Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

Christian Bean, Émile Nadeau, Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.

Robert Brignall, Jakub Sliacan, Juxtaposing Catalan permutation classes with monotone ones, arXiv:1611.05370 [math.CO], 2016.

Juan B. Gil, Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.

Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

G.f. f satisfies: (x^3-2*x^2+x)*f^4+(4*x^3-9*x^2+6*x-1)*f^3+(6*x^3-12*x^2+7*x-1)*f^2+(4*x^3-5*x^2+x)*f+x^3 = 0.

From Vaclav Kotesovec, Jul 06 2024: (Start)

G.f.: (1 + sqrt(1-4*x)) / (4*x) - sqrt(2*(1 + sqrt(1-4*x)-2*x)*(1-x)*(1-5*x)) / (4*(1-x)*x).

a(n) ~ (1 + sqrt(5)) * 5^(n+1) / (16 * sqrt(Pi) * n^(3/2)). (End)

Example

There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Mathematica

CoefficientList[Series[(1 + Sqrt[1 - 4*x]) / (4*x) - Sqrt[2*(1 + Sqrt[1 - 4*x] - 2*x)*(1 - x)*(1 - 5*x)] / (4*(1-x)*x), {x, 0, 30}], x] (* Vaclav Kotesovec, Jul 06 2024 *)

Crossrefs

Sequence in context: A165536 A032351 A165537 * A165539 A109033 A049135

Adjacent sequences: A165535 A165536 A165537 * A165539 A165540 A165541

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

Reference corrected by Vincent Vatter, Sep 04 2012

a(0)=1 prepended by Alois P. Heinz, Jul 06 2024

Status

approved