login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #53 Jul 06 2024 13:21:24

%S 1,1,2,6,22,88,367,1568,6810,29943,132958,595227,2683373,12170778,

%T 55499358,254297805,1170248190,5406570910,25068420955,116617923611,

%U 544157590706,2546278167018,11945937322413,56180864428301,264812677643417,1250853429148333,5920145717412047

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

%H M. H. Albert, M. D. Atkinson, and V. Vatter, <a href="http://arxiv.org/abs/1209.0425">Inflations of geometric grid classes: three case studies</a>, arXiv:1209.0425 [math.CO], 2012.

%H Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.

%H Christian Bean, Émile Nadeau, Henning Ulfarsson, <a href="https://arxiv.org/abs/1912.07503">Enumeration of Permutation Classes and Weighted Labelled Independent Sets</a>, arXiv:1912.07503 [math.CO], 2019.

%H Robert Brignall, Jakub Sliacan, <a href="https://arxiv.org/abs/1611.05370">Juxtaposing Catalan permutation classes with monotone ones</a>, arXiv:1611.05370 [math.CO], 2016.

%H Juan B. Gil, Michael D. Weiner, <a href="https://arxiv.org/abs/1812.01682">On pattern-avoiding Fishburn permutations</a>, arXiv:1812.01682 [math.CO], 2018.

%H Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

%F 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.

%F From _Vaclav Kotesovec_, Jul 06 2024: (Start)

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

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

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

%t 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 *)

%K nonn

%O 0,3

%A _Vincent Vatter_, Sep 21 2009

%E Reference corrected by _Vincent Vatter_, Sep 04 2012

%E a(0)=1 prepended by _Alois P. Heinz_, Jul 06 2024