OFFSET
0,3
COMMENTS
Le proved that this also gives the number of permutations of length n that avoid both 1342 and 3124.
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
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..300
David Callan, The number of {1243, 2134}-avoiding permutations, arXiv:1303.3857 [math.CO], 2013.
David Callan, Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193 [math.CO], 2013.
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.
Ian Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin., 12(1) (2005), Research article 25, 26 pages.
FORMULA
From Vaclav Kotesovec, Oct 24 2012: (Start)
G.f.: (3*x^2-9*x+2+x*(1-x)*sqrt(1-4*x))/(2*(x-1)*(x^2+4*x-1)).
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).
a(n) ~ (1/2-1/sqrt(5))*(sqrt(5)+2)^n. (End)
These formulas were conjectured by Vaclav Kotesovec and proved correct by David Callan (see Link).
a(n) = (A026671(n-1) + 1)/2 for n >= 1. - David Callan, Jun 25 2013
a(n-1) = Sum_{k=0..n} binomial(n, k)*A358092(k) for n >= 1. - Peter Luschny, Oct 29 2022
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Vincent Vatter, Aug 19 2009
STATUS
approved