A165536 Number of permutations of length n which avoid the patterns 1243 and 2341.

1, 1, 2, 6, 22, 88, 365, 1540, 6568, 28269, 122752, 537708, 2375500, 10579400, 47469377, 214454528, 974870969, 4456401809, 20474068387, 94490731125, 437872264778, 2036621291113, 9504521228442, 44491624811512, 208853221780315, 982922903896966, 4636873292528606, 21922022211195195

Offset

0,3

Comments

These permutations have an enumeration scheme of depth 5.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

Sam Miner, Enumeration of several two-by-four classes, arXiv preprint arXiv:1610.01908 [math.CO], 2016.

V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159

Wikipedia, Permutation classes avoiding two patterns of length 4.

Formula

G.f.: (2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*sqrt(1 - 6*x + 5*x^2))/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)). - G. C. Greubel, Oct 22 2018

Example

There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Mathematica

CoefficientList[Series[(2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*Sqrt[1 - 6*x + 5*x^2])/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)), {x, 0, 30}], x] (* G. C. Greubel, Oct 22 2018 *)

Prog

(PARI) x='x+O('x^30); Vec((2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*sqrt(1 - 6*x + 5*x^2))/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2))) \\ G. C. Greubel, Oct 22 2018
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!((2 - 8*x + 2*x^2 + 17*x^3 - 15*x^4 + 4*x^5 - (2 - 10*x + 16*x^2 - 9*x^3 + 2*x^4)*Sqrt(1 - 6*x + 5*x^2))/(2*x*(2 - x)^2*(1 - 2*x)*(1 - 3*x + x^2)))); // G. C. Greubel, Oct 22 2018

Crossrefs

Sequence in context: A165534 A165535 A319028 * A032351 A165537 A165538

Adjacent sequences: A165533 A165534 A165535 * A165537 A165538 A165539

Keyword

nonn

Author

Vincent Vatter, Sep 21 2009

Extensions

Terms a(21) onward added by G. C. Greubel, Oct 22 2018

Status

approved