%I #51 Oct 29 2022 12:19:02
%S 1,1,2,6,22,87,354,1459,6056,25252,105632,442916,1860498,7826120,
%T 32956964,138911074,585926818,2472923499,10442263142,44112331275,
%U 186413949540,788000866243,3331853294090,14090947775581,59604161832772
%N Number of permutations of length n that avoid both 1243 and 2134.
%C Le proved that this also gives the number of permutations of length n that avoid both 1342 and 3124.
%C For n>=1, a(n) is the number of paths of North steps N = (0,1), East steps E = (1,0), and Diagonal steps D = (1,1) from the origin to (n-1,n-1) such that all D steps lie on the diagonal line y = x and the first step away from the diagonal (if there is one) is a North step. For example, a(3) = 6 counts DD, DNE, NED, NENE, NEEN, NNEE. - _David Callan_, Jun 25 2013
%H Vincenzo Librandi, <a href="/A164651/b164651.txt">Table of n, a(n) for n = 0..300</a>
%H David Callan, <a href="http://arxiv.org/abs/1303.3857">The number of {1243, 2134}-avoiding permutations</a>, arXiv:1303.3857 [math.CO], 2013.
%H David Callan, <a href="https://arxiv.org/abs/1306.3193">Permutations avoiding 4321 and 3241 have an algebraic generating function</a>, arXiv:1306.3193 [math.CO], 2013.
%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 Ian Le, <a href="http://www.combinatorics.org/Volume_12/Abstracts/v12i1r25.html">Wilf classes of pairs of permutations of length 4</a>, Electron. J. Combin., 12(1) (2005), Research article 25, 26 pages.
%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 From _Vaclav Kotesovec_, Oct 24 2012: (Start)
%F G.f.: (3*x^2-9*x+2+x*(1-x)*sqrt(1-4*x))/(2*(x-1)*(x^2+4*x-1)).
%F Recurrence: (n-4)*(n-1)*a(n) = (9*n^2 - 51*n + 62)*a(n-1) - (23*n^2 - 145*n + 222)*a(n-2) + (11*n^2 - 73*n + 122)*a(n-3) + 2*(n-3)*(2*n-7)*a(n-4).
%F a(n) ~ (1/2-1/sqrt(5))*(sqrt(5)+2)^n. (End)
%F These formulas were conjectured by _Vaclav Kotesovec_ and proved correct by _David Callan_ (see Link).
%F a(n) = (A026671(n-1) + 1)/2 for n >= 1. - _David Callan_, Jun 25 2013
%F a(n-1) = Sum_{k=0..n} binomial(n, k)*A358092(k) for n >= 1. - _Peter Luschny_, Oct 29 2022
%t CoefficientList[Series[(3*x^2-9*x+2+x*(1-x)*Sqrt[1-4*x])/(2*(x-1)*(x^2+4*x-1)), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Oct 28 2012 *)
%Y Cf. A026671, A358092.
%K nonn
%O 0,3
%A _Vincent Vatter_, Aug 19 2009