A164651 Number of permutations of length n that avoid both 1243 and 2134.
1, 1, 2, 6, 22, 87, 354, 1459, 6056, 25252, 105632, 442916, 1860498, 7826120, 32956964, 138911074, 585926818, 2472923499, 10442263142, 44112331275, 186413949540, 788000866243, 3331853294090, 14090947775581, 59604161832772
Offset: 0
Keywords
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.
- Wikipedia, Permutation classes avoiding two patterns of length 4.
Programs
-
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 *)
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
Comments