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,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.

Wikipedia, Permutation classes avoiding two patterns of length 4.

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

Cf. A026671, A358092.

Sequence in context: A150260 A165532 A165533 * A279566 A367413 A150261

Adjacent sequences: A164648 A164649 A164650 * A164652 A164653 A164654

Keyword

nonn

Author

Vincent Vatter, Aug 19 2009

Status

approved