cp's OEIS Frontend

A022558 Number of permutations of length n avoiding the pattern 1342.

%I A022558 #95 May 31 2020 22:07:25
%S A022558 1,1,2,6,23,103,512,2740,15485,91245,555662,3475090,22214707,
%T A022558 144640291,956560748,6411521056,43478151737,297864793993,
%U A022558 2059159989914,14350039389022,100726680316559,711630547589023,5057282786190872,36132861123763276,259423620328055093
%N A022558 Number of permutations of length n avoiding the pattern 1342.
%C A022558 Differs from A117156 which counts permutations avoiding the *consecutive* pattern 1342. - _Ray Chandler_, Dec 06 2011
%C A022558 Also, number of permutation of length n avoiding the pattern 3142 (see Stankova (1994) below). - _Alexander Burstein_, Aug 09 2013
%C A022558 Conjecture: a(n) is the number of permutations of length n simultaneously avoiding patterns 2143 and 415263. - _Alexander Burstein_, Mar 21 2019
%D A022558 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 768, Th. 12.1.14.
%D A022558 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.48.
%H A022558 Vincenzo Librandi, <a href="/A022558/b022558.txt">Table of n, a(n) for n = 0..200</a>
%H A022558 Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.
%H A022558 Miklos Bona, <a href="https://arxiv.org/abs/math/9702223">Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps</a>, arXiv:math/9702223 [math.CO], 1997.
%H A022558 Miklos Bona, <a href="http://dx.doi.org/10.1006/jcta.1997.2800">Exact enumeration of 1342-avoiding permutations; A close link with labeled trees and planar maps</a>, J. Combinatorial Theory, A80 (1997), 257-272.
%H A022558 Alexander Burstein and Jay Pantone, <a href="http://dx.doi.org/10.4310/JOC.2015.v6.n1.a4">Two examples of unbalanced Wilf-equivalence</a>, J. Combin. 6 (2015), no. 1-2, 55-67.
%H A022558 Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.
%H A022558 A. R. Conway and A. J. Guttmann, <a href="http://dx.doi.org/10.1016/j.aam.2014.12.004">On 1324-avoiding permutations</a>, Adv. Appl. Math. 64 (2015), 50-69.
%H A022558 A. L. L. Gao, S. Kitaev, and P. B. Zhang. <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.
%H A022558 Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H A022558 C. Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint arXiv:1410.2657 [math.CO], 2014.
%H A022558 Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.29">Asymptotic Expansions for Sub-Critical Lagrangean Forms</a>, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
%H A022558 W. Mlotkowski, K. A. Penson, <a href="http://arxiv.org/abs/1507.07312">A Fuss-type family of positive definite sequences</a>, arXiv:1507.07312 (2015), eq. (36).
%H A022558 Z. E. Stankova, <a href="http://dx.doi.org/10.1016/0012-365X(94)90242-9">Forbidden subsequences</a>, Discrete Math., 132 (1994), no. 1-3, 291-316.
%H A022558 Zvezdelina Stankova-Frenkel and Julian West, <a href="http://arxiv.org/abs/math/0103152">A new class of Wilf-equivalent permutations</a>, arXiv:math/0103152 [math.CO], 2001. See Fig. 11.
%F A022558 a(n) = (7*n^2-3*n-2)/2 * (-1)^(n-1) + 3*Sum_{i=2..n} 2^(i+1) * (2*i-4)!/(i!*(i-2)!) * binomial(n-i+2, 2) * (-1)^(n-i).
%F A022558 G.f.: 32*x/(1 + 20*x - 8*x^2 - (1 - 8*x)^(3/2)). - _Emeric Deutsch_, Mar 13 2004
%F A022558 Recurrence: n*a(n) = (7*n-22)*a(n-1) + 4*(2*n-1)*a(n-2). - _Vaclav Kotesovec_, Oct 07 2012
%F A022558 a(n) ~ 2^(3*n+6)/(243*sqrt(Pi)*n^(5/2)). - _Vaclav Kotesovec_, Oct 07 2012
%e A022558 a(4) = 23 because obviously all permutations of length 4 with the exception of 1342 avoid 1342.
%p A022558 a := proc (n) options operator, arrow: (1/2)*(-1)^(n-1)*(7*n^2-3*n-2)+3*(sum((-1)^(n-i)*2^(i+1)*factorial(2*i-4)*binomial(n-i+2, 2)/(factorial(i)*factorial(i-2)), i = 2 .. n)) end proc: seq(a(n), n = 0 .. 30); # _Emeric Deutsch_, Oct 15 2014
%t A022558 Table[SeriesCoefficient[32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)),{x,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 07 2012 *)
%t A022558 Table[1/2*(-1)^(n-1) * (-2-3*n+7*n^2) + 1/4*(-1)^n * (1+n) * (-2-13*n+(n+2) * Hypergeometric2F1[-3/2,-n,-2-n,-8]),{n,0,20}] (* _Vaclav Kotesovec_, Aug 24 2014 *)
%o A022558 (PARI) x='x+O('x^66); Vec( 32*x/(1+20*x-8*x^2-(1-8*x)^(3/2)) ) \\ _Joerg Arndt_, May 04 2013
%Y A022558 Essentially the same as A004040.
%Y A022558 Cf. A117158.
%Y A022558 A005802, A022558, A061552 are representatives for the three Wilf classes for length-four avoiding permutations (cf. A099952).
%K A022558 nonn,easy
%O A022558 0,3
%A A022558 _Miklos Bona_
%E A022558 Minor edits by _Vaclav Kotesovec_, Aug 24 2014